5.2 Permutations · Matrix Theory

Let $𝐷 : 𝐹^{𝑛 \times 𝑛} \to 𝐹$ be multilinear and alternating. In Intuition (What the proof did, and where it leads) we wrote column $𝑗$ of $𝐴$ as $\sum_{𝑖} 𝑎_{𝑖 𝑗} 𝐞_{𝑖}$ and expanded $𝐷 (𝐴)$ in all $𝑛$ columns. A term of the expansion chooses one index in each column, so it is indexed by a function $𝑓 : [𝑛] \to [𝑛]$ , and it equals

𝑎_{𝑓 (1) 1} 𝑎_{𝑓 (2) 2} \dots 𝑎_{𝑓 (𝑛) 𝑛} 𝐷 (𝐞_{𝑓 (1)}, 𝐞_{𝑓 (2)}, \dots, 𝐞_{𝑓 (𝑛)}) .

Alternation kills the term whenever $𝑓$ takes some value twice, so only the bijections $𝑓$ survive. This section studies these bijections, the permutations of $[𝑛]$ . To evaluate a surviving value $𝐷 (𝐞_{𝑓 (1)}, \dots, 𝐞_{𝑓 (𝑛)})$ we interchange two columns at a time until they are in order, and each interchange contributes a factor $- 1$ . The main result, Theorem 5.2.18, says that the parity of the number of interchanges does not depend on how we sort. This gives every permutation $𝜎$ a sign $sgn (𝜎) = \pm 1$ , and Theorem 5.2.31 shows that $𝐷 (𝐞_{𝜎 (1)}, \dots, 𝐞_{𝜎 (𝑛)}) =$ $sgn (𝜎) 𝐷 (𝐼_{𝑛})$ .

5.2.1Permutations

Throughout, $𝑛 \geq 1$ and $[𝑛] = {1, 2, \dots, 𝑛}$ .

Definition 5.2.1 (Permutation). A permutation of

[𝑛]

is a bijection

𝜎 : [𝑛] \to [𝑛]

. The set of all permutations of

[𝑛]

is denoted

𝑆_{𝑛}

Since $[𝑛]$ is finite, a function $𝑓 : [𝑛] \to [𝑛]$ is injective if and only if it is surjective, and hence if and only if it is bijective (Section A.1). So $𝑓$ is a permutation exactly when the list $𝑓 (1),$ $𝑓 (2),$ $\dots,$ $𝑓 (𝑛)$ has no repeated entries, and then this list contains each element of $[𝑛]$ exactly once. In this sense a permutation is a rearrangement of $1, 2, \dots, 𝑛$ . We record a permutation in two-line notation, writing each $𝑖$ above its image:

𝜎 = (\begin{matrix} 1 & 2 & \dots & 𝑛 \\ 𝜎 (1) & 𝜎 (2) & \dots & 𝜎 (𝑛) \end{matrix}) .

The bottom row is the rearrangement.

Example 5.2.2 ( $𝑆_{1}$ , $𝑆_{2}$ , and $𝑆_{3}$ ). $𝑆_{1}$ contains only the identity map of $[1]$ , and $𝑆_{2}$ contains the identity and the permutation $(\begin{matrix} 1 & 2 \\ 2 & 1 \end{matrix})$ , which interchanges $1$ and $2$ . The six elements of $𝑆_{3}$ are

\begin{matrix} (\begin{matrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{matrix}), \\ (\begin{matrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{matrix}) . \end{matrix}

In the expansion of a $3 \times 3$ determinant these are the six orderings of $𝐞_{1}, 𝐞_{2}, 𝐞_{3}$ whose terms survive alternation. For instance, the fourth gives the term $𝑎_{21} 𝑎_{32} 𝑎_{13} 𝐷 (𝐞_{2}, 𝐞_{3}, 𝐞_{1})$ .

Non-example 5.2.3 (A function that is not a permutation). Define

𝑓 : [3] \to [3]

𝑓 (1) = 2

𝑓 (2) = 2

, and

𝑓 (3) = 1

. Then

𝑓

is not injective, so

𝑓 \notin 𝑆_{3}

. In the expansion of

𝐷 (𝐴)

for

𝐴 \in 𝐹^{3 \times 3}

, the term indexed by

𝑓

𝑎_{21} 𝑎_{22} 𝑎_{13} 𝐷 (𝐞_{2}, 𝐞_{2}, 𝐞_{1})

, which is

0

because

𝐞_{2}

appears in two columns. Every function that is not injective is killed in the same way.

Proposition 5.2.4 (Counting permutations).

𝑆_{𝑛}

has exactly

𝑛!

elements.

Proof.routine

Uses. Definition 5.2.1 (Permutation), injective maps $[𝑛] \to [𝑛]$ are bijective (Section A.1)

Hint 1. A permutation is determined by the list

𝜎 (1), \dots, 𝜎 (𝑛)

. Given the first

𝑘

entries, how many choices are there for the next?

Hint 2. Show by induction on

𝑘

that there are

𝑛 (𝑛 - 1) \dots (𝑛 - 𝑘 + 1)

lists of

𝑘

distinct elements of

[𝑛]

Sketch. The permutations correspond to the lists of

𝑛

distinct elements of

[𝑛]

. There are

𝑛

choices for the first entry, then

𝑛 - 1

for the second, and so on, which gives

𝑛!

lists; induction on the length makes this precise.

A permutation

𝜎

is determined by the list

𝜎 (1), \dots, 𝜎 (𝑛)

, and by the remark above, the lists that arise are exactly the lists of

𝑛

distinct elements of

[𝑛]

. We show by induction on

𝑘

, for

0 \leq 𝑘 \leq 𝑛

, that there are

𝑛 (𝑛 - 1) \dots (𝑛 - 𝑘 + 1)

lists of

𝑘

distinct elements of

[𝑛]

, with the empty product

1

for

𝑘 = 0

(the empty list). This is clear for

𝑘 = 0

. If

𝑘 < 𝑛

, a list of

𝑘 + 1

distinct elements consists of a list of

𝑘

distinct elements followed by one of the

𝑛 - 𝑘

elements not in it, and different choices give different lists. So there are

𝑛 (𝑛 - 1) \dots (𝑛 - 𝑘 + 1) \cdot

(𝑛 - 𝑘)

such lists. Taking

𝑘 = 𝑛

gives

𝑛!

. □

The factorial grows quickly: $𝑆_{10}$ already has $3, 628, 800$ elements. So an expansion over $𝑆_{𝑛}$ is a tool for proving things about determinants, not for computing them; Section 5.4 computes determinants by elimination.

Composition and inverses

Permutations are functions $[𝑛] \to [𝑛]$ , so we can compose them. We write $𝜎 𝜏$ for the composite $𝜎 \circ 𝜏$ , so that $(𝜎 𝜏) (𝑖) =$ $𝜎 (𝜏 (𝑖))$ for $𝑖 \in [𝑛]$ : first $𝜏$ , then $𝜎$ . We write $id$ for the identity permutation, $𝜎^{𝑘}$ for the composite of $𝑘$ copies of $𝜎$ , and $𝜎^{0} = id$ .

Proposition 5.2.5 (Composition and inverses). Let $𝜎, 𝜏, 𝜌 \in 𝑆_{𝑛}$ .

(a) $id \in 𝑆_{𝑛}$ , $𝜎 𝜏 \in 𝑆_{𝑛}$ , and $𝜎^{- 1} \in 𝑆_{𝑛}$ .
(b) $(𝜎 𝜏) 𝜌 = 𝜎 (𝜏 𝜌)$ , $𝜎 id = id 𝜎 = 𝜎$ , and $𝜎 𝜎^{- 1} = 𝜎^{- 1} 𝜎 = id$ .
(c) ${(𝜎 𝜏)}^{- 1} = 𝜏^{- 1} 𝜎^{- 1}$ .

Proof.routine

Uses. Definition 5.2.1 (Permutation), composition of functions is associative; inverse functions (Section A.1)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. A function is a bijection exactly when it has a two-sided inverse. Find one for

𝜎 𝜏

Hint 2. Try

𝜏^{- 1} 𝜎^{- 1}

, and regroup using associativity of composition.

Sketch. The identity and

𝜎^{- 1}

are bijections. Regrouping gives

(𝜎 𝜏) (𝜏^{- 1} 𝜎^{- 1}) =

𝜎 𝜎^{- 1} =

id

and

(𝜏^{- 1} 𝜎^{- 1}) (𝜎 𝜏) =

id

, so

𝜎 𝜏

is a bijection with inverse

𝜏^{- 1} 𝜎^{- 1}

. Part (b) is associativity of composition and the definition of an inverse function.

(a) The identity map is a bijection, and the inverse of a bijection $𝜎$ is a bijection, with inverse $𝜎$ . Since composition of functions is associative,

(𝜎 𝜏) (𝜏^{- 1} 𝜎^{- 1}) = 𝜎 (𝜏 𝜏^{- 1}) 𝜎^{- 1} = 𝜎 𝜎^{- 1} = id, (𝜏^{- 1} 𝜎^{- 1}) (𝜎 𝜏) = 𝜏^{- 1} (𝜎^{- 1} 𝜎) 𝜏 = 𝜏^{- 1} 𝜏 = id .

So $𝜎 𝜏$ has a two-sided inverse, and it is a bijection.

(b) These are the associativity of composition and the defining properties of the identity map and of the inverse function.

(c) By the computation in (a), $𝜏^{- 1} 𝜎^{- 1}$ is a two-sided inverse of $𝜎 𝜏$ . A bijection has only one inverse function (if $𝑔$ and $𝑔^{'}$ are both inverses of $𝑓$ , then $𝑔 =$ $𝑔 (𝑓 𝑔^{'}) =$ $(𝑔 𝑓) 𝑔^{'} =$ $𝑔^{'}$ ), so ${(𝜎 𝜏)}^{- 1} = 𝜏^{- 1} 𝜎^{- 1}$ . □

Remark 5.2.6. Parts (a) and (b) say that

𝑆_{𝑛}

with composition is a group: a set with an associative operation that has an identity element and inverses. It is called the symmetric group of degree

𝑛

. We will not need any group theory, but Section 14.1 develops this point of view.

Example 5.2.7 (Composing and inverting). Let

𝜎 = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{matrix}), 𝜏 = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 5 & 3 & 4 \end{matrix}) .

To compute $(𝜎 𝜏) (𝑖)$ , apply $𝜏$ first: $(𝜎 𝜏) (1) =$ $𝜎 (𝜏 (1)) =$ $𝜎 (2) =$ $5$ , $(𝜎 𝜏) (2) = 𝜎 (1) = 3$ , and so on. We get

𝜎 𝜏 = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 3 & 2 & 4 & 1 \end{matrix}), 𝜏 𝜎 = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 3 & 2 & 1 \end{matrix}) .

So $𝜎 𝜏 \neq 𝜏 𝜎$ : composition of permutations is not commutative. To invert $𝜎$ , read the two-line notation from the bottom up. Since $𝜎$ sends $1, 2, 3, 4, 5$ to $3, 5, 4, 1, 2$ , its inverse sends $3, 5, 4, 1, 2$ to $1, 2, 3, 4, 5$ ; sorting the columns,

𝜎^{- 1} = (\begin{matrix} 3 & 5 & 4 & 1 & 2 \\ 1 & 2 & 3 & 4 & 5 \end{matrix}) = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 1 & 3 & 2 \end{matrix}) .

Sums over $𝑆_{𝑛}$ appear throughout this chapter. The following fact lets us substitute $𝜌 𝜎$ , $𝜎 𝜌$ , or $𝜎^{- 1}$ for the summation variable $𝜎$ .

Proposition 5.2.8 (Reindexing sums over $𝑆_{𝑛}$ ). Fix $𝜌 \in 𝑆_{𝑛}$ . Each of the maps $𝑆_{𝑛} \to 𝑆_{𝑛}$ given by $𝜎 \mapsto 𝜌 𝜎$ , by $𝜎 \mapsto 𝜎 𝜌$ , and by $𝜎 \mapsto 𝜎^{- 1}$ is a bijection. Consequently, for every function $𝑔 : 𝑆_{𝑛} \to 𝐹$ ,

\sum_{𝜎 \in 𝑆_{𝑛}} 𝑔 (𝜎) = \sum_{𝜎 \in 𝑆_{𝑛}} 𝑔 (𝜌 𝜎) = \sum_{𝜎 \in 𝑆_{𝑛}} 𝑔 (𝜎 𝜌) = \sum_{𝜎 \in 𝑆_{𝑛}} 𝑔 (𝜎^{- 1}) .

Proof.routine

Uses. Proposition 5.2.5 (Composition and inverses)

Hint 1. To show that

𝜎 \mapsto 𝜌 𝜎

is a bijection, write down its inverse.

Hint 2. For the sums: if

𝜑 : 𝑆_{𝑛} \to 𝑆_{𝑛}

is a bijection, how do the terms of

\sum_{𝜎} 𝑔 (𝜑 (𝜎))

compare with those of

\sum_{𝜎} 𝑔 (𝜎)

Sketch. The inverses are

𝜎 \mapsto 𝜌^{- 1} 𝜎

𝜎 \mapsto 𝜎 𝜌^{- 1}

, and

𝜎 \mapsto 𝜎^{- 1}

itself. If

𝜑

is a bijection of

𝑆_{𝑛}

, then

\sum_{𝜎} 𝑔 (𝜑 (𝜎))

has the same terms as

\sum_{𝜎} 𝑔 (𝜎)

in a different order.

By Proposition 5.2.5, $𝜌^{- 1} (𝜌 𝜎) = 𝜎$ and $𝜌 (𝜌^{- 1} 𝜎) = 𝜎$ for every $𝜎 \in 𝑆_{𝑛}$ , so $𝜎 \mapsto 𝜌^{- 1} 𝜎$ is a two-sided inverse of $𝜎 \mapsto 𝜌 𝜎$ . In the same way $𝜎 \mapsto 𝜎 𝜌^{- 1}$ is a two-sided inverse of $𝜎 \mapsto 𝜎 𝜌$ , and $𝜎 \mapsto 𝜎^{- 1}$ is its own inverse because ${(𝜎^{- 1})}^{- 1} = 𝜎$ . So all three maps are bijections.

Now let $𝜑 : 𝑆_{𝑛} \to 𝑆_{𝑛}$ be a bijection. As $𝜎$ runs through $𝑆_{𝑛}$ , the element $𝜑 (𝜎)$ runs through $𝑆_{𝑛}$ and takes each value exactly once. So the sum $\sum_{𝜎} 𝑔 (𝜑 (𝜎))$ has exactly the terms of $\sum_{𝜎} 𝑔 (𝜎)$ , in another order, and since addition in $𝐹$ is commutative and associative, the two sums are equal. Applying this to the three bijections gives the displayed equalities. □

Exercise 5.2.9.routine Let

𝜎 = (\begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{matrix})

. Compute

𝜎^{2}

𝜎^{3}

, and

𝜎^{- 1}

, and find the least

𝑚 \geq 1

with

𝜎^{𝑚} = id

Solution.

Uses. Proposition 5.2.5 (Composition and inverses)

Hint 1.

𝜎^{2} (𝑖) =

𝜎 (𝜎 (𝑖))

. Apply

𝜎

to each entry of the bottom row of

𝜎

Hint 2. Compare

𝜎^{3}

with

𝜎^{- 1}

: what is

𝜎^{4}

Sketch.

𝜎^{2} = (\begin{matrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{matrix})

𝜎^{3} =

(\begin{matrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{matrix}) =

𝜎^{- 1}

, and

𝜎^{4} = id

. Since

𝜎

𝜎^{2}

𝜎^{3}

are not the identity,

𝑚 = 4

Applying

𝜎

to each entry

2, 4, 1, 3

of the bottom row of

𝜎

gives

𝜎 (2),

𝜎 (4),

𝜎 (1),

𝜎 (3) =

4,

3,

2,

1

, so

𝜎^{2} = (\begin{matrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{matrix})

. Applying

𝜎

4, 3, 2, 1

gives

3, 1, 4, 2

, so

𝜎^{3} = (\begin{matrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{matrix})

, and applying it once more gives

1, 2, 3, 4

, so

𝜎^{4} = id

. Reading

𝜎

from the bottom up,

𝜎^{- 1}

sends

2, 4, 1, 3

1, 2, 3, 4

, so

𝜎^{- 1} =

(\begin{matrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{matrix}) =

𝜎^{3}

, as it must be since

𝜎^{3} 𝜎 = 𝜎^{4} = id

. None of

𝜎

𝜎^{2}

𝜎^{3}

is the identity, so the least

𝑚

4

5.2.2Transpositions and cycles

In Intuition (What the proof did, and where it leads) we sorted the columns of $𝐷 (𝐞_{2}, 𝐞_{3}, 𝐞_{1})$ by interchanging two columns at a time. The permutations that interchange two elements are the building blocks of this section.

Definition 5.2.10 (Transposition). Let $𝑘, 𝑙 \in [𝑛]$ with $𝑘 \neq 𝑙$ . The transposition $𝜏 = (𝑘 𝑙)$ is the permutation that interchanges $𝑘$ and $𝑙$ and fixes everything else:

𝜏 (𝑘) = 𝑙, 𝜏 (𝑙) = 𝑘, 𝜏 (𝑖) = 𝑖 for 𝑖 \notin {𝑘, 𝑙} .

It is an adjacent transposition if $𝑙 = 𝑘 + 1$ .

Transpositions are also called swaps. Note that $(𝑘 𝑙) = (𝑙 𝑘)$ , and that interchanging twice changes nothing: ${(𝑘 𝑙)}^{2} = id$ , so ${(𝑘 𝑙)}^{- 1} = (𝑘 𝑙)$ .

Remark 5.2.11 (Composing with a transposition). Let $𝜎 \in 𝑆_{𝑛}$ and $𝜏 = (𝑘 𝑙)$ . Then $(𝜎 𝜏) (𝑘) = 𝜎 (𝑙)$ , $(𝜎 𝜏) (𝑙) = 𝜎 (𝑘)$ , and $(𝜎 𝜏) (𝑖) = 𝜎 (𝑖)$ for all other $𝑖$ . So the bottom row of $𝜎 𝜏$ is the bottom row of $𝜎$ with the entries in positions $𝑘$ and $𝑙$ interchanged. On the other hand, $𝜏 𝜎$ applies $𝜏$ to every entry of the bottom row of $𝜎$ , so its bottom row is that of $𝜎$ with the values $𝑘$ and $𝑙$ interchanged. For example, with $𝜎 = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{matrix})$ ,

𝜎 (2 4) = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 4 & 5 & 2 \end{matrix}), (2 4) 𝜎 = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 2 & 1 & 4 \end{matrix}) .

Either way, the bottom row changes by interchanging two of its entries.

Every rearrangement of $1, \dots, 𝑛$ can be sorted by interchanging two entries at a time, so we expect every permutation to be a product of transpositions. To turn this into a proof we need a measure of progress. Say that $𝜎$ moves $𝑖$ if $𝜎 (𝑖) \neq 𝑖$ , and let $𝑚 (𝜎)$ be the number of points that $𝜎$ moves. If $𝜎 (𝑘) = 𝑗$ with $𝑗 \neq 𝑘$ , then $(𝑘 𝑗) 𝜎$ sends $𝑘$ to $𝑘$ , so composing with one transposition fixes at least one more point. It may fix two, if also $𝜎 (𝑗) = 𝑘$ , so the measure drops by an amount we do not control. This calls for strong induction.

Technique 5.2.12 (Strong induction and well-ordering). To prove a statement $𝑃 (𝑚)$ for every integer $𝑚 \geq 0$ , it suffices to prove $𝑃 (𝑚)$ for each $𝑚$ under the assumption that $𝑃 (𝑘)$ holds for every $𝑘 < 𝑚$ . When $𝑚 = 0$ there is nothing to assume, so the argument must handle that case outright, but no separate base case is needed. Reach for strong induction when a reduction step replaces an object by a smaller one but you cannot say by how much it shrinks, so that induction from $𝑚 - 1$ to $𝑚$ does not apply. Often the main decision is the measure of size, such as the number of points a permutation moves or the degree of a polynomial.

An equivalent form is the well-ordering principle: every nonempty set of nonnegative integers has a least element. It justifies arguments that begin “let $𝑘$ be the least positive integer such that $\dots$ ”, and proofs by minimal counterexample. The canonical example is Proposition 5.2.13, by induction on the number of moved points. Section A.2 compares the forms of induction, and Section 7.1 uses strong induction on the degree to divide polynomials.

Used in 9 places and 1 practice exercise

Proposition 5.2.13, Proposition 5.2.16, Lemma 5.3.14, Theorem 7.1.14, Exercise 7.1.68, Proposition 7.5.8, Theorem 7.5.13, Lemma 8.2.4, Exercise A.2.9; 1 practice exercise.

Proposition 5.2.13 (Products of transpositions). Every permutation

𝜎 \in 𝑆_{𝑛}

is a product of transpositions: there are transpositions

𝜏_{1}, \dots, 𝜏_{𝑟} \in 𝑆_{𝑛}

, with

𝑟 \geq 0

, such that

𝜎 = 𝜏_{1} 𝜏_{2} \dots 𝜏_{𝑟}

. (For

𝜎 = id

we take

𝑟 = 0

, the empty product.)

Proof.standard

Uses. Definition 5.2.10 (Transposition), Proposition 5.2.5 (Composition and inverses)

Techniques. Strong induction and well-ordering (Technique 5.2.12)

Hint 1. Measure progress by the number

𝑚 (𝜎)

of points that

𝜎

moves. Can you compose

𝜎

with one transposition so that the result fixes more points?

Hint 2. If

𝜎 (𝑘) = 𝑗 \neq 𝑘

, look at

𝜌 = (𝑘 𝑗) 𝜎

. Which points does

𝜌

fix?

Hint 3.

𝜌

fixes

𝑘

and every point that

𝜎

fixes, so

𝑚 (𝜌) < 𝑚 (𝜎)

, but possibly

𝑚 (𝜌) = 𝑚 (𝜎) - 2

. Use strong induction, and recover

𝜎

from

𝜌

using

{(𝑘 𝑗)}^{2} = id

Sketch. Strong induction on

𝑚 (𝜎)

. If

𝜎 = id

, take the empty product. Otherwise pick

𝑘

with

𝜎 (𝑘) = 𝑗 \neq 𝑘

. Then

𝜌 = (𝑘 𝑗) 𝜎

fixes

𝑘

and every point fixed by

𝜎

(a fixed point

𝑖

𝜎

cannot be

𝑗

, by injectivity), so

𝑚 (𝜌) < 𝑚 (𝜎)

. Write

𝜌

as a product of transpositions, and

𝜎 = (𝑘 𝑗) 𝜌

We prove by strong induction on $𝑚 \geq 0$ that every $𝜎 \in 𝑆_{𝑛}$ with $𝑚 (𝜎) = 𝑚$ is a product of transpositions. Let $𝜎 \in 𝑆_{𝑛}$ with $𝑚 (𝜎) = 𝑚$ , and assume the statement for all permutations that move fewer than $𝑚$ points.

If $𝑚 = 0$ , then $𝜎 = id$ , the empty product. Otherwise choose $𝑘$ with $𝜎 (𝑘) \neq 𝑘$ , let $𝑗 = 𝜎 (𝑘)$ , and let $𝜏 = (𝑘 𝑗)$ and $𝜌 = 𝜏 𝜎$ . Then $𝜌 (𝑘) = 𝜏 (𝑗) = 𝑘$ . Now let $𝑖$ be a point fixed by $𝜎$ . Then $𝑖 \neq 𝑘$ , since $𝜎$ moves $𝑘$ . Also $𝑖 \neq 𝑗$ : otherwise $𝜎 (𝑗) = 𝑗 = 𝜎 (𝑘)$ with $𝑗 \neq 𝑘$ , contradicting injectivity of $𝜎$ . So $𝜏$ fixes $𝑖$ , and $𝜌 (𝑖) =$ $𝜏 (𝜎 (𝑖)) =$ $𝜏 (𝑖) =$ $𝑖$ . Thus $𝜌$ fixes every point that $𝜎$ fixes, and it also fixes $𝑘$ , which $𝜎$ moves. Hence $𝑚 (𝜌) \leq 𝑚 - 1$ .

By the induction hypothesis, $𝜌 = 𝜏_{1} \dots 𝜏_{𝑟}$ for some transpositions $𝜏_{𝑖}$ . Since $𝜏^{2} = id$ , we get $𝜎 =$ $𝜏^{2} 𝜎 =$ $𝜏 𝜌 =$ $𝜏 𝜏_{1} \dots 𝜏_{𝑟}$ , a product of transpositions. □

Example 5.2.14 (Sorting by transpositions). Run the proof on $𝜎 = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{matrix})$ , always choosing the least moved point $𝑘$ . By Remark 5.2.11, composing with a transposition on the left interchanges two values in the bottom row. Since $𝜎 (1) = 3$ , the first step interchanges the values $1$ and $3$ , then the values $2$ and $5$ , then $3$ and $4$ :

\begin{aligned} (1 3) 𝜎 & = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 5 & 4 & 3 & 2 \end{matrix}), \\ (2 5) (1 3) 𝜎 & = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 4 & 3 & 5 \end{matrix}), \\ (3 4) (2 5) (1 3) 𝜎 & = id . \end{aligned}

Multiplying on the left by $(1 3) (2 5) (3 4)$ , the inverse of $(3 4) (2 5) (1 3)$ , gives $𝜎 = (1 3) (2 5) (3 4)$ .

Cycles

Following where a permutation sends one element at a time gives a more economical notation. For $𝜎 = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{matrix})$ we have $1 \mapsto 3 \mapsto 4 \mapsto 1$ and $2 \mapsto 5 \mapsto 2$ : the elements of $[5]$ travel around two loops.

Definition 5.2.15 (Cycle). Let $𝑘 \geq 2$ , and let $𝑎_{1}, \dots, 𝑎_{𝑘} \in [𝑛]$ be distinct. The cycle $(𝑎_{1} 𝑎_{2} \dots 𝑎_{𝑘}) \in$ $𝑆_{𝑛}$ is the permutation that sends

𝑎_{1} \mapsto 𝑎_{2} \mapsto \dots \mapsto 𝑎_{𝑘} \mapsto 𝑎_{1}

and fixes every element of $[𝑛]$ outside ${𝑎_{1}, \dots, 𝑎_{𝑘}}$ . Its length is $𝑘$ , and we also call it a $𝑘$ -cycle. Two cycles $(𝑎_{1} \dots 𝑎_{𝑘})$ and $(𝑏_{1} \dots 𝑏_{𝑙})$ are disjoint if ${𝑎_{1}, \dots, 𝑎_{𝑘}} \cap$ ${𝑏_{1}, \dots, 𝑏_{𝑙}} =$ $\emptyset$ .

A $2$ -cycle is a transposition. A $𝑘$ -cycle has $𝑘$ names, one for each starting point: $(𝑎_{1} 𝑎_{2} \dots 𝑎_{𝑘}) =$ $(𝑎_{2} \dots 𝑎_{𝑘} 𝑎_{1})$ . Its inverse runs the loop backwards, ${(𝑎_{1} 𝑎_{2} \dots 𝑎_{𝑘})}^{- 1} =$ $(𝑎_{𝑘} \dots 𝑎_{2} 𝑎_{1})$ . Disjoint cycles $𝛾$ and $𝛿$ commute. Indeed, if $𝛾$ moves $𝑥$ , then $𝛿$ fixes both $𝑥$ and $𝛾 (𝑥)$ , so $𝛾 𝛿 (𝑥) =$ $𝛾 (𝑥) =$ $𝛿 𝛾 (𝑥)$ ; the case where $𝛿$ moves $𝑥$ is symmetric, and if neither moves $𝑥$ , both sides are $𝑥$ . Cycles that are not disjoint need not commute: $(1 2) (2 3) = (1 2 3)$ , while $(2 3) (1 2) = (1 3 2)$ .

Proposition 5.2.16 (Cycle decomposition). Let $𝜎 \in 𝑆_{𝑛}$ . For $𝑖 \in [𝑛]$ , the orbit of $𝑖$ under $𝜎$ is $𝑂 (𝑖) =$ ${𝜎^{𝑚} (𝑖) | 𝑚 \geq 0}$ .

(a)There is a least positive integer $𝑘$ with $𝜎^{𝑘} (𝑖) = 𝑖$ . For this $𝑘$ , the elements $𝑖,$ $𝜎 (𝑖),$ $\dots,$ $𝜎^{𝑘 - 1} (𝑖)$ are distinct, and they are all the elements of $𝑂 (𝑖)$ .
(b)Any two orbits are equal or disjoint.
(c) $𝜎$ is the product of the cycles $(𝑖 𝜎 (𝑖) \dots 𝜎^{𝑘 - 1} (𝑖))$ , one for each orbit with $𝑘 \geq 2$ elements, and these cycles are pairwise disjoint.

Proof.standard

Uses. Definition 5.2.15 (Cycle), Proposition 5.2.5 (Composition and inverses)

Techniques. Strong induction and well-ordering (Technique 5.2.12)

Hint 1. Follow

𝑖,

𝜎 (𝑖),

𝜎^{2} (𝑖),

\dots

. These lie in the finite set

[𝑛]

, so two of them coincide. Why does that force some positive power of

𝜎

to fix

𝑖

Hint 2. If

𝜎^{𝑝} (𝑖) = 𝜎^{𝑞} (𝑖)

with

𝑝 < 𝑞

, apply

𝜎^{- 1}

𝑝

times. Then take the least

𝑘

with

𝜎^{𝑘} (𝑖) = 𝑖

; a repetition among

𝑖, \dots, 𝜎^{𝑘 - 1} (𝑖)

would produce a smaller one.

Hint 3. For (b), if

𝑗 = 𝜎^{𝑝} (𝑖)

, show that

𝑖

is also of the form

𝜎^{𝑞} (𝑗)

. For (c), check the product at each

𝑥 \in [𝑛]

: only the cycle of the orbit of

𝑥

moves

𝑥

Sketch. Finiteness gives

𝜎^{𝑝} (𝑖) = 𝜎^{𝑞} (𝑖)

with

𝑝 < 𝑞

, and cancelling

𝜎^{𝑝}

gives

𝜎^{𝑞 - 𝑝} (𝑖) = 𝑖

. Taking

𝑘

least makes

𝑖, \dots, 𝜎^{𝑘 - 1} (𝑖)

distinct, and division with remainder shows that every

𝜎^{𝑚} (𝑖)

is among them. If

𝑗 = 𝜎^{𝑝} (𝑖)

, then

𝑖 = 𝜎^{𝑘 - 𝑝} (𝑗)

, so each of

𝑖, 𝑗

is in the orbit of the other and the orbits agree. On each orbit

𝜎

acts as the corresponding cycle, and cycles of different orbits move disjoint sets of points, so their product agrees with

𝜎

everywhere.

(a) The elements $𝑖,$ $𝜎 (𝑖),$ $𝜎^{2} (𝑖),$ $\dots$ all lie in the finite set $[𝑛]$ , so $𝜎^{𝑝} (𝑖) = 𝜎^{𝑞} (𝑖)$ for some $0 \leq 𝑝 < 𝑞$ . Applying $𝜎^{- 1}$ to both sides $𝑝$ times gives $𝜎^{𝑞 - 𝑝} (𝑖) = 𝑖$ , with $𝑞 - 𝑝 \geq 1$ . So the set of positive integers $𝑚$ with $𝜎^{𝑚} (𝑖) = 𝑖$ is nonempty, and by the well-ordering principle it has a least element $𝑘$ . If $𝜎^{𝑝} (𝑖) = 𝜎^{𝑞} (𝑖)$ with $0 \leq 𝑝 < 𝑞 \leq 𝑘 - 1$ , the same argument gives $𝜎^{𝑞 - 𝑝} (𝑖) = 𝑖$ with $0 < 𝑞 - 𝑝 < 𝑘$ , contradicting the choice of $𝑘$ . So $𝑖,$ $𝜎 (𝑖),$ $\dots,$ $𝜎^{𝑘 - 1} (𝑖)$ are distinct. Finally, let $𝑚 \geq 0$ , and write $𝑚 = 𝑞 𝑘 + 𝑟$ with $𝑞 \geq 0$ and $0 \leq 𝑟 < 𝑘$ . Since $𝜎^{𝑘} (𝑖) = 𝑖$ , applying $𝜎^{𝑘}$ $𝑞$ times to $𝑖$ gives $𝑖$ , so $𝜎^{𝑚} (𝑖) =$ $𝜎^{𝑟} (𝜎^{𝑞 𝑘} (𝑖)) =$ $𝜎^{𝑟} (𝑖)$ . Hence $𝑂 (𝑖) =$ ${𝑖, 𝜎 (𝑖), \dots, 𝜎^{𝑘 - 1} (𝑖)}$ .

(b) Let $𝑗 \in 𝑂 (𝑖)$ . By (a), $𝑗 = 𝜎^{𝑝} (𝑖)$ with $0 \leq 𝑝 < 𝑘$ , where $𝑘$ is as in (a). For every $𝑚 \geq 0$ , $𝜎^{𝑚} (𝑗) =$ $𝜎^{𝑚 + 𝑝} (𝑖) \in$ $𝑂 (𝑖)$ , so $𝑂 (𝑗) \subseteq 𝑂 (𝑖)$ . Also $𝜎^{𝑘 - 𝑝} (𝑗) =$ $𝜎^{𝑘} (𝑖) =$ $𝑖$ , so $𝑖 \in 𝑂 (𝑗)$ , and the same argument with the roles of $𝑖$ and $𝑗$ exchanged gives $𝑂 (𝑖) \subseteq 𝑂 (𝑗)$ . So $𝑂 (𝑗) = 𝑂 (𝑖)$ whenever $𝑗 \in 𝑂 (𝑖)$ . If two orbits $𝑂 (𝑖)$ and $𝑂 (𝑖^{'})$ have a common element $𝑗$ , then $𝑂 (𝑖) =$ $𝑂 (𝑗) =$ $𝑂 (𝑖^{'})$ .

(c) Let $𝑂_{1}, \dots, 𝑂_{𝑡}$ be the distinct orbits with at least two elements. For each $𝑠$ choose $𝑖_{𝑠} \in 𝑂_{𝑠}$ , let $𝑘_{𝑠} = | 𝑂_{𝑠} |$ , and let $𝛾_{𝑠} =$ $(𝑖_{𝑠} 𝜎 (𝑖_{𝑠}) \dots 𝜎^{𝑘_{𝑠} - 1} (𝑖_{𝑠}))$ . By (a), the entries of $𝛾_{𝑠}$ are distinct, so $𝛾_{𝑠}$ is a cycle, and the set of its entries is $𝑂_{𝑠}$ . By (b), $𝛾_{1}, \dots, 𝛾_{𝑡}$ are pairwise disjoint. We show that $𝜎 = 𝛾_{1} \dots 𝛾_{𝑡}$ by evaluating both sides at each $𝑥 \in [𝑛]$ .

If $𝑥$ lies in none of $𝑂_{1}, \dots, 𝑂_{𝑡}$ , then its orbit $𝑂 (𝑥)$ has one element, so $𝜎 (𝑥) = 𝑥$ ; and every $𝛾_{𝑠}$ fixes $𝑥$ , so the product does too. Otherwise $𝑥 \in 𝑂_{𝑠}$ for exactly one $𝑠$ , say $𝑥 = 𝜎^{𝑝} (𝑖_{𝑠})$ with $0 \leq 𝑝 < 𝑘_{𝑠}$ . Then $𝛾_{𝑠} (𝑥) =$ $𝜎^{𝑝 + 1} (𝑖_{𝑠}) =$ $𝜎 (𝑥)$ ; for $𝑝 = 𝑘_{𝑠} - 1$ this reads $𝛾_{𝑠} (𝑥) =$ $𝑖_{𝑠} =$ $𝜎^{𝑘_{𝑠}} (𝑖_{𝑠}) =$ $𝜎 (𝑥)$ . Every other $𝛾_{𝑠^{'}}$ fixes the elements of $𝑂_{𝑠}$ , in particular $𝑥$ and $𝜎 (𝑥)$ . So when we apply $𝛾_{1} \dots 𝛾_{𝑡}$ to $𝑥$ , the factors to the right of $𝛾_{𝑠}$ fix $𝑥$ , then $𝛾_{𝑠}$ sends $𝑥$ to $𝜎 (𝑥)$ , and the factors to the left of $𝛾_{𝑠}$ fix $𝜎 (𝑥)$ . Hence $(𝛾_{1} \dots 𝛾_{𝑡}) (𝑥) =$ $𝜎 (𝑥)$ . □

Writing $𝜎$ as a product of disjoint cycles, with the fixed points omitted, is cycle notation. To find it, start at the least element, follow it around its loop until it returns, and then start again at the least element not yet used. For example,

(\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{matrix}) = (1 3 4) (2 5), (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 5 & 3 & 4 \end{matrix}) = (1 2) (3 5 4) .

We write $𝑐 (𝜎)$ for the number of orbits of $𝜎$ , counting each fixed point as an orbit with one element. So $𝑐 (id) = 𝑛$ , and $𝑐 ((1 3 4) (2 5)) = 2$ in $𝑆_{5}$ , while $𝑐 ((1 2) (3 4 5)) = 3$ in $𝑆_{6}$ , the orbits being ${1, 2}$ , ${3, 4, 5}$ , and ${6}$ .

Lemma 5.2.17 (Cycles as products of transpositions). Let $𝑘 \geq 2$ and let $𝑎_{1}, \dots, 𝑎_{𝑘} \in [𝑛]$ be distinct. Then

(𝑎_{1} 𝑎_{2} \dots 𝑎_{𝑘}) = (𝑎_{1} 𝑎_{2}) (𝑎_{2} 𝑎_{3}) \dots (𝑎_{𝑘 - 1} 𝑎_{𝑘}) .

In particular, a $𝑘$ -cycle is a product of $𝑘 - 1$ transpositions.

Proof.routine

Uses. Definition 5.2.15 (Cycle), Definition 5.2.10 (Transposition)

Hint 1. Evaluate the right side at each point. The rightmost factor acts first.

Hint 2. Follow

𝑎_{𝑖}

for

𝑖 < 𝑘

: which factors move it, and in what order? Then follow

𝑎_{𝑘}

Sketch. For

𝑖 < 𝑘

, the factors to the right of

(𝑎_{𝑖} 𝑎_{𝑖 + 1})

do not involve

𝑎_{𝑖}

, that factor sends

𝑎_{𝑖}

𝑎_{𝑖 + 1}

, and the factors to its left do not involve

𝑎_{𝑖 + 1}

. The point

𝑎_{𝑘}

is sent to

𝑎_{𝑘 - 1}

, then

𝑎_{𝑘 - 2}

, and so on down to

𝑎_{1}

. Points outside

{𝑎_{1}, \dots, 𝑎_{𝑘}}

are fixed.

Let $𝜋 =$ $(𝑎_{1} 𝑎_{2}) (𝑎_{2} 𝑎_{3}) \dots (𝑎_{𝑘 - 1} 𝑎_{𝑘})$ . To compute $𝜋 (𝑥)$ we apply the factors from right to left, starting with $(𝑎_{𝑘 - 1} 𝑎_{𝑘})$ .

If $𝑥 \notin {𝑎_{1}, \dots, 𝑎_{𝑘}}$ , every factor fixes $𝑥$ , so $𝜋 (𝑥) = 𝑥$ . Let $1 \leq 𝑖 < 𝑘$ . The factors applied before $(𝑎_{𝑖} 𝑎_{𝑖 + 1})$ are the $(𝑎_{𝑗} 𝑎_{𝑗 + 1})$ with $𝑗 > 𝑖$ , which do not involve $𝑎_{𝑖}$ ; then $(𝑎_{𝑖} 𝑎_{𝑖 + 1})$ sends $𝑎_{𝑖}$ to $𝑎_{𝑖 + 1}$ ; and the factors applied after it are the $(𝑎_{𝑗} 𝑎_{𝑗 + 1})$ with $𝑗 < 𝑖$ , which do not involve $𝑎_{𝑖 + 1}$ . So $𝜋 (𝑎_{𝑖}) = 𝑎_{𝑖 + 1}$ . Finally, $(𝑎_{𝑘 - 1} 𝑎_{𝑘})$ sends $𝑎_{𝑘}$ to $𝑎_{𝑘 - 1}$ , then $(𝑎_{𝑘 - 2} 𝑎_{𝑘 - 1})$ sends it to $𝑎_{𝑘 - 2}$ , and so on, until $(𝑎_{1} 𝑎_{2})$ sends $𝑎_{2}$ to $𝑎_{1}$ . So $𝜋 (𝑎_{𝑘}) = 𝑎_{1}$ . Thus $𝜋$ agrees with $(𝑎_{1} \dots 𝑎_{𝑘})$ at every point. □

With Proposition 5.2.16, the lemma gives a second proof of Proposition 5.2.13, and this one counts. If the orbits of $𝜎$ with at least two elements have sizes $𝑘_{1}, \dots, 𝑘_{𝑡}$ , then $𝜎$ is a product of $\sum_{𝑠} (𝑘_{𝑠} - 1)$ transpositions. The orbits partition $[𝑛]$ and $𝑐 (𝜎) - 𝑡$ of them are fixed points, so $𝑘_{1} +$ $\dots +$ $𝑘_{𝑡} +$ $(𝑐 (𝜎) - 𝑡) =$ $𝑛$ , and the number of transpositions is

\sum_{𝑠 = 1}^{𝑡} (𝑘_{𝑠} - 1) = 𝑛 - 𝑐 (𝜎) .

For $𝜎 = (1 3 4) (2 5)$ this gives $𝜎 = (1 3) (3 4) (2 5)$ , with $5 - 2 = 3$ transpositions.

5.2.3Parity

A permutation has many factorizations into transpositions. Since ${(1 2)}^{2} = id$ , the identity is both the empty product and a product of two transpositions. A direct check shows that

(1 3) = (1 2) (2 3) (1 2),

so $(1 3)$ is a product of one transposition and also of three. Substituting this into $𝜎 = (1 3) (3 4) (2 5)$ writes that $𝜎$ as a product of five transpositions as well as of three. In each example the lengths have the same parity, and Theorem 5.2.18 below says that this always happens. Determinants depend on it: if some $𝜎$ were a product of an even number of transpositions and also of an odd number, then sorting the columns of $𝐷 (𝐞_{𝜎 (1)}, \dots, 𝐞_{𝜎 (𝑛)})$ in two ways would give both $𝐷 (𝐼_{𝑛})$ and $- 𝐷 (𝐼_{𝑛})$ . So $𝐷 (𝐼_{𝑛}) = 0$ whenever $1 + 1 \neq 0$ , and no determinant function would exist.

Theorem 5.2.18 (Parity is well defined). Let

𝜎 \in 𝑆_{𝑛}

, and suppose that

𝜎 = 𝜏_{1} \dots 𝜏_{𝑟}

and

𝜎 = 𝜏_{1}^{'} \dots 𝜏_{𝑠}^{'}

, where all

𝜏_{𝑖}

and

𝜏_{𝑗}^{'}

are transpositions. Then

𝑟

and

𝑠

are both even or both odd. In particular, the identity is not a product of an odd number of transpositions.

Intuition (Looking for an invariant). Comparing two factorizations directly is hopeless, since nothing relates the transpositions in one of them to those in the other. Instead, look for a quantity $𝑄 (𝜎)$ that is computed from $𝜎$ alone, without reference to any factorization, and that changes sign whenever we multiply by one more transposition:

𝑄 (𝜌 𝜏) = - 𝑄 (𝜌) for every 𝜌 \in 𝑆_{𝑛} and every transposition 𝜏 .

If $𝜎 = 𝜏_{1} \dots 𝜏_{𝑟}$ , applying this $𝑟$ times gives $𝑄 (𝜎) =$ ${(- 1)}^{𝑟} 𝑄 (id)$ . So if $𝑄$ takes values in $ℚ$ (or in any field in which $1 \neq - 1$ ) and $𝑄 (id) \neq 0$ , then ${(- 1)}^{𝑟} =$ $𝑄 (𝜎) / 𝑄 (id)$ is determined by $𝜎$ , and all factorizations of $𝜎$ have lengths of the same parity.

An obvious candidate is $𝑄 (𝜎) =$ $𝐷 (𝐞_{𝜎 (1)}, \dots, 𝐞_{𝜎 (𝑛)})$ for a determinant function $𝐷$ . It does change sign, by Proposition 5.1.10 and Remark 5.2.11. But we do not know yet that a determinant function exists for $𝑛 \geq 3$ , and the proof of existence in Section 5.3 uses this theorem. So we need a $𝑄$ that we can write down explicitly. Approach 1 below uses a product of differences, and Approach 2 counts the pairs that $𝜎$ puts out of order.

Technique 5.2.19 (Parity via an invariant). To show that the number of steps in a process has a determined parity, attach to each state a quantity that every step changes in a controlled way: it is multiplied by $- 1$ , or it changes by an odd integer. After $𝑟$ steps the quantity has been multiplied by ${(- 1)}^{𝑟}$ , or has changed by an amount of the same parity as $𝑟$ , so the parity of $𝑟$ is determined by the initial and final states, whichever steps were taken. The same idea shows that a state cannot be reached: find a quantity that every allowed move preserves and that differs between the two states.

Reach for it when a statement is about parity, or about which configurations can be reached by repeating moves of one kind: swaps, slides, rotations. The canonical example is Lemma 5.2.20, where a product of differences $𝑥_{𝑗} - 𝑥_{𝑖}$ changes sign under every transposition of the variables. Exercise 5.2.47 applies it to a classic puzzle, and Section 8.4 uses the sign of the determinant to separate rotations from reflections.

Used in 6 places and 1 practice exercise

Lemma 5.2.20, Lemma 5.2.22, Theorem 5.2.18, Exercise 5.2.47, Exercise 5.2.48, Exercise 8.4.44; 1 practice exercise.

Approach 1: a product of differences

For $𝐱 =$ $(𝑥_{1}, \dots, 𝑥_{𝑛}) \in$ $𝐹^{𝑛}$ , let

Δ (𝐱) = \prod_{1 \leq 𝑖 < 𝑗 \leq 𝑛} (𝑥_{𝑗} - 𝑥_{𝑖}) .

For instance, $Δ (𝑥_{1}, 𝑥_{2}, 𝑥_{3}) =$ $(𝑥_{2} - 𝑥_{1}) (𝑥_{3} - 𝑥_{1}) (𝑥_{3} - 𝑥_{2})$ . By Proposition 1.1.17, $Δ (𝐱) \neq 0$ exactly when the entries of $𝐱$ are distinct. (This product reappears as the Vandermonde determinant in Theorem 5.5.21.) For $𝜎 \in 𝑆_{𝑛}$ , write

𝐱^{𝜎} = (𝑥_{𝜎 (1)}, 𝑥_{𝜎 (2)}, \dots, 𝑥_{𝜎 (𝑛)})

for the vector whose $𝑖$ -th entry is $𝑥_{𝜎 (𝑖)}$ , that is, the entries of $𝐱$ rearranged by $𝜎$ .

Take $𝑛 = 3$ and $𝜏 = (1 2)$ . Then $𝐱^{𝜏} =$ $(𝑥_{2}, 𝑥_{1}, 𝑥_{3})$ , and

Δ (𝐱^{𝜏}) = (𝑥_{1} - 𝑥_{2}) (𝑥_{3} - 𝑥_{2}) (𝑥_{3} - 𝑥_{1}) = - (𝑥_{2} - 𝑥_{1}) (𝑥_{3} - 𝑥_{1}) (𝑥_{3} - 𝑥_{2}) = - Δ (𝐱) .

The factor $𝑥_{2} - 𝑥_{1}$ changed sign, and the two factors involving $𝑥_{3}$ traded places. The same happens for every transposition.

Lemma 5.2.20 (A transposition negates

Δ

). Let

𝑛 \geq 2

, let

𝜏 \in 𝑆_{𝑛}

be a transposition, and let

𝐱 \in 𝐹^{𝑛}

. Then

Δ (𝐱^{𝜏}) = - Δ (𝐱)

Proof.standard

Uses. Definition 5.2.10 (Transposition), Proposition 1.1.16 (Sign rules)

Techniques. Parity via an invariant (Technique 5.2.19)

Hint 1. Write

𝜏 = (𝑘 𝑙)

with

𝑘 < 𝑙

and

𝐲 = 𝐱^{𝜏}

, so

𝑦_{𝑘} = 𝑥_{𝑙}

𝑦_{𝑙} = 𝑥_{𝑘}

, and

𝑦_{𝑖} = 𝑥_{𝑖}

otherwise. Sort the factors

𝑦_{𝑗} - 𝑦_{𝑖}

Δ (𝐲)

according to how many of

𝑖, 𝑗

lie in

{𝑘, 𝑙}

Hint 2. Factors that avoid

𝑘

and

𝑙

are unchanged, and the factor for the pair

(𝑘, 𝑙)

changes sign. Every other factor involves exactly one of

𝑘, 𝑙

, together with a third index

𝑚

Hint 3. For each

𝑚 \notin {𝑘, 𝑙}

, multiply the two factors that involve

𝑚

. Show that their product is unchanged, separately in the cases

𝑚 < 𝑘

𝑘 < 𝑚 < 𝑙

, and

𝑚 > 𝑙

Sketch. With

𝜏 = (𝑘 𝑙)

𝑘 < 𝑙

, and

𝐲 = 𝐱^{𝜏}

, the factors of

Δ (𝐲)

not involving

𝑘

𝑙

are those of

Δ (𝐱)

, and

𝑦_{𝑙} -

𝑦_{𝑘} =

- (𝑥_{𝑙} - 𝑥_{𝑘})

. For each

𝑚 \notin {𝑘, 𝑙}

the two factors involving

𝑚

trade places, with two sign changes when

𝑘 < 𝑚 < 𝑙

, so their product is unchanged. So exactly one sign changes overall.

Write $𝜏 = (𝑘 𝑙)$ with $𝑘 < 𝑙$ , and let $𝐲 = 𝐱^{𝜏}$ . Then $𝑦_{𝑘} =$ $𝑥_{𝜏 (𝑘)} =$ $𝑥_{𝑙}$ , $𝑦_{𝑙} = 𝑥_{𝑘}$ , and $𝑦_{𝑖} = 𝑥_{𝑖}$ for $𝑖 \notin {𝑘, 𝑙}$ . Each factor $𝑦_{𝑗} - 𝑦_{𝑖}$ (where $𝑖 < 𝑗$ ) of $Δ (𝐲)$ belongs to exactly one of the following groups, and we compare each group with the corresponding factors of $Δ (𝐱)$ .

Factors with $𝑖, 𝑗 \notin {𝑘, 𝑙}$ . Here $𝑦_{𝑗} -$ $𝑦_{𝑖} =$ $𝑥_{𝑗} -$ $𝑥_{𝑖}$ .

The factor with $(𝑖, 𝑗) = (𝑘, 𝑙)$ . Here $𝑦_{𝑙} -$ $𝑦_{𝑘} =$ $𝑥_{𝑘} -$ $𝑥_{𝑙} =$ $- (𝑥_{𝑙} - 𝑥_{𝑘})$ .

The two factors involving a fixed $𝑚 \notin {𝑘, 𝑙}$ . These are the factors for the pairs ${𝑚, 𝑘}$ and ${𝑚, 𝑙}$ . Let $𝑃_{𝑚} (𝐱)$ be the product of the corresponding two factors of $Δ (𝐱)$ , each of the form $𝑥_{𝑗} - 𝑥_{𝑖}$ with $𝑖 < 𝑗$ .

If $𝑚 < 𝑘$ , then $𝑃_{𝑚} (𝐲) =$ $(𝑦_{𝑘} - 𝑦_{𝑚}) (𝑦_{𝑙} - 𝑦_{𝑚}) =$ $(𝑥_{𝑙} - 𝑥_{𝑚}) (𝑥_{𝑘} - 𝑥_{𝑚}) =$ $𝑃_{𝑚} (𝐱)$ .
If $𝑘 < 𝑚 < 𝑙$ , then $𝑃_{𝑚} (𝐲) =$ $(𝑦_{𝑚} - 𝑦_{𝑘}) (𝑦_{𝑙} - 𝑦_{𝑚}) =$ $(𝑥_{𝑚} - 𝑥_{𝑙}) (𝑥_{𝑘} - 𝑥_{𝑚})$ . Pulling a factor $- 1$ out of each difference (Proposition 1.1.16), this equals $(𝑥_{𝑙} - 𝑥_{𝑚}) (𝑥_{𝑚} - 𝑥_{𝑘}) =$ $𝑃_{𝑚} (𝐱)$ .
If $𝑚 > 𝑙$ , then $𝑃_{𝑚} (𝐲) =$ $(𝑦_{𝑚} - 𝑦_{𝑘}) (𝑦_{𝑚} - 𝑦_{𝑙}) =$ $(𝑥_{𝑚} - 𝑥_{𝑙}) (𝑥_{𝑚} - 𝑥_{𝑘}) =$ $𝑃_{𝑚} (𝐱)$ .

Multiplying over all groups and reordering factors by commutativity, $Δ (𝐲) = - Δ (𝐱)$ , as desired. □

Approach 2: counting inversions

The second approach measures how far the bottom row of $𝜎$ is from being sorted.

Definition 5.2.21 (Inversion). An inversion of

𝜎 \in 𝑆_{𝑛}

is a pair

(𝑖, 𝑗)

with

1 \leq 𝑖 < 𝑗 \leq 𝑛

and

𝜎 (𝑖) > 𝜎 (𝑗)

. We write

inv (𝜎)

for the number of inversions of

𝜎

In the bottom row of the two-line notation, an inversion is a pair of positions whose entries are out of order, the larger entry coming first. For $𝜎 = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{matrix})$ the inversions are

(1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5),

coming from $3 > 1$ , $3 > 2$ , $5 > 4$ , $5 > 1$ , $5 > 2$ , $4 > 1$ , and $4 > 2$ . So $inv (𝜎) = 7$ . The identity has no inversions, the adjacent transposition $(𝑘 𝑘 + 1)$ has exactly one, namely $(𝑘, 𝑘 + 1)$ , and the reversal $𝑖 \mapsto 𝑛 + 1 - 𝑖$ has all $𝑛 (𝑛 - 1) / 2$ pairs as inversions.

There is a picture. Join each $𝑖$ on a top row to $𝜎 (𝑖)$ on a bottom row by a straight segment. Two segments starting at $𝑖 < 𝑗$ cross exactly when they end in the opposite order, that is, when $𝜎 (𝑖) > 𝜎 (𝑗)$ . So $inv (𝜎)$ is the number of crossings, counted pair by pair. Figure 5.2.1 shows this for a permutation $𝜋 \in 𝑆_{6}$ with $8$ inversions, together with the effect of multiplying it by a transposition on the right.

Figure 5.2.1. Left:

𝜋 = (\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 2 & 6 & 1 & 5 & 3 \end{matrix})

, drawn by joining

𝑖

on the top row to

𝜋 (𝑖)

on the bottom row. Each crossing (dot) is an inversion. Right:

𝜋 (3 6)

, in which the strands from

3

and

6

(blue) have exchanged their endpoints. The two blue strands no longer cross. Of the strands that start between

3

and

6

, the one from

4

still crosses one blue strand, and the one from

5

has lost both of its crossings with blue strands. The strands from

1

and

2

cross as many blue strands as before. The total dropped by

1 + 2 = 3

, an odd number.

Lemma 5.2.22 (A transposition changes

inv

by an odd number). Let

𝜎 \in 𝑆_{𝑛}

and let

𝜏

be a transposition. Then

inv (𝜎 𝜏) - inv (𝜎)

is odd. If

𝜏

is an adjacent transposition, then

inv (𝜎 𝜏) =

inv (𝜎) \pm 1

Proof.standard

Uses. Definition 5.2.21 (Inversion), Remark 5.2.11 (Composing with a transposition)

Techniques. Parity via an invariant (Technique 5.2.19)

Hint 1. Write

𝜏 = (𝑘 𝑙)

with

𝑘 < 𝑙

. By Remark 5.2.11, the bottom row of

𝜎 𝜏

is that of

𝜎

with the entries in positions

𝑘

and

𝑙

interchanged. Which pairs of positions can change status?

Hint 2. The pair

(𝑘, 𝑙)

always changes status. For a third position

𝑚

, look at the two pairs that

𝑚

forms with

𝑘

and with

𝑙

, and consider

𝑚 < 𝑘

𝑘 < 𝑚 < 𝑙

, and

𝑚 > 𝑙

separately.

Hint 3. When

𝑘 < 𝑚 < 𝑙

, let

𝑁

and

𝑁^{'}

be the numbers of inverted pairs among the two pairs, before and after. Show that

𝑁 + 𝑁^{'} = 2

Sketch. Let

𝜏 = (𝑘 𝑙)

𝑘 < 𝑙

. The bottom rows of

𝜎

and

𝜎 𝜏

differ by interchanging the entries

𝑎_{𝑘}

and

𝑎_{𝑙}

at positions

𝑘

and

𝑙

. Pairs avoiding

𝑘

and

𝑙

keep their status, and

(𝑘, 𝑙)

flips. If

𝑚 < 𝑘

𝑚 > 𝑙

, the two pairs formed by

𝑚

with

𝑘

and

𝑙

make the same two comparisons, of

𝑎_{𝑚}

with

𝑎_{𝑘}

and with

𝑎_{𝑙}

, before and after. If

𝑘 < 𝑚 < 𝑙

, the number

𝑁

of inverted pairs among them becomes

2 - 𝑁

. So the total changes by

\pm 1

plus an even number. For adjacent

𝑘, 𝑙

there is no

𝑚

in between.

Write $𝜏 = (𝑘 𝑙)$ with $𝑘 < 𝑙$ , and let $𝑎_{𝑖} = 𝜎 (𝑖)$ and $𝑏_{𝑖} = (𝜎 𝜏) (𝑖)$ . By Remark 5.2.11, $𝑏_{𝑘} = 𝑎_{𝑙}$ , $𝑏_{𝑙} = 𝑎_{𝑘}$ , and $𝑏_{𝑖} = 𝑎_{𝑖}$ for $𝑖 \notin {𝑘, 𝑙}$ . For positions $𝑖 < 𝑗$ , say the pair $(𝑖, 𝑗)$ is inverted in $𝑎$ if $𝑎_{𝑖} > 𝑎_{𝑗}$ , and inverted in $𝑏$ if $𝑏_{𝑖} > 𝑏_{𝑗}$ ; so $inv (𝜎)$ and $inv (𝜎 𝜏)$ count the pairs inverted in $𝑎$ and in $𝑏$ . We compare them group by group.

Pairs $(𝑖, 𝑗)$ with $𝑖, 𝑗 \notin {𝑘, 𝑙}$ . These have the same entries in $𝑎$ and $𝑏$ , so the same status.

The pair $(𝑘, 𝑙)$ . It is inverted in $𝑏$ if and only if $𝑎_{𝑙} > 𝑎_{𝑘}$ , that is, if and only if it is not inverted in $𝑎$ . So this pair contributes $+ 1$ or $- 1$ to $inv (𝜎 𝜏) - inv (𝜎)$ .

The two pairs that a fixed $𝑚 \notin {𝑘, 𝑙}$ forms with $𝑘$ and with $𝑙$ . If $𝑚 < 𝑘$ , then in $𝑎$ the pair $(𝑚, 𝑘)$ is inverted if and only if $𝑎_{𝑚} > 𝑎_{𝑘}$ , and $(𝑚, 𝑙)$ if and only if $𝑎_{𝑚} > 𝑎_{𝑙}$ ; in $𝑏$ , the pair $(𝑚, 𝑘)$ is inverted if and only if $𝑎_{𝑚} > 𝑎_{𝑙}$ , and $(𝑚, 𝑙)$ if and only if $𝑎_{𝑚} > 𝑎_{𝑘}$ . These are the same two conditions, so the number of inverted pairs among the two is the same in $𝑎$ and in $𝑏$ . The case $𝑚 > 𝑙$ is the same with the inequalities reversed. If $𝑘 < 𝑚 < 𝑙$ , the pairs are $(𝑘, 𝑚)$ and $(𝑚, 𝑙)$ . In $𝑎$ they are inverted if and only if $𝑎_{𝑘} > 𝑎_{𝑚}$ and $𝑎_{𝑚} > 𝑎_{𝑙}$ , respectively, and in $𝑏$ if and only if $𝑎_{𝑙} > 𝑎_{𝑚}$ and $𝑎_{𝑚} > 𝑎_{𝑘}$ . Let $𝑁$ and $𝑁^{'}$ be the numbers of these pairs that are inverted in $𝑎$ and in $𝑏$ . Since the entries are distinct, exactly one of $𝑎_{𝑘} > 𝑎_{𝑚}$ and $𝑎_{𝑚} > 𝑎_{𝑘}$ holds, and exactly one of $𝑎_{𝑚} > 𝑎_{𝑙}$ and $𝑎_{𝑙} > 𝑎_{𝑚}$ holds. Hence $𝑁 + 𝑁^{'} = 2$ , and $𝑁^{'} - 𝑁 = 2 - 2 𝑁$ is even.

Adding up, $inv (𝜎 𝜏) - inv (𝜎)$ is $\pm 1$ plus a sum of even numbers, so it is odd. If $𝑙 = 𝑘 + 1$ , there is no $𝑚$ with $𝑘 < 𝑚 < 𝑙$ , so the pair $(𝑘, 𝑙)$ is the only group that contributes to $inv (𝜎 𝜏) - inv (𝜎)$ , and $inv (𝜎 𝜏) =$ $inv (𝜎) \pm 1$ . □

Two proofs of the theorem

Each lemma supplies the quantity $𝑄$ of Intuition (Looking for an invariant): $𝑄 (𝜎) = Δ (𝐱^{𝜎})$ for a fixed $𝐱$ with distinct entries, and $𝑄 (𝜎) =$ ${(- 1)}^{inv (𝜎)}$ .

Proof of Theorem 5.2.18 (via the product of differences).standard

Uses. Lemma 5.2.20 (A transposition negates $Δ$ ), Proposition 5.2.13 (Products of transpositions)

Techniques. Parity via an invariant (Technique 5.2.19)

Hint 1. Lemma 5.2.20 says what one transposition does to

Δ

. What does a product of

𝑟

transpositions do?

Hint 2. You will need that rearranging by

𝜌

and then by

𝜏

is rearranging by

𝜌 𝜏

: check that

{(𝐱^{𝜌})}^{𝜏} = 𝐱^{𝜌 𝜏}

Hint 3. Show

Δ (𝐱^{𝜎}) =

{(- 1)}^{𝑟} Δ (𝐱)

by induction on

𝑟

, then evaluate at a vector with

Δ (𝐱) \neq 0

over a field in which

1 \neq - 1

Sketch. Since

{(𝐱^{𝜌})}^{𝜏} = 𝐱^{𝜌 𝜏}

, Lemma 5.2.20 and induction on

𝑟

give

Δ (𝐱^{𝜎}) =

{(- 1)}^{𝑟} Δ (𝐱)

whenever

𝜎

is a product of

𝑟

transpositions. Take

𝐱 = (1, 2, \dots, 𝑛) \in ℚ^{𝑛}

, so

Δ (𝐱) \neq 0

. Then two factorizations of lengths

𝑟

and

𝑠

give

{(- 1)}^{𝑟} Δ (𝐱) =

{(- 1)}^{𝑠} Δ (𝐱)

, so

{(- 1)}^{𝑟} = {(- 1)}^{𝑠}

Let $𝐹$ be any field and $𝐱 \in 𝐹^{𝑛}$ . First, for $𝜌, 𝜋 \in 𝑆_{𝑛}$ , the $𝑖$ -th entry of ${(𝐱^{𝜌})}^{𝜋}$ is the $𝜋 (𝑖)$ -th entry of $𝐱^{𝜌}$ , which is $𝑥_{𝜌 (𝜋 (𝑖))}$ . So

{(𝐱^{𝜌})}^{𝜋} = 𝐱^{𝜌 𝜋} .

We show by induction on $𝑟 \geq 0$ that if $𝜎 = 𝜏_{1} \dots 𝜏_{𝑟}$ is a product of $𝑟$ transpositions, then $Δ (𝐱^{𝜎}) =$ ${(- 1)}^{𝑟} Δ (𝐱)$ . For $𝑟 = 0$ , $𝜎 = id$ and $𝐱^{id} = 𝐱$ . For $𝑟 \geq 1$ there is a transposition in $𝑆_{𝑛}$ , so $𝑛 \geq 2$ . Let $𝜌 = 𝜏_{1} \dots 𝜏_{𝑟 - 1}$ , so that $𝜎 = 𝜌 𝜏_{𝑟}$ and, by the induction hypothesis, $Δ (𝐱^{𝜌}) =$ ${(- 1)}^{𝑟 - 1} Δ (𝐱)$ . Applying Lemma 5.2.20 to the vector $𝐱^{𝜌}$ ,

Δ (𝐱^{𝜎}) = Δ ({(𝐱^{𝜌})}^{𝜏_{𝑟}}) = - Δ (𝐱^{𝜌}) = {(- 1)}^{𝑟} Δ (𝐱) .

Now take $𝐹 = ℚ$ and $𝐱 = (1, 2, \dots, 𝑛)$ . Then $Δ (𝐱) =$ $\prod_{𝑖 < 𝑗} (𝑗 - 𝑖)$ is a product of positive integers (the empty product $1$ if $𝑛 = 1$ ), so $Δ (𝐱) \neq 0$ . If $𝜎 =$ $𝜏_{1} \dots 𝜏_{𝑟} =$ $𝜏_{1}^{'} \dots 𝜏_{𝑠}^{'}$ , then

{(- 1)}^{𝑟} Δ (𝐱) = Δ (𝐱^{𝜎}) = {(- 1)}^{𝑠} Δ (𝐱),

and dividing by $Δ (𝐱)$ gives ${(- 1)}^{𝑟} = {(- 1)}^{𝑠}$ . Since $1 \neq - 1$ in $ℚ$ , the integers $𝑟$ and $𝑠$ have the same parity. □

Proof of Theorem 5.2.18 (by counting inversions).routine

Uses. Lemma 5.2.22 (A transposition changes $inv$ by an odd number), Definition 5.2.21 (Inversion)

Techniques. Parity via an invariant (Technique 5.2.19)

Hint 1. Start from the identity, which has no inversions, and multiply by the transpositions one at a time on the right.

Hint 2. Show by induction on

𝑟

that if

𝜎 = 𝜏_{1} \dots 𝜏_{𝑟}

, then

inv (𝜎) - 𝑟

is even.

Sketch.

inv (id) = 0

, and by Lemma 5.2.22 each additional factor on the right changes

inv

by an odd number. So

inv (𝜏_{1} \dots 𝜏_{𝑟}) \equiv 𝑟

modulo

2

, and any two factorizations of

𝜎

have lengths with the parity of

inv (𝜎)

We show by induction on $𝑟 \geq 0$ that if $𝜎 = 𝜏_{1} \dots 𝜏_{𝑟}$ with transpositions $𝜏_{𝑖}$ , then $inv (𝜎) - 𝑟$ is even. For $𝑟 = 0$ , $𝜎 = id$ and $inv (id) = 0$ . For $𝑟 \geq 1$ , let $𝜌 = 𝜏_{1} \dots 𝜏_{𝑟 - 1}$ , so that $𝜎 = 𝜌 𝜏_{𝑟}$ . Then

inv (𝜎) - 𝑟 = (inv (𝜎) - inv (𝜌)) + (inv (𝜌) - (𝑟 - 1)) - 1 .

The first term is odd by Lemma 5.2.22 and the second is even by the induction hypothesis, so the sum is even.

Hence if $𝜎 =$ $𝜏_{1} \dots 𝜏_{𝑟} =$ $𝜏_{1}^{'} \dots 𝜏_{𝑠}^{'}$ , both $𝑟$ and $𝑠$ have the same parity as $inv (𝜎)$ . □

Intuition (Comparing the two proofs). Both proofs follow Technique 5.2.19, and the invariants are closer than they look. With $𝐱 = (1, \dots, 𝑛)$ , the factor $𝜎 (𝑗) - 𝜎 (𝑖)$ of $Δ (𝐱^{𝜎})$ is negative exactly when $(𝑖, 𝑗)$ is an inversion, and the absolute values $| 𝜎 (𝑗) - 𝜎 (𝑖) |$ are the numbers $𝑗 - 𝑖$ in another order (as ${𝑖, 𝑗}$ runs over all two-element sets, so does ${𝜎 (𝑖), 𝜎 (𝑗)}$ ). So $Δ (𝐱^{𝜎}) =$ ${(- 1)}^{inv (𝜎)} Δ (𝐱)$ . The arguments are still different. Approach 1 never asks which factors are negative. Its lemma is an algebraic identity, valid for every vector over every field, and the sign falls out of regrouping. That is the pattern of Theorem 5.2.31 below, where an alternating function plays the role of $Δ$ . Approach 2 is combinatorial and gives a formula you can read off from the two-line notation. Its sharper statement for adjacent transpositions also shows that $inv (𝜎)$ is the number of interchanges of neighbors that sorting $𝜎$ requires (Exercise 5.2.43).

A third proof counts orbits instead. By Lemma 5.2.17, $𝜎$ is a product of $𝑛 - 𝑐 (𝜎)$ transpositions, and one can show that multiplying by a transposition changes $𝑐$ by exactly $1$ . Exercise 5.2.50 works this out.

5.2.4The sign of a permutation

Definition 5.2.23 (Sign of a permutation). A permutation

𝜎 \in 𝑆_{𝑛}

is even if it is a product of an even number of transpositions, and odd if it is a product of an odd number of transpositions. The sign of

𝜎

sgn (𝜎) = 1

𝜎

is even and

sgn (𝜎) = - 1

𝜎

is odd.

By Proposition 5.2.13 every permutation is even or odd, and by Theorem 5.2.18 it is not both. So $sgn$ is well defined, and

sgn (𝜎) = {(- 1)}^{𝑟} whenever 𝜎 is a product of 𝑟 transpositions .

The sign is an integer, $1$ or $- 1$ . When it multiplies an element of a field $𝐹$ , we read it as $1$ or $- 1$ in $𝐹$ ; if $1 + 1 = 0$ in $𝐹$ , these are the same element.

Corollary 5.2.24 (Formulas for the sign). Let $𝜎 \in 𝑆_{𝑛}$ .

(a) $sgn (𝜎) =$ ${(- 1)}^{inv (𝜎)}$ .
(b)For every field $𝐹$ and every $𝐱 \in 𝐹^{𝑛}$ , $Δ (𝐱^{𝜎}) =$ $sgn (𝜎) Δ (𝐱)$ . In particular,
$sgn (𝜎) = \prod_{1 \leq 𝑖 < 𝑗 \leq 𝑛} \frac{𝜎 (𝑗) - 𝜎 (𝑖)}{𝑗 - 𝑖} .$

Proof.routine

Uses. Theorem 5.2.18 (Parity is well defined), Definition 5.2.23 (Sign of a permutation), Proposition 5.2.13 (Products of transpositions)

Hint 1. Both proofs of Theorem 5.2.18 established more than the theorem. What did each show about a product of

𝑟

transpositions?

Hint 2. For the product formula, take

𝐹 = ℚ

and

𝐱 = (1, 2, \dots, 𝑛)

in (b).

Sketch. Write

𝜎 = 𝜏_{1} \dots 𝜏_{𝑟}

. The second proof showed

inv (𝜎) \equiv 𝑟

, and the first showed

Δ (𝐱^{𝜎}) =

{(- 1)}^{𝑟} Δ (𝐱)

for every

𝐱

over every field. Both say the claimed formulas, since

{(- 1)}^{𝑟} = sgn (𝜎)

. With

𝐱 = (1, \dots, 𝑛)

, (b) becomes the product formula after dividing by

Δ (𝐱) \neq 0

Write $𝜎 = 𝜏_{1} \dots 𝜏_{𝑟}$ with transpositions $𝜏_{𝑖}$ (Proposition 5.2.13), so that $sgn (𝜎) = {(- 1)}^{𝑟}$ .

(a) The second proof of Theorem 5.2.18 showed that $inv (𝜎) - 𝑟$ is even, so ${(- 1)}^{inv (𝜎)} =$ ${(- 1)}^{𝑟} =$ $sgn (𝜎)$ .

(b) The first proof showed that $Δ (𝐱^{𝜎}) =$ ${(- 1)}^{𝑟} Δ (𝐱)$ for every field $𝐹$ and every $𝐱 \in 𝐹^{𝑛}$ , which is the first claim. Taking $𝐹 = ℚ$ and $𝐱 = (1, 2, \dots, 𝑛)$ , we have $Δ (𝐱^{𝜎}) =$ $\prod_{𝑖 < 𝑗} (𝜎 (𝑗) - 𝜎 (𝑖))$ and $Δ (𝐱) =$ $\prod_{𝑖 < 𝑗} (𝑗 - 𝑖) \neq$ $0$ , and dividing gives the product formula. □

For $𝜎 =$ $(1 3 4) (2 5) =$ $(\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{matrix})$ we found $inv (𝜎) = 7$ and $𝜎 = (1 3) (3 4) (2 5)$ . Both give $sgn (𝜎) = - 1$ , as they must. Table 5.2.1 lists the signs of the six permutations of $[3]$ .

$𝜎$	Cycles	$inv (𝜎)$	$sgn (𝜎)$
$(\begin{matrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{matrix})$	$id$	$0$	$1$
$(\begin{matrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{matrix})$	$(2 3)$	$1$	$- 1$
$(\begin{matrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{matrix})$	$(1 2)$	$1$	$- 1$
$(\begin{matrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{matrix})$	$(1 2 3)$	$2$	$1$
$(\begin{matrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{matrix})$	$(1 3 2)$	$2$	$1$
$(\begin{matrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{matrix})$	$(1 3)$	$3$	$- 1$

Table 5.2.1. The six permutations of

[3]

. The three even ones are the identity and the two

3

-cycles; the three odd ones are the transpositions.

Proposition 5.2.25 (Multiplicativity of the sign).

(a) $sgn (id) = 1$ , and $sgn (𝜏) = - 1$ for every transposition $𝜏$ .
(b) $sgn (𝜎 𝜌) =$ $sgn (𝜎) sgn (𝜌)$ for all $𝜎, 𝜌 \in 𝑆_{𝑛}$ .
(c) $sgn (𝜎^{- 1}) = sgn (𝜎)$ for all $𝜎 \in 𝑆_{𝑛}$ .

Proof.routine

Uses. Definition 5.2.23 (Sign of a permutation), Theorem 5.2.18 (Parity is well defined), Proposition 5.2.5 (Composition and inverses)

Hint 1. Use the definition: factor

𝜎

and

𝜌

into transpositions. What is a factorization of

𝜎 𝜌

Hint 2. For (c), apply (b) to

𝜎 𝜎^{- 1} = id

Sketch. Concatenating factorizations of

𝜎

(with

𝑟

factors) and

𝜌

(with

𝑠

factors) gives one of

𝜎 𝜌

with

𝑟 + 𝑠

factors, so

sgn (𝜎 𝜌) =

{(- 1)}^{𝑟 + 𝑠}

. Then

sgn (𝜎) sgn (𝜎^{- 1}) =

sgn (id) =

1

(a) The identity is the product of zero transpositions, and a transposition is a product of one.

(b) Write $𝜎 = 𝜏_{1} \dots 𝜏_{𝑟}$ and $𝜌 = 𝜏_{1}^{'} \dots 𝜏_{𝑠}^{'}$ with transpositions $𝜏_{𝑖}, 𝜏_{𝑗}^{'}$ . Then $𝜎 𝜌 =$ $𝜏_{1} \dots 𝜏_{𝑟} 𝜏_{1}^{'} \dots 𝜏_{𝑠}^{'}$ is a product of $𝑟 + 𝑠$ transpositions, so by Definition 5.2.23 (which is legitimate by Theorem 5.2.18),

sgn (𝜎 𝜌) = {(- 1)}^{𝑟 + 𝑠} = {(- 1)}^{𝑟} {(- 1)}^{𝑠} = sgn (𝜎) sgn (𝜌) .

(c) By (b) and (a), $sgn (𝜎) sgn (𝜎^{- 1}) =$ $sgn (𝜎 𝜎^{- 1}) =$ $sgn (id) =$ $1$ . Multiplying both sides by $sgn (𝜎)$ and using ${sgn (𝜎)}^{2} = 1$ gives $sgn (𝜎^{- 1}) = sgn (𝜎)$ . □

With the definition through transpositions, (b) takes one line. Proving it directly from the inversion count is harder (Exercise 5.2.49). This is the reason to define $sgn$ through transpositions and to treat ${(- 1)}^{inv (𝜎)}$ as a way of computing it. In the language of Section 14.1, (b) says that $sgn$ is a homomorphism from $𝑆_{𝑛}$ to the group ${1, - 1}$ under multiplication. For example, if $𝜎$ is odd, then $𝜎^{- 1}$ is odd by (c), while $𝜎^{2}$ is even since $sgn (𝜎^{2}) =$ ${sgn (𝜎)}^{2} =$ $1$ .

Proposition 5.2.26 (Sign of a cycle). A

𝑘

-cycle has sign

{(- 1)}^{𝑘 - 1}

. More generally,

sgn (𝜎) =

{(- 1)}^{𝑛 - 𝑐 (𝜎)}

for every

𝜎 \in 𝑆_{𝑛}

, where

𝑐 (𝜎)

is the number of orbits of

𝜎

Proof.routine

Uses. Lemma 5.2.17 (Cycles as products of transpositions), Proposition 5.2.16 (Cycle decomposition), Definition 5.2.23 (Sign of a permutation)

Hint 1. Lemma 5.2.17 writes a

𝑘

-cycle as a product of how many transpositions?

Hint 2. For general

𝜎

, combine Proposition 5.2.16 with the count

𝑛 - 𝑐 (𝜎)

that follows Lemma 5.2.17.

Sketch. A

𝑘

-cycle is a product of

𝑘 - 1

transpositions. Decomposing

𝜎

into the cycles of its orbits and each cycle into transpositions writes

𝜎

as a product of

𝑛 - 𝑐 (𝜎)

transpositions.

By Lemma 5.2.17 a

𝑘

-cycle is a product of

𝑘 - 1

transpositions, so its sign is

{(- 1)}^{𝑘 - 1}

. For general

𝜎

, Proposition 5.2.16 and Lemma 5.2.17 write

𝜎

as a product of

𝑛 - 𝑐 (𝜎)

transpositions, as computed after Lemma 5.2.17. So

sgn (𝜎) =

{(- 1)}^{𝑛 - 𝑐 (𝜎)}

. □

So a cycle of odd length is an even permutation and a cycle of even length is odd. For $𝜎 = (1 3 4) (2 5) \in 𝑆_{5}$ , $𝑐 (𝜎) = 2$ , and again $sgn (𝜎) = {(- 1)}^{3} = - 1$ .

Proposition 5.2.27 (Half of all permutations are even). For

𝑛 \geq 2

, exactly

𝑛! / 2

elements of

𝑆_{𝑛}

are even and

𝑛! / 2

are odd. Equivalently,

\sum_{𝜎 \in 𝑆_{𝑛}} sgn (𝜎) = 0

Proof.routine

Uses. Proposition 5.2.8 (Reindexing sums over $𝑆_{𝑛}$ ), Proposition 5.2.25 (Multiplicativity of the sign), Proposition 5.2.4 (Counting permutations)

Hint 1. Find a bijection from the even permutations to the odd ones.

Hint 2. Multiply by a fixed transposition, say

(1 2)

, on the right.

Sketch.

𝜑 (𝜎) = 𝜎 (1 2)

is a bijection of

𝑆_{𝑛}

that reverses signs, and

𝜑 \circ 𝜑 = id

, so it restricts to a bijection from the even permutations to the odd ones. With

| 𝑆_{𝑛} | = 𝑛!

the two sets have

𝑛! / 2

elements each.

Let

𝜏 = (1 2)

, which exists since

𝑛 \geq 2

, and let

𝜑 : 𝑆_{𝑛} \to 𝑆_{𝑛}

𝜑 (𝜎) = 𝜎 𝜏

, a bijection by Proposition 5.2.8. By Proposition 5.2.25,

sgn (𝜑 (𝜎)) =

- sgn (𝜎)

, so

𝜑

maps the set

𝑆_{𝑛}^{+}

of even permutations into the set

𝑆_{𝑛}^{-}

of odd permutations, and

𝑆_{𝑛}^{-}

into

𝑆_{𝑛}^{+}

. Since

𝜏^{2} = id

, we have

𝜑 (𝜑 (𝜎)) = 𝜎

, so the restrictions

𝑆_{𝑛}^{+} \to 𝑆_{𝑛}^{-}

and

𝑆_{𝑛}^{-} \to 𝑆_{𝑛}^{+}

𝜑

are inverse to each other. Hence

| 𝑆_{𝑛}^{+} | = | 𝑆_{𝑛}^{-} |

. As every permutation is even or odd but not both,

| 𝑆_{𝑛}^{+} | +

| 𝑆_{𝑛}^{-} | =

𝑛!

by Proposition 5.2.4, so each set has

𝑛! / 2

elements, and

\sum_{𝜎} sgn (𝜎) =

| 𝑆_{𝑛}^{+} | -

| 𝑆_{𝑛}^{-} | =

0

. □

Pairing each $𝜎$ with $𝜎 (𝑘 𝑙)$ , which has the opposite sign, is the standard way to make the terms of a sum over $𝑆_{𝑛}$ cancel in pairs.

Exercise 5.2.28.routine

(a)Show that $𝜎^{2}$ and $𝜎 𝜌 𝜎^{- 1} 𝜌^{- 1}$ are even for all $𝜎, 𝜌 \in 𝑆_{𝑛}$ .
(b)Deduce that $(1 2)$ is not the square of any permutation, and that neither is $(1 2) (3 4 5)$ .

Solution.

Uses. Proposition 5.2.25 (Multiplicativity of the sign), Proposition 5.2.26 (Sign of a cycle)

Hint 1. Apply

sgn

and use Proposition 5.2.25. Values of

sgn

are numbers, so they commute.

Hint 2. For (b), compute the signs of the two given permutations.

Sketch.

sgn (𝜎^{2}) =

{sgn (𝜎)}^{2} =

1

, and

sgn (𝜎 𝜌 𝜎^{- 1} 𝜌^{- 1}) =

{sgn (𝜎)}^{2} {sgn (𝜌)}^{2} =

1

. A transposition is odd, and

(1 2) (3 4 5)

has sign

(- 1) (+ 1) = - 1

, so neither is a square.

(a) By Proposition 5.2.25, $sgn (𝜎^{2}) =$ ${sgn (𝜎)}^{2} =$ $1$ , and

sgn (𝜎 𝜌 𝜎^{- 1} 𝜌^{- 1}) = sgn (𝜎) sgn (𝜌) sgn (𝜎^{- 1}) sgn (𝜌^{- 1}) = {sgn (𝜎)}^{2} {sgn (𝜌)}^{2} = 1,

where we used $sgn (𝜎^{- 1}) = sgn (𝜎)$ and that the integers $sgn (𝜎), sgn (𝜌)$ commute.

(b) $sgn ((1 2)) = - 1$ , and by Proposition 5.2.26 and Proposition 5.2.25, $sgn ((1 2) (3 4 5)) =$ ${(- 1)}^{1} {(- 1)}^{2} =$ $- 1$ . By (a) every square has sign $1$ , so neither permutation is a square.

5.2.5Permutation matrices

We return to the values that survive in the expansion of Intuition (What the proof did, and where it leads). They are values of $𝐷$ at matrices whose columns are the standard basis vectors in some order.

Definition 5.2.29 (Permutation matrix). For

𝜎 \in 𝑆_{𝑛}

, the permutation matrix

𝐸_{𝜎} \in 𝐹^{𝑛 \times 𝑛}

is the matrix with columns

𝐞_{𝜎 (1)},

𝐞_{𝜎 (2)},

\dots,

𝐞_{𝜎 (𝑛)}

. That is, its

(𝑖, 𝑗)

entry is

1

𝑖 = 𝜎 (𝑗)

, and

0

otherwise.

Each column of $𝐸_{𝜎}$ is a standard basis vector, and since $𝜎$ is a bijection, each standard basis vector is exactly one of the columns. So $𝐸_{𝜎}$ has exactly one entry $1$ in each row and in each column, and zeros elsewhere. We have $𝐸_{id} = 𝐼_{𝑛}$ , and for a transposition $(𝑘 𝑙)$ , $𝐸_{(𝑘 𝑙)}$ is $𝐼_{𝑛}$ with columns $𝑘$ and $𝑙$ interchanged, which is the elementary matrix that interchanges rows $𝑘$ and $𝑙$ (Definition 3.2.2). For example, in $𝑆_{3}$ ,

𝐸_{(1 2 3)} = (\begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}), 𝐸_{(1 3 2)} = (\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix}), 𝐸_{(1 3)} = (\begin{matrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}) .

The first has columns $𝐞_{2}, 𝐞_{3}, 𝐞_{1}$ , because $(1 2 3)$ sends $1, 2, 3$ to $2, 3, 1$ .

Proposition 5.2.30 (Algebra of permutation matrices). Let $𝜎, 𝜌 \in 𝑆_{𝑛}$ , and let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ have columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ .

(a) $𝐴 𝐸_{𝜎}$ is the matrix with columns $𝐚_{𝜎 (1)},$ $\dots,$ $𝐚_{𝜎 (𝑛)}$ .
(b) $𝐸_{𝜎} 𝐸_{𝜌} = 𝐸_{𝜎 𝜌}$ .
(c) $𝐸_{𝜎}$ is invertible, and $𝐸_{𝜎}^{- 1} =$ $𝐸_{𝜎^{- 1}} =$ $𝐸_{𝜎}^{𝖳}$ .

Proof.routine

Uses. Definition 5.2.29 (Permutation matrix), Definition 2.4.1 (Matrix product), Definition 2.3.8 (Matrix–vector product), Definition 2.5.12 (Invertible), Definition 2.4.21 (Transpose)

Hint 1. Column

𝑗

of a product

𝐴 𝐵

𝐴

times column

𝑗

𝐵

, and

𝐴 𝐞_{𝑘}

is column

𝑘

𝐴

Hint 2. For (b), apply (a) with

𝐴 = 𝐸_{𝜎}

. For (c), use (b) with

𝜌 = 𝜎^{- 1}

, and compare entries for the transpose.

Sketch. Column

𝑗

𝐴 𝐸_{𝜎}

𝐴 𝐞_{𝜎 (𝑗)} =

𝐚_{𝜎 (𝑗)}

. With

𝐴 = 𝐸_{𝜎}

, column

𝑗

𝐸_{𝜎} 𝐸_{𝜌}

is column

𝜌 (𝑗)

𝐸_{𝜎}

, which is

𝐞_{𝜎 (𝜌 (𝑗))}

. Then

𝐸_{𝜎} 𝐸_{𝜎^{- 1}} =

𝐸_{id} =

𝐼_{𝑛} =

𝐸_{𝜎^{- 1}} 𝐸_{𝜎}

, and the

(𝑖, 𝑗)

entry of

𝐸_{𝜎}^{𝖳}

1

exactly when

𝑗 = 𝜎 (𝑖)

, that is,

𝑖 = 𝜎^{- 1} (𝑗)

(a) By Definition 2.4.1, column $𝑗$ of $𝐴 𝐸_{𝜎}$ is $𝐴$ times column $𝑗$ of $𝐸_{𝜎}$ , which is $𝐴 𝐞_{𝜎 (𝑗)} =$ $𝐚_{𝜎 (𝑗)}$ .

(b) Apply (a) with $𝐴 = 𝐸_{𝜎}$ , whose columns are $𝐞_{𝜎 (1)},$ $\dots,$ $𝐞_{𝜎 (𝑛)}$ : column $𝑗$ of $𝐸_{𝜎} 𝐸_{𝜌}$ is column $𝜌 (𝑗)$ of $𝐸_{𝜎}$ , which is $𝐞_{𝜎 (𝜌 (𝑗))} =$ $𝐞_{(𝜎 𝜌) (𝑗)}$ . So $𝐸_{𝜎} 𝐸_{𝜌} = 𝐸_{𝜎 𝜌}$ .

(c) By (b), $𝐸_{𝜎} 𝐸_{𝜎^{- 1}} =$ $𝐸_{id} =$ $𝐼_{𝑛}$ and $𝐸_{𝜎^{- 1}} 𝐸_{𝜎} =$ $𝐸_{id} =$ $𝐼_{𝑛}$ , so $𝐸_{𝜎^{- 1}}$ is a two-sided inverse of $𝐸_{𝜎}$ . For the transpose, the $(𝑖, 𝑗)$ entry of $𝐸_{𝜎}^{𝖳}$ is the $(𝑗, 𝑖)$ entry of $𝐸_{𝜎}$ , which is $1$ if $𝑗 = 𝜎 (𝑖)$ and $0$ otherwise. Since $𝑗 = 𝜎 (𝑖)$ if and only if $𝑖 = 𝜎^{- 1} (𝑗)$ , this is the $(𝑖, 𝑗)$ entry of $𝐸_{𝜎^{- 1}}$ . □

Part (a) says that multiplying by $𝐸_{𝜎}$ on the right rearranges the columns, putting column $𝜎 (𝑗)$ in position $𝑗$ . Multiplication of a vector on the left goes the other way: $𝐸_{𝜎} 𝐱 =$ $\sum_{𝑗} 𝑥_{𝑗} 𝐞_{𝜎 (𝑗)}$ , so the entry $𝑥_{𝑗}$ moves to position $𝜎 (𝑗)$ , and $𝐸_{𝜎} 𝐱 = 𝐱^{𝜎^{- 1}}$ in the notation of Approach 1: a product of differences. Keep the two descriptions apart.

Intuition. Write

𝜎 = 𝜏_{1} \dots 𝜏_{𝑟}

with transpositions

𝜏_{𝑖}

. By Proposition 5.2.30,

𝐴 𝐸_{𝜎} =

𝐴 𝐸_{𝜏_{1}} \dots 𝐸_{𝜏_{𝑟}}

, so the columns of

𝐴 𝐸_{𝜎}

are obtained from those of

𝐴

𝑟

interchanges of two columns, and each interchange negates

𝐷

. So

𝐷 (𝐴 𝐸_{𝜎}) =

{(- 1)}^{𝑟} 𝐷 (𝐴)

. The right side involves a factorization of

𝜎

, and Theorem 5.2.18 is exactly what makes it independent of the factorization.

Theorem 5.2.31 (Alternating functions and permutations). Let $𝐷 : 𝐹^{𝑛 \times 𝑛} \to 𝐹$ be multilinear and alternating, and let $𝜎 \in 𝑆_{𝑛}$ . For all $𝐚_{1}, \dots, 𝐚_{𝑛} \in 𝐹^{𝑛}$ ,

𝐷 (𝐚_{𝜎 (1)}, 𝐚_{𝜎 (2)}, \dots, 𝐚_{𝜎 (𝑛)}) = sgn (𝜎) 𝐷 (𝐚_{1}, 𝐚_{2}, \dots, 𝐚_{𝑛}) .

That is, $𝐷 (𝐴 𝐸_{𝜎}) =$ $sgn (𝜎) 𝐷 (𝐴)$ for every $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ . In particular $𝐷 (𝐸_{𝜎}) =$ $sgn (𝜎) 𝐷 (𝐼_{𝑛})$ , and if $𝐷$ is a determinant function, then $𝐷 (𝐸_{𝜎}) = sgn (𝜎)$ .

Proof.standard

Uses. Proposition 5.1.10 (Alternating implies antisymmetric), Proposition 5.2.13 (Products of transpositions), Definition 5.2.23 (Sign of a permutation), Proposition 5.2.30 (Algebra of permutation matrices)

Hint 1. Factor

𝜎

into transpositions and induct on the number

𝑟

of factors.

Hint 2. If

𝜎 = 𝜌 𝜏

with

𝜏 = (𝑘 𝑙)

, put

𝐛_{𝑖} = 𝐚_{𝜌 (𝑖)}

. How is the list

𝐚_{𝜎 (1)},

\dots,

𝐚_{𝜎 (𝑛)}

related to

𝐛_{1}, \dots, 𝐛_{𝑛}

Hint 3. It is the same list with the entries in positions

𝑘

and

𝑙

interchanged. Use Proposition 5.1.10.

Sketch. By induction on

𝑟

, if

𝜎

is a product of

𝑟

transpositions then

𝐷 (𝐚_{𝜎 (1)}, \dots) =

{(- 1)}^{𝑟} 𝐷 (𝐚_{1}, \dots)

: writing

𝜎 = 𝜌 𝜏

with

𝜏 = (𝑘 𝑙)

and

𝐛_{𝑖} = 𝐚_{𝜌 (𝑖)}

, the list

𝐚_{𝜎 (𝑖)} = 𝐛_{𝜏 (𝑖)}

𝐛

with positions

𝑘

and

𝑙

interchanged, which negates

𝐷

. Since

{(- 1)}^{𝑟} = sgn (𝜎)

, done. The matrix forms follow from Proposition 5.2.30.

We show by induction on $𝑟 \geq 0$ : if $𝜎$ is a product of $𝑟$ transpositions, then for all $𝐚_{1}, \dots, 𝐚_{𝑛} \in 𝐹^{𝑛}$ ,

𝐷 (𝐚_{𝜎 (1)}, \dots, 𝐚_{𝜎 (𝑛)}) = {(- 1)}^{𝑟} 𝐷 (𝐚_{1}, \dots, 𝐚_{𝑛}) .

For $𝑟 = 0$ , $𝜎 = id$ and there is nothing to prove. For $𝑟 \geq 1$ , write $𝜎 = 𝜌 𝜏$ , where $𝜌$ is a product of $𝑟 - 1$ transpositions and $𝜏 = (𝑘 𝑙)$ . Put $𝐛_{𝑖} = 𝐚_{𝜌 (𝑖)}$ for $𝑖 \in [𝑛]$ . Then $𝐚_{𝜎 (𝑖)} =$ $𝐚_{𝜌 (𝜏 (𝑖))} =$ $𝐛_{𝜏 (𝑖)}$ . Since $𝜏$ interchanges $𝑘$ and $𝑙$ and fixes everything else, the list $𝐛_{𝜏 (1)},$ $\dots,$ $𝐛_{𝜏 (𝑛)}$ is the list $𝐛_{1}, \dots, 𝐛_{𝑛}$ with the entries in positions $𝑘$ and $𝑙$ interchanged. By Proposition 5.1.10 and then the induction hypothesis,

𝐷 (𝐚_{𝜎 (1)}, \dots, 𝐚_{𝜎 (𝑛)}) = - 𝐷 (𝐛_{1}, \dots, 𝐛_{𝑛}) = - 𝐷 (𝐚_{𝜌 (1)}, \dots, 𝐚_{𝜌 (𝑛)}) = {(- 1)}^{𝑟} 𝐷 (𝐚_{1}, \dots, 𝐚_{𝑛}) .

By Proposition 5.2.13, every $𝜎$ is a product of some number $𝑟$ of transpositions, and ${(- 1)}^{𝑟} = sgn (𝜎)$ by Definition 5.2.23. This proves the displayed identity. By Proposition 5.2.30, the columns of $𝐴 𝐸_{𝜎}$ are $𝐚_{𝜎 (1)},$ $\dots,$ $𝐚_{𝜎 (𝑛)}$ , so $𝐷 (𝐴 𝐸_{𝜎}) =$ $sgn (𝜎) 𝐷 (𝐴)$ . Taking $𝐴 = 𝐼_{𝑛}$ gives $𝐷 (𝐸_{𝜎}) =$ $sgn (𝜎) 𝐷 (𝐼_{𝑛})$ , and a determinant function has $𝐷 (𝐼_{𝑛}) = 1$ . □

This answers the first question raised in Intuition (What the proof did, and where it leads): each surviving value is determined, $𝐷 (𝐞_{𝜎 (1)}, \dots, 𝐞_{𝜎 (𝑛)}) =$ $sgn (𝜎) 𝐷 (𝐼_{𝑛})$ , however we sort. Substituting into the expansion expresses $𝐷 (𝐴)$ as $𝐷 (𝐼_{𝑛})$ times a sum, over $𝜎 \in 𝑆_{𝑛}$ , of signed products of entries of $𝐴$ . Section 5.3 carries out this substitution (Theorem 5.3.3) and answers the second question by checking that the resulting formula satisfies the axioms.

Remark 5.2.32 (Two comments on the theorem). (1) If $1 + 1 = 0$ in $𝐹$ , then $sgn (𝜎) = 1$ in $𝐹$ for every $𝜎$ , and the theorem says that $𝐷 (𝐴 𝐸_{𝜎}) = 𝐷 (𝐴)$ : rearranging the columns does not change $𝐷$ at all. This matches Example 5.1.12, where interchanging two columns changed nothing over $𝔽_{2}$ .

(2) The induction in the proof does not use Theorem 5.2.18. So if we had, over $ℚ$ , a multilinear alternating $𝐷 : ℚ^{𝑛 \times 𝑛} \to ℚ$ with $𝐷 (𝐼_{𝑛}) \neq 0$ , constructed without permutations, then two factorizations of $𝜎$ of lengths $𝑟$ and $𝑠$ would give ${(- 1)}^{𝑟} 𝐷 (𝐼_{𝑛}) =$ $𝐷 (𝐸_{𝜎}) =$ ${(- 1)}^{𝑠} 𝐷 (𝐼_{𝑛})$ , a third proof of Theorem 5.2.18. In this sense the parity theorem is exactly what the existence of determinants requires. The construction in Section 5.3 uses $sgn$ , so it cannot be used this way (Exercise 5.2.38).

Exercises

Exercise 5.2.33.routine Let

𝜎 = (\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 6 & 1 & 3 & 4 \end{matrix}), 𝜏 = (1 4) (2 6) \in 𝑆_{6} .

Compute $𝜎 𝜏$ , $𝜏 𝜎$ , and $𝜎^{- 1}$ , in two-line and in cycle notation, and find the signs of $𝜎$ , $𝜏$ , $𝜎 𝜏$ , $𝜏 𝜎$ , and $𝜎^{- 1}$ .

Solution.

Uses. Proposition 5.2.16 (Cycle decomposition), Proposition 5.2.26 (Sign of a cycle), Proposition 5.2.25 (Multiplicativity of the sign)

Hint 1. Write

𝜏

in two-line notation first. For

𝜎 𝜏

, apply

𝜏

first.

Hint 2. For the signs, use the cycle notation and Proposition 5.2.26, and check the answers against Proposition 5.2.25.

Sketch.

𝜎 = (1 2 5 3 6 4)

and

𝜏 = (\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 6 & 3 & 1 & 5 & 2 \end{matrix})

. Then

𝜎 𝜏 =

(\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 4 & 6 & 2 & 3 & 5 \end{matrix}) =

(2 4) (3 6 5)

𝜏 𝜎 =

(\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 5 & 2 & 4 & 3 & 1 \end{matrix}) =

(1 6) (2 5 3)

, and

𝜎^{- 1} =

(\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 5 & 6 & 2 & 3 \end{matrix}) =

(1 4 6 3 5 2)

. The signs are

- 1, 1, - 1, - 1, - 1

Following $1 \mapsto 2 \mapsto 5 \mapsto 3 \mapsto 6 \mapsto 4 \mapsto 1$ , we get $𝜎 = (1 2 5 3 6 4)$ , a $6$ -cycle. The permutation $𝜏$ interchanges $1, 4$ and $2, 6$ , so $𝜏 = (\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 6 & 3 & 1 & 5 & 2 \end{matrix})$ .

$𝜎 𝜏$ . Applying $𝜎$ to the bottom row $4, 6, 3, 1, 5, 2$ of $𝜏$ gives $𝜎 (4),$ $𝜎 (6),$ $𝜎 (3),$ $𝜎 (1),$ $𝜎 (5),$ $𝜎 (2) =$ $1,$ $4,$ $6,$ $2,$ $3,$ $5$ . So $𝜎 𝜏 =$ $(\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 4 & 6 & 2 & 3 & 5 \end{matrix}) =$ $(2 4) (3 6 5)$ .

$𝜏 𝜎$ . Applying $𝜏$ to the bottom row $2, 5, 6, 1, 3, 4$ of $𝜎$ gives $6, 5, 2, 4, 3, 1$ . So $𝜏 𝜎 =$ $(\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 5 & 2 & 4 & 3 & 1 \end{matrix}) =$ $(1 6) (2 5 3)$ .

$𝜎^{- 1}$ . Running the cycle of $𝜎$ backwards, $𝜎^{- 1} =$ $(4 6 3 5 2 1) =$ $(1 4 6 3 5 2)$ , which in two-line notation is $(\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 5 & 6 & 2 & 3 \end{matrix})$ .

Signs. By Proposition 5.2.26, a $6$ -cycle has sign ${(- 1)}^{5} = - 1$ , so $sgn (𝜎) =$ $sgn (𝜎^{- 1}) =$ $- 1$ . Also $sgn (𝜏) =$ $(- 1) (- 1) =$ $1$ , $sgn (𝜎 𝜏) =$ $(- 1) \cdot$ $1 =$ $- 1$ (a transposition times a $3$ -cycle), and $sgn (𝜏 𝜎) = - 1$ in the same way. These agree with Proposition 5.2.25: $sgn (𝜎 𝜏) =$ $sgn (𝜏 𝜎) =$ $sgn (𝜎) sgn (𝜏) =$ $- 1$ .

Exercise 5.2.34.routine

(a)Let $1 \leq 𝑘 < 𝑙 \leq 𝑛$ . Show that $inv ((𝑘 𝑙)) =$ $2 (𝑙 - 𝑘) -$ $1$ .
(b)Find $inv$ of the $𝑛$ -cycle $(1 2 \dots 𝑛)$ , and check the result against Proposition 5.2.26.
(c)Let $𝜔 \in 𝑆_{𝑛}$ be the reversal, $𝜔 (𝑖) = 𝑛 + 1 - 𝑖$ . Compute $sgn (𝜔)$ in two ways, from $inv (𝜔)$ and from the cycle notation of $𝜔$ , and deduce that ${(- 1)}^{𝑛 (𝑛 - 1) / 2} =$ ${(- 1)}^{⌊ 𝑛 / 2 ⌋}$ . For which $𝑛$ is $𝜔$ even?

Solution.

Uses. Definition 5.2.21 (Inversion), Corollary 5.2.24 (Formulas for the sign), Proposition 5.2.26 (Sign of a cycle), Proposition 5.2.25 (Multiplicativity of the sign)

Hint 1. In (a), the bottom row of

(𝑘 𝑙)

1,

\dots,

𝑘 -

1,

𝑙,

𝑘 +

1,

\dots,

𝑙 -

1,

𝑘,

𝑙 +

1,

\dots,

𝑛

. Only pairs involving position

𝑘

or position

𝑙

can be inverted.

Hint 2. In (b), the bottom row is

2, 3, \dots, 𝑛, 1

. In (c), every pair is inverted, and

𝜔

is a product of the disjoint transpositions

(𝑖 𝑛 + 1 - 𝑖)

for

𝑖 < (𝑛 + 1) / 2

Sketch. (a) Position

𝑘

(entry

𝑙

) is inverted with each of the

𝑙 - 𝑘

later positions up to

𝑙

, and position

𝑙

(entry

𝑘

) with each of the

𝑙 - 𝑘 - 1

positions strictly between. (b) The inversions are

(𝑖, 𝑛)

for

𝑖 < 𝑛

, so

inv = 𝑛 - 1

and the sign is

{(- 1)}^{𝑛 - 1}

. (c)

inv (𝜔) =

𝑛 (𝑛 - 1) / 2

, while

𝜔

is a product of

⌊ 𝑛 / 2 ⌋

disjoint transpositions. So

𝜔

is even exactly when

𝑛 \equiv 0

1

modulo

4

(a) The bottom row of $(𝑘 𝑙)$ has $𝑙$ in position $𝑘$ , $𝑘$ in position $𝑙$ , and $𝑖$ in position $𝑖$ otherwise. A pair of positions avoiding $𝑘$ and $𝑙$ has entries $𝑖 < 𝑗$ in order. Let $𝑚 \notin {𝑘, 𝑙}$ . If $𝑚 < 𝑘$ , its entry $𝑚$ is smaller than both $𝑙$ and $𝑘$ , so neither pair $(𝑚, 𝑘)$ nor $(𝑚, 𝑙)$ is inverted. If $𝑚 > 𝑙$ , its entry $𝑚$ is larger than both, so again neither is inverted. If $𝑘 < 𝑚 < 𝑙$ , then $(𝑘, 𝑚)$ is inverted since $𝑙 > 𝑚$ , and $(𝑚, 𝑙)$ is inverted since $𝑚 > 𝑘$ . Finally, $(𝑘, 𝑙)$ is inverted since $𝑙 > 𝑘$ . So the inversions are $(𝑘, 𝑚)$ and $(𝑚, 𝑙)$ for the $𝑙 - 𝑘 - 1$ values of $𝑚$ strictly between $𝑘$ and $𝑙$ , together with $(𝑘, 𝑙)$ : in total $2 (𝑙 - 𝑘 - 1) +$ $1 =$ $2 (𝑙 - 𝑘) -$ $1$ .

(b) The bottom row of $(1 2 \dots 𝑛)$ is $2, 3, \dots, 𝑛, 1$ . The entries $2, \dots, 𝑛$ are in increasing order, and each is larger than the final entry $1$ . So the inversions are $(𝑖, 𝑛)$ for $1 \leq 𝑖 \leq 𝑛 - 1$ , and $inv = 𝑛 - 1$ . By Corollary 5.2.24 the sign is ${(- 1)}^{𝑛 - 1}$ , which is the sign of an $𝑛$ -cycle in Proposition 5.2.26.

(c) The bottom row of $𝜔$ is $𝑛, 𝑛 - 1, \dots, 1$ , so every pair $𝑖 < 𝑗$ is an inversion and $inv (𝜔) =$ $𝑛 (𝑛 - 1) / 2$ . Hence $sgn (𝜔) =$ ${(- 1)}^{𝑛 (𝑛 - 1) / 2}$ by Corollary 5.2.24. On the other hand, $𝜔$ interchanges $𝑖$ and $𝑛 + 1 - 𝑖$ , so it is the product of the disjoint transpositions $(𝑖 𝑛 + 1 - 𝑖)$ for $1 \leq 𝑖 < (𝑛 + 1) / 2$ ; there are $⌊ 𝑛 / 2 ⌋$ of them (the middle point is fixed when $𝑛$ is odd). So $sgn (𝜔) =$ ${(- 1)}^{⌊ 𝑛 / 2 ⌋}$ by Proposition 5.2.25, and the two expressions agree. Now $⌊ 𝑛 / 2 ⌋$ is even exactly when $𝑛 \equiv 0$ or $1$ modulo $4$ , so $𝜔$ is even exactly for these $𝑛$ . For example $𝜔$ is odd in $𝑆_{2}$ and $𝑆_{3}$ , even in $𝑆_{4}$ and $𝑆_{5}$ , and odd in $𝑆_{6}$ and $𝑆_{7}$ .

Exercise 5.2.35.routine Find the error in the following argument.

Claim. If $𝜎 \in 𝑆_{𝑛}$ and $𝜏$ is a transposition, then $inv (𝜎 𝜏) =$ $inv (𝜎) \pm 1$ .

Proof. By Remark 5.2.11, the bottom row of $𝜎 𝜏$ is that of $𝜎$ with two entries interchanged. Interchanging two entries changes their relative order and nothing else. So exactly one pair of positions changes from inverted to not inverted, or the other way.

Solution.

Uses. Lemma 5.2.22 (A transposition changes $inv$ by an odd number), Exercise 5.2.34

Hint 1. Test the claim with

𝜎 = id

and

𝜏 = (1 3)

Hint 2. Look at an entry that sits between the two interchanged positions. Is it still on the same side of each interchanged entry?

Sketch. The claim fails for

𝜎 = id

𝜏 = (1 3)

inv ((1 3)) = 3

. The error is “nothing else”: every entry between the two interchanged positions also changes its order relative to both interchanged entries. The correct statement is Lemma 5.2.22: the change is odd, and it is

\pm 1

for adjacent transpositions.

The claim is false:

inv (id) = 0

, while the bottom row of

(1 3)

3, 2, 1

, which has

3

inversions. The error is the sentence “changes their relative order and nothing else”. Think of an inversion as a pair of entries that appear in the wrong order, and interchange the entries

𝑎_{𝑘}

and

𝑎_{𝑙}

in positions

𝑘 < 𝑙

. An entry

𝑎_{𝑚}

with

𝑚 < 𝑘

𝑚 > 𝑙

stays on the same side of both

𝑎_{𝑘}

and

𝑎_{𝑙}

, so its pairs with them keep their status. But an entry

𝑎_{𝑚}

with

𝑘 < 𝑚 < 𝑙

used to stand to the right of

𝑎_{𝑘}

and to the left of

𝑎_{𝑙}

, and afterwards stands to the left of

𝑎_{𝑘}

and to the right of

𝑎_{𝑙}

. So the relative order of

𝑎_{𝑚}

with both interchanged entries changes, and the pairs

{𝑎_{𝑚}, 𝑎_{𝑘}}

and

{𝑎_{𝑚}, 𝑎_{𝑙}}

both change status. In the example, the entry

2

in the middle forms an inversion with

3

and with

1

afterwards, and with neither before. Each such

𝑚

changes the count by

- 2

0

, or

2

, which is why the total change is always odd (Lemma 5.2.22). When

𝑙 = 𝑘 + 1

there is no entry in between, and then the claim is true.

Exercise 5.2.36.standard Let $𝜎 \in 𝑆_{𝑛}$ .

(a)Let $𝐴 \in 𝐹^{𝑛 \times 𝑚}$ . Show that row $𝜎 (𝑖)$ of $𝐸_{𝜎} 𝐴$ is row $𝑖$ of $𝐴$ , for every $𝑖$ .
(b)Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ . Show that the $(𝜎 (𝑖), 𝜎 (𝑗))$ entry of $𝐸_{𝜎} 𝐴 𝐸_{𝜎}^{𝖳}$ is $𝑎_{𝑖 𝑗}$ , for all $𝑖, 𝑗$ .
(c)The adjacency matrix of a graph with vertices $1, \dots, 𝑛$ is the $𝑛 \times 𝑛$ matrix with $(𝑖, 𝑗)$ entry $1$ if $𝑖$ and $𝑗$ are joined by an edge, and $0$ otherwise. Explain what (b) says about adjacency matrices when the vertices of a graph are renamed by $𝜎$ .

Solution.

Uses. Definition 5.2.29 (Permutation matrix), Definition 2.4.1 (Matrix product), Proposition 5.2.30 (Algebra of permutation matrices)

Hint 1. Compute the

(𝜎 (𝑖), 𝑘)

entry of

𝐸_{𝜎} 𝐴

from the definition of the product:

\sum_{𝑗} {(𝐸_{𝜎})}_{𝜎 (𝑖) 𝑗} 𝑎_{𝑗 𝑘}

. Which

𝑗

gives a nonzero term?

Hint 2. For (b),

𝐸_{𝜎}^{𝖳} = 𝐸_{𝜎^{- 1}}

, so by Proposition 5.2.30 the columns of

𝐴 𝐸_{𝜎}^{𝖳}

are the columns of

𝐴

rearranged. Combine this with (a).

Sketch.

{(𝐸_{𝜎})}_{𝜎 (𝑖) 𝑗} = 1

exactly when

𝑗 = 𝑖

, so

{(𝐸_{𝜎} 𝐴)}_{𝜎 (𝑖) 𝑘} =

𝑎_{𝑖 𝑘}

. Dually, column

𝜎 (𝑗)

𝐴 𝐸_{𝜎^{- 1}}

is column

𝑗

𝐴

. Together,

{(𝐸_{𝜎} 𝐴 𝐸_{𝜎}^{𝖳})}_{𝜎 (𝑖) 𝜎 (𝑗)} =

𝑎_{𝑖 𝑗}

: renaming vertex

𝑖

𝜎 (𝑖)

replaces the adjacency matrix

𝐴

𝐸_{𝜎} 𝐴 𝐸_{𝜎}^{𝖳}

(a) For every $𝑘$ , the $(𝜎 (𝑖), 𝑘)$ entry of $𝐸_{𝜎} 𝐴$ is $\sum_{𝑗 = 1}^{𝑛} {(𝐸_{𝜎})}_{𝜎 (𝑖) 𝑗} 𝑎_{𝑗 𝑘}$ . By Definition 5.2.29, ${(𝐸_{𝜎})}_{𝜎 (𝑖) 𝑗} = 1$ if $𝜎 (𝑖) = 𝜎 (𝑗)$ , that is, if $𝑗 = 𝑖$ , and $0$ otherwise. So the sum is $𝑎_{𝑖 𝑘}$ , and row $𝜎 (𝑖)$ of $𝐸_{𝜎} 𝐴$ is row $𝑖$ of $𝐴$ .

(b) Let $𝐵 =$ $𝐴 𝐸_{𝜎}^{𝖳} =$ $𝐴 𝐸_{𝜎^{- 1}}$ (Proposition 5.2.30). By part (a) of that proposition, column $𝑝$ of $𝐵$ is column $𝜎^{- 1} (𝑝)$ of $𝐴$ ; with $𝑝 = 𝜎 (𝑗)$ , column $𝜎 (𝑗)$ of $𝐵$ is column $𝑗$ of $𝐴$ , so $𝑏_{𝑖 𝜎 (𝑗)} = 𝑎_{𝑖 𝑗}$ . By (a) applied to $𝐵$ , row $𝜎 (𝑖)$ of $𝐸_{𝜎} 𝐵$ is row $𝑖$ of $𝐵$ . Hence the $(𝜎 (𝑖), 𝜎 (𝑗))$ entry of $𝐸_{𝜎} 𝐴 𝐸_{𝜎}^{𝖳} =$ $𝐸_{𝜎} 𝐵$ is $𝑏_{𝑖 𝜎 (𝑗)} = 𝑎_{𝑖 𝑗}$ .

(c) Rename each vertex $𝑖$ as $𝜎 (𝑖)$ . In the renamed graph, $𝜎 (𝑖)$ and $𝜎 (𝑗)$ are joined exactly when $𝑖$ and $𝑗$ were joined in the original, so its adjacency matrix $𝐴^{'}$ satisfies $𝑎_{𝜎 (𝑖) 𝜎 (𝑗)}^{'} =$ $𝑎_{𝑖 𝑗}$ for all $𝑖, 𝑗$ . Since $𝜎$ is a bijection, every entry of $𝐴^{'}$ is of this form, so by (b), $𝐴^{'} =$ $𝐸_{𝜎} 𝐴 𝐸_{𝜎}^{𝖳} =$ $𝐸_{𝜎} 𝐴 𝐸_{𝜎}^{- 1}$ . Renaming the vertices replaces the adjacency matrix by a similar matrix, conjugated by a permutation matrix.

Exercise 5.2.37.standard Prove or disprove each statement, for all $𝑛$ and all $𝜎, 𝜏 \in 𝑆_{𝑛}$ .

(a)The product of two odd permutations is odd.
(b)If $𝜎^{2} = id$ , then $𝜎$ is the identity or a transposition.
(c) $inv (𝜎^{- 1}) = inv (𝜎)$ .
(d) $inv (𝜎 𝜏) =$ $inv (𝜎) +$ $inv (𝜏)$ .
(e) $sgn (𝜎 𝜏 𝜎^{- 1}) =$ $sgn (𝜏)$ .

Solution.

Uses. Proposition 5.2.25 (Multiplicativity of the sign), Definition 5.2.21 (Inversion)

Hint 1. (a) and (d): try

𝜎 = 𝜏 = (1 2)

. (b): try two disjoint transpositions.

Hint 2. (c): an inversion of

𝜎

is a pair

𝑖 < 𝑗

with

𝜎 (𝑖) > 𝜎 (𝑗)

. Rename

𝑝 = 𝜎 (𝑗)

and

𝑞 = 𝜎 (𝑖)

, and see what

𝜎^{- 1}

does to

𝑝 < 𝑞

Hint 3. (e): use Proposition 5.2.25.

Sketch. (a) False:

{(1 2)}^{2} = id

is even. (b) False for

𝑛 \geq 4

(1 2) (3 4)

. (c) True:

(𝑖, 𝑗) \mapsto

(𝜎 (𝑗), 𝜎 (𝑖))

is a bijection from the inversions of

𝜎

to those of

𝜎^{- 1}

. (d) False:

inv ({(1 2)}^{2}) = 0 \neq 2

. (e) True, by multiplicativity.

(a) False. $(1 2)$ is odd, but $(1 2) (1 2) = id$ is even. In fact the product of two odd permutations is always even, by Proposition 5.2.25.

(b) False when $𝑛 \geq 4$ . For $𝜎 = (1 2) (3 4)$ , the two disjoint transpositions commute, so $𝜎^{2} = {(1 2)}^{2} {(3 4)}^{2} = id$ , but $𝜎$ moves four points, so it is neither the identity nor a transposition. (For $𝑛 \leq 3$ the statement is true, as Table 5.2.1 shows for $𝑛 = 3$ .)

(c) True. Let $(𝑖, 𝑗)$ be an inversion of $𝜎$ , so $𝑖 < 𝑗$ and $𝜎 (𝑖) > 𝜎 (𝑗)$ . Put $𝑝 = 𝜎 (𝑗)$ and $𝑞 = 𝜎 (𝑖)$ . Then $𝑝 < 𝑞$ and $𝜎^{- 1} (𝑝) =$ $𝑗 >$ $𝑖 =$ $𝜎^{- 1} (𝑞)$ , so $(𝑝, 𝑞)$ is an inversion of $𝜎^{- 1}$ . The same argument applied to $𝜎^{- 1}$ , whose inverse is $𝜎$ , sends an inversion $(𝑝, 𝑞)$ of $𝜎^{- 1}$ to the inversion $(𝜎^{- 1} (𝑞), 𝜎^{- 1} (𝑝))$ of $𝜎$ , and the two maps are inverse to each other. So they are bijections, and $inv (𝜎^{- 1}) = inv (𝜎)$ .

(d) False. With $𝜎 = 𝜏 = (1 2)$ , $inv (𝜎 𝜏) =$ $inv (id) =$ $0$ but $inv (𝜎) + inv (𝜏) = 2$ . Only the parities add (Corollary 5.2.24 and Proposition 5.2.25).

(e) True. By Proposition 5.2.25, $sgn (𝜎 𝜏 𝜎^{- 1}) =$ $sgn (𝜎) sgn (𝜏) sgn (𝜎^{- 1}) =$ ${sgn (𝜎)}^{2} sgn (𝜏) =$ $sgn (𝜏)$ .

Exercise 5.2.38.standard Find the errors in the following argument.

Claim. Theorem 5.2.18.

Proof. Let $det$ be the determinant function on $𝐹^{𝑛 \times 𝑛}$ (Theorem 5.3.4). If $𝜎 = 𝜏_{1} \dots 𝜏_{𝑟}$ is a product of transpositions, then by Proposition 5.2.30 the columns of $𝐸_{𝜎}$ are obtained from those of $𝐼_{𝑛}$ by $𝑟$ interchanges of two columns, and each interchange multiplies $det$ by $- 1$ (Proposition 5.1.10). So $det 𝐸_{𝜎} =$ ${(- 1)}^{𝑟} det 𝐼_{𝑛} =$ ${(- 1)}^{𝑟}$ . Since $det 𝐸_{𝜎}$ depends only on $𝜎$ , so does ${(- 1)}^{𝑟}$ , and the parity of $𝑟$ is determined by $𝜎$ .

Solution.

Uses. Theorem 5.3.4 (Existence and uniqueness of the determinant), Remark 5.2.32 (Two comments on the theorem), Theorem 5.2.31 (Alternating functions and permutations)

Hint 1. How is the existence of a determinant function on

𝐹^{𝑛 \times 𝑛}

proved in Section 5.3, and what does that proof use?

Hint 2. Suppose

𝐹 = 𝔽_{2}

. What does

det 𝐸_{𝜎} = {(- 1)}^{𝑟}

tell you about

𝑟

Sketch. The argument is circular: the existence half of Theorem 5.3.4 is proved with a formula involving

sgn

, which is defined using Theorem 5.2.18. It also takes

𝐹

arbitrary, but if

1 + 1 = 0

then

{(- 1)}^{𝑟} = 1

for every

𝑟

and nothing about

𝑟

follows. Over

ℚ

, with a determinant function constructed without permutations, the argument would be valid.

There are two errors.

Circularity. The proof assumes that a determinant function exists on $𝐹^{𝑛 \times 𝑛}$ . For $𝑛 \geq 3$ the existence of a determinant function is the existence half of Theorem 5.3.4, which Section 5.3 proves by checking that a formula built from $sgn$ satisfies the axioms. That formula only makes sense once $sgn$ is well defined, that is, once Theorem 5.2.18 is known. So the argument assumes what it is trying to prove.

The field. Even granting a determinant function, the conclusion “ ${(- 1)}^{𝑟}$ is determined, so the parity of $𝑟$ is determined” needs $1 \neq - 1$ in $𝐹$ . Over $𝔽_{2}$ , ${(- 1)}^{𝑟} = 1$ for every $𝑟$ , so the equation $det 𝐸_{𝜎} = {(- 1)}^{𝑟}$ says nothing about $𝑟$ .

The core of the argument is sound, as Remark 5.2.32 explains: if one had a multilinear alternating $𝐷$ on $ℚ^{𝑛 \times 𝑛}$ with $𝐷 (𝐼_{𝑛}) \neq 0$ , constructed without permutations, then the induction in the proof of Theorem 5.2.31 gives ${(- 1)}^{𝑟} 𝐷 (𝐼_{𝑛}) =$ $𝐷 (𝐸_{𝜎}) =$ ${(- 1)}^{𝑠} 𝐷 (𝐼_{𝑛})$ for two factorizations, and $𝑟 \equiv 𝑠$ modulo $2$ follows.

Exercise 5.2.39.standard

(a)Let $𝜎 \in 𝑆_{𝑛}$ and let $(𝑎_{1} \dots 𝑎_{𝑘})$ be a cycle. Show that
$𝜎 (𝑎_{1} 𝑎_{2} \dots 𝑎_{𝑘}) 𝜎^{- 1} = (𝜎 (𝑎_{1}) 𝜎 (𝑎_{2}) \dots 𝜎 (𝑎_{𝑘})) .$
(b)Let $𝑛 \geq 2$ and $𝑘 \neq 𝑙$ in $[𝑛]$ . Show that $(𝑘 𝑙) = 𝜌 (1 2) 𝜌^{- 1}$ for some $𝜌 \in 𝑆_{𝑛}$ .
(c)Compute $𝜎 (1 2 3) (4 5) 𝜎^{- 1}$ for $𝜎 = (1 5 2) (3 4)$ without multiplying permutations.

Solution.

Uses. Definition 5.2.15 (Cycle), Proposition 5.2.5 (Composition and inverses), Proposition 5.2.16 (Cycle decomposition)

Hint 1. Evaluate the left side at

𝜎 (𝑎_{𝑖})

, and at a point

𝑦

not of this form.

Hint 2. For (b), find

𝜌

with

𝜌 (1) = 𝑘

and

𝜌 (2) = 𝑙

, and apply (a).

Hint 3. For (c), write the conjugate of a product as a product of conjugates:

𝜎 𝛾 𝛿 𝜎^{- 1} =

(𝜎 𝛾 𝜎^{- 1}) (𝜎 𝛿 𝜎^{- 1})

Sketch. Let

𝛾 = (𝑎_{1} \dots 𝑎_{𝑘})

. At

𝜎 (𝑎_{𝑖})

𝜎 𝛾 𝜎^{- 1}

gives

𝜎 (𝛾 (𝑎_{𝑖})) =

𝜎 (𝑎_{𝑖 + 1})

(indices mod

𝑘

), and at any other

𝑦

𝜎^{- 1} (𝑦)

is not an

𝑎_{𝑖}

, so

𝑦

is fixed. For (b), take

𝜌

with

𝜌 (1) = 𝑘

𝜌 (2) = 𝑙

. For (c), rename each entry by

𝜎

(5 1 4) (3 2)

(a) Let $𝛾 = (𝑎_{1} \dots 𝑎_{𝑘})$ , and read indices modulo $𝑘$ , so $𝛾 (𝑎_{𝑖}) = 𝑎_{𝑖 + 1}$ and $𝑎_{𝑘 + 1} = 𝑎_{1}$ . For each $𝑖$ ,

𝜎 𝛾 𝜎^{- 1} (𝜎 (𝑎_{𝑖})) = 𝜎 (𝛾 (𝑎_{𝑖})) = 𝜎 (𝑎_{𝑖 + 1}) .

If $𝑦 \in [𝑛]$ is not one of $𝜎 (𝑎_{1}),$ $\dots,$ $𝜎 (𝑎_{𝑘})$ , then $𝜎^{- 1} (𝑦)$ is not one of $𝑎_{1}, \dots, 𝑎_{𝑘}$ , so $𝛾$ fixes it and $𝜎 𝛾 𝜎^{- 1} (𝑦) =$ $𝜎 (𝜎^{- 1} (𝑦)) =$ $𝑦$ . Since $𝜎 (𝑎_{1}),$ $\dots,$ $𝜎 (𝑎_{𝑘})$ are distinct (as $𝜎$ is injective), this is exactly the cycle $(𝜎 (𝑎_{1}) \dots 𝜎 (𝑎_{𝑘}))$ .

(b) The sets $[𝑛] ∖ {1, 2}$ and $[𝑛] ∖ {𝑘, 𝑙}$ both have $𝑛 - 2$ elements, so there is a bijection $𝛽$ between them. Define $𝜌 (1) = 𝑘$ , $𝜌 (2) = 𝑙$ , and $𝜌 (𝑖) = 𝛽 (𝑖)$ for $𝑖 \geq 3$ . Then $𝜌$ is a bijection of $[𝑛]$ , and by (a), $𝜌 (1 2) 𝜌^{- 1} =$ $(𝜌 (1) 𝜌 (2)) =$ $(𝑘 𝑙)$ .

(c) Since $𝜎^{- 1} 𝜎 = id$ , we have $𝜎 𝛾 𝛿 𝜎^{- 1} =$ $(𝜎 𝛾 𝜎^{- 1}) (𝜎 𝛿 𝜎^{- 1})$ . Here $𝜎$ sends $1 \mapsto 5$ , $2 \mapsto 1$ , $3 \mapsto 4$ , $4 \mapsto 3$ , $5 \mapsto 2$ , so by (a),

𝜎 (1 2 3) (4 5) 𝜎^{- 1} = (5 1 4) (3 2) = (1 4 5) (2 3) .

Exercise 5.2.40.standard Let

𝑛 \geq 3

. Show that every even permutation in

𝑆_{𝑛}

is a product of

3

-cycles. Conclude that a permutation is even if and only if it is a product of

3

-cycles.

Solution.

Uses. Definition 5.2.23 (Sign of a permutation), Lemma 5.2.17 (Cycles as products of transpositions), Proposition 5.2.26 (Sign of a cycle), Proposition 5.2.25 (Multiplicativity of the sign)

Hint 1. An even permutation is a product of an even number of transpositions. Group them in pairs.

Hint 2. Show that a product of two transpositions is a product of at most two

3

-cycles. Distinguish whether the two transpositions are equal, share one point, or are disjoint.

Hint 3. If they share one point, name them

(𝑎 𝑏)

and

(𝑏 𝑐)

; by Lemma 5.2.17 their product is

(𝑎 𝑏 𝑐)

. If they are disjoint, insert

(𝑏 𝑐) (𝑏 𝑐) = id

Sketch. Pair up the transpositions of an even factorization. Equal transpositions multiply to

id

;

(𝑎 𝑏) (𝑏 𝑐) =

(𝑎 𝑏 𝑐)

; and for disjoint ones,

(𝑎 𝑏) (𝑐 𝑑) =

(𝑎 𝑏) (𝑏 𝑐) (𝑏 𝑐) (𝑐 𝑑) =

(𝑎 𝑏 𝑐) (𝑏 𝑐 𝑑)

. Conversely,

3

-cycles are even.

Let $𝜎$ be even, so $𝜎 = 𝜏_{1} 𝜏_{2} \dots 𝜏_{2 𝑞}$ for some transpositions $𝜏_{𝑖}$ , and $𝜎 =$ $(𝜏_{1} 𝜏_{2}) (𝜏_{3} 𝜏_{4}) \dots (𝜏_{2 𝑞 - 1} 𝜏_{2 𝑞})$ . It suffices to show that a product $𝜋$ of two transpositions is a product of $3$ -cycles (with the empty product allowed). There are three cases.

The transpositions are equal. Then $𝜋 = id$ , the empty product.

They share exactly one point. Since $(𝑥 𝑦) = (𝑦 𝑥)$ , we can write them as $(𝑎 𝑏)$ and $(𝑏 𝑐)$ with $𝑎, 𝑏, 𝑐$ distinct, in the order they occur in $𝜋$ . By Lemma 5.2.17, $𝜋 =$ $(𝑎 𝑏) (𝑏 𝑐) =$ $(𝑎 𝑏 𝑐)$ .

They are disjoint, say $(𝑎 𝑏)$ and $(𝑐 𝑑)$ with $𝑎, 𝑏, 𝑐, 𝑑$ distinct. Inserting ${(𝑏 𝑐)}^{2} = id$ and using the previous case twice,

𝜋 = (𝑎 𝑏) (𝑏 𝑐) (𝑏 𝑐) (𝑐 𝑑) = (𝑎 𝑏 𝑐) (𝑏 𝑐 𝑑) .

Conversely, a $3$ -cycle is even by Proposition 5.2.26, so a product of $3$ -cycles is even by Proposition 5.2.25. Hence a permutation is even if and only if it is a product of $3$ -cycles. (We need $𝑛 \geq 3$ for $3$ -cycles to exist; for $𝑛 \leq 2$ the only even permutation is $id$ , the empty product.)

Exercise 5.2.41.standard The order of $𝜎 \in 𝑆_{𝑛}$ is the least $𝑚 \geq 1$ with $𝜎^{𝑚} = id$ .

(a)Show that the order of a $𝑘$ -cycle is $𝑘$ , and that if $𝜎 = 𝛾_{1} \dots 𝛾_{𝑡}$ is a product of disjoint cycles of lengths $𝑘_{1}, \dots, 𝑘_{𝑡}$ , then the order of $𝜎$ is the least common multiple of $𝑘_{1}, \dots, 𝑘_{𝑡}$ .
(b)Let $𝜎 =$ $(1 2 3) (4 5 6 7) \in$ $𝑆_{7}$ . Find the least $𝑚 \geq 1$ with $𝐸_{𝜎}^{𝑚} = 𝐼_{7}$ .

Solution.

Uses. Proposition 5.2.16 (Cycle decomposition), Proposition 5.2.30 (Algebra of permutation matrices), Definition 5.2.15 (Cycle)

Hint 1. For a

𝑘

-cycle

𝛾 = (𝑎_{1} \dots 𝑎_{𝑘})

, compute

𝛾^{𝑚} (𝑎_{𝑖})

Hint 2. Disjoint cycles commute, so

𝜎^{𝑚} = 𝛾_{1}^{𝑚} \dots 𝛾_{𝑡}^{𝑚}

, and

𝛾_{𝑠}^{𝑚}

moves only points of its own cycle. When is the product the identity?

Hint 3. For (b),

𝐸_{𝜎}^{𝑚} = 𝐸_{𝜎^{𝑚}}

, and

𝐸_{𝜋} = 𝐼_{𝑛}

only when

𝜋 = id

Sketch.

𝛾^{𝑚} (𝑎_{𝑖}) =

𝑎_{𝑖 + 𝑚}

(indices mod

𝑘

), so

𝛾^{𝑚} = id

iff

𝑘 ∣ 𝑚

. Since the

𝛾_{𝑠}

commute and move disjoint sets,

𝜎^{𝑚} = id

iff each

𝛾_{𝑠}^{𝑚} = id

iff each

𝑘_{𝑠} ∣ 𝑚

. In (b),

𝐸_{𝜎}^{𝑚} = 𝐸_{𝜎^{𝑚}}

, so the answer is the order of

𝜎

lcm (3, 4) = 12

(a) Let $𝛾 = (𝑎_{1} \dots 𝑎_{𝑘})$ and read indices modulo $𝑘$ . By induction on $𝑚$ , $𝛾^{𝑚} (𝑎_{𝑖}) =$ $𝑎_{𝑖 + 𝑚}$ , and $𝛾^{𝑚}$ fixes every point outside ${𝑎_{1}, \dots, 𝑎_{𝑘}}$ . So $𝛾^{𝑚} = id$ if and only if $𝑎_{𝑖 + 𝑚} = 𝑎_{𝑖}$ for all $𝑖$ , that is, if and only if $𝑘$ divides $𝑚$ . The least such $𝑚 \geq 1$ is $𝑘$ .

Now let $𝜎 = 𝛾_{1} \dots 𝛾_{𝑡}$ with disjoint cycles $𝛾_{𝑠}$ of lengths $𝑘_{𝑠}$ . Disjoint cycles commute, so $𝜎^{𝑚} = 𝛾_{1}^{𝑚} \dots 𝛾_{𝑡}^{𝑚}$ . Each $𝛾_{𝑠}^{𝑚}$ maps the entries of $𝛾_{𝑠}$ among themselves and fixes all other points. So for $𝑥$ an entry of $𝛾_{𝑠}$ , $𝜎^{𝑚} (𝑥) =$ $𝛾_{𝑠}^{𝑚} (𝑥)$ , and $𝜎^{𝑚}$ fixes the points that no $𝛾_{𝑠}$ moves. Hence $𝜎^{𝑚} = id$ if and only if $𝛾_{𝑠}^{𝑚} = id$ for every $𝑠$ , that is, if and only if every $𝑘_{𝑠}$ divides $𝑚$ . The least such $𝑚 \geq 1$ is $lcm (𝑘_{1}, \dots, 𝑘_{𝑡})$ .

(b) By Proposition 5.2.30, $𝐸_{𝜎}^{𝑚} = 𝐸_{𝜎^{𝑚}}$ . A permutation matrix $𝐸_{𝜋}$ equals $𝐼_{7}$ only if $𝐞_{𝜋 (𝑗)} = 𝐞_{𝑗}$ for all $𝑗$ , that is, $𝜋 = id$ . So $𝐸_{𝜎}^{𝑚} = 𝐼_{7}$ if and only if $𝜎^{𝑚} = id$ , and by (a) the least such $𝑚$ is $lcm (3, 4) = 12$ .

Exercise 5.2.42.standard

(a)Find $𝜎 \in 𝑆_{5}$ with $𝜎^{2} = (1 2 3 4 5)$ .
(b)Find $𝜎 \in 𝑆_{4}$ with $𝜎^{2} = (1 2) (3 4)$ .
(c)Show that there is no $𝜎 \in 𝑆_{𝑛}$ (for any $𝑛 \geq 5$ ) with $𝜎^{2} = (1 2) (3 4 5)$ .

Solution.

Uses. Exercise 5.2.28, Exercise 5.2.41, Proposition 5.2.26 (Sign of a cycle)

Hint 1. Square a

5

-cycle

(𝑏_{1} 𝑏_{2} 𝑏_{3} 𝑏_{4} 𝑏_{5})

: where does

𝑏_{1}

go?

Hint 2. For (b), the square of a

4

-cycle

(𝑏_{1} 𝑏_{2} 𝑏_{3} 𝑏_{4})

(𝑏_{1} 𝑏_{3}) (𝑏_{2} 𝑏_{4})

Hint 3. For (c), compute a sign (Exercise 5.2.28).

Sketch. (a)

{(𝑏_{1} \dots 𝑏_{5})}^{2} =

(𝑏_{1} 𝑏_{3} 𝑏_{5} 𝑏_{2} 𝑏_{4})

, so

𝜎 = (1 4 2 5 3)

. (b)

𝜎 = (1 3 2 4)

. (c)

(1 2) (3 4 5)

is odd, and squares are even.

(a) For a $5$ -cycle $𝛾 =$ $(𝑏_{1} 𝑏_{2} 𝑏_{3} 𝑏_{4} 𝑏_{5})$ , $𝛾^{2}$ sends $𝑏_{𝑖} \mapsto 𝑏_{𝑖 + 2}$ (indices mod $5$ ), so $𝛾^{2} =$ $(𝑏_{1} 𝑏_{3} 𝑏_{5} 𝑏_{2} 𝑏_{4})$ . We want this to be $(1 2 3 4 5)$ , so we take $𝑏_{1} = 1$ , $𝑏_{3} = 2$ , $𝑏_{5} = 3$ , $𝑏_{2} = 4$ , $𝑏_{4} = 5$ , that is, $𝜎 = (1 4 2 5 3)$ . Check: $𝜎$ sends $1 \mapsto 4 \mapsto 2 \mapsto 5 \mapsto 3 \mapsto 1$ , so $𝜎^{2}$ sends $1 \mapsto 2$ , $2 \mapsto 3$ , $3 \mapsto 4$ , $4 \mapsto 5$ , $5 \mapsto 1$ .

(b) For $𝛾 = (𝑏_{1} 𝑏_{2} 𝑏_{3} 𝑏_{4})$ , $𝛾^{2}$ sends $𝑏_{1} \mapsto 𝑏_{3} \mapsto 𝑏_{1}$ and $𝑏_{2} \mapsto 𝑏_{4} \mapsto 𝑏_{2}$ , so $𝛾^{2} =$ $(𝑏_{1} 𝑏_{3}) (𝑏_{2} 𝑏_{4})$ . Taking $𝑏_{1} = 1$ , $𝑏_{3} = 2$ , $𝑏_{2} = 3$ , $𝑏_{4} = 4$ gives $𝜎 = (1 3 2 4)$ with $𝜎^{2} = (1 2) (3 4)$ .

(c) By Proposition 5.2.26, $sgn ((1 2) (3 4 5)) =$ $(- 1) (+ 1) =$ $- 1$ . By Exercise 5.2.28, every square $𝜎^{2}$ is even. So $(1 2) (3 4 5)$ is not a square.

Exercise 5.2.43.standard Show that

inv (𝜎)

is the least number of adjacent transpositions whose product is

𝜎

. That is,

𝜎

is a product of

inv (𝜎)

adjacent transpositions, and not of fewer.

Solution.

Uses. Lemma 5.2.22 (A transposition changes $inv$ by an odd number), Definition 5.2.21 (Inversion)

Techniques. Algorithms as proofs: invariants and termination (Technique 3.3.5)

Hint 1. For the lower bound, start from

id

and multiply on the right by adjacent transpositions one at a time. By how much can

inv

change at each step?

Hint 2. For the upper bound, induct on

inv (𝜎)

. If

𝜎 \neq id

, find

𝑘

with

𝜎 (𝑘) > 𝜎 (𝑘 + 1)

, and show that

inv (𝜎 (𝑘 𝑘 + 1)) =

inv (𝜎) -

1

Sketch. Each adjacent transposition changes

inv

by exactly

1

(Lemma 5.2.22), so a product of

𝑟

of them has

inv \leq 𝑟

. Conversely, if

inv (𝜎) > 0

, the bottom row has a descent

𝜎 (𝑘) > 𝜎 (𝑘 + 1)

; interchanging those two entries removes exactly one inversion. Repeating (bubble sort) reaches

id

after

inv (𝜎)

steps, and reversing the steps writes

𝜎

as a product of

inv (𝜎)

adjacent transpositions.

Lower bound. Suppose $𝜎 = 𝑠_{1} \dots 𝑠_{𝑟}$ with adjacent transpositions $𝑠_{𝑖}$ . By Lemma 5.2.22, $inv (𝑠_{1} \dots 𝑠_{𝑗}) \leq$ $inv (𝑠_{1} \dots 𝑠_{𝑗 - 1}) +$ $1$ for each $𝑗$ , and $inv (id) = 0$ , so by induction $inv (𝑠_{1} \dots 𝑠_{𝑗}) \leq 𝑗$ . In particular $inv (𝜎) \leq 𝑟$ .

Upper bound. We show by induction on $𝑁 = inv (𝜎)$ that $𝜎$ is a product of $𝑁$ adjacent transpositions. If $𝑁 = 0$ , the bottom row of $𝜎$ has no pair out of order, so it is increasing, and an increasing arrangement of $1, \dots, 𝑛$ is $1, \dots, 𝑛$ . So $𝜎 = id$ , the empty product. If $𝑁 > 0$ , the bottom row is not increasing, so $𝜎 (𝑘) > 𝜎 (𝑘 + 1)$ for some $𝑘$ . Let $𝑠 = (𝑘 𝑘 + 1)$ . By Remark 5.2.11, the bottom row of $𝜎 𝑠$ is that of $𝜎$ with the entries in positions $𝑘$ and $𝑘 + 1$ interchanged. The proof of Lemma 5.2.22 shows that, for an adjacent transposition, the pairs other than $(𝑘, 𝑘 + 1)$ contribute the same number of inversions before and after, so $inv (𝜎 𝑠) - inv (𝜎)$ is the change in the status of $(𝑘, 𝑘 + 1)$ alone. Here that pair changes from inverted to not inverted, so $inv (𝜎 𝑠) = 𝑁 - 1$ , and by the induction hypothesis $𝜎 𝑠 = 𝑠_{1} \dots 𝑠_{𝑁 - 1}$ with adjacent transpositions $𝑠_{𝑖}$ . Then $𝜎 =$ $𝜎 𝑠 𝑠 =$ $𝑠_{1} \dots 𝑠_{𝑁 - 1} 𝑠$ , a product of $𝑁$ adjacent transpositions.

The upper bound is the analysis of bubble sort, which repeatedly interchanges an adjacent pair that is out of order. Each interchange lowers $inv$ by exactly $1$ , so the algorithm stops after exactly $inv (𝜎)$ interchanges, whichever out-of-order pairs it picks.

Exercise 5.2.44.standard A matrix is monomial if it has exactly one nonzero entry in each row and in each column.

(a)Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ be monomial. Show that there are $𝜎 \in 𝑆_{𝑛}$ and nonzero $𝑐_{1}, \dots, 𝑐_{𝑛} \in 𝐹$ such that column $𝑗$ of $𝐴$ is $𝑐_{𝑗} 𝐞_{𝜎 (𝑗)}$ . Deduce that if $𝐷 : 𝐹^{𝑛 \times 𝑛} \to 𝐹$ is multilinear and alternating, then $𝐷 (𝐴) =$ $sgn (𝜎) 𝑐_{1} 𝑐_{2} \dots 𝑐_{𝑛} 𝐷 (𝐼_{𝑛})$ .
(b)Over $ℂ$ , find $𝐷 (𝐴)$ in terms of $𝐷 (𝐼_{4})$ for
$𝐴 = (\begin{matrix} 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & - 1 \\ 𝑖 & 0 & 0 & 0 \\ 0 & 0 & 1 - 𝑖 & 0 \end{matrix}) .$
(c)Over $𝔽_{3}$ , find $𝐷 (𝐵)$ in terms of $𝐷 (𝐼_{3})$ for $𝐵 = (\begin{matrix} 0 & 2 & 0 \\ 0 & 0 & 2 \\ 2 & 0 & 0 \end{matrix})$ .

Solution.

Uses. Theorem 5.2.31 (Alternating functions and permutations), Definition 5.1.1 (Determinant function), Proposition 5.2.26 (Sign of a cycle)

Techniques. Expand by multilinearity (Technique 5.1.7)

Hint 1. In (a), let

𝜎 (𝑗)

be the row of the nonzero entry in column

𝑗

. Why is

𝜎

a permutation?

Hint 2. Pull the scalars

𝑐_{𝑗}

out of the columns by multilinearity, and apply Theorem 5.2.31 to what is left.

Hint 3. In (b), read off

𝜎

column by column and find its cycle notation.

Sketch. (a) The rows

𝜎 (𝑗)

of the nonzero entries are distinct because each row has one nonzero entry, so

𝜎 \in 𝑆_{𝑛}

. Multilinearity gives

𝐷 (𝐴) =

𝑐_{1} \dots 𝑐_{𝑛} 𝐷 (𝐸_{𝜎}) =

𝑐_{1} \dots 𝑐_{𝑛} sgn (𝜎) 𝐷 (𝐼_{𝑛})

. (b)

𝜎 = (1 3 4 2)

, odd, and

𝑐_{1} 𝑐_{2} 𝑐_{3} 𝑐_{4} =

𝑖 \cdot

2 \cdot

(1 - 𝑖) (- 1) =

- 2 -

2 𝑖

, so

𝐷 (𝐴) =

(2 + 2 𝑖) 𝐷 (𝐼_{4})

. (c)

𝜎 = (1 3 2)

, even, so

𝐷 (𝐵) =

8 𝐷 (𝐼_{3}) =

2 𝐷 (𝐼_{3})

𝔽_{3}

(a) For each column $𝑗$ , let $𝜎 (𝑗)$ be the row of its nonzero entry and $𝑐_{𝑗}$ that entry, so column $𝑗$ is $𝑐_{𝑗} 𝐞_{𝜎 (𝑗)}$ . If $𝜎 (𝑗) = 𝜎 (𝑗^{'})$ with $𝑗 \neq 𝑗^{'}$ , row $𝜎 (𝑗)$ would have two nonzero entries; so $𝜎$ is injective, hence a permutation. Pulling $𝑐_{𝑗}$ out of column $𝑗$ for each $𝑗$ (multilinearity, Definition 5.1.1) and applying Theorem 5.2.31,

𝐷 (𝐴) = 𝑐_{1} \dots 𝑐_{𝑛} 𝐷 (𝐞_{𝜎 (1)}, \dots, 𝐞_{𝜎 (𝑛)}) = 𝑐_{1} \dots 𝑐_{𝑛} 𝐷 (𝐸_{𝜎}) = sgn (𝜎) 𝑐_{1} \dots 𝑐_{𝑛} 𝐷 (𝐼_{𝑛}) .

(b) The columns of $𝐴$ are $𝑖 𝐞_{3}$ , $2 𝐞_{1}$ , $(1 - 𝑖) 𝐞_{4}$ , and $- 𝐞_{2}$ . So $𝜎 = (\begin{matrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{matrix})$ , that is, $1 \mapsto 3 \mapsto 4 \mapsto 2 \mapsto 1$ , the $4$ -cycle $(1 3 4 2)$ , which is odd by Proposition 5.2.26. The product of the scalars is

𝑖 \cdot 2 \cdot (1 - 𝑖) \cdot (- 1) = - 2 𝑖 (1 - 𝑖) = - 2 𝑖 + 2 𝑖^{2} = - 2 - 2 𝑖 .

So $𝐷 (𝐴) =$ $- (- 2 - 2 𝑖) 𝐷 (𝐼_{4}) =$ $(2 + 2 𝑖) 𝐷 (𝐼_{4})$ .

(c) The columns of $𝐵$ are $2 𝐞_{3}$ , $2 𝐞_{1}$ , $2 𝐞_{2}$ , so $𝜎 = (\begin{matrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{matrix}) = (1 3 2)$ , a $3$ -cycle, which is even. Hence $𝐷 (𝐵) =$ $2^{3} 𝐷 (𝐼_{3}) =$ $8 𝐷 (𝐼_{3}) =$ $2 𝐷 (𝐼_{3})$ , since $8 = 2$ in $𝔽_{3}$ .

Exercise 5.2.45.standard

(a)Let $2 \leq 𝑘 \leq 𝑛$ . Show that $𝑆_{𝑛}$ contains exactly $𝑛! / ((𝑛 - 𝑘)! 𝑘)$ cycles of length $𝑘$ .
(b)Sort the $24$ elements of $𝑆_{4}$ by their cycle notation: the identity, transpositions, $3$ -cycles, $4$ -cycles, and products of two disjoint transpositions. Count each kind, and use the counts to check Proposition 5.2.27 for $𝑛 = 4$ .

Solution.

Uses. Definition 5.2.15 (Cycle), Proposition 5.2.16 (Cycle decomposition), Proposition 5.2.26 (Sign of a cycle), Proposition 5.2.27 (Half of all permutations are even)

Hint 1. Count lists

𝑎_{1}, \dots, 𝑎_{𝑘}

of distinct elements, then ask how many lists name the same cycle.

Hint 2. Two lists name the same

𝑘

-cycle exactly when one is a rotation of the other. Why?

Hint 3. For (b), a product of two disjoint transpositions is determined by how it splits

[4]

into two pairs.

Sketch. There are

𝑛! / (𝑛 - 𝑘)!

lists of

𝑘

distinct elements, and each

𝑘

-cycle has exactly

𝑘

names (its rotations), giving

𝑛! / ((𝑛 - 𝑘)! 𝑘)

. In

𝑆_{4}

1 + 6 + 8 + 6 + 3 = 24

. The even ones are

id

, the

3

-cycles, and the double transpositions:

1 + 8 + 3 = 12 = 4! / 2

(a) By the argument of Proposition 5.2.4, there are $𝑛 (𝑛 - 1) \dots (𝑛 - 𝑘 + 1) =$ $𝑛! / (𝑛 - 𝑘)!$ lists $𝑎_{1}, \dots, 𝑎_{𝑘}$ of distinct elements of $[𝑛]$ , and each names the $𝑘$ -cycle $(𝑎_{1} \dots 𝑎_{𝑘})$ . The $𝑘$ rotations $𝑎_{𝑝},$ $𝑎_{𝑝 + 1},$ $\dots,$ $𝑎_{𝑘},$ $𝑎_{1},$ $\dots,$ $𝑎_{𝑝 - 1}$ name the same cycle. Conversely, if $(𝑏_{1} \dots 𝑏_{𝑘}) =$ $𝛾 =$ $(𝑎_{1} \dots 𝑎_{𝑘})$ , then $𝑏_{1}$ is moved by $𝛾$ , so $𝑏_{1} = 𝑎_{𝑝}$ for some $𝑝$ , and then $𝑏_{2} =$ $𝛾 (𝑏_{1}) =$ $𝑎_{𝑝 + 1}$ , $𝑏_{3} =$ $𝛾 (𝑏_{2}) =$ $𝑎_{𝑝 + 2}$ , and so on (indices mod $𝑘$ ); so the list $𝑏$ is a rotation of the list $𝑎$ . The $𝑘$ rotations of a list of distinct elements are distinct lists, since their first entries differ. So each $𝑘$ -cycle has exactly $𝑘$ names, and there are $𝑛! / ((𝑛 - 𝑘)! 𝑘)$ of them.

(b) By Proposition 5.2.16, each $𝜎 \in 𝑆_{4}$ is a product of disjoint cycles whose lengths add up to at most $4$ , so its cycle notation is one of: $id$ ; a transposition; a $3$ -cycle; a $4$ -cycle; two disjoint transpositions. By (a) there are $4! / (2! \cdot 2) = 6$ transpositions, $4! / (1! \cdot 3) = 8$ three-cycles, and $4! / (0! \cdot 4) = 6$ four-cycles. A product of two disjoint transpositions $(𝑎 𝑏) (𝑐 𝑑)$ is determined by the partition ${{𝑎, 𝑏}, {𝑐, 𝑑}}$ of $[4]$ , and there are $3$ such partitions (the partner of $1$ determines it). The total is $1 + 6 + 8 + 6 + 3 = 24 = 4!$ , as it must be.

By Proposition 5.2.26, transpositions and $4$ -cycles are odd, while $id$ , $3$ -cycles, and products of two disjoint transpositions are even. So there are $1 + 8 + 3 = 12$ even permutations and $6 + 6 = 12$ odd ones, as Proposition 5.2.27 predicts.

Exercise 5.2.46.hard Let

𝑛 \geq 2

, let

𝐹

be a field, and let

𝑓 : 𝑆_{𝑛} \to 𝐹

satisfy

𝑓 (𝜎) \neq 0

and

𝑓 (𝜎 𝜌) =

𝑓 (𝜎) 𝑓 (𝜌)

for all

𝜎, 𝜌 \in 𝑆_{𝑛}

. Show that either

𝑓 (𝜎) = 1

for all

𝜎

, or

𝑓 (𝜎) = sgn (𝜎)

for all

𝜎

Solution.

Uses. Exercise 5.2.39, Proposition 5.2.13 (Products of transpositions), Proposition 1.1.17 (No zero divisors), Definition 5.2.23 (Sign of a permutation)

Hint 1. First find

𝑓 (id)

. Then show that

𝑓

takes the same value

𝑐

on every transposition, using Exercise 5.2.39.

Hint 2. Compute

𝑐^{2}

from

{(1 2)}^{2} = id

, and conclude that

𝑐 = \pm 1

Hint 3. Every

𝜎

is a product of transpositions, so

𝑓 (𝜎)

is a power of

𝑐

Sketch.

{𝑓 (id)}^{2} = 𝑓 (id) \neq 0

gives

𝑓 (id) = 1

. Each transposition is

𝜌 (1 2) 𝜌^{- 1}

, so

𝑓

of it is

𝑓 (𝜌) 𝑐 {𝑓 (𝜌)}^{- 1} =

𝑐

where

𝑐 = 𝑓 ((1 2))

. Then

𝑐^{2} = 𝑓 (id) = 1

, so

𝑐 = \pm 1

, and

𝑓 (𝜏_{1} \dots 𝜏_{𝑟}) = 𝑐^{𝑟}

1

{(- 1)}^{𝑟} = sgn (𝜎)

$𝑓 (id) = 1$ . From $𝑓 (id) =$ $𝑓 (id id) =$ ${𝑓 (id)}^{2}$ and $𝑓 (id) \neq 0$ , cancelling one factor $𝑓 (id)$ gives $𝑓 (id) = 1$ . Consequently $𝑓 (𝜌) 𝑓 (𝜌^{- 1}) =$ $𝑓 (id) =$ $1$ , so $𝑓 (𝜌^{- 1}) = {𝑓 (𝜌)}^{- 1}$ .

$𝑓$ is constant on transpositions. Let $𝑐 = 𝑓 ((1 2))$ . By Exercise 5.2.39, every transposition has the form $𝜌 (1 2) 𝜌^{- 1}$ , and since $𝐹$ is commutative,

𝑓 (𝜌 (1 2) 𝜌^{- 1}) = 𝑓 (𝜌) 𝑐 {𝑓 (𝜌)}^{- 1} = 𝑐 .

$𝑐 = \pm 1$ . Since ${(1 2)}^{2} = id$ , $𝑐^{2} = 𝑓 (id) = 1$ , so $(𝑐 - 1) (𝑐 + 1) = 0$ , and by Proposition 1.1.17, $𝑐 = 1$ or $𝑐 = - 1$ .

Conclusion. Let $𝜎 \in 𝑆_{𝑛}$ , and write $𝜎 = 𝜏_{1} \dots 𝜏_{𝑟}$ with transpositions $𝜏_{𝑖}$ (Proposition 5.2.13). Then $𝑓 (𝜎) =$ $𝑓 (𝜏_{1}) \dots 𝑓 (𝜏_{𝑟}) =$ $𝑐^{𝑟}$ . If $𝑐 = 1$ , then $𝑓 (𝜎) = 1$ for all $𝜎$ . If $𝑐 = - 1$ , then $𝑓 (𝜎) =$ ${(- 1)}^{𝑟} =$ $sgn (𝜎)$ by Definition 5.2.23. (If $1 + 1 = 0$ in $𝐹$ , the two cases coincide.)

Exercise 5.2.47 (The 15 puzzle).hard In the 15 puzzle, fifteen square tiles numbered

1, \dots, 15

and one empty space sit in a

4 \times 4

frame. A move slides a tile that shares an edge with the empty space into it. In the solved position the tiles read

1, \dots, 15

row by row, from the top left, with the empty space in the bottom right corner. Show that no sequence of moves turns the solved position into the position in which tiles

14

and

15

are interchanged and all other tiles, and the empty space, are where they were.

Solution.

Uses. Proposition 5.2.25 (Multiplicativity of the sign), Remark 5.2.11 (Composing with a transposition)

Techniques. Parity via an invariant (Technique 5.2.19)

Hint 1. Number the cells

1, \dots, 16

row by row and call the empty space tile

16

. A position is then a permutation

𝜋 \in 𝑆_{16}

, with

𝜋 (𝑝)

the tile in cell

𝑝

. What does a move do to

𝜋

Hint 2. A move interchanges the contents of two adjacent cells, so it multiplies

𝜋

by a transposition, flipping

sgn (𝜋)

. What else flips with every move?

Hint 3. Color the cells like a checkerboard. Every move changes the color of the cell holding the empty space. Consider the product of

sgn (𝜋)

and

\pm 1

for that color.

Sketch. Encode a position as

𝜋 \in 𝑆_{16}

(

𝜋 (𝑝)

= tile in cell

𝑝

, the empty space being

16

). A move with the empty space in cell

𝑝

and a tile in an adjacent cell

𝑞

replaces

𝜋

𝜋 (𝑝 𝑞)

, which flips

sgn (𝜋)

, and also moves the empty space to a cell of the other checkerboard color. So

sgn (𝜋)

times the color sign of the empty cell is invariant. It is

+ 1

for the solved position and

- 1

for the target, which has

𝜋 = (14 15)

and the empty space in the same cell.

Number the cells $1, \dots, 16$ row by row from the top left, and call the empty space tile $16$ . A position is then described by the permutation $𝜋 \in 𝑆_{16}$ with $𝜋 (𝑝)$ the tile in cell $𝑝$ . The solved position is $𝜋 = id$ , and the target position is $𝜋 = (14 15)$ .

Suppose the empty space is in cell $𝑝$ , so $𝜋 (𝑝) = 16$ , and the tile in an adjacent cell $𝑞$ slides into it. Afterwards cell $𝑝$ holds $𝜋 (𝑞)$ , cell $𝑞$ holds $16$ , and all other cells are unchanged. By Remark 5.2.11 this is the position $𝜋 (𝑝 𝑞)$ , so by Proposition 5.2.25 every move multiplies $sgn (𝜋)$ by $- 1$ .

Give the cell in row $𝑟$ and column $𝑐$ the color $𝜀 = {(- 1)}^{𝑟 + 𝑐}$ , and let $𝜀 (𝜋)$ be the color of the cell containing the empty space. Two cells that share an edge differ by $1$ in exactly one of $𝑟$ , $𝑐$ , so they have opposite colors. Hence every move also multiplies $𝜀 (𝜋)$ by $- 1$ , and the product $𝑄 (𝜋) =$ $sgn (𝜋) 𝜀 (𝜋)$ is unchanged by every move.

In the solved position, $𝑄 =$ $sgn (id) \cdot$ ${(- 1)}^{4 + 4} =$ $1$ . In the target position, the empty space is again in row $4$ , column $4$ , and $sgn ((14 15)) = - 1$ , so $𝑄 = - 1$ . Since moves never change $𝑄$ , the target cannot be reached from the solved position.

The same argument shows that every position reachable from the solved one with the empty space back in the bottom right corner is an even permutation. Neither $sgn (𝜋)$ nor $𝜀 (𝜋)$ is invariant on its own; the invariant is their product.

Exercise 5.2.48.hard The numbers

1, \dots, 𝑛

(where

𝑛 \geq 3

) are written in a row in some order. A move chooses three consecutive entries

𝑥, 𝑦, 𝑧

and replaces them by

𝑧, 𝑥, 𝑦

. For which starting orders can the row be sorted into

1, 2, \dots, 𝑛

by a sequence of moves?

Solution.

Uses. Proposition 5.2.26 (Sign of a cycle), Proposition 5.2.25 (Multiplicativity of the sign), Definition 5.2.23 (Sign of a permutation)

Techniques. Parity via an invariant (Technique 5.2.19)

Hint 1. Regard the row as the bottom row of a permutation

𝜎

. Which permutation

𝛾

satisfies “the row after the move is the bottom row of

𝜎 𝛾

”?

Hint 2.

𝛾

is a

3

-cycle, so moves preserve the sign. That rules out odd

𝜎

Hint 3. For even

𝜎

: a move at positions

𝑝 - 2, 𝑝 - 1, 𝑝

carries the entry at position

𝑝

two places to the left. Use this to bring

1

to the front, then

2

to position

2

, and so on. What happens with the last two entries?

Sketch. A move at positions

𝑖, 𝑖 + 1, 𝑖 + 2

replaces

𝜎

𝜎 𝛾

with

𝛾 = (𝑖 𝑖 + 2 𝑖 + 1)

, a

3

-cycle, so

sgn

is invariant and odd orders cannot be sorted. For even orders, move

1

left two places at a time; if it gets stuck in position

2

, two moves at positions

1, 2, 3

bring it to the front. Then sort positions

2, \dots, 𝑛

the same way without touching position

1

, and so on, until only positions

𝑛 - 1, 𝑛

remain. The result is

id

(𝑛 - 1 𝑛)

, and since the sign is still

1

, it is

id

. Answer: exactly the even orders.

Write the row as the bottom row of $𝜎 \in 𝑆_{𝑛}$ , so that the entry in position $𝑖$ is $𝜎 (𝑖)$ . A move at positions $𝑖, 𝑖 + 1, 𝑖 + 2$ produces the row whose entries in these positions are $𝜎 (𝑖 + 2),$ $𝜎 (𝑖),$ $𝜎 (𝑖 + 1)$ . This is the bottom row of $𝜎 𝛾$ , where $𝛾 (𝑖) = 𝑖 + 2$ , $𝛾 (𝑖 + 1) = 𝑖$ , $𝛾 (𝑖 + 2) = 𝑖 + 1$ , and $𝛾$ fixes everything else; that is, $𝛾 = (𝑖 𝑖 + 2 𝑖 + 1)$ . By Proposition 5.2.26 and Proposition 5.2.25, $sgn (𝜎 𝛾) = sgn (𝜎)$ . So moves never change the sign, and since the sorted row is $id$ , with sign $1$ , an odd starting order can never be sorted.

Now let $𝜎$ be even. We sort the row in stages, placing the value $𝑣$ in position $𝑣$ at stage $𝑣$ , for $𝑣 = 1, \dots, 𝑛 - 2$ , using only moves within positions $𝑣, \dots, 𝑛$ at stage $𝑣$ . Suppose the values $1, \dots, 𝑣 - 1$ are already in positions $1, \dots, 𝑣 - 1$ , and $𝑣$ is in position $𝑝 \geq 𝑣$ . While $𝑝 \geq 𝑣 + 2$ , a move at positions $𝑝 - 2, 𝑝 - 1, 𝑝$ carries the entry $𝑣$ from position $𝑝$ to position $𝑝 - 2$ and does not touch positions before $𝑝 - 2 \geq 𝑣$ . When this stops, $𝑝 = 𝑣$ or $𝑝 = 𝑣 + 1$ . If $𝑝 = 𝑣 + 1$ , then $𝑣 + 2 \leq 𝑛$ (as $𝑣 \leq 𝑛 - 2$ ), and two moves at positions $𝑣, 𝑣 + 1, 𝑣 + 2$ change $𝑥, 𝑣, 𝑧$ there into $𝑧, 𝑥, 𝑣$ and then into $𝑣, 𝑧, 𝑥$ . Either way $𝑣$ ends in position $𝑣$ , and positions $1, \dots, 𝑣 - 1$ were not touched.

After stage $𝑛 - 2$ , the values $1, \dots, 𝑛 - 2$ are in place, and positions $𝑛 - 1$ and $𝑛$ hold $𝑛 - 1$ and $𝑛$ in some order. So the current permutation is $id$ or $(𝑛 - 1 𝑛)$ . Since moves preserve the sign and $𝜎$ is even, it is even, so it is $id$ : the row is sorted.

Answer: the row can be sorted exactly when the starting order is an even permutation.

Exercise 5.2.49.hard This exercise proves $sgn (𝜎 𝜌) =$ $sgn (𝜎) sgn (𝜌)$ directly from inversions, without using Theorem 5.2.18.

For a two-element set ${𝑖, 𝑗} \subseteq [𝑛]$ , say that $𝜋 \in 𝑆_{𝑛}$ reverses ${𝑖, 𝑗}$ if $𝜋 (𝑖) - 𝜋 (𝑗)$ and $𝑖 - 𝑗$ have opposite signs. So $inv (𝜋)$ is the number of two-element subsets that $𝜋$ reverses.

(a)Show that $𝜎 𝜌$ reverses ${𝑖, 𝑗}$ if and only if exactly one of the following holds: $𝜌$ reverses ${𝑖, 𝑗}$ ; $𝜎$ reverses ${𝜌 (𝑖), 𝜌 (𝑗)}$ .
(b)Deduce that $inv (𝜎 𝜌) -$ $inv (𝜎) -$ $inv (𝜌)$ is even. Figure 5.2.2 shows an example.
Figure 5.2.2. Stacking the diagrams of $𝜌 = (\begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{matrix})$ and $𝜎 = (\begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{matrix})$ gives a diagram of $𝜎 𝜌 = (\begin{matrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4 \end{matrix})$ . The blue strands from $1$ and $3$ cross once in each half, so they end in their original order. There are $3 + 2 = 5$ crossings but only $inv (𝜎 𝜌) = 1$ inversion, and $5 - 1$ is even.
(c)Use (b) and Exercise 5.2.34 to give another proof of Theorem 5.2.18.

Solution.

Uses. Definition 5.2.21 (Inversion), Exercise 5.2.34, Proposition 5.2.13 (Products of transpositions)

Hint 1. In (a), write

(𝜎 𝜌 (𝑖) - 𝜎 𝜌 (𝑗)) / (𝑖 - 𝑗)

as a product of two fractions. Which two?

Hint 2. For (b), the reversal conditions are

0

1

quantities

𝑢

𝑣

, and “exactly one” is

𝑢 + 𝑣 - 2 𝑢 𝑣

. Sum over all pairs, and note that

{𝑖, 𝑗} \mapsto

{𝜌 (𝑖), 𝜌 (𝑗)}

is a bijection on two-element sets.

Hint 3. For (c), by (b),

{(- 1)}^{inv (𝜎 𝜌)} =

{(- 1)}^{inv (𝜎)} {(- 1)}^{inv (𝜌)}

, and

inv

of a transposition is odd.

Sketch. (a)

(𝜎 𝜌 (𝑖) - 𝜎 𝜌 (𝑗)) / (𝑖 - 𝑗) =

[(𝜎 (𝜌 (𝑖)) - 𝜎 (𝜌 (𝑗))) / (𝜌 (𝑖) - 𝜌 (𝑗))] \cdot

[(𝜌 (𝑖) - 𝜌 (𝑗)) / (𝑖 - 𝑗)]

, and a product of two nonzero rationals is negative exactly when one factor is. (b) Summing

𝑢 + 𝑣 - 2 𝑢 𝑣

over pairs gives

inv (𝜎 𝜌) =

inv (𝜌) +

inv (𝜎) -

2 𝑀

, since the pairs

{𝜌 (𝑖), 𝜌 (𝑗)}

run over all pairs. (c) So

{(- 1)}^{inv}

is multiplicative and is

- 1

on transpositions; hence

{(- 1)}^{𝑟} =

{(- 1)}^{inv (𝜎)} =

{(- 1)}^{𝑠}

for factorizations of lengths

𝑟

and

𝑠

(a) Let $𝑖 \neq 𝑗$ . Since $𝜌$ and $𝜎$ are injective, $𝜌 (𝑖) \neq 𝜌 (𝑗)$ and $𝜎 (𝜌 (𝑖)) \neq$ $𝜎 (𝜌 (𝑗))$ , so in $ℚ$ ,

\frac{𝜎 𝜌 (𝑖) - 𝜎 𝜌 (𝑗)}{𝑖 - 𝑗} = \frac{𝜎 (𝜌 (𝑖)) - 𝜎 (𝜌 (𝑗))}{𝜌 (𝑖) - 𝜌 (𝑗)} \cdot \frac{𝜌 (𝑖) - 𝜌 (𝑗)}{𝑖 - 𝑗},

a product of two nonzero rationals. The left side is negative exactly when $𝜎 𝜌$ reverses ${𝑖, 𝑗}$ , the second factor is negative exactly when $𝜌$ reverses ${𝑖, 𝑗}$ , and the first factor is negative exactly when $𝜎$ reverses ${𝜌 (𝑖), 𝜌 (𝑗)}$ . A product of two nonzero rationals is negative exactly when exactly one factor is negative.

(b) Let $𝑃$ be the set of two-element subsets of $[𝑛]$ . For $𝑝 = {𝑖, 𝑗} \in 𝑃$ , let $𝑢_{𝑝} = 1$ if $𝜌$ reverses $𝑝$ and $𝑢_{𝑝} = 0$ otherwise, and let $𝑣_{𝑝} = 1$ if $𝜎$ reverses $𝜌 (𝑝) =$ ${𝜌 (𝑖), 𝜌 (𝑗)}$ and $𝑣_{𝑝} = 0$ otherwise. By (a), $𝜎 𝜌$ reverses $𝑝$ exactly when $𝑢_{𝑝} + 𝑣_{𝑝} = 1$ , and the integer $𝑢_{𝑝} +$ $𝑣_{𝑝} -$ $2 𝑢_{𝑝} 𝑣_{𝑝}$ is $1$ in that case and $0$ otherwise. So

inv (𝜎 𝜌) = \sum_{𝑝 \in 𝑃} (𝑢_{𝑝} + 𝑣_{𝑝} - 2 𝑢_{𝑝} 𝑣_{𝑝}) = \sum_{𝑝 \in 𝑃} 𝑢_{𝑝} + \sum_{𝑝 \in 𝑃} 𝑣_{𝑝} - 2 \sum_{𝑝 \in 𝑃} 𝑢_{𝑝} 𝑣_{𝑝} .

The first sum is $inv (𝜌)$ . Since $𝜌$ is a bijection, $𝑝 \mapsto 𝜌 (𝑝)$ is a bijection of $𝑃$ (with inverse $𝑝 \mapsto 𝜌^{- 1} (𝑝)$ ), so as $𝑝$ runs over $𝑃$ , $𝜌 (𝑝)$ runs over $𝑃$ once, and the second sum is the number of elements of $𝑃$ reversed by $𝜎$ , which is $inv (𝜎)$ . Hence $inv (𝜎 𝜌) -$ $inv (𝜎) -$ $inv (𝜌)$ is even.

(c) By (b), ${(- 1)}^{inv (𝜎 𝜌)} =$ ${(- 1)}^{inv (𝜎)} {(- 1)}^{inv (𝜌)}$ for all $𝜎, 𝜌$ . By Exercise 5.2.34, $inv ((𝑘 𝑙)) =$ $2 (𝑙 - 𝑘) -$ $1$ is odd, so ${(- 1)}^{inv (𝜏)} = - 1$ for every transposition $𝜏$ . If $𝜎 = 𝜏_{1} \dots 𝜏_{𝑟}$ , then by induction on $𝑟$ , ${(- 1)}^{inv (𝜎)} =$ ${(- 1)}^{inv (𝜏_{1})} \dots {(- 1)}^{inv (𝜏_{𝑟})} =$ ${(- 1)}^{𝑟}$ . So two factorizations of $𝜎$ of lengths $𝑟$ and $𝑠$ give ${(- 1)}^{𝑟} =$ ${(- 1)}^{inv (𝜎)} =$ ${(- 1)}^{𝑠}$ , and $𝑟$ and $𝑠$ have the same parity.

Compared with Approach 2 in the text, this proof establishes multiplicativity first and gets the parity theorem from it, while the text proves the parity theorem first and gets multiplicativity for free from the definition.

Exercise 5.2.50.hardBeyond 21-242 This exercise gives a third proof of Theorem 5.2.18, by counting orbits. Recall that $𝑐 (𝜎)$ is the number of orbits of $𝜎$ , fixed points included.

(a)Let $𝜎 \in 𝑆_{𝑛}$ and let $𝜏 = (𝑎 𝑏)$ . Show that if $𝑎$ and $𝑏$ lie in the same orbit of $𝜎$ , then $𝑐 (𝜎 𝜏) = 𝑐 (𝜎) + 1$ , and otherwise $𝑐 (𝜎 𝜏) = 𝑐 (𝜎) - 1$ .
(b)Deduce that if $𝜎$ is a product of $𝑟$ transpositions, then $𝑐 (𝜎) - (𝑛 - 𝑟)$ is even, and use this to prove Theorem 5.2.18 and $sgn (𝜎) =$ ${(- 1)}^{𝑛 - 𝑐 (𝜎)}$ without Lemma 5.2.20 or Lemma 5.2.22.
(c)Show that the least number of transpositions whose product is $𝜎$ is $𝑛 - 𝑐 (𝜎)$ .

Solution.

Uses. Proposition 5.2.16 (Cycle decomposition), Lemma 5.2.17 (Cycles as products of transpositions), Definition 5.2.23 (Sign of a permutation)

Hint 1.

𝜎 𝜏

agrees with

𝜎

except at

𝑎

and

𝑏

(𝜎 𝜏) (𝑎) = 𝜎 (𝑏)

and

(𝜎 𝜏) (𝑏) = 𝜎 (𝑎)

. So only the orbits containing

𝑎

𝑏

can change.

Hint 2. If

𝑎

and

𝑏

are in one orbit, list it as

𝑎,

𝑥_{1},

\dots,

𝑥_{𝑝},

𝑏,

𝑦_{1},

\dots,

𝑦_{𝑞}

in the order

𝜎

visits it, and follow

𝜎 𝜏

from

𝑎

and from

𝑏

. If they are in different orbits, follow

𝜎 𝜏

from

𝑎

Hint 3. For (c), (a) shows that each transposition changes

𝑐

1

, and

𝑐 (id) = 𝑛

Sketch. (a) Same orbit

𝑎,

𝑥_{1},

\dots,

𝑥_{𝑝},

𝑏,

𝑦_{1},

\dots,

𝑦_{𝑞}

: under

𝜎 𝜏

𝑎 \mapsto 𝑦_{1} \mapsto \dots \mapsto 𝑦_{𝑞} \mapsto 𝑎

and

𝑏 \mapsto 𝑥_{1} \mapsto \dots \mapsto 𝑥_{𝑝} \mapsto 𝑏

, so the orbit splits in two. Different orbits

𝑎, 𝑥_{1}, \dots, 𝑥_{𝑝}

and

𝑏, 𝑦_{1}, \dots, 𝑦_{𝑞}

𝑎 \mapsto

𝑦_{1} \mapsto

\dots \mapsto

𝑦_{𝑞} \mapsto

𝑏 \mapsto

𝑥_{1} \mapsto

\dots \mapsto

𝑥_{𝑝} \mapsto

𝑎

, so they merge. (b) Start from

𝑐 (id) = 𝑛

; each factor changes

𝑐

\pm 1

. (c)

𝑟

factors give

𝑐 (𝜎) \geq 𝑛 - 𝑟

, and Lemma 5.2.17 gives

𝑛 - 𝑐 (𝜎)

factors.

(a) Since $𝜏$ fixes every point other than $𝑎$ and $𝑏$ , $(𝜎 𝜏) (𝑥) = 𝜎 (𝑥)$ for $𝑥 \notin {𝑎, 𝑏}$ , while $(𝜎 𝜏) (𝑎) = 𝜎 (𝑏)$ and $(𝜎 𝜏) (𝑏) = 𝜎 (𝑎)$ . An orbit of $𝜎$ containing neither $𝑎$ nor $𝑏$ is mapped into itself by $𝜎$ , hence by $𝜎 𝜏$ , on which they agree; so it is also an orbit of $𝜎 𝜏$ . It remains to see what happens to the orbits containing $𝑎$ or $𝑏$ .

Same orbit. By Proposition 5.2.16, the orbit of $𝑎$ is $𝑎,$ $𝜎 (𝑎),$ $𝜎^{2} (𝑎),$ $\dots$ until it returns to $𝑎$ , and $𝑏$ occurs in it. Write it as $𝑎,$ $𝑥_{1},$ $\dots,$ $𝑥_{𝑝},$ $𝑏,$ $𝑦_{1},$ $\dots,$ $𝑦_{𝑞}$ in this order, with $𝑝, 𝑞 \geq 0$ , so $𝜎$ sends $𝑎 \mapsto$ $𝑥_{1} \mapsto$ $\dots \mapsto$ $𝑥_{𝑝} \mapsto$ $𝑏 \mapsto$ $𝑦_{1} \mapsto$ $\dots \mapsto$ $𝑦_{𝑞} \mapsto$ $𝑎$ (where $𝑎 \mapsto 𝑥_{1}$ is read as $𝑎 \mapsto 𝑏$ if $𝑝 = 0$ , and so on). Then $𝜎 𝜏$ sends $𝑎 \mapsto$ $𝜎 (𝑏) =$ $𝑦_{1} \mapsto$ $\dots \mapsto$ $𝑦_{𝑞} \mapsto$ $𝜎 (𝑦_{𝑞}) =$ $𝑎$ and $𝑏 \mapsto$ $𝜎 (𝑎) =$ $𝑥_{1} \mapsto$ $\dots \mapsto$ $𝑥_{𝑝} \mapsto$ $𝜎 (𝑥_{𝑝}) =$ $𝑏$ . (If $𝑞 = 0$ , then $𝜎 (𝑏) = 𝑎$ and $𝑎$ is fixed by $𝜎 𝜏$ ; similarly if $𝑝 = 0$ .) So the orbit splits into the two orbits ${𝑎, 𝑦_{1}, \dots, 𝑦_{𝑞}}$ and ${𝑏, 𝑥_{1}, \dots, 𝑥_{𝑝}}$ of $𝜎 𝜏$ , and $𝑐 (𝜎 𝜏) = 𝑐 (𝜎) + 1$ .

Different orbits. Write them as $𝑎, 𝑥_{1}, \dots, 𝑥_{𝑝}$ and $𝑏, 𝑦_{1}, \dots, 𝑦_{𝑞}$ in the order $𝜎$ visits them. Then $𝜎 𝜏$ sends $𝑎 \mapsto$ $𝜎 (𝑏) =$ $𝑦_{1} \mapsto$ $\dots \mapsto$ $𝑦_{𝑞} \mapsto$ $𝜎 (𝑦_{𝑞}) =$ $𝑏 \mapsto$ $𝜎 (𝑎) =$ $𝑥_{1} \mapsto$ $\dots \mapsto$ $𝑥_{𝑝} \mapsto$ $𝜎 (𝑥_{𝑝}) =$ $𝑎$ , with the same conventions when $𝑝$ or $𝑞$ is $0$ . So the two orbits merge into one orbit of $𝜎 𝜏$ , and $𝑐 (𝜎 𝜏) = 𝑐 (𝜎) - 1$ .

(b) We show by induction on $𝑟$ that $𝑐 (𝜏_{1} \dots 𝜏_{𝑟}) -$ $(𝑛 - 𝑟)$ is even. For $𝑟 = 0$ , $𝑐 (id) = 𝑛$ . For the step, (a) gives $𝑐 (𝜏_{1} \dots 𝜏_{𝑟}) =$ $𝑐 (𝜏_{1} \dots 𝜏_{𝑟 - 1}) \pm 1$ , which changes $𝑐 - (𝑛 - 𝑟)$ by $\pm 1 + 1$ , an even number. So if $𝜎 =$ $𝜏_{1} \dots 𝜏_{𝑟} =$ $𝜏_{1}^{'} \dots 𝜏_{𝑠}^{'}$ , then $𝑟$ and $𝑠$ both have the parity of $𝑛 - 𝑐 (𝜎)$ , which proves Theorem 5.2.18, and $sgn (𝜎) =$ ${(- 1)}^{𝑟} =$ ${(- 1)}^{𝑛 - 𝑐 (𝜎)}$ .

(c) If $𝜎 = 𝜏_{1} \dots 𝜏_{𝑟}$ , then by (a) and induction, $𝑐 (𝜏_{1} \dots 𝜏_{𝑗}) \geq$ $𝑛 -$ $𝑗$ for each $𝑗$ , so $𝑐 (𝜎) \geq 𝑛 - 𝑟$ , that is, $𝑟 \geq 𝑛 - 𝑐 (𝜎)$ . On the other hand, Proposition 5.2.16 and Lemma 5.2.17 write $𝜎$ as a product of exactly $𝑛 - 𝑐 (𝜎)$ transpositions. So the least number is $𝑛 - 𝑐 (𝜎)$ .

Exercise 5.2.51.challengeBeyond 21-242 Let $𝑝$ be an odd prime and let $𝑎 \in 𝔽_{𝑝}$ with $𝑎 \neq 0$ . Multiplication by $𝑎$ permutes the nonzero elements $1, 2, \dots, 𝑝 - 1$ of $𝔽_{𝑝}$ ; let $𝜇_{𝑎} \in 𝑆_{𝑝 - 1}$ be the permutation with $𝜇_{𝑎} (𝑘) = 𝑎 𝑘$ , the product computed in $𝔽_{𝑝}$ .

(a)Show that $𝑎^{𝑝 - 1} = 1$ in $𝔽_{𝑝}$ .
(b)Show that $sgn (𝜇_{𝑎}) =$ $𝑎^{(𝑝 - 1) / 2}$ , where the right side is computed in $𝔽_{𝑝}$ and is therefore $1$ or $- 1$ . (This is Zolotarev’s lemma.)
(c)Check (b) for $𝑝 = 7$ and $𝑎 = 2, 3$ by finding the cycle notation of $𝜇_{2}$ and $𝜇_{3}$ .

Solution.

Uses. Corollary 5.2.24 (Formulas for the sign), Proposition 1.1.24 ( $ℤ / 𝑛 ℤ$ is a field if and only if $𝑛$ is prime), Proposition 1.1.17 (No zero divisors), Proposition 5.2.26 (Sign of a cycle)

Hint 1. For (a), multiply all the nonzero elements together, before and after applying

𝜇_{𝑎}

Hint 2. For (b), use Corollary 5.2.24 (b) over the field

𝔽_{𝑝}

, with

𝐱 =

(1, 2, \dots, 𝑝 - 1) \in

𝔽_{𝑝}^{𝑝 - 1}

. What is

𝐱^{𝜇_{𝑎}}

Hint 3. Each factor of

Δ (𝐱^{𝜇_{𝑎}})

𝑎 𝑗 -

𝑎 𝑖 =

𝑎 (𝑗 - 𝑖)

, and there are

(𝑝 - 1) (𝑝 - 2) / 2

factors. Then use (a) and that

𝑝 - 2

is odd.

Sketch. (a)

𝜇_{𝑎}

permutes the factors of

𝑃 = 1 \cdot 2 \dots (𝑝 - 1) \neq 0

, so

𝑎^{𝑝 - 1} 𝑃 = 𝑃

. (b) With

𝐱 = (1, \dots, 𝑝 - 1)

𝐱^{𝜇_{𝑎}} =

(𝑎, 2 𝑎, \dots, (𝑝 - 1) 𝑎)

, so

Δ (𝐱^{𝜇_{𝑎}}) =

𝑎^{𝑁} Δ (𝐱)

with

𝑁 = (𝑝 - 1) (𝑝 - 2) / 2

, and

Δ (𝐱) \neq 0

. By Corollary 5.2.24,

sgn (𝜇_{𝑎}) = 𝑎^{𝑁}

𝔽_{𝑝}

. With

ℎ = (𝑝 - 1) / 2

𝑎^{ℎ} = \pm 1

by (a), and

𝑎^{𝑁} =

{(𝑎^{ℎ})}^{𝑝 - 2} =

𝑎^{ℎ}

since

𝑝 - 2

is odd. (c)

𝜇_{2} = (1 2 4) (3 6 5)

is even and

2^{3} = 1

;

𝜇_{3} = (1 3 2 6 4 5)

is odd and

3^{3} = - 1

Since $𝑝$ is prime, $𝔽_{𝑝}$ is a field (Proposition 1.1.24). If $𝑎 𝑘 = 𝑎 𝑘^{'}$ then $𝑘 = 𝑘^{'}$ (multiply by $𝑎^{- 1}$ ), and $𝑎 𝑘 \neq 0$ for $𝑘 \neq 0$ , so $𝜇_{𝑎}$ is indeed a permutation of the $𝑝 - 1$ nonzero elements.

(a) Let $𝑃 =$ $1 \cdot$ $2 \dots (𝑝 - 1) \in$ $𝔽_{𝑝}$ , which is nonzero by Proposition 1.1.17. Since $𝜇_{𝑎}$ is a bijection of the nonzero elements, the products of $1, \dots, 𝑝 - 1$ and of $𝑎 \cdot$ $1,$ $𝑎 \cdot$ $2,$ $\dots,$ $𝑎 (𝑝 - 1)$ have the same factors in a different order, so they are equal: $𝑎^{𝑝 - 1} 𝑃 = 𝑃$ . Cancelling $𝑃$ gives $𝑎^{𝑝 - 1} = 1$ .

(b) Let $𝐱 =$ $(1, 2, \dots, 𝑝 - 1) \in$ $𝔽_{𝑝}^{𝑝 - 1}$ , so $𝑥_{𝑘} = 𝑘$ . Its entries are distinct, so $Δ (𝐱) \neq 0$ . The $𝑘$ -th entry of $𝐱^{𝜇_{𝑎}}$ is $𝑥_{𝜇_{𝑎} (𝑘)} = 𝑎 𝑘$ . So each factor of $Δ (𝐱^{𝜇_{𝑎}})$ is $𝑎 𝑗 -$ $𝑎 𝑖 =$ $𝑎 (𝑗 - 𝑖)$ , and since there are $𝑁 =$ $(\binom{𝑝 - 1}{2}) =$ $(𝑝 - 1) (𝑝 - 2) / 2$ factors,

Δ (𝐱^{𝜇_{𝑎}}) = 𝑎^{𝑁} Δ (𝐱) .

By Corollary 5.2.24 (b) over $𝐹 = 𝔽_{𝑝}$ , the left side is $sgn (𝜇_{𝑎}) Δ (𝐱)$ . Cancelling $Δ (𝐱) \neq 0$ , $sgn (𝜇_{𝑎}) = 𝑎^{𝑁}$ in $𝔽_{𝑝}$ . Let $ℎ = (𝑝 - 1) / 2$ . By (a), ${(𝑎^{ℎ})}^{2} = 1$ , so $𝑎^{ℎ} = \pm 1$ by Proposition 1.1.17. Since $𝑁 = ℎ (𝑝 - 2)$ and $𝑝 - 2$ is odd, $𝑎^{𝑁} =$ ${(𝑎^{ℎ})}^{𝑝 - 2} =$ $𝑎^{ℎ}$ . So $sgn (𝜇_{𝑎}) = 𝑎^{ℎ}$ in $𝔽_{𝑝}$ . Because $𝑝$ is odd, $1 \neq - 1$ in $𝔽_{𝑝}$ , so this equation in $𝔽_{𝑝}$ determines the integer $sgn (𝜇_{𝑎})$ .

(c) For $𝑝 = 7$ , $𝜇_{2}$ sends $1 \mapsto 2 \mapsto 4 \mapsto 1$ and $3 \mapsto 6 \mapsto 5 \mapsto 3$ , so $𝜇_{2} = (1 2 4) (3 6 5)$ , which is even by Proposition 5.2.26; and $2^{3} = 8 = 1$ in $𝔽_{7}$ . Also $𝜇_{3}$ sends $1 \mapsto 3 \mapsto 2 \mapsto 6 \mapsto 4 \mapsto 5 \mapsto 1$ , a $6$ -cycle, which is odd; and $3^{3} = 27 = - 1$ in $𝔽_{7}$ .

More practice

The practice bank has 34 exercises on this section’s topics.