Recall that \(\ell (\sigma )\) is the number of inversions of \(\sigma \), while \(\ell (\sigma ^{-1})\) is the number of inversions of \(\sigma ^{-1}\).

An inversion of \(\sigma \) is a pair \((i,j) \in [n] \times [n]\) such that \(i {\lt} j\) and \(\sigma (i) {\gt} \sigma (j)\). Likewise, an inversion of \(\sigma ^{-1}\) is a pair \((u,v) \in [n] \times [n]\) such that \(u {\lt} v\) and \(\sigma ^{-1}(u) {\gt} \sigma ^{-1}(v)\).

Thus, if \((i,j)\) is an inversion of \(\sigma \), then \((\sigma (j), \sigma (i))\) is an inversion of \(\sigma ^{-1}\). Hence, we obtain a map

This map is bijective (indeed, it has an inverse map, which sends each \((u,v) \in \{ \text{inversions of } \sigma ^{-1}\} \) to \((\sigma ^{-1}(v), \sigma ^{-1}(u))\)). Thus, the bijection principle yields

In other words, \(\ell (\sigma ) = \ell (\sigma ^{-1})\). (See [ Grinbe15 , Exercise 5.2 (f) ] for details.)

This combines parts (a) and (b).

The proof partitions the inversions of \(\sigma \) and \(\sigma s_k\) into two kinds. Call an inversion \((i,j)\) of a permutation \(\tau \) the key pair if \((i,j) = (k,k+1)\); all other inversions are non-key.

Key observation: There is a bijection between non-key inversions of \(\sigma \) and non-key inversions of \(\sigma s_k\), given by applying the swap \(k \leftrightarrow k+1\) to both coordinates. This bijection preserves the strict ordering of the pair coordinates because there is no element strictly between \(k\) and \(k+1\).

Thus

For the key pair \((k,k+1)\): it is an inversion of \(\sigma \) if and only if \(\sigma (k+1) {\lt} \sigma (k)\), and it is an inversion of \(\sigma s_k\) if and only if \(\sigma (k) {\lt} \sigma (k+1)\). So the key pair’s inversion status flips when we pass from \(\sigma \) to \(\sigma s_k\).

Combining these two observations: the number of inversions changes by exactly \(\pm 1\), depending on whether the key pair is added or removed.

We use the identity \(s_k \sigma = (\sigma ^{-1} s_k)^{-1}\) (since \(s_k\) is its own inverse) and then apply Proposition 3.54 and part (a).

This combines parts (a) and (b).

For \(k\) between \(i\) and \(j\) with \(k \neq i, j\), the swap \(t_{i,j}\) fixes \(k\), so \((\sigma \cdot t_{i,j})(k) = \sigma (k)\). The conditions \((\sigma t_{i,j})(j) {\lt} \sigma (k) {\lt} (\sigma t_{i,j})(i)\) become \(\sigma (i) {\lt} \sigma (k) {\lt} \sigma (j)\), which defines \(R\).

Since \((\sigma t_{i,j})(i) = \sigma (j) {\lt} \sigma (i) = (\sigma t_{i,j})(j)\), the pair \((i,j)\) is no longer an inversion after applying \(t_{i,j}\).

Direct verification using the definition of \(Q\) and the swap.

Direct verification using the definition of \(Q\) and the swap.

Direct verification.

Direct verification.

Direct verification.

Direct verification.

By case analysis on whether \(a\) or \(b\) equals \(i\) or \(j\), and using the fact that the swap only changes the values at positions \(i\) and \(j\).

By case analysis, similar to the lost inversion completeness.

By explicit enumeration and counting of the five types of lost inversions and two types of gained inversions.

Case \(\sigma (i) {\gt} \sigma (j)\): This is [ Grinbe15 , Exercise 5.20 ] . Apply Lemma 3.74 directly. The symmetric difference formula \(|\mathrm{inv}(\sigma t_{i,j})| + |\mathrm{lost}| = |\mathrm{inv}(\sigma )| + |\mathrm{gained}|\) together with \(|\mathrm{lost}| = |\mathrm{gained}| + 2|Q| + 1\) gives \(\ell (\sigma t_{i,j}) = \ell (\sigma ) - 2|Q| - 1\).

Case \(\sigma (i) {\lt} \sigma (j)\): Apply the previous case to \(\sigma t_{i,j}\) instead of \(\sigma \). Since \((\sigma t_{i,j})(i) = \sigma (j) {\gt} \sigma (i) = (\sigma t_{i,j})(j)\), and \(\sigma t_{i,j} t_{i,j} = \sigma \), and the sets \(Q\) and \(R\) trade places when we replace \(\sigma \) by \(\sigma t_{i,j}\), we obtain \(\ell (\sigma ) = \ell (\sigma t_{i,j}) - 2|R| - 1\), hence \(\ell (\sigma t_{i,j}) = \ell (\sigma ) + 2|R| + 1\).

This follows immediately from part (b): when \(\sigma (i) {\gt} \sigma (j)\), the formula gives \(\ell (\sigma t_{i,j}) = \ell (\sigma ) - 2|Q| - 1 {\lt} \ell (\sigma )\), and when \(\sigma (i) {\lt} \sigma (j)\), the formula gives \(\ell (\sigma t_{i,j}) = \ell (\sigma ) + 2|R| + 1 {\gt} \ell (\sigma )\).

This combines parts (a) and (b).

(See [ Grinbe15 , Exercise 5.2 (e) ] for details.)

We proceed by strong induction on \(\ell (\sigma )\).

Base case: If \(\ell (\sigma ) = 0\), then \(\sigma = \mathrm{id}\) (a permutation with no inversions is the identity), so the empty word works.

Induction step: If \(\ell (\sigma ) = h + 1 {\gt} 0\), then \(\sigma \) has at least one inversion, so there exists \(k \in [n-1]\) with \(\sigma (k) {\gt} \sigma (k+1)\). By Lemma 3.56 (a), \(\ell (\sigma s_k) = \ell (\sigma ) - 1 = h\). By the induction hypothesis, \(\sigma s_k\) has a reduced word \(w\) of length \(h\). Then \(w \mathbin {+\! +} [k]\) is a reduced word of length \(h+1\) for \(\sigma s_k \cdot s_k = \sigma \).

(See [ Grinbe15 , Exercise 5.2 (g) ] for details.)

We prove \(\ell (s_{k_1} s_{k_2} \cdots s_{k_g}) \leq g\) by induction on \(g\). The base case \(g = 0\) gives \(\ell (\mathrm{id}) = 0\). For the induction step, Lemma 3.56 (b) gives \(\ell (s_k \cdot \tau ) \leq \ell (\tau ) + 1\) for any \(\tau \) and \(k\), so \(\ell (s_{k_1} \cdots s_{k_g}) \leq \ell (s_{k_2} \cdots s_{k_g}) + 1 \leq (g-1) + 1 = g\).

Immediate from parts (a) and (b).

This combines parts (a), (b), and (c).

(See [ Grinbe15 , Exercise 5.2 (b) ] for details.)

Write \(\tau = s_{k_1} s_{k_2} \cdots s_{k_q}\) with \(q = \ell (\tau )\) (using Theorem 3.81 (a)). Then

(See [ Grinbe15 , Exercise 5.2 (c) ] for details.)

Get reduced words \(w_1, w_2\) for \(\sigma , \tau \). Then \(w_1 \mathbin {+\! +} w_2\) represents \(\sigma \tau \), so \(\ell (\sigma \tau ) \leq |w_1 \mathbin {+\! +} w_2| = |w_1| + |w_2| = \ell (\sigma ) + \ell (\tau )\) by Theorem 3.81 (b).

The inequality \(q \geq \ell (\sigma )\) is Theorem 3.81 (b). The parity claim \(q \equiv \ell (\sigma ) \pmod{2}\) is proved by the same telescoping argument as part (a), starting from \(\ell (\sigma ) = \ell (s_{k_1} \cdots s_{k_q})\) and peeling off one simple at a time.

This follows directly from Theorem 3.81 (a): every \(\sigma \in S_n\) can be written as a product of simple transpositions, so every \(\sigma \) lies in the subgroup generated by the simples.

The map \((i,j) \mapsto (i, \sigma ^{-1}(j))\) is a bijection from Rothe diagram cells to inversions: the condition \(j {\lt} \sigma (i)\) becomes \(\sigma (\sigma ^{-1}(j)) {\lt} \sigma (i)\), which is \(\sigma (k) {\lt} \sigma (i)\) with \(k = \sigma ^{-1}(j) {\gt} i\).

The set counted by \(\ell _i(\sigma )\) is a subset of \(\{ j : j {\gt} i\} \), which has cardinality \(n - 1 - i {\lt} n - i\).

The elements \(j {\gt} 0\) with \(\sigma (j) {\lt} \sigma (0)\) are in bijection (via \(j \mapsto \sigma (j)\)) with elements \(v {\lt} \sigma (0)\). Since \(\sigma \) is a bijection, there are exactly \(\sigma (0)\) such elements.

The Lehmer entry \(\ell _i(\sigma )\) counts \(j {\gt} i\) with \(\sigma (j) {\lt} \sigma (i)\). We split this count by whether \(j = i'\) or \(j {\gt} i'\): \(\ell _i(\sigma ) = [[\sigma (i') {\lt} \sigma (i)]] + |\{ j {\gt} i' : \sigma (j) {\lt} \sigma (i)\} |\). The set \(\{ j {\gt} i' : \sigma (j) {\lt} \sigma (i)\} \) contains \(\{ j {\gt} i' : \sigma (j) {\lt} \sigma (i')\} \) (counted by \(\ell _{i'}(\sigma )\)) when \(\sigma (i') {\lt} \sigma (i)\), from which the equivalence follows.

For each \(i\), the value \(\sigma (i)\) equals \(|\{ j : \sigma (j) {\lt} \sigma (i)\} |\) (since \(\sigma \) is a bijection onto \(\{ 0, \ldots , n-1\} \)). The hypothesis implies \(\{ j : \sigma (j) {\lt} \sigma (i)\} = \{ j : \tau (j) {\lt} \tau (i)\} \) for each \(i\), so \(\sigma (i) = \tau (i)\).

The block consists of \(\ell _i(\sigma )\) simple transpositions by construction.

Each block \(a_i\) has length \(\ell _i(\sigma )\), and the total length is \(\sum _i \ell _i(\sigma ) = \ell (\sigma )\) (since each inversion contributes to exactly one Lehmer entry).

By a bijection between the set of pairs \(\{ (i, j) : i \in [n],\ j \text{ such that } (i,j) \text{ is an inversion}\} \) and the set of all inversions.

The set \(\{ j : j {\lt} i\} \) has cardinality \(i\) and splits into \(\{ j {\lt} i : \sigma (j) {\lt} \sigma (i)\} \) and \(\{ j {\lt} i : \sigma (j) {\gt} \sigma (i)\} \), which are disjoint (since \(\sigma \) is injective, \(\sigma (j) \neq \sigma (i)\) for \(j \neq i\)).

The elements \(j\) with \(\sigma (j) {\lt} \sigma (i)\) partition into those with \(j {\lt} i\) (counted by \(s(\sigma , i)\)) and those with \(j {\gt} i\) (counted by \(\ell _i\)). Their total count is \(\sigma (i)\).

From \(\sigma (p) = s(\sigma , p) + \ell _p(\sigma )\) and \(p = s(\sigma , p) + g(\sigma , p)\), we get \(p + \ell _p(\sigma ) - g(\sigma , p) = \sigma (p)\).

Follows from the formulas \(\sigma (i) = s(\sigma , i) + \ell _i(\sigma )\) and \(i = s(\sigma , i) + g(\sigma , i)\).

We refer to [ Grinbe15 , Exercise 5.21 parts (b) and (c) ] for a detailed proof.

We prove by extensionality: for each position \(p\), we track where it ends up after applying all blocks.

By tracking position \(p\) through all blocks, the final position is

Since \(p = s(\sigma , p) + g(\sigma , p)\) and \(\sigma (p) = s(\sigma , p) + \ell _p(\sigma )\) (Lemma 3.104), we get

Combine Proposition 3.107 (the product of the canonical reduced word equals \(\sigma \)) with the length equality from Lemma 3.99 (\(|w(\sigma )| = \ell (\sigma )\)).