Practice: Permutations

(a) $\sigma =(25143)$. Inversions. Count, for each entry, the strictly smaller entries to its right: | entry | smaller, to its right | count |
|---|---|---|
| 2 | 1 | 1 |
| 5 | 1, 4, 3 | 3 |
| 1 | — | 0 |
| 4 | 3 | 1 |
| 3 | — | 0 | $\mathrm{inv}(\sigma )=1+3+0+1+0=5$, so $\mathrm{sgn}(\sigma )=(-1{)}^5=-1$. Odd. Cycles. Trace: $1\mapsto 2\mapsto 5\mapsto 3\mapsto 1$, closing a 4-cycle $(1253)$. Then $4\mapsto 4$, a fixed point. So $\sigma =(1253)(4)$. One cycle of length 4 contributes $4-1=3$ transpositions; the fixed point contributes none. Total 3, so $\mathrm{sgn}(\sigma )=(-1{)}^3=-1$ ✓. The routes agree. Note that 5 inversions and 3 transpositions are different counts, only their parity must match, and both are odd. (b) $\tau =(135)(24)$. One-line. From the cycles: $1\mapsto 3$, $3\mapsto 5$, $5\mapsto 1$, and $2\mapsto 4$, $4\mapsto 2$. Listing the images of $1,2,3,4,5$ in order:

Sign. A 3-cycle is $3-1=2$ transpositions (even); a 2-cycle is 1 (odd). Total 3, so $\mathrm{sgn}(\tau )=-1$. Odd. Check by inversions on $(34521)$: 3 beats 2 and 1 → 2; 4 beats 2 and 1 → 2; 5 beats 2 and 1 → 2; 2 beats 1 → 1; total $2+2+2+1=7$, and $(-1{)}^7=-1$ ✓. (c) The composition $\sigma \circ \tau$, applying $\tau$ first. $(\sigma \circ \tau )(i)=\sigma (\tau (i))$, with $\sigma =(25143)$ and $\tau =(34521)$: | $i$ | $\tau (i)$ | $\sigma (\tau (i))$ |
|---|---|---|
| 1 | 3 | 1 |
| 2 | 4 | 4 |
| 3 | 5 | 3 |
| 4 | 2 | 5 |
| 5 | 1 | 2 | So $\sigma \circ \tau =(14352)$. Its sign by inversions. 1 beats nothing → 0; 4 beats 3 and 2 → 2; 3 beats 2 → 1; 5 beats 2 → 1; total $0+2+1+1=4$, so the sign is $(-1{)}^4=+1$. Multiplicativity. $\mathrm{sgn}(\sigma )\mathrm{sgn}(\tau )=(-1)(-1)=+1$ ✓. Two odd permutations compose to an even one, exactly as adding two odd numbers gives an even one. (d) The permutation matrix.

Why. In the Leibniz sum $detP=\sum _{\pi }\mathrm{sgn}(\pi )\prod _i{p}_{i,\pi (i)}$, a term survives only if $p_{i,\pi (i)}=1$ for every $i$, which happens for the single permutation $\pi =\sigma$. That term is $\mathrm{sgn}(\sigma )$ times a product of five ones. Geometrically: $P$ maps the unit cube onto itself, so $|detP|=1$, and the sign says orientation is reversed, $\sigma$ being odd, $P$ acts as a reflection rather than a rotation. (e) Why parity is well defined. The decomposition into transpositions is genuinely non-unique: $(1253)$ can be written as $(13)(15)(12)$, or with extra cancelling pairs such as $(13)(15)(12)(45)(45)$, giving 3 factors or 5. What never changes is the parity. The argument. Composing with any transposition changes the inversion count by an odd number. For an adjacent swap this is immediate: exactly one pair reverses relative order, so $\mathrm{inv}$ changes by $\pm 1$. A transposition of positions $i$ and $j$ with $d=j-i$ is a product of $2d-1$ adjacent swaps, move one entry right $d$ steps, move the displaced entry left $d-1$ steps, and $2d-1$ is odd, so the total change is a sum of an odd number of odd changes, hence odd. Now start from the identity, which has $\mathrm{inv}=0$, and apply $m$ transpositions to reach $\sigma$. Each flips the parity of $\mathrm{inv}$, so the parity after $m$ steps is the parity of $m$. But it also equals the parity of $\mathrm{inv}(\sigma )$, a number fixed by $\sigma$ alone. Therefore $m\equiv \mathrm{inv}(\sigma )(\mathrm{mod}2)$ for every decomposition, and $\mathrm{sgn}$ is well defined. What would break. The Leibniz formula assigns each of the $n!$ terms a sign depending only on its permutation. If parity were not invariant, the same term could be assigned $+$ or $-$ according to how its permutation happened to be written, and the sum would not be a function of $A$ at all, $det$ would be undefined rather than merely awkward. Every downstream fact would fail with it: the row-swap rule, $det(AB)=detAdetB$, and the characterisation of invertibility by a nonzero determinant.