137
$\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$
49
  • 34
    $\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 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 at 17:17
  • 13
    $\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 at 17:40
  • 8
    $\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 at 17:42
  • 10
    $\begingroup$ Usually the sign is used to show that the top exterior power is nonzero $\endgroup$ Mar 8 at 18:32

32 Answers 32

87
$\begingroup$

(This is a variant of Cartier's argument mentioned by Dan Ramras.)

Let $X$ be a finite set of size at least $2$. Let $E$ be the set of edges of the complete graph on $X$. The set $D$ of ways of directing those edges is a torsor under $\{\pm1\}^E$. Let $G$ be the kernel of the product homomorphism $\{\pm1\}^E \to \{\pm1\}$. Since $(\{\pm1\}^E:G)=2$, the set $D/G$ of $G$-orbits in $D$ has size $2$. The symmetric group $\operatorname{Sym}(X)$ acts on $X$, $D$, and $D/G$, so we get a homomorphism $\operatorname{Sym}(X) \to \operatorname{Sym}(D/G) \simeq \{\pm 1\}$. Each transposition $(ij)$ maps to $-1$ because if $d \in D$ has all edges at $i$ and $j$ outward except for the edge from $i$ to $j$, then $(ij)d$ equals $d$ except for the direction of the edge between $i$ and $j$.

$\endgroup$
41
  • 7
    $\begingroup$ I think this one is "the" answer. $\endgroup$ Mar 9 at 14:48
  • 36
    $\begingroup$ This has been an educational MO question for me, but I feel that I've learned more about mathematicians than about mathematics. Clearly, some other people's intuitions don't line up with my own, and I feel like I have to reverse engineer the mindset that makes certain arguments seem natural and others seem contrived. $\endgroup$ Mar 10 at 17:18
  • 12
    $\begingroup$ @HJRW Yes, I don't find it more natural. Roughly speaking, it gives an algebraic proof of what I consider to be a geometric fact. Nothing wrong with that, but I don't find it any more explanatory than, say, simply counting inversions. That $A_n$ is the group of rotations of a simplex is, to me, the explanation for its existence. $\endgroup$ Mar 11 at 13:58
  • 6
    $\begingroup$ @BjornPoonen I've mentioned this in other comments. Following Atiyah, I will accept the devil's offer to use algebra if you insist on a formal answer to your question. But in my soul I know that the true explanation for $A_n$ is geometric. Algebra is just there to silence the skeptics. (Again, I'm focusing on conceptual explanation rather than formal proof.) $\endgroup$ Mar 11 at 16:55
  • 14
    $\begingroup$ Even in 3 dimensions, capturing our geometric intuition of a rotation is formally difficult. The conventional approach requires us to construct the real numbers and describe continuous transformations that preserve the metric. But to me this does not imply that rotations in 3 dimensions are a complicated concept. It says more about the gap between our intuitive grasp of geometry and our ability to formalize it. $\endgroup$ Mar 11 at 17:06
71
$\begingroup$

This is obviously a subjective question, but I teach this in two phases

(1) I need to know this fact very early, so I give the quickest definition I know: $$\mathtt{sign}(\sigma) = \frac{\prod_{i<j} \left( x_{\sigma(i)} - x_{\sigma(j)} \right)}{\prod_{i<j} \left( x_i - x_j \right)}.$$ This makes it clear that $\texttt{sign}$ is well defined and is a group homomorphism, but does look rather like pulling a rabbit out of a hat. On the positive side, it is early practice in computing group actions on polynomials, which the students need any way.

But then, for motivation, a week or two later:

(2) I have students classify all group homomorphisms $\chi: S_n \to A$ where $A$ is abelian. Since $S_n$ is generated by transpositions, $\chi$ is determined by its value on transpositions. Since any two transpositions are conjugate, there must be one value $z$ which is $\chi((ij))$ for all $i$, $j$, since $(ij)^2=1$, we must have $z^2=1$. So either we have the trivial character, or else we can call $z$ by the name $-1$ and we have the sign character.

This explains why $\mathtt{sign}$ is inevitable — it is the only nontrivial character of $S_n$, so anyone mucking around with $S_n$ has to discover it.

As a bonus, the computation in part (2) can exactly be mimicked to show that $A_n$ has no nontrivial characters for $n \geq 5$: $A_n$ is generated by $3$-cycles, any character must take the $3$-cycles to cube roots of unity, but (for $n \geq 5$) every $3$-cycle is conjugate to its inverse, so in fact every character is trivial on the $3$-cycles.

$\endgroup$
17
  • 7
    $\begingroup$ Historically, I think (1) isn't just a rabbit from a hat—it connects up quite well with the idea of factoring the group determinant, which was the motivation for the original notion of a (possibly non-linear) group character. $\endgroup$
    – LSpice
    Mar 8 at 17:48
  • 10
    $\begingroup$ Agree with this second approach. The point is that the sign is the only miracle that can occur, that it actually does occur is still a bit of a miracle. $\endgroup$ Mar 8 at 23:53
  • 23
    $\begingroup$ Why not just $\prod_{i<j}(\sigma(i)-\sigma(j))/\prod_{i<j}(i-j)$? There is no need to introduce polynomials. $\endgroup$ Mar 9 at 15:26
  • 5
    $\begingroup$ It seems to me somewhat common in algebra that uniqueness can be proved in a clean way but existence requires getting one's hands dirty. The Lie group E8, the Monster group -- there was a gap between when the properties of the conjectural object were described (root system, character table) and when the object was proved to exist. Why shouldn't it be similar for homorphisms $S_n \to \mathbb{C}^{\ast}$? $\endgroup$ Mar 9 at 17:16
  • 5
    $\begingroup$ @NeilStrickland: With polynomials, it is easy prove that the map is a homomorphism, since $S_n$ acts on $\mathbb{Z}[x_1, \ldots, x_n]$. Using your suggestion, you need to show that the number of inversions mod $2$ defines a homomorphism $S_n \rightarrow \mathbb{Z}/2\mathbb{Z}$. Which is not that difficult but maybe not as slick. $\endgroup$
    – spin
    Mar 10 at 3:02
33
$\begingroup$

Draw a braid on $n$ strings sloppily, so that no three strings pass through the same point. Convince yourself that the parity of the number of crossings is the same in every other drawing of the same braid. (By looking at two of the strings.) Notice that composition of braids gives addition of the number of crossings.

$\endgroup$
1
  • 2
    $\begingroup$ This is my favorite way, as this count is essentially a geometric representation of the first cohomology of symmetric groups with Z/2 coefficients. The entire cohomology can be understood in similar terms! $\endgroup$
    – Dev Sinha
    Mar 16 at 0:12
23
$\begingroup$

Some years ago, Keith Dennis posted a nice discussion of signs of permutations on the Group-Pub-Forum mailing list, following some papers by Cartier. I gave it to my graduate algebra class as a series of exercises, which I'll copy below. Dennis also pointed out that Cartier used similar ideas to give alternate viewpoints on the group-theoretic transfer and on Legendre symbols. References to Cartier's papers follow.

The complete graph $K_n$ on $\{1, 2, 3, \dotsc, n\}$ is the graph with $n$ vertices and with an edge connecting every pair of distinct vertices. An orientation of $K_n$ is a choice of direction for each edge (formally, the edges are sets consisting of two distinct vertices, and an orientation just selects an ordering for each such set).
Note that we don't require any kind of compatibility between the orderings of different edges.

If $o$ and $o'$ are orientations of $K_n$, we define $m(o, o')$ to be the number of edges on which the orientations differ, and we set $d(o,o') = (-1)^{m(o,o')}$.

Prove the following statements:

a) $d(o,o')d(o',o'') = d(o,o'')$ for all orientations $o, o', o''$ of $K_n$;

b) The symmetric group $S_n$ acts on the set of orientations of $K_n$. Formally, if $o$ is an orientation in which the edge between $i$ and $j$ points from $i$ to $j$, then in the orientation $\sigma \cdot o$, the edge between $\sigma(i)$ and $\sigma(j)$ points from $\sigma(i)$ to $\sigma(j)$. Prove that this defines an action, and show that $d(o, \sigma\cdot o) = d(o', \sigma \cdot o')$ for all orientations $o, o'$ of $K_n$ and all $\sigma \in S_n$.

We can now define $\operatorname{sgn} (\sigma) = d(o, \sigma o)$.

c) Prove that $\operatorname{sgn}: S_n \rightarrow \{\pm1\}$ is a homomorphism.

d) Prove that $\operatorname{sgn} (\tau) = -1$ for every transposition $\tau$.

References:

  1. Zbl 0195.03101 Cartier, P. Remarques sur la signature d'une permutation (French) Enseign. Math., II. Sér. 16, 7-19 (1970).

  2. Zbl 0195.04001 Cartier, P. Sur une généralisation du transfert en théorie des groupes (French) Enseign. Math., II. Sér. 16, 49-57 (1970).

  3. Zbl 0195.05802 Cartier, P. Sur une généralisation des symboles de Legendre–Jacobi (French) Enseign. Math., II. Sér. 16, 31-48 (1970).

$\endgroup$
12
  • 1
    $\begingroup$ I hope you don't mind that I changed the target of $\operatorname{sgn}$ from $\mathbb Z/2\mathbb Z$ to $\{\pm1\}$. To get a $\mathbb Z/2\mathbb Z$-valued map, I think you'd want just to define $\operatorname{sgn}(\sigma) = m(o, \sigma\cdot o)$. $\endgroup$
    – LSpice
    Mar 9 at 2:53
  • 1
    $\begingroup$ @LSpice Thanks for the correction (I just updated my old problem set too...). I don't see how to match this up with inversions. The number of inversions in a permutation is a fixed number, but the number $m(o, \sigma o)$ depends on $o$ (of course the point is that changing $m(o, \sigma o)$ is equivalent to $m(o', \sigma o')$ (mod 2) for any two orientations $o$ and $o'$). But maybe you have something in mind to connect orientations and inversions that I'm not thinking of at the moment. $\endgroup$
    – Dan Ramras
    Mar 9 at 4:44
  • 2
    $\begingroup$ Thanks, this proof is very nice! It's related to the proof I used in my class. The proof I used differs in that there one picks a favorite orientation $o_{std}$ (in practice, one does this using the linear ordering on $\{1,\dots,n\}$), and defines $sgn(\sigma) = m(o_{std}, \sigma \cdot o_{std})$, then verifies directly that $sgn(\sigma \cdot \tau) = sgn(\sigma) \cdot sgn(\tau)$. This amounts to the same work as your (a) + (b), but by separating them out like this, the proof you're describing looks much more natural! $\endgroup$
    – Tim Campion
    Mar 9 at 14:48
  • 1
    $\begingroup$ Douady and Douady give this argument in Algebre and Theories Galiosienne but instead of talking about orientations they talk about choice functions which select one element from each ordered pair. The action then becomes on functions and so which might be easier $\endgroup$ Mar 9 at 15:56
  • 1
    $\begingroup$ @LSpice Ok, I see. Maybe this is like a "coordinate-free" version of the inversion argument. I'll note that part a) is useful in the later steps, i.e. it's helpful, at least conceptually and notationally, to consider orientations other than the standard one. $\endgroup$
    – Dan Ramras
    Mar 9 at 20:48
22
$\begingroup$

This is an elaboration of Will Brian's comment. As I understand it, the goal isn't to find the simplest possible proof or a proof that is most palatable to students; the goal is to make things seem "inevitable" or "not miraculous." To achieve this goal, I think it is best to view $A_n$ as an entity in its own right, rather than start with $S_n$ and then try to extricate $A_n$ from $S_n$. Rotations of a simplex provide a natural realization of $A_n$. We can build a group of order $n!/2$ inductively, by starting with $n=3$ (rotations of a triangle) and multiplying by $n$ at each step.

Once you've constructed $A_n$, then you can construct $S_n$ as the group of "signed rotations," which has twice as many elements. The "miracle" now is that there exists such an extension of $A_n$, but that presumably seems less miraculous.

$\endgroup$
10
  • 2
    $\begingroup$ Is it clear that you can define what it means for a permutation of the vertices of a simplex to be orientation-preserving (in other words, what a "rotation" of the simplex is) without an appeal to the notion of sign of a permutation (or something similar like a determinant)? $\endgroup$ Mar 9 at 3:44
  • 8
    $\begingroup$ @SamHopkins I'm not claiming that one can construct a formal proof without ever introducing the concept of the sign of a permutation. What I'm suggesting is that one's geometric intuition suggests that there is a group of order $n!/2$ since this is obvious for $n=3$ and $n=4$, and one does not expect this pattern to suddenly break down for some larger value of $n$. It isn't a miracle that the obvious conjecture is true; it would be a miracle if it weren't. That converting geometric intuition into formal proofs might require some machinery doesn't mean that there's a deep fact involved. $\endgroup$ Mar 9 at 4:02
  • 4
    $\begingroup$ If our minds worked slightly differently, then the inductive nature of passing from rotations in $n$-space to $(n+1)$-space might seem more obvious than the inductive nature of syntactic objects. That we feel the need to represent a rotation of a simplex using (say) a linear ordering of labels attached to the vertices says more about what we feel a rigorous proof is than what things are inevitably true. By contrast, the sporadic simple groups seem like genuine miracles. $\endgroup$ Mar 9 at 4:13
  • 3
    $\begingroup$ "What I'm suggesting is that one's geometric intuition suggests that there is a group of order $n!/2$ since this is obvious for $n=3$ and $n=4$, and one does not expect this pattern to suddenly break down for some larger value of $n$." I was trying to think of how I would respond to the obvious question of "Why not, since there are many examples of patterns in geometry that break in high enough dimensions?" I suppose it boils down to the fact that $n$-simplices are primitive enough(?). $\endgroup$ Mar 11 at 22:58
  • 5
    $\begingroup$ @TimothyChow: I’m with PaceNielsen here. There are many examples in geometry of sporadic, low-complexity examples that don’t extend to higher dimensions. $\endgroup$
    – HJRW
    Mar 12 at 11:02
19
$\begingroup$

A fun answer: You would not be able to ask this question otherwise : No fermions and no stable matter in our Universe.

$\endgroup$
2
  • 9
    $\begingroup$ Proof by the anthropic principle :D $\endgroup$ Mar 9 at 13:42
  • 29
    $\begingroup$ Well, this is a proof that there is a homomorphism $S_n \to \{ \pm 1 \}$ for $n$ less than the number of particles in the universe :). $\endgroup$ Mar 9 at 17:18
16
$\begingroup$

Fun question!

I encountered a similar pedagogical problem when I wrote the article "The Grassmann–Berezin calculus and theorems of the matrix-tree type" about Grassmann/Fermionic variables. This could be item 7 in the OP's list.

Let $\xi_1,\dotsc,\xi_n$ be formal variables or symbols. Let $R$ be a commutative ring with unit which contains $\mathbb{Q}$. Consider $R\langle\xi_1,\dotsc,x_n\rangle$ the free noncommutative $R$-algebra generated by the symbols $\xi$, namely formal $R$-linear combinations of words in the symbols $\xi$ with concatenation as a product. Let $I$ be the two sided ideal generated by the elements $\xi_i\xi_j+\xi_j\xi_i$ for all $i$, $j$ (not necessarily distinct). Finally consider the quotient algebra $R[\xi_1,\dotsc,\xi_n]=R\langle\xi_1,\dotsc,x_n\rangle/I$. It is trivial to see that the $2^n$ monomials $\xi_{i_1}\dotsm\xi_{i_k}$, with $0\le k\le n$ and $1\le i_1<\dotsb<i_k\le n$, $R$-linearly generate $R[\xi_1,\dotsc,\xi_n]$. However, one needs a little bit of work to show linear independence. Once this is done, then one can define the sign of a permutation $\sigma$ as the coefficient of $\xi_{\sigma(1)}\dotsm\xi_{\sigma(n)}$ with respect to the basis element $\xi_1\dotsm\xi_n$.

I had a fun proof of this linear independence while pretending not knowing anything about determinants, exterior algebra, etc. I don't remember it perfectly but the key fact was that if one makes a graph with vertices corresponding to all words in the $\xi$'s of a fixed length and putting an edge when two words differ by switching two consecutive $\xi$'s, then this graph is bipartite.

Variant: (with topology?)

When teaching linear algebra, I often define the sign of a permutation as follows. Represent the permutation $\sigma$ as a bunch of left to right arrows between two columns representing two copies of the set $\{1,\ldots,n\}$, then let $c(\sigma)$ be number of crossings between arrows. Now if $\tau$ is another permutation, draw the analogous diagram for $\tau$ immediately to the right of sigma, as a continuation. Then I explain that $c(\tau\circ\sigma)-c(\tau)-c(\sigma)$ is even. Suppose arrows are made of rubber strings and that they are pinned in the middle where the two permutations are connected. Upon release the elastic strings straighten, but when doing so crossings always disappear in pairs. Of course once this is clear, one immediately has a homomorphism $\sigma\mapsto (-1)^{c(\sigma)}$.

$\endgroup$
8
  • 1
    $\begingroup$ I changed your link direct to ScienceDirect to a DOI link. I hope you don't mind. $\endgroup$
    – LSpice
    Mar 8 at 18:21
  • 1
    $\begingroup$ Is it for more robust referencing? Thanks for fixing the xi typo also. $\endgroup$ Mar 8 at 18:22
  • 1
    $\begingroup$ By the way, @TheoJohnson-Freyd also mentioned the (pseudo-)topological proof you reference. $\endgroup$
    – LSpice
    Mar 8 at 19:06
  • 1
    $\begingroup$ @LSpice: you're right, I didn't see Theo's comment. $\endgroup$ Mar 8 at 20:35
  • 1
    $\begingroup$ Yes, that's what I meant (see also arxiv.org/abs/1303.5366 for more advanced strategies). $\endgroup$ Mar 9 at 16:50
15
$\begingroup$

This argument is not drastically different from some of the other answers, but I'm going to write it down for the record. It is a kind of unbiased version of the inversion counting argument and can also be seen as a simplification of the argument via the action on the set of orientations of the complete graph.

Let $X$ be a finite set with at least $2$ elements and let $T_X$ be the set of total orders on $X$. Consider the following relation $\sim$ on $T_X$: two orders are equivalent if the number of $2$-element subsets of $X$ on which they disagree is even. Check that this is an equivalence relation with exactly two equivalence classes. The symmetric group $\Sigma_X$ acts on $T_X$ and respects $\sim$. Thus $\Sigma_X$ acts on the $2$-element set $T_X / \sim$ and any transposition acts non-trivially. It follows that $\Sigma_X \to \Sigma_{T_X / \sim}$ is a surjective homomorphism.

$\endgroup$
6
  • $\begingroup$ This could be viewed as a variant of @DanRamras's Cartier-inspired answer using orientations on $K_n$, where we use only 'compatible' orientations (those respecting a total order). $\endgroup$
    – LSpice
    Mar 9 at 22:54
  • 2
    $\begingroup$ Yes, I have noted that. I even dared to say that it is a simplification of that argument since I find it easier to think about the set of total orders as opposed to the set of all orientations. $\endgroup$ Mar 10 at 14:42
  • $\begingroup$ I like this answer as it builds a bridge between two other answers I read earlier, clarifying them both: the accepted answer linked to in the first comment on this answer and Wilberd van der Kallen's answer using braids. $\endgroup$
    – Vincent
    Mar 14 at 10:41
  • 1
    $\begingroup$ I think that from a pedagogical standpoint, this is my favorite answer. Every time I think about the action of the symmetric group on orientations, I feel slightly worried I'm getting it wrong, and when I gave the exercises in my answer to students, they got stuck on exactly this point. On the other hand, I find the action of the symmetric group on total orders very simple to think about; it "feels" just like the action on {1, ..., n}. So I definitely agree with @KarolSzumiło that this is a welcome simplification. $\endgroup$
    – Dan Ramras
    Mar 15 at 21:02
  • 1
    $\begingroup$ @DanRamras That's my thinking exactly. When I was trying to understand the action on the set of orientations, I wrote it down wrong at first. Working out my mistake is what led me to notice that it seems simpler when we restrict attention to total orders. $\endgroup$ Mar 17 at 9:04
13
$\begingroup$

There are already plenty of other great answers, but I figured I might as well give my own.

My approach is to introduce students to permutations by taking plastic cups that have large numbers on them, say consecutively numbered from $1$ to $8$, and then move them around (like in a "3 cup Monte" exhibition) in a random fashion, and end up with a permutation of them. For concreteness, let's say that the cups end up in the order $$ \begin{matrix}3 & 5 & 2 & 1 & 4 & 7 & 6 &8\end{matrix}. $$ We will focus on this permutation for the rest of the explanation.

Now, it is easy to show students that this permutation can easily be obtained by transpositions. But it is in fact easy to show them that this permutation is obtained by transpositions where the entries of the transposition are consecutive numbers $(i\ i+1)$, which we will call swaps.

For instance, starting with $$ \begin{matrix}1 & 2& 3 & 4& 5& 6& 7 &8\end{matrix} $$ we can first push cup $3$ past cup $2$, and then past cup $1$ to get $$ \begin{matrix}3 & 1& 2& 4& 5& 6& 7 &8\end{matrix}, $$ so cup $3$ is in the correct position. Next, we push cup $5$ past $4$, then $2$, then $1$, to get $$ \begin{matrix}3 & 5 & 1 & 2 & 4 & 6 & 7 &8\end{matrix}, $$ so now both cup $3$ and cup $5$ are in the correct positions. Continuing in this way, we can get all the cups in the correct positions using just swaps. We might call this the "left-swap" algorithm. The total number of swaps needed to reach the final position (for this permutation) is seven.

Next, it is easy to explain why this algorithm gets the cups into position in the fewest possible swaps. Notice that no matter which way we swap the cups, eventually cups $3$ and $2$ will have to swap sides from one another, as will $3$ and $1$. So, each of those swaps was inevitable. Indeed, all of the swaps in the "left-swap" algorithm are inevitable.

However, it is important to point out to the students that the order of the swaps was not inevitable. Indeed, we could have performed a symmetrically defined "right-swap" algorithm, also in seven moves.

Now, the key point to proving that the sign function is a group homomorphism really boils down to the fact that if we add one more swap, such as swapping cups $4$ and $7$ to get the new line-up $$ \begin{matrix}3 & 5& 2& 1& 7 & 4& 6 &8 \end{matrix}, $$ then the minimum number of swaps needed to reach this new permutation has changed by one. (In other words, the parity of the minimum number of swaps has changed.)

Here is the easy idea of the proof. First note that the "left-swap" algorithm in both cases begins by making exactly the same swaps for the cups $3,5,2,1$. So, we might as well ignore those cups, and show that the minimum number of swaps going from $$ \begin{matrix}4 & 6 & 7 &8 \end{matrix} $$ to $$ \begin{matrix}4 & 7 & 6 &8 \end{matrix} $$ is one different than the minimum number of swaps when instead going to $$ \begin{matrix}7 & 4 & 6 &8\end{matrix}. $$ But now, using the "right-swap" algorithm, we can also ignore cups $6$ and $8$. So, it really boils down to the fact that in the first case we didn't need to swap $4$ and $7$, but in the second case we did. So in this case, the minimum number of swaps increases by one. (Of course, if we had chosen different cups to swap, it might have had the opposite effect, so that there was one less swap needed.)


There are some other reasons I really like this "cup" approach. It makes it easy to explain Cayley's theorem, and other "renaming" theorems. If you use another eight cups labelled $1,r,r^2, r^3,s,rs,r^2s,r^3s$, then you can explain how $D_8$ acts on the cups, and gives a permutation representation in $S_8$. Just put the new cups on top of the original cups, and see that they also get permuted, then take the new cups off and see how the old numbers were permuted. Of course, this cup method shouldn't be used exclusively, as sometimes it is hard for people to think visually. In fact, I think it is most helpful after they already know that permutations are products of transpositions.

$\endgroup$
2
  • 1
    $\begingroup$ Such a simple and effective explanation, really good $\endgroup$
    – seldon
    Mar 18 at 9:34
  • $\begingroup$ Thank you for taking the time out to break down your steps and thought process without skipping steps! Your details are much appreciated $\endgroup$
    – Xoque55
    Mar 26 at 22:33
13
$\begingroup$

Obviously, there are lots of answers already, but I thought I'd give the proof of (5) as given by Jordan already in 1870 in his Traité des substitutions -- this has the benefit of being quite clear to read, and cuts directly into the "conceptual".

The following is my translation of his Theorem 77, its proof, and the paragraph above it (pp. 64--65), with some update of the words used (e.g. permutation instead of "substitution"):

A cycle on $p$ letters $a, b, c, \dots$ is clearly the product of the $p-1$ transpositions $(ab), (ac), \dots$. Hence an arbitrary permutation on $k$ letters and containing $n$ cycles is the product of $k-n$ transpositions.

Theorem: Let $S, T$ be two permutations which are respectively the product of $\alpha$ and $\beta$ transpositions. The number of successive transpositions in the product $ST$ is even or odd, according as to whether $\alpha + \beta$ is even or odd.

Proof: As any permutation is the product of transpositions, it suffices to show the theorem when $T$ is a transposition, in which case $\beta = 1$.

To make the idea clear, let $S = (abcde)(fg)$. If $T$ transposes two letters which appear in the same cycle, such as $a$ and $c$, then we have $$ ST = (ab)(cde)(fg), $$ which is a permutation containing one cycle more than $S$, and which, accordingly, is a product of $\alpha-1$ transpositions. If on the other hand $T$ transposes two letters $a, f$ appearing in different cycles, then $ST=(abcdefg)$ will contain one cycle less than $S$, and will hence be the product of $\alpha+1$ transpositions. In either case, the number of transpositions in the product $ST$ will be congruent to $\alpha + 1 \pmod 2$.

I think this counts more as the "traditional" proof than the determinant-proof, as it appears in the first book on group theory ever published :-) Of course, it does fall into "Using a decomposition into disjoint cycles, one can simply compute what happens when multiplying by a transposition", but it doesn't strike me as magic (and I don't think it struck Jordan as magic either!)

$\endgroup$
2
  • $\begingroup$ I guess this is the first proof of this result, since Galois didn't work with alternating groups. A more verbose/modern/student-friendly version of Jordan's proof is in Rotman, "An Introduction to the Theory of Groups", pp. 7-9. $\endgroup$
    – spin
    Mar 11 at 4:41
  • 1
    $\begingroup$ I think that this proof becomes clearer if you draw a picture of a cycle and how it breaks in two when multiplied by a transposition, and also how two cycles get joined when their product is multiplied by a transposition. $\endgroup$
    – Ben McKay
    Mar 11 at 16:40
10
$\begingroup$

The symmetric group can be thought of as automorphisms of the boundary of $n$-simplex, and whether the permutation is even depends on whether it reverses orientation, as others have pointed out. The boundary of the $n$-simplex can be thought of as the ($n-1$)-dimensional sphere up to homotopy equivalence. And so the result would follow from the fact that there are two connected components of the space of automorphisms of spheres with $n$ at least $2$.

Edit: Now I guess I would like to address the issue that perhaps it is not clear automorphisms of the sphere fall in two components. Here I propose an intuition which is not necessarily elementary. I propose to think of the automorphisms of the sphere inducing automorphisms of the sphere spectrum. Then accepting that the sphere spectrum discretized looks like the integers; I would claim that this gives an intuition that the automorphisms fall in two components using the fact that the integers only has two automorphisms as a group.

$\endgroup$
2
  • $\begingroup$ As you say, others have pointed this out (notably @WillBrian and, in reference to orthogonal groups, @TheoJohnson-Freyd), and the questioner has indicated (1 2) that this approach is not yet satisfactory to them. $\endgroup$
    – LSpice
    Mar 9 at 19:36
  • 1
    $\begingroup$ Ah yes i didn't read all the comments carefully sorry. Then this answer contains nothing more than the comment of @Theo $\endgroup$
    – davik
    Mar 9 at 19:47
9
$\begingroup$

This answer grew out of an attempt to understand the polynomial product formula in David Speyer's answer (also Theo Johnson-Freyd's comment). It has been superseded by Bjorn Poonen's excellent self-contained answer.

If $T$ is a totally ordered set of $n$ elements, the product in Speyer's answer is defined in terms of the section to $$T^2 \setminus \Delta_T \to {T \choose 2}$$ taking $S \subseteq T$ to $(\min(S),\max(S))$, but clearly does not depend on the choice of this section (swapping a pair of indices induces a $-1$ on the top and bottom). This is reminiscent of a norm or corestriction in group cohomology. An earlier version of my answer worked this out in a more general setting using cocycles and crossed homomorphisms, but thanks to Poonen's answer and Benjamin Steinberg's comment, I can now do this without using cocycles.

If $S$ and $T$ are finite sets, then $S(T) \times S(S)$ acts on $X = \operatorname{Inj}(S,T)$ by post- and precomposition. The action of $S(S)$ is free since injections are monic, and we denote the quotient $X/S(S)$ by $Y={T \choose S}$. Concretely, we want $\lvert S\rvert = 2$ and $\lvert T \rvert = n$ to get $S_n \times S_2$ acting on $\operatorname{Inj}(2,T) \cong T^2 \setminus \Delta_T$. This is an example of the following more general object:

Setup. Let $G$ and $A$ be groups (eventually $A$ will be abelian), let $X$ be a set with a $(G \times A)$-action such that the $A$-action is free, and set $Y = X/A$. Equivalently, $\pi \colon X \to Y$ is a $G$-equivariant $A$-torsor, in the sense that $\pi$ is a $G$-equivariant map of $G$-sets such that \begin{align*} \mu \colon A \times X &\to X \underset Y\times X \\ (a,x) &\mapsto (ax,x) \end{align*} is a $G$-equivariant bijection, where $G$ acts trivially on $A$. In other words, this is an $\underline{A}$-torsor on the slice category $G\text{-}\mathbf{Set}/Y$, where $\underline{A}$ is the 'constant object' on $A$ (the pullback of $A$ from the terminal Grothendieck topos $\mathbf{Set}$).

The internal hom $\mathbf{Hom}_Y(Y,{-}) \colon G\text{-}\mathbf{Set}/Y \to G\text{-}\mathbf{Set}$ preserves limits, so takes the above to the $A^Y$-torsor $\mathbf{Hom}_Y(Y,X)$ of sections to $\pi$ (this is the torsor in Poonen's answer). Here, $A^Y$ is no longer a constant object: it has a natural $G$-action. Such a torsor corresponds to an element $\phi \in H^1(G,A^Y)$ (nonabelian cohomology, although we will now assume $A$ is abelian), i.e. a crossed homomorphism $\phi \colon G \to A^Y$. Given a section $s \colon Y \to X$ of $\pi$, the crossed homomorphism $\phi \colon G \to A^Y$ can be computed via the composition $$\begin{array}{ccccccc}G & \to & X \underset Y\times X & \stackrel\sim\leftarrow & A \times X & \stackrel{\pi_1}\to & A \\ g & \mapsto & (gs(y),s(gy)).\! & & & & \end{array}$$ In other words, $\phi(g)(y)$ is the unique $a \in A$ such that $gs(y) = as(gy)$. Different choices of section give crossed homomorphisms that differ by a principal crossed homomorphism.

If $A$ is abelian and $Y$ finite, then there is a ($G$-equivariant) multiplication map $\Pi \colon A^Y \to A$, giving a map $H^1(\Pi) \colon H^1(G,A^Y) \to H^1(G,A)$. Since the $G$-action on $A$ is trivial, this is just $\operatorname{Hom}(G,A)$, so $H^1(\Pi)(\phi)$ is a homomorphism $G \to A$.

In the case of $S_n \times S_2$ $\style{display: inline-block; transform: rotate(90deg)}{\circlearrowright}$ $\!\operatorname{Inj}(2,n)$, this gives a homomorphism $S_n \to S_2$. Given a section $s \colon {T \choose 2} \to T^2 \setminus \Delta_T$, write $s_1, s_2 \colon {T \choose 2} \to T$ for the projections $\pi_i \circ s$. Then the crossed homomorphism $\phi \colon S_n \to \{\pm 1\}^{T \choose 2}$ can be identified with $$\phi(\sigma)(S) = \frac{x_{\sigma(s_1(S))}-x_{\sigma(s_2(S))}}{x_{s_1(\sigma(S))}-x_{s_2(\sigma(S))}}.$$ Taking the product over all $S \in {T \choose 2}$ recovers the formula in Speyer's answer when $s$ is given by $S \mapsto (\min(S),\max(S))$.

Remark. One thing I still find weird about this is that it almost works to give a homomorphism $S_n \to S_3$ as well, by taking $\operatorname{Inj}(3,n)$ instead of $\operatorname{Inj}(2,n)$. It somehow only fails because $S_3$ is not abelian. Replacing $S_3$ by its subgroup $C_3$ does give a homomorphism $S_n \to C_3$, which presumably is trivial. But somehow for $C_2 = S_2$ the map is nontrivial!


Relation to corestriction.

If the $G$-action on $Y$ is transitive, then choosing a point $y \in Y$ gives an isomorphism $G/H \stackrel\sim\to Y$ of $G$-sets, where $H = \operatorname{Stab}_G(y)$. Left Kan extension \begin{align*} H\text{-}\mathbf{Set} &\to G\text{-}\mathbf{Set} \\ Z &\mapsto (G \times Z)/H \cong \coprod_{G/H} Z \end{align*} identifies $H\text{-}\mathbf{Set}$ with the slice topos $G\text{-}\mathbf{Set}/Y$, and $A^Y$ is the coinduction of the trivial $H$-module $A$. For $\lvert Y\rvert = [G:H]$ finite, this is also the induction, so Shapiro's lemma says that $$H^1(G,A^Y) \cong H^1(H,A) = \operatorname{Hom}(H,A).$$ The map $H^1(H,A) \to H^1(G,A)$ in this case is called corestriction.

The homomorphism $H \to A$ can be deduced immediately from the Setup: if $x \in X$ is a lift of $y$, then $$\operatorname{Stab}_{G \times A}(x) \to \operatorname{Stab}_G(y) = H$$ is an isomorphism, so its inverse gives a projection $H \to A$. In our main example, the point $\{1,2\} \in {T \choose 2}$ has stabiliser $H = S_2 \times S_{n-2} \subseteq S_n$, and the above shows that the sign $S_n \to S_2$ is the corestriction of the projection $H \to S_2$.

$\endgroup$
5
  • $\begingroup$ The approach described by @DavidE.Speyer was earlier mentioned by @‍TheoJohnson-Freyd in the comments. $\endgroup$
    – LSpice
    Mar 9 at 1:54
  • 1
    $\begingroup$ @LSpice Thanks for the call-out, but David gives many more details. And I assume it is what Tim had in mind with his rejection of things about polynomials. $\endgroup$ Mar 9 at 12:38
  • 1
    $\begingroup$ If you view $f$ as a map $G\to A^Y$ via currying, and you view $A^Y$ as a $G$-module in the obvious way (when $A$ is abelian) then you do have a crossed homomorphism. This is is what is used in my write up using wreath products. Then the $G$-module homomorphism $A^Y\to A$ which sends $f$ to $\prod_{y\in Y}f(y)$ is a $G$-module homomorphism where $A$ is a trivial $G$-module and so gives a homomorphism $H^1(G,A^Y)\to H^1(G,A)$ that is your homomorphism. $\endgroup$ Mar 10 at 18:43
  • $\begingroup$ @BenjaminSteinberg oh much better. That's also closer to Poonen's answer, where $A^Y$ and the multiplication map $A^Y \to A$ are the key players. $\endgroup$ Mar 10 at 20:07
  • $\begingroup$ I made it a new CW answer but I think it is basically the same as yours. $A^Y$ just got hidden in your proof because you didn't curry. $\endgroup$ Mar 10 at 20:13
9
$\begingroup$

$\DeclareMathOperator\sgn{sgn}$How about arguing by induction? I claim that there is a homomorphism map $\sgn_n : \Sigma_n \to \{\pm1\}$ that takes the value $-1$ at every transposition. This is vacuously true for $n = 0$ and $n = 1$.

In general, suppose that $n$ is greater than $1$ and we have such a map $\sgn_{n - 1}$ on $\Sigma_{n - 1}$.

Let $\tau$ be the transposition that swaps $n$ and $n - 1$. Since $\Sigma_n$ equals $\Sigma_{n - 1} \sqcup \Sigma_{n - 1}\tau\Sigma_{n - 1}$, and since two elements of $\Sigma_{n - 1}$ that are conjugate by $\tau$ are already conjugate in $\Sigma_{n - 1}$ (so that $\sgn_{n - 1}$ agrees on them), there is a unique function $\sgn_n : \Sigma_n \to \{\pm1\}$ that transforms by $\sgn_{n - 1}$ under left and right translation by $\Sigma_{n - 1}$, and that takes the value $1$ at $1$ and $-1$ at $\tau$. Since all transpositions that move $n$ are conjugate under $\Sigma_{n - 1}$, the map $\sgn_n$ is independent of the choice of $\tau$.

I originally thought that it was obvious that $\sgn_n$ was a homomorphism, and said:

It's hard to imagine your, or anyone's, liking this argument better than the one proposed by @TheoJohnsonFreyd in the comments or by @DavidESpeyer in the answers, but I think it doesn't violate any of your interdicts.

… but now I see that some computation has to be done, which was at least tacitly ruled out. Oh well!

It is clear that $\sgn_n(\sigma)^{-1}\sgn_n(\sigma\bullet)$ equals $\sgn_n$ for all $\sigma \in \Sigma_{n - 1}$; and that $\sgn_n(\tau)^{-1}\sgn_n(\tau\bullet)$ equals $1$ at $1$ and $-1$ at $\tau$, and transforms by $\sgn_{n - 1}$ under left translation by $\Sigma_{n - 2}$ and right translation by $\Sigma_{n - 1}$. It thus remains only to show that $\sgn_n(\tau)^{-1}\sgn_n(\tau\bullet)$ agrees with $\sgn_n$ at every element of the form $\sigma\tau$, where $\sigma \in \Sigma_{n - 1}$ is a transposition that moves $n - 1$. The braid relations—mentioned in one of your bullet points as a possible acceptable line of attack—say that $\tau\sigma\tau$ equals $\sigma\tau\sigma$. Thus, $\sgn_n(\tau)^{-1}\sgn_n(\tau\sigma\tau)$ equals $-\sgn_n(\sigma\tau\sigma) = \sgn_{n - 1}(\sigma)\sgn_{n - 1}(\sigma)\sgn_n(\tau)\sgn_{n - 1}(\sigma) = \sgn_n(\sigma\tau)$.

$\endgroup$
4
  • $\begingroup$ As is probably obvious, this is clumsily inspired by the Hopf-algebra approach to the representation theory of the symmetric groups. $\endgroup$
    – LSpice
    Mar 8 at 18:22
  • 3
    $\begingroup$ Extending your comment: the involution that sends a Schur function $s_{\lambda}$ to $s_{\lambda^t}$ -- and hence the trivial representation to the sign representation -- is (essentially: maybe there's a sign) the antipode in the Hopf algebra of symmetric functions. I wonder if this observation could somehow be used to prove the existence of the sign representation. $\endgroup$ Mar 8 at 19:06
  • $\begingroup$ @SamHopkins, that would be very appealing! If you figure it out, then I hope you'll post it as an answer! $\endgroup$
    – LSpice
    Mar 8 at 22:57
  • $\begingroup$ @Vincent, thank you for fixing my typo. $\endgroup$
    – LSpice
    Mar 16 at 17:38
8
$\begingroup$

The following framing of statement 4 from the list of equivalent statements allows you to shift what I presume is the "not-terrible computation" to another place:

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

A swap here is a transposition of the form $(i\; (i+1))$.

Proof of 4': In any ordering of $1,2,\ldots, n$, if you swap the two integers at positions $i$ and $i+1$, it changes the number of inversions by exactly $1$, since only the relative order between the integers at those positions is affected. (An inversion is a pair $(a,b)$ with $a>b$.) If we start with the list in order and apply an odd number of swaps, we thus end up with an odd number of inversions. But the identity permutation has 0 inversions. $\Box$

The 'conceptual reason,' then: a swap changes 'how wrong' an ordering is by exactly $1$, and so we can't use an odd number of them on $1,2,\ldots,n$ in order to get back to having $0$ pairs in the wrong order.

That 4 and 4' are equivalent follows from the fact that any transposition $(ij)$ can be written as a product of an odd number of swaps. You can write this down explicitly: $(ij) = \cdots((i+1)\;(i+2))\; (i\; (i+1))$ (if $i<j$). Or you can maybe see it intuitively: move $i$ over to $j$ by swaps, and then move $j$ to where $i$ was, which needs $1$ fewer moves since it's already been shifted once. In any case, this is where the computation is. But maybe this is a preferable place to have it.

$\endgroup$
7
$\begingroup$

For my taste, an accidentally discovered proof of the well-definedness of "parity of number adjacent transpositions to express a permutation" can arise in attempting to clarify/simplify proofs about (not only spherical and affine) buildings acted upon by naturally-arising groups (especially "classical groups").

The critical point can be expressed in orthodox terms: that the length $\ell(s\cdot w)$ of $s\cdot w$, in a Coxeter group $W$ with specified reflexion-generators $S$, with $w\in W$ and $s\in S$, is $\ell(w)\pm 1$. Never $\ell(w)$ again. In particular, the parity flips, exactly.

Some orthodox treatments of this are unsatisfying to me, because they presume combinatorial things exactly like proving that permutations have well-defined parities.

Likewise, some developments of "buildings" depend crucially on developing lots of combinatorial theory of Coxeter groups first.

On another hand, a theorem of J. Tits showed that the automorphism groups of apartments in "thick" buildings are Coxeter groups. That is, the apartments are Coxeter complexes...

The argument for that is not trivial, but it does have more of the geometric/conceptual flavor that one might like. After studying the orthodox version for a while, a few years ago I realized that the same sort of "geometric" building-theoretic arguments could prove that crucial $\ell(s\cdot w)=\ell(w)\pm 1$ property directly. See http://www.math.umn.edu/~garrett/m/v/bldgs.pdf for a self-contained discussion of this and other corollaries of a somewhat stubbornly-impatient attitude about it (also, similarly, refined aspects of Bruhat decompositions...)

... oop, and forgot to mention that realizing permutation groups as the apartment automorphism groups for the (thick) building constructed from subspaces of a vectorspace over a field is pretty easy.

$\endgroup$
7
$\begingroup$

Is the inversion counting argument really so magical? Let me write it out and you can point out which step seems unmotivated.

An unordered pair $\{i,j\}$ is an inversion of $\sigma$ if $\sigma(i)$ and $\sigma(j)$ are ordered in the opposite manner to $i$ and $j$. Thinking of computing $\{\pi(\sigma(i)), \pi(\sigma(j))\}$ in two steps, namely $\{i,j\} \mapsto \{\sigma(i), \sigma(j)\} \mapsto \{\pi(\sigma(i)), \pi(\sigma(j))\}$, we see the following equivalence which I claim is really the heart of the matter:

$\{i,j\}$ is an inversion of $\pi \circ \sigma$ if and only if exactly one the following statements is true:

  • $\{i,j\}$ is an inversion of $\sigma$.
  • $\{\sigma(i), \sigma(j)\}$ is an inversion of $\pi$.

This means that the set of inversions $I(\sigma)$ satisfies $I(\pi \circ \sigma) = I(\sigma) \mathbin\triangle \sigma^{-1}(I(\pi))$, where $\triangle$ denotes symmetric difference. Then taking parities of cardinalities, we get that $\#I : S_n \to \mathbb{Z}/2$ is a homomorphism.

$\endgroup$
0
6
$\begingroup$

There are already enough answers but here is a rewrite of Poonen's and De Bruyn's answer in the language of wreath products.

Let $A$ be a group acting freely on the right of a finite set $X$. Then $\mathrm{Aut}_A(X)$ is well known to be isomorphic to the permutational wreath product $A\wr \mathrm{Sym}(X/A)=A^{X/A}\rtimes \mathrm{Sym}(X/A)$. The isomorphism depends on choosing a transversal for $X/A$ but any two isomorphisms are conjugate by an element of $A^{X/A}$. In concrete terms, choose a section $t\colon X/A\to X$ and send $f\in \mathrm{Aut}_A(X)$ to $(F,f')$ where $f'$ is the permutation of $X/A$ induced by $f$ and $F\colon X/A\to A$ is defined on $e\in X/A$ by $f(t(e))=t(f'(e))F(e)$. If $t'\colon X/A\to X$ is another section, then there is $h\in A^{X/A}$ such that $t'(e)=t(e)h(e)$ for all $e\in X/A$ and the isomorphism constructed from $t'$ is conjugate to the one constructed from $t$ by $(h,1)\in A\wr \mathrm{Sym}(X/A)$. I didn't give the inverse of the isomorphism because it is not needed to construct the sign map.

In the case $A$ is abelian, there is a homomorphism $\tau_0\colon A^{X/A}\rtimes \mathrm{Sym}(X/A)\to A$ given by $(f,\sigma)\mapsto \prod_{e\in X/A}f(e)$ (sometimes called the transfer map). This gives a homomorphism $\tau\colon \mathrm{Aut}_A(X)\to A$ which is independent of the isomorphism constructed above since isomorphisms coming from different sections (i.e. transversals) differ by an inner automorphism and $A$ is abelian.

Now consider the group $A=C_2$ (the two element cyclic group) and consider the set $E$ of distinct pairs of elements from $[n]=\{1,\ldots, n\}$. Then $C_2$ acts freely on the right of $E$ by having the nontrivial element switching the coordinates and the action of $S_n$ on $E$ commutes with this. We then the composed homomorphism $S_n\to \mathrm{Aut}_{C_2}(E)\xrightarrow{\,\tau\,} C_2$.

As usual we just then need to check the transposition $(1,2)$ is sent to the nontrivial element of $C_2$, but this follows easily if you choose as your transversal the ordered pairs $(i,j)$ with $i<j$ and follow through the construction.

$\endgroup$
6
$\begingroup$

Not the most pedagogical, but I think this counts as "conceptual": it comes down to the fact that a hyperplane separates space into exactly two components.

As has been pointed out in many previous answers, we can get the $\operatorname{sgn}$ homomorphism from $\operatorname{det}$.

We can get $\operatorname{det}$ conceptually by thinking about the topology of $\operatorname{O}(n)$. We know that the connected component of the identity, $\operatorname{SO}(n)$, is a normal subgroup, so we get a surjective map $\operatorname{det}:\operatorname{O}(n) \rightarrow \operatorname{O}(n)/ \operatorname{SO}(n) = \operatorname{G}$ where $\operatorname{G}$ has size equal to the number of connected components. Once we know that there are exactly two components, $\operatorname{G}$ must be $\mathbb{Z}/2$

The usual way to analyze the topology of $\operatorname{O}(n)$ is by fibering, i.e. thinking of the columns of each matrix as an orthogonal basis, and projecting the set of orthogonal bases onto the set of sets of $k$ orthogonal vectors for $ 1 \leq k \leq n$.

Let $\operatorname{Fr}(n,k)$ denote the space of $k$-tuples of orthogonal unit vectors in $\mathbb{R}^n$ (i.e. tuples that could be the first $k$ columns of a matrix in $\operatorname{O}(n)$). Then we have a surjective map $\pi_k : \operatorname{Fr}(n,k) \rightarrow \operatorname{Fr}(n,k-1)$ given by forgetting the last vector. The fiber of this map over any point is homotopic to $S^{n-k}$. So arguing by induction, for $k < n$, we have that $\operatorname{Fr}(n,k)$ is connected since $\operatorname{Fr}(n,k-1)$ and $S^{n-k}$ are.

To really complete the proof, you have to be more careful about analyzing the topology of $\operatorname{O}(n)$ to show that the fibration in the last step is not a nontrivial double cover. This should be pretty straightforward since $\pi_1(\operatorname{Fr}(n, n - 1))$ has to be generated by the $S^1$ that appears as the fiber of the map $\pi_{n - 1}$, so you can write it down and check the action on the fiber of the map $\pi_{n}$

Alternatively, if you just want to get the correct number of connected components, I think the following works (for $\operatorname{GL}(n)$ instead of $\operatorname{O}(n)$): using row reduction and the fact that matrices $\begin{bmatrix} 1 & k \\ 0 & 1\end{bmatrix}$, $\begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}$, $diag(1,...,k,...,1)$ for $k > 0$ are in the connected component of the identity, you can explicitly construct a path from any matrix to some diagonal matrix with only $1$ and $-1$ on the diagonal. Then since $\begin{bmatrix} -1 & 0 \\ 0 & -1 \end{bmatrix}$ is in the connected component of the identity, you can connect any matrix to a diagonal matrix with only $1$ and at most one $-1$ on the diagonal. This gives that there are at most two components. Then you still need to show that there are two separate components, which you can do by defining $\hat{\operatorname{det}}$ as the sign of the product of the multi-set of eigenvalues. Of course you need to somehow show that the multi-set of eigenvalues depends continuously on the matrix, but I think this is possible to do without introducing the polynomial expression for the determinant. But you specifically do not need to know that $\hat{\operatorname{det}}$ is a homomorphism.

$\endgroup$
3
  • $\begingroup$ "In this way it is straightforward to see that the set of sets of n−1 orthogonal vectors is connected" - I don't see how $\endgroup$
    – wlad
    Mar 10 at 21:51
  • $\begingroup$ Edited, hopefully I've clarified things. $\endgroup$
    – manzana
    Mar 10 at 22:57
  • 5
    $\begingroup$ It seems to me that it's easier to do induction on the bundle $O(n-1)\to O(n)\to S^{n-1}$. From the long exact homotopy sequence it follows that the inclusion $O(n-1)\to O(n)$ gives a bijection on $\pi_0$ if $n\ge 3$. This reduces everything to $O(2)$ which is easy to deal with by hand. $\endgroup$ Mar 13 at 16:04
6
$\begingroup$

Seems to be really addictive, so you will have to endure one more answer I am afraid.

What follows is actually present in several of already given answers, I am just trying to make it as simple as possible.

Write down $\binom n2$ statements "$1<2$", "$1<3$", ..., "$n-1<n$".

Now perform a permutation and count how many of these statements will become violated.

If this permutation is a transposition $(ij)$, for $i<j$, then those violated are all "$i<k$" with $k<j$, all "$\ell<j$" with $\ell>i$ (same number twice), and "$i<j$". So each transposition violates an odd number of these statements.

Viewing result of a permutation as a reordering, we see that performing one more transposition switches between "even violators" and "odd violators".

I believe this suffices to convince oneself that parity of the number of transpositions producing any given permutation (unlike the number itself) is unambiguously defined, and coincides with parity of the number of those violations.

$\endgroup$
5
  • 3
    $\begingroup$ But in this formulation, it is not clear that this is a group homomorphism! $\endgroup$ Mar 10 at 20:12
  • $\begingroup$ @R.vanDobbendeBruyn Hmm is not it at least clear that parity of the number of involved transpositions is unambiguously defined and equal to the parity of the number of violations? $\endgroup$ Mar 10 at 20:27
  • 2
    $\begingroup$ I think this is a fine argument, but I will note that it is already mentioned in the original question, as "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." $\endgroup$ Mar 10 at 20:36
  • 2
    $\begingroup$ I like this description. It's basically decoding some of the other answers into plain language. $\endgroup$ Mar 10 at 21:00
  • $\begingroup$ @SridharRamesh Well, I tried to make it look less magic. Maybe I omitted some essential step, I am not sure anymore to be honest... $\endgroup$ Mar 10 at 21:30
5
$\begingroup$

Here is another variation on the other answers (particularly, the Cartier approach). Let $G$ be a group acting on the left of a finite set $X$, let $A$ an abelian group and let $c\colon G\times X\to A$ be a "$1$-cocycle", meaning that $c(gh,x) = c(g,hx)c(h,x)$ for all $x\in X$ and $g,h\in H$. You can then define a homomorphism $\theta\colon G\to A$ by the rule $$\theta(g) = \prod_{x\in X}c(g,x).$$ Although we are supposed to rule out computation, this is easy: $$\theta(gh)=\prod_{x\in X}c(gh,x)=\prod_{x\in X}c(g,hx)c(h,x) =\prod_{y\in X}c(g,y)\prod_{x\in X}c(h,x) =\theta(g)\theta(h)$$ by putting $y=hx$.

Now apply this to $S_n$ acting on the set $X$ of $2$-element subsets of $\{1,\ldots, n\}$ with $A=\{\pm 1\}$. For $i<j$, put $$c(\sigma,\{i,j\})= \begin{cases} 1, & \text{if}\ \sigma(i)<\sigma(j)\\ -1, &\text{if}\ \sigma(i)>\sigma(j)\end{cases}$$ (so $c$ checks if $\sigma$ inverts $\{i,j\}$) and observe that the $1$-cocycle condition just says that $\sigma\tau$ inverts $i,j$ if and only if exactly one of $\tau$ inverting $i,j$ and $\sigma$ inverting $\tau(i),\tau(j)$ occurs. Then $c((1,2),\{i,j\})=-1$ iff $\{i,j\}=\{1,2\}$ and so $\theta((1,2))=-1$.

Categorical remark. In categorical terms, you can build the transformation groupoid (aka Grothendieck construction, aka category of elements) $G\ltimes X$ and a $1$-cocycle is precisely a functor, that is, an element of $H^1(G\ltimes X,A)\cong H^1(G,A^X)$ (by Shapiro's lemma), the latter of which maps to $H^1(G,A)$ via the augmentation $A^X\to A$ sending $f$ to $\prod_{x\in X}f(x)$ like in my other answer. In fancier terms, $B(G\ltimes X)$ is the finite sheet covering space of $BG$ corresponding to the $G$-set $X$, and so you can use the transfer map to get $\mathrm{Hom}(G\ltimes X,A)\cong H^1(B(G\ltimes X),A)\to H^1(BG,A)\cong \mathrm{Hom}(G,A)$.

Topological remark. As essentially mentioned in DeBruyn's latest version of his answer (in categorical language), we can view this all topologically (but then I get switched to right actions). Let $BS_n$ be the classifying space of $S_n$ built via the bar construction. Let $X$ the right $S_n$-set of all two-element subsets of $\{1,\ldots, n\}$. Then this is a transitive $S_n$-set so corresponds to a connected finite sheet covering $E\to BS_n$ whose fundamental group is isomorphic to a stabilizer, which in turn is isomorphic to $S_2\times S_{n-2}$. Moreover, $E$ is a classifying space for its fundamental group since its universal covering space, that of $BS_n$, is contractible. Since $H^1(S_2\times S_{n-2},\{\pm 1\})$ is obviously nontrivial via the projection to $S_2$, this gives a nontrivial $1$-cocycle $c$ on $E$. Edges of $E$ look like $(e,\sigma)\colon e\to e\sigma$ where $e\in X$, $\sigma \in S_n$ and the corresponding $2$-cocycle gives $-1$ if $\sigma$ inverts $e$ and $1$, else. Now the transfer map sends this cocycle to an element of $H^1(BS_n,\{\pm 1\})=\mathrm{Hom}(S_n,\{\pm 1\})$ which is easily verified by the construction of transfer to send $\sigma$ to the product of the $c(e,\sigma)$ over all $e$, which is $-1$ raised to the number of inversions.

$\endgroup$
5
$\begingroup$

There is a comment by Benjamin Steinberg, saying that

"Usually the sign is used to show that the top exterior power is nonzero"

I think it is possible to turn things around and first prove the existence of non-zero top-forms on an arbitrary $n$-dimensional $K$-vector-space (by induction on $n$, essentially by using Laplace expansion) and extract the sign of permutations from such non-zero top forms by a straightforward group-action:

For $n=1$, the existence of non-zero top forms is vacuously true. So let $n>1$, $V$ an arbitrary $n$-dimensional $K$-vector-space, $\varphi\in V^*\setminus\{0\}$, $\psi\in \varphi^{-1}(\{1\})$ and define the following linear "projection on $\ker \varphi$": $$P:V \to \ker \varphi : v \mapsto v-\frac{\varphi(v)}{\varphi(\psi)}\psi = v-\varphi(v)\psi.$$ $$\forall j \in \{1,...,n\}:\,P_j:V^n \to (\ker \varphi)^{n-1}: v \mapsto (P(v_1),...,P(v_{j-1}),P(v_{j+1}),...,P(v_n))$$ Since $\ker \varphi$ is an $(n-1)-$dimensional $K$-vector-space, the induction hypothesis implies that there exists a non-zero multi-linear alternating map $\epsilon_{n-1}: (\ker \varphi)^{n-1} \to K$. Then define $$\epsilon_n: V^n \to K: v \mapsto \sum_{j=1}^n (-1)^{j+1} \varphi(v_j)\epsilon_{n-1}(P_j(v)).$$ Checking that $\epsilon$ is non-zero and multilinear is easy. The "alternation" becomes easy to check after noting that it suffices to prove that $\forall v\in V^n:\,\forall j\in \{1,...,n-1\}:\,v_{j}=v_{j+1}\Rightarrow \epsilon_n(v)=0$.

To proceed to get the sign of permutations, one still has to show that all permutations are compositions of a number of transpositions (maybe of neirest-neighbour-elements $(j,j+1)$). Strictly speaking, for the goal of getting the sign quickly we could have omitted here the proof that $\epsilon_n$ is multilinear, although in that case we have to prove the version of alternation/antisymmetry which says that $$\forall v\in V^n:\,\forall j\in \{1,...,n-1\}:\, \epsilon_n(v_1,...,v_n)=-\epsilon_n(v_{\pi_{j,j+1}(1)},...,v_{\pi_{j,j+1}(n)}).$$

$\endgroup$
1
  • $\begingroup$ This is a great answer. (It's a bit confusing to use $\psi$ for an element of $V$ rather than of $V^*$ … but maybe that's just my taste in naming vectors.) What you propose as a sufficient condition for anti-symmetry is, I would argue, the right definition—usually called ‘alternating’—as the only one that carries over sensibly to characteristic $2$; but, of course, in characteristic $2$, one doesn't worry about defining the sign anyway. $\endgroup$
    – LSpice
    Apr 5 at 13:40
4
$\begingroup$

It is related to the Steenrod operation $\mathrm{Sq}^2$ vanishing in the cohomology of the sphere spectrum.

This vanishing is witnessed by a spectrum map $\sigma: S \to E$, where $E$ is the fiber of a map $H\mathbb{Z} \to \Sigma^2 H\mathbb{Z}/2\mathbb{Z}$ representing $\mathrm{Sq}^2$. Now, $\Omega^\infty S$ is the initial grouplike $E_\infty$-monoid under $N_\bullet \mathrm{FinSet}^\sim$, and the composition $$N_\bullet\mathrm{FinSet}^\sim \to \Omega^\infty S \xrightarrow{\Omega^\infty \sigma} \Omega^\infty E = \mathbb{Z} \times BS_2$$ defines the sign homomorphism. (Hope I used the modern terminology and notation correctly here, otherwise feel free to improve.)

From this point of view the sign homomorphism is just one special case of a cohomology class $\sigma_p \in H^{2p-3}(BS_n;\mathbb{Z}/p\mathbb{Z})$, defined for each prime number $p$ using vanishing of the Steenrod operation $\mathcal{P}^1$ in the cohomology of the sphere spectrum.

$\endgroup$
1
  • 10
    $\begingroup$ May I be permitted to plead that this is probably not the answer that will best convince students who are just learning about permutations of the natural-ness of the signum map? $\endgroup$
    – LSpice
    Mar 9 at 19:42
4
$\begingroup$

EDIT: This doesn't work, since orientation is built into the definition of homology.


Maybe if I unravel this enough it is actually circular, but I don't think so.

Given an element of $M \in \textrm{GL}_{n+1}(\mathbb{R})$, restrict it to the sphere $\tilde{M}: S^n \to S^n$ via $\tilde{M}(p) = \frac{M(p)}{|M(p)|}$.

$H_n(S^n) \cong \mathbb{Z}$ by an easy computation. Now just need to check that $\tilde{I}$ gets mapped to $1 \in \mathbb{Z}$ while the permutation matrix of a transposition gets sent to $-1$.

$\endgroup$
7
  • 2
    $\begingroup$ Well you don't need $\pi_n$, you can directly look at $H_n$ :) In fact I think the only way I know how to prove that transpositions are sent to $-1$ without being circular uses $H_n$ rather than $\pi_n$ (and for $H_n$, you can use explicit generating cycles in the singular chain complex of $S^n$, which get mapped to their opposite) $\endgroup$ Mar 9 at 17:03
  • 1
    $\begingroup$ If you do simplicial homology, then the sign is built into the definition of the action on chains. If you do singular homology, I'm not sure, but I am skeptical that you can get far enough to prove that $H^n_{sing}(S^n)$ is nontrivial without ever introducing the sign of a permutation. $\endgroup$ Mar 9 at 17:32
  • $\begingroup$ @DavidESpeyer Yes, I guess you are correct about this. I really love and hate this question. $\endgroup$ Mar 9 at 18:02
  • $\begingroup$ @DavidESpeyer : what do you mean ? It seems to me like neither the definition of singular homology nor its computation in the case of $S^n$ involves the sign, can you specify where it would come up ? (I'm probably just missing something) $\endgroup$ Mar 9 at 18:14
  • 2
    $\begingroup$ I don't think it requires an orientation, you just have ordered simplices and you plug in a $(-1)^i$ when you remove the $i$th one. What you have is way stronger than an orientation, it's an ordering (I agree that otherwise, you might as well just talk about oriented simplices) $\endgroup$ Mar 9 at 18:42
4
$\begingroup$

Here is another rewrite of De Bruyn and Poonen's proof using group cohomology. This is certainly overpowered.

Let $A$ be an abelian group acting freely on the right of a finite set $X$ and let $G$ act on the left of $X$ via automorphisms of the $A$-action. Put $Y=X/A$ and note that $A^Y$ is a right $G$-module via precomposition (since $G$ has an induced action on $Y$). Also, if we make $A$ a trivial right $G$-module, we have a $G$-module homomorphism $\eta\colon A^Y\to A$ given by $\eta(f)=\prod_{y\in Y}f(y)$.

Given a section $t\colon Y\to X$, we get a crossed homomorphism (aka $1$-cocycle) $c\colon G\to A^Y$ by the rule $g(t(y)) = t(gy)c(g)(y)$ using that the action of $G$ on $X$ commutes with the action of $A$. One easily checks that if you choose a different section, then you get a cohomologous crossed homomorphism and so there is a well defined class $[c]\in H^1(G,A^Y)$ associated to this free action. Then we have $\eta_*\colon H^1(G,A^Y)\to H^1(G,A)=\mathrm{Hom}(G,A)$ and so $\eta_*([c])$ is a homomorphism $G\to A$.

Let $N=\ker \eta$. Note that a crossed homomorphism $g\colon G\to A^Y$ that does not take values in $N$ maps to a nontrivial element of $H^1(G,A)=\mathrm{Hom}(G,A)$ under $\eta_*$.

Poonen's answer is of course the case $A=\{\pm 1\}$ acting on the set $X$ of ordered pairs $(i,j)$ with $1\leq i\neq j\leq n$ and then $S_n$ acts on the left of $X$ with the action commuting with $A$. One can show that the transposition does not map into $N$ under the crossed homomorphism $c$ obtained using the transversal consisting of the $(i,j)$ with $i<j$ since $c((1,2))$ takes on exactly one nontrivial value from $A$. Therefore, $\eta_*([c])$ is a nontrivial homomorphism $S_n\to \{\pm 1\}$ as required.

$\endgroup$
4
$\begingroup$

Here is a slightly more geometric version of the arguments given that has more of a Coxeter group feel. It boils down though to Cartier's argument but orientations of the complete graph are replaced by considering the corresponding graphical hyperplane arrangement.

Let $\mathcal A_n$ be the braid arrangement in $\mathbb R^n$. It consists of the $\binom{n}{2}$ hyperplanes $$H_{ij} = \{\vec x\in \mathbb R^n\mid x_i=x_j\}$$ with $i\neq j$.

The group $S_n$ acts on $\mathbb R^n$ by permuting the coordinates and this action permutes $\mathcal A_n$. Let $\vec p=(1,2,3,\cdots, n)$ and note that $\vec p\notin H_{ij}$ for all $i,j$. Let $X$ be the orbit $S_n\cdot \vec p$; it consists of $n!$-distinct elements, none of which belong to any $H_{ij}$.

For $\vec q, \vec r\in X$, put $s(\vec q,\vec r)$ to be the number of hyperplanes in $\mathcal A_n$ separating $\vec q,\vec r$, where a hyperplane separates these vectors if they are in different connected components of the complement (of which there are two). Put $d(\vec q,\vec r)=(-1)^{s(\vec q,\vec r)}$.

Easy facts:

  1. $d(\vec q,\vec r)=d(\vec r,\vec q)$ (immediate)
  2. $d(\sigma(\vec q),\sigma(\vec r)) =d(\vec q,\vec r)$ for $\sigma\in S_n$ since $\mathcal A_n$ is permuted by $S_n$.
  3. $d(\vec q,\vec r)d(\vec r,\vec s)=d(\vec q,\vec s)$ because a hyperplane separates $\vec q$ and $\vec s$ if and only if it separates exactly one of $\vec q,\vec r$ and $\vec r,\vec s$ because hyperplane complements have two connected components.

From this we can define $$\mathrm{sgn}(\sigma) = d(\sigma (\vec q),\vec q)$$ where $\vec q\in X$. This is independent of $\vec q$ because $$d(\sigma(\vec r), \vec r)=d(\sigma(\vec r),\sigma(\vec q))d(\sigma(\vec q),\vec q)d(\vec q,\vec r) = d(\sigma(\vec q),\vec q)$$ by 1,2 and 3 above.

It is a homomorphism because $$\mathrm{sgn}(\sigma\tau)=d(\sigma\tau(\vec q),\vec q) =d(\sigma\tau(\vec q),\tau(\vec q))d(\tau(\vec q),\vec q) = \mathrm{sgn}(\sigma)\mathrm{sgn}(\tau)$$ by 3 and independence of $\mathrm{sgn}$ on the choice of $\vec q$.

Finally, if $\sigma=(1,2)$, then $\sigma(\vec p) = (2,1,3,\ldots, n)$ and so only $H_{1,2}$ separates $\vec p$ and $\sigma(\vec p)$. Thus $\mathrm{sgn(\sigma)}=-1$.

This can be identified with Speyer's answer by just observing that $f(\vec x)=x_i-x_j$ is a form defining $H_{ij}$ and so $$d(\sigma \vec p,\vec p) =\prod_{1\leq i<j\leq n}\dfrac{\sigma(j)-\sigma(i)}{j-i}.$$

$\endgroup$
1
  • 5
    $\begingroup$ And note that the polynomial $\Delta:=\prod_{i<j } (x_i - x_j)$ is positive on the $A_n$ chambers and negative on the non-$A_n$ chambers. This polynomial is very motivated in this context; it is the minimal polynomial (up to sign) which vanishes on all the hyperplanes. $\endgroup$ Mar 17 at 15:45
4
$\begingroup$

Update 3: Here is a complete re-write of the arguments given earlier (which are appended below after the horizontal line).

We work over a field $k$ of characteristic different from $2$.

For $i=1,\cdots, n$ let $e_i$ denote the standard basis of the standard inner-product space $V$ of dimension $n$ over $k$.

Given $v\in V$ such that $\langle v,v\rangle\neq 0$ we define $$ r_v(x) = x - 2 \frac{\langle x,v\rangle}{\langle v,v\rangle} v $$ which is the usual definition of a "reflection".

Given $i\neq j$, the reflection $r_{e_i-e_j}$ operates on $V$ by interchanging $e_i$ and $e_j$, and fixing $e_k$ for $k$ different from $i$ and $j$.

It follows that the map which sends the transposition $(i,j)$ to $r_{e_i-e_j}$ embeds the permutation group as a subgroup of the group $R(V)$ generated by reflections $r_v$ as $v$ varies.

Let $S(V)$ be the subgroup of $R(V)$ generated by elements of the form $r_v\cdot r_w$.

Claim: The group $S(V)$ is of index 2 in $R(V)$.

Consider the space $W=V+k e_0$ as an inner-product space by defining $$ \langle v+a e_0, w+b e_0\rangle = \langle v,w\rangle + ab $$ Clearly, this inner-product extends the inner-product on $V$.

If $v\in V$, then $r_v:W\to W$ has the property that it is $r_v:V\to V$ extended by $r_v(e_0)=e_0$.

Further $r_{e_0}(v)=v$ for $v\in V$ and $r_{e_0} \cdot r_v= r_v\cdot r_{e_0}$ for every $v\in V$.

It follows that the group $R(V,W)$ inside automorphisms of $W$ generated by the elements $r_{e_0}\cdot r_v$ acts on $V$ and can be identified with $R(V)$ via this action.

Since $r_{e_0}$ commutes with $r_v$ for every $v$, the subgroup of $R(V,W)$ which acts as identity on $e_0$ can be identified under this action with $S(V)$.

This shows that the group $S(V)$ is of index 2 in $R(V)$.


A topological argument could go as follows.

The group $\Sigma_n$ acts in an obvious manner on an $(n-1)$-simplex via the action on vertices.

The sign decides whether the action preserves or reverses orientation.

Perhaps this is a circular definition since the question is what is orientation. The answer is that it is something that is preserved under rotations but inverted under reflections.

Put differently, we can play the game of applying rotations to the simplex to try to return the simplex to its original position. Since $3$-cycles are clearly represented by rotations, we see that (the group generated by them) $A_n$ can be applied to the position. Thus, we can transform any position using $A_n$ to a position where all except two chosen vertices are correctly positioned.

Update: Taking up the answer given by manzana one can also argue in terms of the orthogonal group.

The permutation group $\Sigma_n$ operates in a natural way on the $n$-dimensional inner-product space $V$ with a positive definite innner product. One can proceed as follows to study the group $O(V)$ of automorphisms of $V$:

  1. Prove by induction that any automorphism of $V$ is a product of simple reflections. Let $r_v$ denote the simple reflection that is constant on $v^{\perp}$ and sends $v$ to $-v$.

  2. The product $r_v\cdot r_w$ of two reflections is constant on an orthogonal subspace $\{v,w\}^{\perp}$ of codimension 2 and is thus determined by what it does on the span of $v$ and $w$.

  3. One then shows that if $u$ lies in the plane of $v$ and $w$, then there is a $t$ such that $r_v\cdot r_w = r_t \cdot r_u$. (We can take $t=r_v\cdot r_w(-u)+u$.)

  4. It then follows that the subgroup $SO(V)$ of elements of $O(V)$ that are a product of an even number of reflections is a connected group.

  5. It also follows that $SO(V)$ is a subgroup of index 2 in $O(V)$.

Update 2: In response to the comments and based on the answer given by Timothy Chow, here is another (hopefully simpler) argument.

Let $W$ be an inner-product space of dimension $n+1$ which contains the $n$-dimensional subspace $V$. Let $e_0,e_1,\dots, e_n$ denote the standard basis of $W$.

As above, for a non-zero vector $v$ in $W$, let $r_v$ denote the reflection defined by $r_v(x)=x-2(<x,v>/<v,v>)v$,

For each $0<i,j\leq n$ define automorphisms $R_{i,j}=r_{e_0}\cdot r_{e_i-e_j}$ of $W$. Note that these automorphisms preserve $V$ and the action of $R_{i,j}$ on $V$ is exactly the action of the transposition $(i,j)$ as described above. This shows that the group generated by $R_{i,j}$ is $S_n$ via the above action on $V$.

The subgroup of this group that fixes $e_0$ is $A_n$. It is clearly of index 2.

Geometrically, the above is an explicit realisation of the group of rigid motions of the "bi-pyramid" that is mentioned in the comment to the answer by Timothy Chow.

$\endgroup$
11
  • $\begingroup$ Timothy Chow posted basically the same answer about 10 minutes ago. $\endgroup$ Mar 9 at 3:45
  • $\begingroup$ @‍TimothyChow's answer referenced by @SamHopkins. $\endgroup$
    – LSpice
    Mar 9 at 19:39
  • $\begingroup$ Since the 1-skeleton of the simplex is a complete graph, this is also essentially the same as Bjorn Poonen's answer. $\endgroup$
    – HJRW
    Mar 11 at 8:33
  • $\begingroup$ The "update" is fantastic, and gives a completely satisfying geometric resolution to the problem for me. $\endgroup$ Mar 16 at 14:48
  • $\begingroup$ @StevenGubkin: I see the standard argument that $SO_n$ is connected, but I'm not seeing an argument that $O_n$ has at least two components, i.e. why can't you write a reflection as an element of $SO_n$? $\endgroup$ Mar 16 at 16:35
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$
6
  • 5
    $\begingroup$ How do you prove that the nth exterior power is one-dimensional? $\endgroup$ Mar 9 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 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 at 2:34
  • $\begingroup$ @AlexArvanitakis How do these two properties make the map well-defined? $\endgroup$ Mar 10 at 5:42
  • 5
    $\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 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 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 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 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 at 9:47
3
$\begingroup$

If they have studied Galois Theory, you could consider the extension of fields $E:= \mathbb{R}(x_1, \ldots, x_n)^{S_n} \subset F:= \mathbb{R}(x_1, \ldots, x_n)$ of symmetric rational functions into rational functions. One can play around and try to find a rational function that is "almost symmetric", beside the sign, but not symmetric.

Let's try to find it together. One can start with $x_1-x_2$ and see that it is almost fixed by all the $\sigma$ that swaps $1$ and $2$, but as soon as $1$ is sent to something else, you obtain another difference, e.g. $x_3-x_2$. But hey,if we multiply all such differences, they will be swapped between them, but the product (beside the sign) will be preserved.

Now consider your polynomial $p(x_1, \ldots, x_n) = \prod_{i < j} (x_i -x_j)$. Since it is almost symmetric, $p^2$ is symmetric, because the square kills the sign. This means $E(p)$ is a degree $2$ extension of $E$.

On the Galois side, this yields a subgroup $G:= \textrm{Gal}(F/E(p))$ of index $2$. Almost symmetricity of $p$ also implies that $E(p)/E$ is normal, so that we have obtained our normal subgroup $A_n = G$ of $S_n$. It's easy to see that a permutation acts trivially on $p$ if and only if the number of inversions is even.

Notes. I am not sure this easily explains why $2$ is the right thing, which is better explained by the first answer of character. Existence, however, is explained easily with Galois Theory, with no computation needed. You can give the exercise of finding $p$ for $n=2,3$ and I am sure they will guess (or at least be at ease with) the general formula.

$\endgroup$
1
$\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 at 14:31

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