Conceptual reason why the sign of a permutation is well-defined?

Question

Teaching group theory this semester, I found myself laboring through a proof that the sign of a permutation is a well-defined homomorphism $\operatorname{sgn} : \Sigma_n \to \Sigma_2$. An insightful student has pressed me for a more illuminating proof, and I'm realizing that this is a great question, and I don't know a satisfying answer. There are many ways of phrasing this question:

Question: Is there a conceptually illuminating reason explaining any of the following essentially equivalent statements?

1. The symmetric group $\Sigma_n$ has a subgroup $A_n$ of index 2.

2. The symmetric group $\Sigma_n$ is not simple.

3. There exists a nontrivial group homomorphism $\Sigma_n \to \Sigma_2$.

4. The identity permutation $(1) \in \Sigma_n$ is not the product of an odd number of transpositions.

5. The function $\operatorname{sgn} : \Sigma_n \to \Sigma_2$ which counts the number of transpositions "in" a permutation mod 2, is well-defined.

6. There is a nontrivial "determinant" homomorphism $\det : \operatorname{GL}_n(k) \to \operatorname{GL}_1(k)$.

7. ….

Of course, there are many proofs of these facts available, and the most pedagogically efficient will vary by background. In this question, I'm not primarily interested in the pedagogical merits of different proofs, but rather in finding an argument where the existence of the sign homomorphism looks inevitable, rather than a contingency which boils down to some sort of auxiliary computation.

The closest thing I've found to a survey article on this question is a 1972 note "An Historical Note on the Parity of Permutations" by TL Bartlow in the American Mathematical Monthly. However, although Bartlow gives references to several different proofs of these facts, he doesn't comprehensively review and compare all the arguments himself.

Here are a few possible avenues:

• $\Sigma_n$ is a Coxeter group, and as such it has a presentation by generators (the adjacent transpositions) and relations where each relation respects the number of words mod 2. But just from the definition of $\Sigma_n$ as the group of automorphisms of a finite set, it's not obvious that it should admit such a presentation, so this is not fully satisfying.

• Using a decomposition into disjoint cycles, one can simply compute what happens when multiplying by a transposition. This is not bad, but here the sign still feels like an ex machina sort of formula.

• Defining the sign homomorphism in terms of the number of pairs whose order is swapped likewise boils down to a not-terrible computation to see that the sign function is a homomorphism. But it still feels like magic.

• Proofs involving polynomials again feel like magic to me.

• Some sort of topological proof might be illuminating to me.

Answer 1

Here is my favorite conceptual definition of the determinant, which answers point 6 and looks pretty much inevitable.

If $V$ is an $n$-dimensional $k$-vector space and $T$ is an endomorphism of $V$, then $T$ induces an endomorphism of $\Lambda^n V$. Since $\Lambda^n V$ is one-dimensional, this endomorphism must be multiplication by some scalar, which is none other than $\det T$. It is clear that if $T$ is invertible then so is the induced map on $\Lambda^n V$, and that $\det$ is multiplicative, so it defines a homomorphism $GL(V)\to k^\times$.

Once you have the determinant you can just define $\text{sgn}(\pi)$ as the determinant of the permutation matrix corresponding to $\pi$.

Answer 2

My first thought was to do it by induction and trace what happens to $n$. So (first draft) assume it's true for $S_{n-1}$, which fixes $n$. Let $\sigma \in S_n$, and let $i = \sigma(n)$. If you could write $\sigma$ as a product of both an odd and an even number of transpositions, you could then write $(i \ n) \cdot \sigma$ as a product of both an even and an odd number of transpositions. But $\sigma$ takes $n$ to $i$ and $(i \ n)$ takes it back to $n$, so $(i \ n) \cdot \sigma$ lies in $S_{n-1}$, and must be a product of even or odd numbers of transpositions but not both.

As the first commenter below pointed out in like a minute :-) this doesn't get at the main issue, which is that you could have $\sigma \in S_n$ that you can write as both an odd product and an even product in some larger ambient $S_n$. It's really about the base case in the induction, which is the identity: if you can prove that this can't happen for the identity, you've really done it for any $\sigma \in S_n$. (If $\sigma$ is a product of both an odd and an even number of transpositions, we get that $\mbox{id} = \sigma \cdot \sigma^{-1}$ is a product of an odd + even = odd number of transpositions.)

If we stick to looking at the identity, it's clear in principle what happens to $n$: it starts as the last element, and ends there too. So we should be able to pull it out! To help picture this, make one more reduction, which is that it's equivalent to look at odd vs. even products of adjacent transpositions. This is because any transposition is conjugate by a series of adjacent transpositions to an adjacent transposition, and conjugation preserves parity.

All that said, suppose we can write the identity as a product of an odd number of adjacent transpositions in some $S_n$. Pick the smallest such $n$, and let the number of adjacent transpositions used be minimal for that $n$. Represent the product as a (singular) braid diagram, with the strings ordered left to right as $1, \ldots , n$, and with each adjacent transposition represented by a singular crossing. String $n$ begins to the right of every other string, and, since our product is the identity, it ends to the right of every other string too. This means, for any other string $i$, that $n$ begins and ends on the same (right) side of $i$, and hence (here's the whole point!) crosses $i$ an even number of times. Now I hope you see the punch line: pull the string! I.e., pulling the $n$-th string all the way to the right, out of the braid, reduces the number of crossings (adjacent transpositions in the product) if there were any, but keeps it even, contradicting the minimality above.

Answer 3

Think of permutations as acyclic orientations on a complete graph. One reaches neighboring permutations by edge flips that preserve acyclicity; these correspond to adjacent pair swaps. Each edge acts as a toggle switch, so every cycle in the neighbor graph is even, and the parity of a permutation is well-defined.

The illustration is a permutahedron as zonotope (Mercator projection). Classification of Vertex-Transitive Zonotopes gives a survey and generalization of this point of view.

Answer 4

I'm building off ideas in the answer of manzana and a comment of Vitali Kapovitch. I hope people won't mind one more answer to this excellent question.

The plan is to show that the orthogonal group is disconnected. Then, $O(n) \to \pi_0 O(n)$ will be a surjective group homomorphism with an interesting kernel. If we also know that $O(n)$ is generated by hyperplane reflections, then by continuously adjusting a general product of hyperplane reflections we obtain a similar product where all the hyperplanes coincide. (This uses connectivity of the space of hyperplanes). So $O(n)$ has at most two path components.

Let us visualize $O(n)$ as a space of orthonormal frames given by column vectors. We consider $O(n-1) \subseteq O(n)$ by setting the final vector of a frame to $e_n$. Write $Q(n) \subseteq O(n)$ for the open subset of frames where $-e_n$ is not the final vector of the frame. We have $O(n) \subseteq Q(n+1) \subseteq O(n+1)$. That $O(n)$ is disconnected follows from applying the following lemma to a putative path connecting the two elements of $O(1)$.

Lemma Let $n \geq 1$. Any path contained in $O(n+1)$ and connecting endpoints in $O(n)$ gives rise to

• another path with the same endpoints but contained in $Q(n+1)$
• another path with the same endpoints but contained in $O(n)$.

Proof

The first claim works a bit differently for $n=1$ and $n \geq 2$. When $n$ is large, the open set $U$ is the complement of a submanifold of codimension at least 2, so we can perturb the path to avoid the bad set. (This step requires justification, but at least it's intuitive.) If $n=1$, we can adjust the path by multiplying both diagonal entries by the sign of the entry in the lower right.

The second claim follows because frames in $Q(n+1)$ rotate into $O(n)$ without much fuss. Choose coordinates so that $e_{n+1}$ points directly up. Apply the first claim so that, along the whole path of frames, the final vector never points straight down. We are going to operate on the whole path at once, rotating each frame around a different axis. No need to touch the frames where the final vector already points up! For every other frame on the path, we choose our axis to be the orthogonal complement of the 2-plane spanned by the final vector and the vertical. Then, coordinating speeds, we rotate each frame so that, at time $t=1$, all the final vectors point exactly upwards.

Answer 5

$\DeclareMathOperator\GL{GL}$Here's a conceptual explanation for why there exists a determinant homomorphism $\det:\GL_n(\mathbb R)\to \GL_1(\mathbb R)$.

It comes from the action of $\GL_n(\mathbb R)$ on $L^1(\mathbb R^n)$.

The number $\det(A)$ encodes the way in which the $L^1$-norm of a function changes as it gets pulled back by the linear map $A:\mathbb R^n\to \mathbb R^n$.

Now, you might (righfully) complain that this actually gives $\lvert\det(A)\rvert$, and not $\det(A)$….
But you can't complain that it's not conceptual.

Answer 6

[This is a repetition of this answer, except for few modifications.]

Fix ${ n \in \mathbb{Z} _{\gt 0} }.$

Def: A list ${ [k _1, \ldots, k _n] }$ made by taking ${ 1, \ldots, n }$ in some order is called an arrangement.

Def: For ${ \sigma \in S _n }$ and arrangement ${ [k _1, \ldots, k _n] },$ let ${ \sigma \ast [k _1, \ldots, k _n] := ( [k _1, \ldots, k _n] \text{ after putting whatever is in slot } i \text{ into slot } \sigma(i) ) }.$

We see ${ \sigma \ast [k _1, \ldots, k _n] }$ ${ = [k _{\sigma ^{-1} (1)} , \ldots, k _{\sigma ^{-1} (n)} ] }$

In ${ [k _1, \ldots, k _n] }$ ${ \rightsquigarrow \sigma \ast [k _1, \ldots, k _n] },$ the ${ k _t }$ which gets sent to slot ${ j }$ satisfies ${ \sigma (t) = j }$ that is ${ t = \sigma ^{-1} (j) }.$

Also ${ \sigma \ast (\pi \ast [k _1, \ldots, k _n]) }$ ${ = (\sigma \pi) \ast [k _1, \ldots, k _n] }$

In ${ [k _1, \ldots, k _n] }$ ${ \rightsquigarrow \sigma \ast (\pi \ast [k _1, \ldots, k _n]) },$ ${ k _i }$ is first sent to slot ${ \pi (i) }$ and then to slot ${ \sigma (\pi (i)) }.$
And ${ [k _1, \ldots, k _n] }$ ${ \rightsquigarrow (\sigma \pi) \ast [k _1, \ldots, k _n] }$ has the same effect.

Notation: ${ [k _1, \ldots, k _n] \overset{\sigma}{\rightsquigarrow} [\ell _1, \ldots, \ell _n ] }$ will mean ${ [\ell _1, \ldots, \ell _n] = \sigma \ast [k _1, \ldots, k _n] }.$

---

Every ${ \sigma \in S _n }$ is a product of disjoint cycles. It leads to: Is every cycle further a product of transpositions ?

Eg 1: Consider ${ (1234) }.$
It is easy to verify ${ (1234) }$ ${ = (34)(24)(14) },$ but here is one way to come up with this in the first place.
We have ${ [1,2,3,4] \overset{(1234)}{\rightsquigarrow} [4 , 1, 2 , 3] .}$ To get the same effect using transpositions, ${ [1,2,3,4] \overset{(14)}{\rightsquigarrow} [{\color{green}{4}}, 2, 3, 1] }$ ${ \overset{(24)}{\rightsquigarrow} [{\color{green}{4}}, {\color{green}{1}}, 3, 2] }$ ${ \overset{(34)}{\rightsquigarrow} [{\color{green}{4}}, {\color{green}{1}}, {\color{green}{2}}, {\color{green}{3}} ].}$
So formally ${ (1 2 3 4) \ast [1,2,3,4] }$ ${ = (34) \ast ( (24) \ast ( (14) \ast [1,2,3,4] ) ) , }$ that is ${ (1234) \ast [1,2,3,4] }$ ${ = (34)(24)(14) \ast [1,2,3,4] }$ that is ${ (1234) = (34)(24)(14). }$
This suggests that in general ${ (a _1 a _2 \ldots a _{k-1} a _k) }$ ${ = (a _{k-1} a _k) \ldots (a _2 a _k) (a _1 a _k),}$ which is clearly true.

This leads to: Is every transposition further a product of elementary transpositions ?

Eg 2: Consider ${ (14) }.$ We have

So ${ (14) }$ ${ = (12)(23)(34)(23)(12) }.$ (This is also natural from conjugations).
Similarly any transposition can be written as a product of an odd number of elementary transpositions.

Every ${ \sigma \in S _n }$ is a product of elementary transpositions. This leads to: How are we constrained in writing a ${ \sigma \in S _n }$ as a product of elementary transpositions ?

Let ${ \sigma \in S _n }.$ We can write it as a product of elementary transpositions ${ \sigma }$ ${ = \tau _1 \ldots \tau _k }.$ Suppose ${ \sigma }$ ${ = \tau ' _1 \ldots \tau ' _{\ell} }$ is another expression as a product of elementary transpositions.
Now ${ \tau _1 \ldots \tau _k }$ ${ = \tau ' _1 \ldots \tau ' _{\ell} },$ that is ${ \tau ' _{\ell} \ldots \tau ' _1 \tau _1 \ldots \tau _k }$ ${ = \text{id} }.$
We know ${ [k _1, \ldots, k _n] }$ ${ \rightsquigarrow (j \text{ } j+1) \ast [k _1, \ldots, k _n] }$ changes the number of inversions by ${ \pm 1 }.$
So ${ [1, \ldots, n] }$ ${ \rightsquigarrow \tau ' _{\ell} \ast ( \ldots \tau _k \ast [1, \ldots, n] \ldots ) }$ changes number of inversions by ${ \underbrace{\pm 1 \ldots \pm 1} _{k+\ell \text{ terms}} }.$
But ${ \tau ' _{\ell} \ldots \tau _k \ast [1, \ldots, n] }$ ${ = \text{id} \ast [1, \ldots, n] }$ has ${ 0 }$ inversions.
So ${ k+\ell }$ must be even, that is ${ k, \ell }$ have the same parity.

So for ${ \sigma \in S _n },$ no matter how we express ${ \sigma }$ as a product of elementary transpositions, the quantity ${ (-1) }$ raised to the number of elementary transpositions remains the same. This invariant is defined as ${ \text{sgn}(\sigma) }.$

Now ${ \text{sgn} : S _n \to \lbrace \pm 1 \rbrace }$ is a homomorphism.

Let ${ \sigma, \pi \in S _n }.$ Can write them as products of elementary transpositions, ${ \sigma = \tau _1 \ldots \tau _k }$ and ${ \pi = \tau ' _1 \ldots \tau ' _{\ell} }.$ So ${\text{sgn}( \sigma \pi) }$ ${ = (-1) ^{k+\ell} }$ ${ = (-1) ^k (-1) ^{\ell} }$ ${ = \text{sgn}(\sigma) \text{sgn}(\pi) }.$

From Eg 2, sign of any transposition is ${ (-1) }.$ From Eg 1, sign of any cycle is ${ \text{sgn}(a _1 \ldots a _k) }$ ${ = \text{sgn}(a _{k-1} a _k) \ldots \text{sgn}(a _1 a _k) }$ ${ = (-1) ^{k-1} }.$

---

Rem: If only establishing the sign homomorphism were the goal, Eg 1 and Eg 2 are unnecessary. (One can directly see any permutation is a product of elementary transpositions, and proceed with the rest of the argument). But they let us compute signs.

Answer 7

Consider finite complete oriented graphs with finitely many vertices. For $G= (X, E)$ , $ G' = (X', E')$, consider a map from $G$ to $G'$ to be a bijection from $X$ to $X'$. Define its sign to be the $\pm 1$, the product of the sign changes between corresponding edges of $G$, and $G'$. It should be clear that the sign of composition of maps is the product of signs of the factors.

Now consider any finite set $X$, and a complete oriented graph $G= (X,E)$. Take a bijection from $X$ to itself, and look at its sign as a map from $(X,E)$ to $(X,E)$. Now change the orienttation of some edges of $G$ and get $G' = (X, E')$. Look at the sign of the correponding map from $(X,E')$ to $(X,E')$. Can you see that it is the same sign? Indeed: write $\phi\colon (X,E') \to (X,E')$ as a composition of three maps : $\mathbb{1}$ from $(X,E')$ to $(X,E)$, $\phi$ from $(X,E)$ to $(X,E)$ and $\mathbb{1}$ from $(X,E)$ to $(X,E')$ ( some abuse of notation occured).

Added: The signature of a bijection between oriented (finite) sets, and not only for bijections from a set to itself, is useful. Take for instance the case of totally ordered finite sets --they get an orientation from the order. The signature appears when one considers minors of a matrix, and especially Laplace expansion of a determinant.

Added: The answer looks similar to Björn's answer. I consider maps between "oriented sets", that makes it more "functorial".