[proofplan] We prove multiplicativity by expressing each permutation as a product of transpositions. The key input is that the signature of a permutation is $(-1)^m$ whenever the permutation is written as a product of $m$ transpositions, so concatenating two transposition decompositions adds the exponents. This gives $\operatorname{sgn}(\sigma\pi)=(-1)^{m+\ell}=(-1)^m(-1)^\ell=\operatorname{sgn}(\sigma)\operatorname{sgn}(\pi)$ for arbitrary $\sigma,\pi\in S_n$. [/proofplan] [step:Choose transposition decompositions for the two permutations] Let $\sigma,\pi\in S_n$ be arbitrary. We use the standard fact that every element of $S_n$ is a product of transpositions. Thus there exist integers $m,\ell\ge 0$ and transpositions $\tau_1,\dots,\tau_m,\rho_1,\dots,\rho_\ell\in S_n$ such that \begin{align*} \sigma=\tau_1\tau_2\cdots\tau_m \end{align*} and \begin{align*} \pi=\rho_1\rho_2\cdots\rho_\ell. \end{align*} When $m=0$ or $\ell=0$, the corresponding product is the empty product, hence the identity permutation in $S_n$. [guided] Fix arbitrary permutations $\sigma,\pi\in S_n$. The goal is to compare the signature of the product $\sigma\pi$ with the separate signatures of $\sigma$ and $\pi$. Since the signature is controlled by transposition decompositions, we first write both permutations in that form. Every element of $S_n$ can be written as a product of transpositions. Therefore there are integers $m,\ell\ge 0$ and transpositions $\tau_1,\dots,\tau_m,\rho_1,\dots,\rho_\ell\in S_n$ satisfying \begin{align*} \sigma=\tau_1\tau_2\cdots\tau_m \end{align*} and \begin{align*} \pi=\rho_1\rho_2\cdots\rho_\ell. \end{align*} The cases $m=0$ and $\ell=0$ are included: an empty product denotes the identity element of $S_n$. This convention is necessary because the identity permutation has no required transpositions in its shortest decomposition, and the homomorphism identity must also hold when one of $\sigma$ or $\pi$ is the identity. [/guided] [/step] [step:Concatenate the decompositions to express the product] Using associativity of composition in the group $S_n$, the product $\sigma\pi$ has the [transposition decomposition](/theorems/777) \begin{align*} \sigma\pi=(\tau_1\tau_2\cdots\tau_m)(\rho_1\rho_2\cdots\rho_\ell). \end{align*} Thus $\sigma\pi$ is expressed as a product of $m+\ell$ transpositions, namely $\tau_1,\dots,\tau_m,\rho_1,\dots,\rho_\ell$ in that order. [guided] The group operation in $S_n$ is composition of permutations, and composition is associative. Therefore, after choosing the decompositions \begin{align*} \sigma=\tau_1\tau_2\cdots\tau_m \end{align*} and \begin{align*} \pi=\rho_1\rho_2\cdots\rho_\ell, \end{align*} their product is \begin{align*} \sigma\pi=(\tau_1\tau_2\cdots\tau_m)(\rho_1\rho_2\cdots\rho_\ell). \end{align*} This is already a product of transpositions: the first $m$ factors are $\tau_1,\dots,\tau_m$, and the next $\ell$ factors are $\rho_1,\dots,\rho_\ell$. Hence the total number of transpositions in the displayed decomposition of $\sigma\pi$ is $m+\ell$. The order matters because multiplication in $S_n$ is generally not commutative, so we keep the factors exactly in the order coming from $\sigma$ followed by $\pi$. [/guided] [/step] [step:Apply the transposition decomposition formula for signature] The theorem [Signature from Transposition Decompositions](/theorems/7876) [citetheorem:7876] says that if a permutation in $S_n$ is written as a product of $r$ transpositions, then its signature is $(-1)^r$. Applying this result with $r=m$ to the displayed decomposition of $\sigma$ gives \begin{align*} \operatorname{sgn}(\sigma)=(-1)^m. \end{align*} Applying the same result with $r=\ell$ to the displayed decomposition of $\pi$ gives \begin{align*} \operatorname{sgn}(\pi)=(-1)^\ell. \end{align*} Applying it with $r=m+\ell$ to the concatenated decomposition of $\sigma\pi$ gives \begin{align*} \operatorname{sgn}(\sigma\pi)=(-1)^{m+\ell}. \end{align*} [guided] We now use the precise external input on which the proof rests: Signature from Transposition Decompositions [citetheorem:7876]. Its hypothesis is that a permutation in $S_n$ has been expressed as a product of transpositions, and its conclusion is that the signature of that permutation equals $(-1)^r$, where $r$ is the number of transpositions in the chosen expression. For $\sigma$, the hypothesis is satisfied by the decomposition \begin{align*} \sigma=\tau_1\tau_2\cdots\tau_m, \end{align*} where each $\tau_i$ is a transposition in $S_n$. Therefore the theorem gives \begin{align*} \operatorname{sgn}(\sigma)=(-1)^m. \end{align*} For $\pi$, the hypothesis is satisfied by the decomposition \begin{align*} \pi=\rho_1\rho_2\cdots\rho_\ell, \end{align*} where each $\rho_j$ is a transposition in $S_n$. Therefore \begin{align*} \operatorname{sgn}(\pi)=(-1)^\ell. \end{align*} Finally, the previous step showed that $\sigma\pi$ has a decomposition into $m+\ell$ transpositions, namely $\tau_1,\dots,\tau_m,\rho_1,\dots,\rho_\ell$. Applying the same theorem one more time gives \begin{align*} \operatorname{sgn}(\sigma\pi)=(-1)^{m+\ell}. \end{align*} This is the point where the well-definedness of the parity in a transposition decomposition is being used: the theorem guarantees that these values of the signature do not depend on the particular decompositions chosen. [/guided] [/step] [step:Identify the product of signatures] Since integer powers of $-1$ satisfy $(-1)^{m+\ell}=(-1)^m(-1)^\ell$, we obtain \begin{align*} \operatorname{sgn}(\sigma\pi)=(-1)^{m+\ell}. \end{align*} Substituting the three identities from the preceding step gives \begin{align*} \operatorname{sgn}(\sigma\pi)=\operatorname{sgn}(\sigma)\operatorname{sgn}(\pi). \end{align*} Because $\sigma,\pi\in S_n$ were arbitrary, the map \begin{align*} \operatorname{sgn}:S_n\to\{1,-1\} \end{align*} preserves multiplication. Hence $\operatorname{sgn}$ is a [group homomorphism](/page/Group%20Homomorphism) from $S_n$ to the multiplicative group $\{1,-1\}$. [guided] The three identities obtained from the transposition decomposition formula are \begin{align*} \operatorname{sgn}(\sigma)=(-1)^m, \end{align*} \begin{align*} \operatorname{sgn}(\pi)=(-1)^\ell, \end{align*} and \begin{align*} \operatorname{sgn}(\sigma\pi)=(-1)^{m+\ell}. \end{align*} The remaining step is arithmetic in the multiplicative group $\{1,-1\}$. Since exponent laws for integer powers give \begin{align*} (-1)^{m+\ell}=(-1)^m(-1)^\ell, \end{align*} we substitute the first two displayed identities into the right-hand side and the third displayed identity into the left-hand side. This yields \begin{align*} \operatorname{sgn}(\sigma\pi)=\operatorname{sgn}(\sigma)\operatorname{sgn}(\pi). \end{align*} The permutations $\sigma$ and $\pi$ were chosen arbitrarily in $S_n$, so this equality holds for every pair of elements of $S_n$. Therefore the map \begin{align*} \operatorname{sgn}:S_n\to\{1,-1\} \end{align*} preserves the group operation. Since $\{1,-1\}$ is equipped with multiplication, this is exactly the assertion that $\operatorname{sgn}$ is a group homomorphism from $S_n$ to $\{1,-1\}$. [/guided] [/step]