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

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

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.

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

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.

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.

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

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.

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.

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

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.

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.

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

answered Mar 11, 2022 at 18:02

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

answered Mar 9, 2022 at 3:33

paul garrett

23.3k3 gold badges89 silver badges126 bronze badges

answered Sep 27, 2023 at 5:56

Ian Agol

71.3k3 gold badges200 silver badges370 bronze badges

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.

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

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

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

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.

answered Jun 6, 2022 at 14:38

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

answered Nov 28, 2023 at 6:17

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.