The sign of a permutation, and realizing permutations as linear transformations.

Lemma 1. Let n ≥ 2. Let S_{n} be the group of permutations of {1, 2, …, n}. There exists a surjective homomorphism of groups

sgn : S_{n} ⟶ {±1}

(called the ‘sign’). It has the property that for every i ≠ j,

sgn( (ij) ) = −1.

Proof. Consider the polynomial in n-variables^{1}

p(x_{1}, …, x_{n}) = ∏_{i<j}(x_{i} − x_{j}).

Given a permutation σ we may define a new polynomial

∏_{i<j}(x_{σ(i)} − x_{σ(j)}).

Note that σ(i) ≠ σ(j) and for any pair k < ℓ we obtain in the new product either (x_{k} −x_{ℓ}) or (x_{ℓ}−x_{k}). Thus, for a suitable choice of sign sgn(σ) ∈ {±1}, we have^{2}

∏_{i<j}(x_{σ(i)} − x_{σ(j)}) = sgn(σ) ∏_{i<j}(x_{i} − x_{j}).

We obtain a function

sgn : S_{n} ⟶ {±1}.

This function satisfies sgn( (kℓ) ) = −1 (for k < ℓ): Let σ = (kℓ) and consider the product

∏_{i<j}(x_{σ(i)} − x_{σ(j)}) = (x_{ℓ} − x_{k}) ∏_{\begin{matrix}i<j \\ i≠k,j≠ℓ \end{matrix}} (x_{i} − x_{j}) ∏_{\begin{matrix}k<j \\ j≠ℓ \end{matrix}} (x_{ℓ} − x_{j}) ∏_{\begin{matrix}i<ℓ \\ i≠k \end{matrix}} (x_{i} − x_{k})

Counting the number of signs that change we find that

∏_{i<j}(x_{σ(i)} − x_{σ(j)}) = (−1)(−1)^{♯{j:k<j<ℓ}}(−1)^{♯{i:k<i<ℓ}} ∏_{i<j}(x_{i} − x_{j}) = − ∏_{i<j}(x_{i} − x_{j}).

It remains to show that sgn is a group homomorphism. We first make the innocuous observation that for any variables y_{1}, …, y_{n} and for any permuation σ we have

∏_{i<j}(y_{σ(i)} − y_{σ(j)}) = sgn(σ) ∏_{i<j}(y_{i} − y_{j}).

Let τ be a permutation. We apply this observation for the variables y_{i} := x_{τ(i)}. We get

sgn(τσ)p(x_{1}, …, x_{n}) = p(x_{τσ(1)}, …, x_{τσ(n)})
= p(y_{σ(1)}, …, y_{σ(n)})
= sgn(σ)p(y_{1}, …, y_{n})
= sgn(σ)p(x_{τ(1)}, …, x_{τ(n)})
= sgn(σ)sgn(τ)p(x_{1}, …, x_{n}).

1For n = 2 we get x_{1} − x_{2}. For n = 3 we get (x_{1} − x_{2})(x_{1} − x_{3})(x_{2} − x_{3}).

2For example, if n = 3 and σ is the cycle (123) we have

(x_{σ(1)} − x_{σ(2)})(x_{σ(1)} − x_{σ(3)})(x_{σ(2)} − x_{σ(3)}) = (x_{2} − x_{3})(x_{2} − x_{1})(x_{3} − x_{1}) = (x_{1} − x_{2})(x_{1} − x_{3})(x_{2} − x_{3}).

Hence, sgn( (1 2 3) ) = 1.

This gives

sgn(τσ) = sgn(τ)sgn(σ).
□

Calculating sgn in practice. Recall that every permutation σ can be written as a product of disjoint cycles

σ = (a_{1} … a_{ℓ})(b_{1} … b_{m}) … (f_{1} … f_{n}).

\underline{Claim}: sgn(a_{1} … a_{ℓ}) = (−1)^{ℓ−1}. \underline{Corollary}: sgn(σ) = (−1)^{♯ even length cycles}.

Proof. We write

(a_{1} … a_{ℓ}) = \underbrace{(a_{1}a_{ℓ}) … (a_{1}a_{3})(a_{1}a_{2})}_{ℓ−1 transpositions}.

Since a transposition has sign −1 and sgn is a homomorphism, the claim follows. □

A Numerical example. Let n = 11 and

σ = (\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 2 & 5 & 4 & 3 & 1 & 7 & 8 & 10 & 6 & 9 \end{matrix}) .

Then

σ = (1 2 5)(3 4)(6 7 8 10 9).

Now,

sgn( (1 2 5) ) = 1, sgn( (3 4) ) = −1, sgn( (6 7 8 10 9) ) = 1.

We conclude that sgn(σ) = −1.

Realizing S_{n} as linear transformations. Let 𝔽 be any field. Let σ ∈ S_{n}. There is a unique linear transformation

T_{σ} : 𝔽^{n} ⟶ 𝔽^{n},

such that

T (e_{i}) = e_{σ(i)}, i = 1, … n,

where, as usual, e_{1}, …, e_{n} are the standard basis of 𝔽^{n}. Note that

T_{σ} (x_{1} ; x_{2} ; ⋮ ; x_{n}) = (x_{σ^{−1}(1)} ; x_{σ^{−1}(2)} ; ⋮ ; x_{σ^{−1}(n)}) .

(For example, because T_{σ}x_{1}e_{1} = x_{1}e_{σ(1)}, the σ(1) coordinate is x_{1}, namely, in the σ(1) place we have the entry x_{σ^{−1}(σ(1))}.) Since for every i we have T_{σ}T_{τ} (e_{i}) = T_{σ}e_{τ(i)} = e_{στ(i)} = T_{στ} e_{i}, we have the relation

T_{σ}T_{τ} = T_{στ} .

The matrix representing T_{σ} is the matrix (a_{ij}) with a_{ij} = 0 unless i = σ(j). For example, for n = 4 the matrices representing the permutations (12)(34) and (1 2 3 4) are, respectively

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

Otherwise said,^{3}

T_{σ} = (e_{σ(1)} | e_{σ(2)} | … | e_{σ(n)}) = (e_{σ^{−1}(1)} ; ——– ; e_{σ^{−1}(2)} ; ——– ; ⋮ ; ——– ; e_{σ^{−1}(n)}) .

It follows that

sgn(σ) det(T_{σ}) = sgn(σ) det (e_{σ(1)} | e_{σ(2)} | … | e_{σ(n)})
= det (e_{1} | e_{2} | … | e_{n})
= det(I_{n})
= 1.

Recall that sgn(σ) ∈ {±1}. We get

det(T_{σ}) = sgn(σ).

3This gives the interesting relation T_{σ^{−1}} = T_{σ}^{t}. Because σ ↦ T_{σ} is a group homomorphism we may conclude that T_{σ}^{−1} = T_{σ}^{t}. Of course for a general matrix this doesn’t hold.