[proofplan] We decompose the finite set $\{1,\dots,n\}$ into orbits under repeated application of $\sigma$, and each nontrivial orbit gives one cycle. Then we prove directly that every cycle can be written as a product of transpositions by checking its action on each element of its support. Multiplying the transposition decompositions of all nontrivial cycles gives $\sigma$, while the identity case is handled by the empty product convention. [/proofplan] [step:Decompose $\sigma$ into disjoint cycles from its finite orbits] Let $X:=\{1,\dots,n\}$, and define a relation $\sim$ on $X$ by declaring that, for $x,y \in X$, \begin{align*} x \sim y \quad \text{if and only if} \quad y=\sigma^q(x) \text{ for some } q \in \mathbb{Z}. \end{align*} This is an [equivalence relation](/page/Equivalence%20Relation) because $\sigma^0=\operatorname{id}_X$, because $\sigma^{-q}$ is the inverse power of $\sigma^q$, and because $\sigma^{q+r}=\sigma^q \circ \sigma^r$ for all $q,r \in \mathbb{Z}$. Let $O_1,\dots,O_s$ be the distinct equivalence classes for this relation. For each $i \in \{1,\dots,s\}$, choose an element $a_{i,1} \in O_i$. Since $O_i$ is finite, there is a least integer $k_i \geq 1$ such that $\sigma^{k_i}(a_{i,1})=a_{i,1}$. Define \begin{align*} a_{i,j}:=\sigma^{j-1}(a_{i,1}) \quad \text{for } j \in \{1,\dots,k_i\}. \end{align*} Then the elements $a_{i,1},\dots,a_{i,k_i}$ are distinct by the minimality of $k_i$, and \begin{align*} O_i=\{a_{i,1},\dots,a_{i,k_i}\}. \end{align*} On $O_i$, the permutation $\sigma$ acts by \begin{align*} a_{i,1}\mapsto a_{i,2},\quad a_{i,2}\mapsto a_{i,3},\quad \dots,\quad a_{i,k_i-1}\mapsto a_{i,k_i},\quad a_{i,k_i}\mapsto a_{i,1}. \end{align*} Thus the restriction of $\sigma$ to $O_i$ is the cycle $(a_{i,1}\ a_{i,2}\ \cdots\ a_{i,k_i})$, with the convention that a $1$-cycle fixes its single element. Since the classes $O_i$ are disjoint and cover $X$, $\sigma$ is the product of these disjoint cycles. [/step] [step:Write each nontrivial cycle as a product of transpositions] Let $k \geq 2$, and let $a_1,\dots,a_k \in X$ be distinct. Define transpositions $\rho_j \in S_n$ for $j \in \{2,\dots,k\}$ by \begin{align*} \rho_j:=(a_1\ a_j). \end{align*} We claim that \begin{align*} (a_1\ a_2\ \cdots\ a_k)=\rho_k\rho_{k-1}\cdots\rho_2. \end{align*} The product on the right fixes every element outside $\{a_1,\dots,a_k\}$, because each factor $\rho_j$ fixes every element outside this set. For $a_1$, the rightmost transposition $\rho_2$ sends $a_1$ to $a_2$, and every later factor $\rho_3,\dots,\rho_k$ fixes $a_2$. Hence $\rho_k\rho_{k-1}\cdots\rho_2(a_1)=a_2$. If $2 \leq j < k$, then $\rho_2,\dots,\rho_{j-1}$ fix $a_j$, the factor $\rho_j$ sends $a_j$ to $a_1$, the next factor $\rho_{j+1}$ sends $a_1$ to $a_{j+1}$, and all remaining factors fix $a_{j+1}$. Hence \begin{align*} \rho_k\rho_{k-1}\cdots\rho_2(a_j)=a_{j+1}. \end{align*} Finally, $\rho_2,\dots,\rho_{k-1}$ fix $a_k$, and $\rho_k$ sends $a_k$ to $a_1$, so \begin{align*} \rho_k\rho_{k-1}\cdots\rho_2(a_k)=a_1. \end{align*} Therefore the product $\rho_k\rho_{k-1}\cdots\rho_2$ has exactly the same value as the cycle $(a_1\ a_2\ \cdots\ a_k)$ on every element of $X$, so the two permutations are equal. [guided] We want to replace one cycle by swaps of two entries. The useful choice is to keep $a_1$ fixed as a pivot and swap it successively with $a_2,\dots,a_k$. For each $j \in \{2,\dots,k\}$, define the transposition \begin{align*} \rho_j:=(a_1\ a_j). \end{align*} We prove that \begin{align*} (a_1\ a_2\ \cdots\ a_k)=\rho_k\rho_{k-1}\cdots\rho_2. \end{align*} To prove equality of two permutations in $S_n$, it is enough to check that they send every element of $X=\{1,\dots,n\}$ to the same element. First take $x \in X \setminus \{a_1,\dots,a_k\}$. Every transposition $\rho_j$ swaps only $a_1$ and $a_j$, so every $\rho_j$ fixes $x$. Hence the product $\rho_k\rho_{k-1}\cdots\rho_2$ fixes $x$, just as the cycle $(a_1\ a_2\ \cdots\ a_k)$ fixes $x$. Now evaluate the product on the entries of the cycle, remembering that the rightmost factor acts first. For $a_1$, the factor $\rho_2$ sends $a_1$ to $a_2$. Since $\rho_3,\dots,\rho_k$ only involve $a_1$ and one of $a_3,\dots,a_k$, they all fix $a_2$. Thus \begin{align*} \rho_k\rho_{k-1}\cdots\rho_2(a_1)=a_2. \end{align*} Next let $j \in \{2,\dots,k-1\}$. The factors $\rho_2,\dots,\rho_{j-1}$ do not involve $a_j$, so they fix $a_j$. The factor $\rho_j$ sends $a_j$ to $a_1$. Then $\rho_{j+1}$ sends $a_1$ to $a_{j+1}$, and all later factors $\rho_{j+2},\dots,\rho_k$ fix $a_{j+1}$. Therefore \begin{align*} \rho_k\rho_{k-1}\cdots\rho_2(a_j)=a_{j+1}. \end{align*} Finally, the factors $\rho_2,\dots,\rho_{k-1}$ fix $a_k$, and the last remaining factor $\rho_k$ sends $a_k$ to $a_1$. Hence \begin{align*} \rho_k\rho_{k-1}\cdots\rho_2(a_k)=a_1. \end{align*} The product therefore sends $a_1$ to $a_2$, sends each $a_j$ with $2 \leq j < k$ to $a_{j+1}$, sends $a_k$ to $a_1$, and fixes every element outside the support of the cycle. This is exactly the action of $(a_1\ a_2\ \cdots\ a_k)$, so the two permutations are equal. [/guided] [/step] [step:Multiply the decompositions of all nontrivial cycles] From the first step, write $\sigma$ as the product of its disjoint cycles \begin{align*} \sigma=(a_{1,1}\ \cdots\ a_{1,k_1})(a_{2,1}\ \cdots\ a_{2,k_2})\cdots(a_{s,1}\ \cdots\ a_{s,k_s}), \end{align*} where cycles with $k_i=1$ are identity permutations on their singletons. For every index $i$ with $k_i \geq 2$, the second step gives \begin{align*} (a_{i,1}\ a_{i,2}\ \cdots\ a_{i,k_i})=(a_{i,1}\ a_{i,k_i})(a_{i,1}\ a_{i,k_i-1})\cdots(a_{i,1}\ a_{i,2}). \end{align*} Each factor on the right is a transposition in $S_n$, since $a_{i,1}$ and $a_{i,j}$ are distinct for $j \geq 2$. Replacing every nontrivial cycle in the disjoint-cycle product by this transposition product expresses $\sigma$ as a finite product of transpositions. If every orbit has size $1$, then $\sigma=\operatorname{id}_X$, and this is the empty product of transpositions by convention. Hence every element of $S_n$ is a product of transpositions. [/step]