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

Question

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

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

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

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

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

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

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

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

7. ….

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

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

Here are a few possible avenues:

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

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

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

• Proofs involving polynomials again feel like magic to me.

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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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

Answer 7

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.

Answer 8

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

Answer 9

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.

Answer 10

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!)

Answer 11

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.

Answer 12

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

Answer 13

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.

Answer 14

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.

Answer 15

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

Answer 16

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.

Answer 17

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.

Answer 18

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.

Answer 19

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.

Answer 20

This is really a variation on manzana’s answer to show $O(n)$ has two components, but I wanted to describe it in the way that I think about orientations.

We may think of an element of $O(n)$ as an orthonormal frame $(v_1,\ldots,v_n)$, $|v_i|=1$, $v_i\cdot v_j=0, i\neq j$, giving an orientation of $\mathbb{R}^n$. For $n>1$, we may rotate the first $n-1$ vectors to $e_1=(1,0,\ldots,0), e_2=(0,1,0,\ldots,0), \ldots, e_{n-1}=(0,\ldots,0,1,0)$. To do this, rotate the first vector $v_1$ to $e_1$, which we may do since $S^{n-1}$ is connected (and rotating the rest of the frame along at each step). Then rotate $v_2$ to $e_2$ while keeping $e_1$ fixed using that the sphere $S^{n-2}=S^{n-1}\cap e_1^\perp$ is connected, and so on until we get to rotate $v_{n-1}$ to $e_{n-1}$ keeping $e_1,\ldots, e_{n-2}$ fixed using $S^1$ is connected. Moreover, this rotation is canonical and sends $v_n$ to $\pm e_n$. Thus we see that $O(n)$ has two components, and the determinant is the sign of the last vector in the orthogonal frame that we have rotated to.

Of course, to prove this rigorously (to see that we indeed get two components), one must proceed by induction on dimension and use a fibration as in manzana’s answer. But I thought I would point out that this is how I (and maybe others) intuitively / pictorially think about orientations of $\mathbb{R}^n$ via the components of the space of $n$-frames.

Answer 21

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.

Answer 22

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

Answer 23

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_n$ 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)}).$$

Answer 24

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.

Answer 25

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.

Answer 26

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

Answer 27

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.

Answer 28

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.

Answer 29

Here is a formula I have not seen in the long and excellent list of answers: If $\sigma\in\mathfrak S_n$, then $\mathop{\rm sgn}(\sigma)=(-1)^{n-p}$, where $p$ is the number of orbits of $\sigma$ on $\{1,\dots,n\}$.

(This definition does even work for a symmetric group on any finite set, and extends to the infinite symmetric group — permutations with finite support.)

The only nonobvious thing is that it defines a morphism of groups. For this, it suffices to prove that if $\tau$ is a transposition, then $\mathop{\rm sgn}(\sigma\tau)=-\mathop{\rm sgn}(\sigma)$. There are two cases, according to which the elements which are swapped by $\tau$ belong to the same orbit, or not. In fact, if $\{a_1,\dots,a_m\}$ is one orbit of $\sigma$, written in cyclic order, and if $\tau=(a_1,a_k)$, with $1<k\le m$, then $\sigma\tau$ has the same orbits as $\sigma$ except that the orbit $(a_1,\dots,a_m)$ is split into two orbits $\{a_1,a_{k+1},\dots,a_m\}$ and $\{a_2,\dots,a_k\}$; in this case $\sigma\tau$ has one more orbit than $\sigma$. The other case is proved in the same manner, (and can even be avoided because the two elements swapped by $\tau$ then belong to the same orbit of $\tau\sigma$).

EDIT : Add parenthesis about the infinite symmetric group

Answer 30

There is an interesting wrong "proof" by Hans Liebeck in the American Mathematical Monthly article Even and odd permutations: He claims that if a product of transpositions $(1\;i)$ is the identity, then each transposition $(1\;s)$ appears an even number of times. However, $(1\;2)(1\;3)(1\;2)(1\;3)(1\;2)(1\;3)=e$ contradicts this "fact". (Thanks to my colleague Florian Möller who noticed this type of mistake in a similar "proof" of mine ...)

Answer 31

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

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

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

Answer 32

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

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

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

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

Answer 33

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

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

Answer 34

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

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

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

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

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

Proof

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

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

Answer 35

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

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

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

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

Answer 36

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

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

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

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

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

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

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

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

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

---

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

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

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

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

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

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

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

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

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

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

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

---

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

Answer 37

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