# Proof of $\text{sgn}(\sigma \cdot \tau)=\text{sgn}(\sigma) \cdot \text{sgn}(\tau)$ in Hoffman’s Linear Algebra

From the point of view of products of permutations, the basic property of the sign of a permutation is that $$\text{sgn}(\sigma \cdot \tau)=\text{sgn}(\sigma) \cdot \text{sgn}(\tau)$$. In other words, $$\sigma\cdot \tau$$ is an even permutation if $$\sigma$$ and $$\tau$$ are either both even or both odd, while $$\sigma \cdot \tau$$ is odd if one of the two permutations is odd and the other is even. One can see this from the definition of the sign in terms of successive interchanges of pairs $$(i, j)$$.

In last sentence, Hoffman’s claim we can prove $$\text{sgn}(\sigma \cdot \tau)=\text{sgn}(\sigma) \cdot \text{sgn}(\tau)$$ from definition of sgn in terms of successive interchanges of pairs, i.e. $$\text{sgn}:S_n \to K$$ such that $$\text{sgn}(\sigma)=1_K$$, if $$(\sigma (1),…,\sigma (n))$$ is obtained from $$(1,2,…,n)$$ by even number of interchanges of pairs, and $$\text{sgn}(\sigma)=-1_K$$, if $$(\sigma (1),…,\sigma (n))$$ is obtained from $$(1,2,…,n)$$ by odd number of interchanges of pairs. Que: I don’t really see if $$(\sigma \circ \tau(1),…,\sigma \circ \tau(n))$$ is obtained from $$(1,…,n)$$ by even or odd number of interchanges of pair. IMO, composition makes things bit complicated. There must be some intermediate argument to convince why $$\text{sgn}(\sigma \cdot \tau)=\text{sgn}(\sigma) \cdot \text{sgn}(\tau)$$ is true using definition of sgn in terms of interchanges of pairs.

Hoffman’s then showed $$\text{sgn}(\sigma \cdot \tau)=\text{sgn}(\sigma) \cdot \text{sgn}(\tau)$$ from elementary property of determinant.

Let $$\sigma ,\tau \in S_n$$. Let $$A=(e_{\tau (1)},…,e_{\tau (n)})$$ and $$B=(e_{\sigma (1)},…,e_{\sigma (n)})$$. Then $$\text{det}(A)=\sum_{\mu\in S_n}\text{sgn}(\mu)\prod_{i=1}^nA(i,\mu (i))$$. If $$\mu \neq \tau$$, then $$\exists j\in J_n$$ such that $$\mu (j)\neq \tau (j)$$. So $$A(j,\mu (j))=0$$. Thus $$\text{sgn}(\mu)\prod_{i=1}^nA(i,\mu (i))=0$$, $$\forall \mu \in S_n \setminus\{\tau\}$$. Hence $$\text{det}(A)=\text{sgn}(\tau)\prod_{i=1}^nA(i,\tau (i))=\text{sgn}(\tau)$$. Similarly, $$\text{det}(B)=\text{sgn}(\sigma)$$. It’s easy to see $$AB=(e_{\sigma \cdot \tau(1)},…,e_{\sigma \cdot \tau (n)})$$. So $$\text{det}(AB)=\text{sgn}(\sigma \cdot \tau)$$. Since $$\text{det}(AB)= \text{det}(A)\cdot \text{det}(B)$$, we have $$\text{sgn}(\sigma \cdot \tau)=\text{sgn}(\sigma) \cdot \text{sgn}(\tau)$$.

Que: How to rigioursly show $$AB=(e_{\sigma \cdot \tau(1)},…,e_{\sigma \cdot \tau (n)})$$? I known $$AB=(e_{\tau(1)},…,e_{\tau (n)})\cdot B=(e_{\tau (1)}\cdot B,…,e_{\tau (n)}\cdot B)$$, by this post.

Edit: $$P_\sigma =B^t$$ and $$P\tau =A^t$$. It’s easy to check, if $$R,S\in M_{n\times n}(K)$$, then $$(R\cdot S)^t=S^t\cdot R^t$$. So $$P_{\sigma \tau}= P_{\sigma}\cdot P_{\tau}=B^t\cdot A^t=(A\cdot B)^t$$. Thus $$A\cdot B=(P_{\sigma \tau})^t=(e_{\sigma \cdot \tau(1)},…,e_{\sigma \cdot \tau (n)})$$.

• Could you detail what $A,B$ are? Oct 20, 2022 at 19:54
• @mathcounterexamples.net yess. $A,B\in M_n(K)$ with $e_{\tau (1)},…,e_{\tau (n)}$ and $e_{\sigma(1)},…,e_{\sigma (n)}$ rows, respectively, where $e_i=(a_1,…,a_n)$ such that $a_i=1$ and $a_j=0$, $\forall j\in J_n-\{i\}$. Oct 20, 2022 at 19:58
• Consider the polynomial $\prod (x_k-x_j)A$ with $k > j$ and for all $k,j \leq n$. Now consider how the permutation action changes that polynomial to establish there is a homomorphism from $S_n$ to $\{1,-1\}$ under multiplication. Oct 20, 2022 at 19:59
• @CyclotomicField I’m sorry to say, your solution is more difficult than Hoffman’s. Oct 20, 2022 at 20:05
• Because it was already contained in my answer which was posted 10min earlier (and also mixed up which of $A$ or $B$ went to $\sigma$ or $\tau$).
– anon
Oct 20, 2022 at 21:47

Actually, if we define $$\mathrm{sgn}$$ to be $$\pm1$$ according to the parity of the number of transpositions used to create the permutation, the hard part is showing the sign is even well-defined to begin with (since the number of transpositions is not unique), after which showing it is a homomorphism is easy.

This is because if $$\sigma=\sigma_1\cdots\sigma_k$$ is a product of $$k$$ transpositions and $$\tau=\tau_1\cdots\tau_\ell$$ a product of $$\ell$$ transpositions, then $$\sigma\tau=\sigma_1\cdots\sigma_k\tau_1\cdots\tau_\ell$$ is a product of $$k+\ell$$ transpositions, so the homomorphism property $$\mathrm{sgn}(\sigma\tau)=\mathrm{sgn}(\sigma)\mathrm{sgn}(\tau)$$ simply reads $$(-1)^{k+\ell}=(-1)^k(-1)^\ell$$.

Let $$P_\sigma=(e_{\sigma(1)}~\cdots~e_{\sigma(n)})$$ be the permutation matrix associated to a permutation $$\sigma$$. Then $$P_\sigma$$ is characterized by the property $$P_\sigma e_j=e_{\sigma(j)}$$, by definition of matrix multiplication. This means we can simply read off $$P_\sigma P_\tau e_j=P_\sigma e_{\tau(j)}=e_{\sigma(\tau(j))}$$ to conclude $$P_\sigma P_\tau=P_{\sigma\tau}$$.

Or, we can define $$P_\sigma=[\delta_{i\sigma(j)}]$$ using the Kronecker delta symbol, then calculate $$P_\sigma P_\tau=[\delta_{i\sigma(j)}][\delta_{j\tau(k)}]=\Big[\sum_j \delta_{i\sigma(j)}\delta_{j\tau(k)}\Big]=[\delta_{i\sigma(\tau(k))}]=P_{\sigma\tau}.$$

Note after matrix multiplication we can erase all zero summands (i.e. all but when $$j=\tau(k)$$).

• I will take some time to completely absorb your answer and ask you some que. First paragraph: “hard part is showing the sign is even well-defined to begin with” in this post I showed sgn maps to a unique point in $\{1_K,-1_K\}$ using contradiction, i.e. number of interchanges is always even or always odd. Are you taking about group homomorphism? Because we’re looking for $f(u\cdot v)=f(u)\cdot f(v)$ property, preserve group structure. We haven’t yet shown sgn is homomorphism. Oct 20, 2022 at 20:39
• I don't think it's obvious that the parity in the number of transpositions used to construct a permutation is invariant. If you define the determinant (which is unique), the sign of a permutation is easily seen to be well-defined as it is the determinant of the permutation matrix, but this requires linear algebra for a combinatorial question, so I still wouldn't call it obvious. As for the second part of my answer, your $AB=(e_{\sigma\tau})$ claim is just $P_\sigma P_\tau=P_{\sigma\tau}\,$, which says $\sigma\mapsto P_\sigma$ is a homomorphism.
– anon
Oct 20, 2022 at 21:45
• I agree, we used notion of determinant to prove sgn is well defined. Second paragraph: I don’t known proof of “every $\sigma \in S_n$ may be factored in a product of adjacent transposition” because Hoffman didn’t took this approach. First time I saw that claim in this video (time stamp 10:24). It’s proof is not straightforward. I don’t understand following statement, “so the homomorphism property $\mathrm{sgn}(\sigma\tau)=\mathrm{sgn}(\sigma)\mathrm{sgn}(\tau)$ simply reads $(-1)^{k+\ell}=(-1)^k(-1)^\ell$“. Oct 21, 2022 at 10:29
• Third paragraph: For future reader I’m completing details of $P_\sigma e_j=e_{\sigma(j)}$ result. $(P_\sigma\cdot e_j)_{i1}=\sum_k (P_\sigma)_{ik}\cdot (e_j)_{k1}=\sum_k \delta_{i\sigma (k)}\delta_{kj}$. So $\delta_{i\sigma (k)}\delta_{kj}\neq 0$, if $i=\sigma (k)$ and $j=k$. Which implies $\sigma (j)=\sigma (k)=i$ and $j=k$. Thus $(P_\sigma e_j)_{i1}=0$, $\forall i\neq \sigma (j)$ and $(P_\sigma e_j)_{\sigma (j)1}=\delta_{\sigma (j)\sigma (j)}\delta_{jj}=1$. Hence $P_\sigma e_j=e_{\sigma (j)}$. Oct 21, 2022 at 10:35
• $(P_\sigma P_{\tau})(e_j)=e_{\sigma \tau (j)}=P_{\sigma \tau}(e_j)$, $\forall j\in J_n$ implies $P_\sigma P_\tau=P_{\sigma \tau}$, because if $A\in M_n(F)$, then $A\cdot e_j$ is $j$th column of $A$. Fourth paragraph: $\delta_{i\sigma(j)}\delta_{j\tau(k)}\neq 0$, if $i=\sigma (j)$ and $\tau (k)=j$. Which implies $\sigma (\tau (k))=\sigma (j)=i$ and $j=\tau (k)$. Hence $\sum_j \delta_{i\sigma(j)}\delta_{j\tau(k)}=\delta_{i \sigma (\tau (k))}$. Oct 21, 2022 at 10:47