Permutation Matrix

In today's blog, I will talk about Permutation Matrices. These matrices are later used in my blog about permutations and determinants.

Today's blog is taken straight from Matrices and Linear Algebra by Hans Schneider and George Philip Barker.

Definition 1: Permutation of a sequence 1 ... n.

If σ(i) is a permutation of the sequence for 1 ≤ i ≤ n, then for all 1 ≤ i ≤ n,
(i) σ(i) = k where 1 ≤ k ≤ n
(ii) 1 ≤ i,j ≤ n, if σ(i)=k and i ≠ j, then σ(j) ≠ k.

Definition 2: Inversion in the permutation

Let σ(i) be a permutation. An inversion exists for each integers i,j such that i is less than j but σ(i) is greater than σ(j).

So, for example, if σ(i) = { 3, 2, 1 }, we can see that there are three inversions:

σ(1)=3 is greater than σ(2)=2
σ(1)=3 is greater than σ(3)=1
σ(2)=2 is greater than σ(3)=1

Definition 3: sign of a permutation

Let σ(i) be a permutation. The sign of σ(i) is the value (-1)^u where u is the number of inversions in the permutation σ(i). If u is even, then σ(i) is called an even permutation. If u is odd, then σ(i) is called an odd permutation.

Definition 4: Transposition of a sequence 1 .. n

A transposition is a permutation of a sequence 1 ... n that switches two values. If σ(i) is a transposition then:
(i) There exists i,j where i ≠ j and 1 ≤ i ≤ n and 1 ≤ j ≤ n.
(ii) σ(i) = j and σ(j)=i
(iii) If 1 ≤ k ≤ n and k ≠ i and k ≠ j, then σ(k)=k.

Lemma 1: Sign of a Transposition

If two integers are transposed in a permutation, then the sign of the permutation switches. If it was an odd permutation, then after the transposition, it is even. If it was an even permutation, then after the transposition, it is odd.

Proof:

(1) Let σ(i) be a permutation such that σ(i) = { σ(1), ..., σ(i), ..., σ(j), ..., σ(n) } where i is less than j.

(2) If we wish to transpose the integer at position i with the integer at position j and keep track of all the inversions, then we need to do a series of sequential transpositions:

(a) First, we need to transpose the integer in position i with the integer at position i+1.

(b) Next, we need to transpose the integer in position i+1 with the integer at position i+2.

(c) We continue in this this process until we transpose the integer at j-1 with the integer at j.

(3) With each of these sequential transpositions, if σ(k),σ(k+1) was an inversion, then we have removed it. If σ(k), σ(k+1) was not an inversion, then we have added one.

(4) We can see that moving the integer at position i to the position j requires the following sequential transpositions:

i+0,i+1
i+1,i+2
...
i+(j-i-1),i+(j-i)

(5) That is, it required i+0 ... i+(j-i-1) = j-i sequential transpositions

(6) But now, we need to move the integer that was previously at position j (now at position j-1) to position i.

(7) We now do sequential swaps the other way so that we have:

j-1, j-2
...
j-(j-i-1),j-(j-i)

(9) That is, it requires j-1 .. j-(j-i-1) = (j-i-1) transpositions

(10) So, the total number of transpositions is (j-i) + (j-i-1) = 2(j-i)-1

(11) This is an odd number so that if the sign was even before the transposition of i,j, then the new sign is odd. If the sign was odd before the transposition of i,j, then the new sign is even.

(12) In short, if (-1)^u is the sign of σ(i) before the transposition, then (-1)*(-1^u) = (-1)^u+1 is the sign after the transposition.

QED

Definition 5: Identity Permutation

Let σ(i) be a permutation such that σ(i) = i. This permutation denoted by ε is the permutation that leaves all integers fixed.

Since there are no inversions, the identity permutation is an even permutation and its sign is (-1)⁰=1.

Lemma 2: Every permutation can be obtained from the identity permutation by a sequence of transpositions

Proof:

(1) To establish this proof, I will present an algorithm for obtaining any permutation σ(i) by a sequence of transpositions.

(2) If σ(1)=1, then there is nothing to do in this step. Otherwise, we use the method outlined in lemma 1 above to transpose the integer at position 1 with the integer at position σ(1).

(3) We label this result σ₁(i) where we have:

σ₁(i) = { σ(1), 2, ..., σ(1)-1, 1, σ(1)+1, ..., n }

(4) If σ(2)=2, then there is nothing to do in this step. Otherwise, we use the method outlined in lemma 1 above to tranpose the integer at position 2 with the integer at position σ(2).

(5) We label this result σ₂(i) where we have:

σ₂(i) = { σ(1), σ(2), ..., n }

(6) In this way, it is possible to built the permutation σ_i-1(i) such that:

σ_i-1(1) = σ(1)
σ_i-1(2) = σ(2)
...
σ_i-1(i-1) = σ(i-1)

(7) To obtain σ_i(i), all we need to do in transpose the integer at position i-1 with the integer at position σ(i).

(8) After this, we have:

σ_i(1) = σ(1)
σ_i(2) = σ(2)
...
σ_i(i) = σ(i)

(9) In this way, after at most n steps, we obtain σ(i) = σ_n(i) since each step is either a transposition or else it is the identity permutation which can be skipped.

QED

Lemma 3:

If sigma;(i) is obtained from the identity permutation by n transpositions, then sign σ(i) = (-1)ⁿ

Proof:

(1) The identity permutation is even. [See definition 5 above]

(2) So, it is clear that this lemma is true for n=0.

(3) Assume that it is true up to n.

(4) Using Lemma 1 above, it is clear that with every transposition, the sign switches.

(5) Let τ(i) be the permutation that consists of n transpositions and σ(i) be the permuation that consists of n+1 transpositions where the first n transpositions lead to τ(i).

(6) The inductive hypothesis gives us that sign τ(i) = (-1)ⁿ.

(7) Since σ(i) is τ(i) followed by 1 transposition, lemma 1 above gives us that sign σ(i) = (-1)*(-1)ⁿ = (-1)ⁿ⁺¹

QED

Definition 6: Permutation Matrix

Let σ(i) be a permutation on { 1, ..., n }. The matrix P_σ(i) for which each row consists entirely of 0's except for one 1.

For example, if P_σ(i) is the permutation matrix which represents the permutation of { 1, 2, 3, 4 } to { 3, 2, 4, 1}, then we would have:

P_σ(i) =



We can see that:






Theorem 4: Determinant of the Permutation Matrix

Let P_σ(i) be a permutation matrix.

Then:

det(P_σ(i)) = sign σ(i)

Proof:

(1) By Lemma 2 above, we can use the identity permutation to make a sequence of transpositions to obtain σ(i).

(2) Let n be the number of transpositions required.

(3) Then by Lemma 3 above, sign σ(i) = (-1)ⁿ

(4) We can represent each transposition as a single row of a permutation matrix.

(5) Since each row of the permutation matrix corresponds to a multiplication by an elementary matrix I_{(Ri ↔ Rj)} [see Definition 2, here for definition of I_{(Ri ↔ Rj)}] since

It is clear that the permutation matrix can be derived from the identity matrix [See Definition 1, here for definition of identity matrix] using a series of
I_{(Ri ↔ Rj)} multiplications [See Lemma 1, here and Corollary 4.1, here]

(6) Since there are n such rows, it follows that det(P_σ(i)) = (-1)ⁿ [See Lemma 9, here]

(7) Hence det(P_σ(i)) = sign σ(i).

QED

References

• Hans Schneider, George Philip Barker, Matrices and Linear Algebra, 1989.