> [!NOTE] **Theorem** (Cycle Decomposition) > Let $n\in\mathbb{N}^{+}$ and $S_{n}$ be the [[Symmetric Groups of Finite Degree|nth symmetric group]]. Every [[Permutation of Finite Degree|permutation]] $\rho\in S_{n}$ can be expressed as product of disjoint [[Cyclic Permutation of n Letters|cycles]]. > **Proof of Existence of Cycle Decomposition by Construction**: Let $\rho\in S_{n}.$ Consider the sequence $1, \rho (1), \rho^{2} (1), \rho^{3} (1), \dots$Every term in this infinite sequence is contained in the finite set $\{ 1, 2,\dots , n\}$ Thus the sequence must contain repetition. Let $\rho^{u} 1$ be the first term in the sequence that has already appeared. Thus $\rho^{u} 1 = \rho^{v}1$ for some $0 \leq v < u$. Applying $\rho^{-v}$ to both sides gives $\rho^{u-v} 1 =1$ Note that $0<u-v \leq u$. Cases 1. If $u-v<u$, then $\rho^{u-v} 1=1$ is in fact the first term in the sequence that has already appeared, which contradicts are assumption that $\rho^{u}1$ is the first term in the sequence that has already appeared 2. Therefore, $u-v = u$ so $v=0$. Hence $\rho^{u} =1$ and $1, \rho 1, \dots,\rho^{u-1} 1$ are distinct. Let $\mu_{1}$ be the cycle of length u: $\mu_{1} = (1,\rho 1, \rho^{2} 1,\dots, \rho^{u-1} 1)$It is clear that $\mu_{1}$ has the same effect as $\rho$ on the elements $1, \rho 1 ,\dots, \rho^{u-1} 1$ Now let $a \in \{ 1,2,\dots,n \}$ be the first element not appearing in the list $1,\rho 1, \rho^{2} 1,\dots, \rho^{u-1} 1$. Repeat the above argument with the sequence $a, \rho a, \rho^{2} a, \dots$ We deduce the existence of a cycle $\mu_{2}=(a, \rho a, \dots,\rho^{v-1} a)$Now we will show that $\mu_{1}$ and $\mu_{2}$ are disjoint. Suppose otherwise. Then $\rho^{i} 1 = \rho^{j} a$ for some $0\leq i <u$ and $0 \leq j < v$. Now apply $\rho^{v-j}$ to both sides to obtain $\rho^{k} 1 = a$ where $k = i+v-j$. This contradicts our assumption that $a$ does not appear in the list $1,\rho 1, \rho^{2} 1,\dots, \rho^{u-1} 1$. Hence the cycles $\mu_{1}, \mu_{2}$ are disjoint.