160
$\begingroup$

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.

$\endgroup$
56
  • 38
    $\begingroup$ So I guess your first and third bullet points have ruled out a proof of the form: "Draw the permutation by connecting dots on either sides of a strip. Use wiggly lines if you like, but only use normal crossings. Now count the number of crossings, and argue that this count mod 2 is a topological invariant." $\endgroup$ Mar 8, 2022 at 17:12
  • 7
    $\begingroup$ @markvs I don't actually know how to define the determinant (or else characterize it and prove its existence) without knowing that the sign of a permutation is well-defined. $\endgroup$
    – Tim Campion
    Mar 8, 2022 at 17:17
  • 15
    $\begingroup$ If you think about the sign of a permutation as counting (the parity of) the number of inversions, rather than (the parity of) the number of transpositions, then I think #3 becomes much more clear. You still have to prove that this function is a homomorphism (see, e.g., this question), but at least you don't have to deal with any of the well-definedness issues. $\endgroup$ Mar 8, 2022 at 17:40
  • 9
    $\begingroup$ @LSpice Although the motivation is partly pedagogical, at this point I'm not primarily interested in finding a proof which will optimally satisfy my students, but rather one which will satisfy me. Right now, I know that the sign of a permutation is a well-defined homomorphism, but I don't know "why, really". $\endgroup$
    – Tim Campion
    Mar 8, 2022 at 17:42
  • 10
    $\begingroup$ Usually the sign is used to show that the top exterior power is nonzero $\endgroup$ Mar 8, 2022 at 18:32

37 Answers 37

1
2
3
$\begingroup$

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$.

$\endgroup$
7
  • 5
    $\begingroup$ How do you prove that the nth exterior power is one-dimensional? $\endgroup$ Mar 9, 2022 at 23:05
  • 2
    $\begingroup$ Right, now that I think of it, we can hardly say anything about exterior powers without the notion of the sign of a permutation. $\endgroup$ Mar 9, 2022 at 23:21
  • $\begingroup$ @SamHopkins Here's a workaround. Have $\{e_i\}$ be a basis of $\mathbb R^n$. Then specify a multilinear map $\det: (\mathbb R^n)^n\to\mathbb R$ by $\det(e_1,e_2,\dots e_n)=1$ and $\det(v_1,v_2,\dots v_n)=0$ whenever the vectors $v_1\dots v_n$ are linearly dependent. You then prove this is antisymmetric by setting any pair of arguments to $u+v$. Then define the determinant of any operator by $\det A\equiv\det(Ae_1,Ae_2,\dots Ae_n)$. $\endgroup$ Mar 10, 2022 at 2:34
  • $\begingroup$ @AlexArvanitakis How do these two properties make the map well-defined? $\endgroup$ Mar 10, 2022 at 5:42
  • 6
    $\begingroup$ The real problem with this method is showing that $\bigwedge^n V$ is nonzero. It is clearly spanned by $e_1 \wedge \ldots \wedge e_n$, but you need some argument to show that this element is not itself zero. Usually the determinant is used for that, which is constructed using a sign. This was discussed extensively in the comments to the original question. That said, there might be a noncommutative Gröbner basis argument that shows the nonvanishing, but this is probably getting too technical. $\endgroup$ Mar 10, 2022 at 20:46
3
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ This needs a little more work to actually be a full proof, I think - just because $(i n) \cdot \sigma$ can't be written as a product of both an even and odd number of transpositions in $S_{n - 1}$ doesn't mean it can't be written as a product of both an even and odd number of transpositions in $S_n$, because there are more transpositions in $S_n$. $\endgroup$
    – user44191
    Mar 13, 2022 at 23:27
  • $\begingroup$ You're right, I should have been careful in my inductive hypothesis that though $\sigma$ fixes everything after $n$, it might be factored in a larger ambient symmetric group. So the real heart of things is the base case, i.e., showing that the identity can't be expanded as a product of an odd number of transpositions. I'd like to find a good inductive argument for that but I'm not seeing it. $\endgroup$ Mar 14, 2022 at 0:27
  • $\begingroup$ Hi Eugene, you should merge your accounts, then you can edit your posts. Ask the moderators about it. $\endgroup$ Mar 14, 2022 at 15:38
  • $\begingroup$ Welcome to MathOverflow! Please use the Contact Us form to have your accounts merged, to regain full control over your posts. $\endgroup$
    – Glorfindel
    Mar 17, 2022 at 9:47
2
$\begingroup$

The permutahedron as zonotope, Mercator projection

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.

$\endgroup$
1
  • $\begingroup$ This feels like a "Proof Without Words" that I'm not getting. $\endgroup$ Apr 5, 2022 at 14:31
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

$\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.

$\endgroup$
3
  • 9
    $\begingroup$ It seems to me this kills the problem. If one has a determinant then one can define the sign as the det of the permutation matrix, but if one takes the absolute value this just gives the homomorphism from $S_n$ to the trivial group $\{1\}$. I guess one would need the change of variable formula without $|\cdot|$ but this means the theory of integration of differential forms. $\endgroup$ Mar 9, 2022 at 14:24
  • $\begingroup$ @AbdelmalekAbdesselam. I know. I'm only answering item 6 of the question. Not the question about $\Sigma_n$. $\endgroup$ Mar 10, 2022 at 0:56
  • $\begingroup$ I see. There is in fact a way of constructing the det without the absolute value first and then the sign function. Maybe I'll add that to my answer later. $\endgroup$ Mar 10, 2022 at 18:22
0
$\begingroup$

[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

elemtransp

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.

$\endgroup$
0
$\begingroup$

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".

$\endgroup$
5
  • 2
    $\begingroup$ This is similar to Ramras answer, above, I think? $\endgroup$
    – Sam Nead
    Aug 14, 2023 at 7:16
  • $\begingroup$ @Sam Nead: My signature is a functor :-) $\endgroup$
    – orangeskid
    Aug 14, 2023 at 10:04
  • 1
    $\begingroup$ I don't get the joke. And I think you have not answered my question. What is original about your answer? I suggest you edit to make that clear. $\endgroup$
    – Sam Nead
    Aug 14, 2023 at 11:31
  • $\begingroup$ @Sam Nead: Thank you for the feedback! Added more details. $\endgroup$
    – orangeskid
    Aug 14, 2023 at 18:41
  • $\begingroup$ MathJax note: please use double stars **double stars**, not $\bf{TeX trickery}$ $\bf{TeX trickery}$, for boldface (and *single stars* for italics). I edited accordingly. $\endgroup$
    – LSpice
    Sep 28, 2023 at 4:02
1
2

Not the answer you're looking for? Browse other questions tagged or ask your own question.