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.

Determinant and Permutations

In today's blog, I show how the determinant of an n x n matrix can be computed using the permutations of the the sequence { 1 .. n }. [For review of the idea of the determinant, start here]

This formula is not practical for computation purposes since it requires the summation of n! terms [since there are n! permutations of n integers, see Corollary 1.1 here for details if needed].

The content in today's blog is taken straight from Matrices and Linear Algebra by Hans Schneider and George Philip Barker.

Let me start by offering a notation that I will use in establishing the proof.

Definition 1: V_i

Let V_i be a 1 x n matrix where for all j ≠ i, v_1,j = 0 and v_1,i=1.

Theorem 1: Determinant of a matrix based on permutations

Let A be an n x n matrix.

Let S(n) be the set of all permutations on the sequence {1, ..., n}. [We can see that S(n) has n! elements]

Let σ₁(i), σ₂(i), ..., σ_n!(i) represent each of the possible permutations of the sequence {1, ..., n} so that for all σ(i) ∈ S(i), there exists k such that σ(i) = σ_k(i).

Then:

det(A) = ∑ (k=1, n!) {(sign σ_k)[a_1,σk(1)*...*a_n,σk(n)]}

Proof:

(1) For any row i of a matrix A, we know that:

Row_i(A) = a_i,1*V₁ + a_i,2*V₂ + ... + a_i,n*V_n [See Definition 3 here if needed for matrix addition]

(2) Using the linear function of rows property of determinants (see Lemma 2, here), we know that:

det(A) =



=



=




Note: This last step comes from the multiplicative property of determinants. det(A_(kRi)) = k*det(A) [See Corollary 4.1 here]

(3) Since we can apply step #1 to Row₂, we can further expand each of these sums in this way:







(4) Indeed, in this way, we can continue to expand each a_u,v to get:






(5) Putting this all together gives us:

det(A) =




(6) Thus, we have nⁿ sums of determinants using the product rule (see Postulate 2, here) since:

(a) There are n ways to select an item from the first row.
(b) And n ways to select an item from the second row.
(c) etc. up to n ways to select an item from the nth row.

(7) We can think of each the multiples on the determinant as a function on {1, 2, ..., n} so that if we define a function f(i), we get:

a_1,f(1)*a_2,f(2)*...*a_n,f(n)*P_f(i)

where P_f(i) is a matrix derived from V_f(i). In other words:

Row₁(P_f(i)) = V_f(1)
Row₂(P_f(i)) = V_f(2)
...
Row_n(P_f(i)) = V_f(n)

(8) Now if P_f(i) has any identical rows, then det(P_f(i)) = 0 [See Corollay 1.1R, here]

(9) So, we can ignore all f(i) where f(i)=f(j) and i ≠ j and still get the same sum.

(10) But if we assume that f(i)=f(j) → i=j, then f(i) is a permutation (see Definition 1, here) and P_f(i) is a permutation matrix (see Definition 6, here)

(11) This means that we only need to consider n! (see Corollary 1.1, here) out of the nⁿ terms to obtain det(A).

(12) Now from our previous result, we know that if P_f(i) is a permuation matrix, then det(P_f(i)) = sign f(i). [See Theorem 4, here]

(13) Putting this all together gives us that:

det(A) = ∑ (k=1, n!) {(sign σ_k)[a_1,σk(1)*...*a_n,σk(n)]}

where σ_k is the permutation which corresponds with the permutation matrix P_f(i).

QED

References

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

Combinatorics

In today's blog, I review some basic formulas regarding permutations and combinations. These are standard counting formulas. I assume that you are familiar with factorials and exponents.
Postulate 1: Sum Rule

If there a ways to A and b ways to B with A,B being completely independent, then there are (a+b) ways to A or B.

Postulate 2: Product Rule

If there a ways to A and b ways to B and a process consists of doing step A and then doing step B, then there are a*b ways to the process (A then B).

Definition 1: Permutations P(n,r)

P(n,r) = the number of permutations possible by choosing r elements from n without allowing repeats.

Defintion 2: r-Permutation of n

An r-permutation of n is any ordering of r elements from a set n.

Lemma 1: r-permuations of n without repeats

P(n,r) = n!/(r-n)!

Proof:

(1) We can view the selection of r elements from n as a process of r steps where each step consists of select 1 of the remaining elements.

(2) For step1, we have n choices. For step2, we have n-1 choices and so on until we reach the last step where we have n-r+1 choices.

(3) Using the Product Rule above, this gives us:
P(r,n) = (n)*(n-1)*...*(n-r+1)

(4) Using some simple multiplication we get:

(n)*(n-1)*...*(n-r+1) = [(n)*(n-1)*...*(n-r+1)]*[(n-r)*...*(1)]/[(n-r)*...(1)] = = n!/(n-r)!

QED

Corollary 1.1: P(n,n) = n!

Proof:

This follows directly from Lemma 1 above since:

P(n,n) = n!/(n-n)! = n!/0! = n!/1 = n!

QED

Lemma 2: r-permutation of a set n with repeats

If repeats are allowed, then there are n^r ways to order r elements from a set n

Proof:

(1) We can view the selection of r elements from n as a process of r steps where each step consists of select 1 of the n elements.

(2) For step1, we have n choices. For step2, we have n choices and so on until we reach the last step where we still have n choices.

(3) Using the Product Rule above, this gives us:

Number of permutations = n*n*...*n = n^r

QED

Definition 3: Combinations C(n,r)

C(n,r) = the number of combinations possible by selecting r elements from a set of n without allowing repeats and ignoring the order of selection.

Definition 4: r-Combinations of a set n

r-Combinations of a set n refers to a set of r elements that are selected from a set of n elements.

Lemma 3: Nonrepeating r-combinations of a set n

C(n,r) = n!/(n-r)!r!

Proof:

(1) Let P(n,r) = the number of permutations of r elements from a set of n.

(2) Let C(n,r) = the number of r combinations from of a set of n elements.

(3) Let P(r,r) = the number of ways to order r elements.

[The number of ways of ordering r elements is logically equivalent to the number of nonrepeating permutations of r elements since each possible permutation corresponds to a possible ordering]

(4) Now, we can see that:
P(n,r) = C(n,r)*P(r,r)

Since the total number of permutations of r elements from the set of n is equal to the total number of combinations of r elements multiplied by the total number of orderings of these same r elements.

(5) This then gives us:

C(n,r) = P(n,r)/P(r,r) = [n!/(n-r)!][1/r!] = n!/(n-r)!r!

QED

Lemma 4: r-combinations of a set n with repeats

If repeats are allowed, then there are C(n+r-1,r) ways to select r elements from a set n

Proof:

(1) We can restate the problem in terms of (n-1) slashes (/) and r asterisks (*).

(2) We can characterize any selection of r elements as the placement of r asterisks within (n-1) slashes. For example, if we wanted to select 10 elements from 5 choices, we could represent the selection of 3 of the 1st, 2 of the 2nd, 3 of the third, 1 of the fourth, and 1 of the fifth as follows:

***/**/***/*/*

We can see that the 5 possible choices corresponds to the four slashes and the 10 selections corresponds to 10 asterisks.

(3) Another way to look at this is to consider each place to be an element. In the above example we have r + n - 1 = 14 elements.

(4) Selection with repeats, then, is the same as either selecting 4 out of 14 elements (if we select which ones are slashes) or selecting 10 out of 14 elements (if we select which ones are asterisks).

(5) Indeed, generalizing this result gives us:

C(r+n-1,r) = (r+n-1)!/(r)!(r+n-1-r)! = (r+n-1)!/(r)!(n-1)!

C(r+n-1,n-1) = (r+n-1)!(n-1)!(r+n-1-n+1)! = (r+n-1)!/(n-1)!(r)!

QED

Lemma 5: C(n,r) is an integer

Proof:

(1) For n=1, this is true since:

C(1,0) = 1!/(0!)(1!) = 1

C(1,1) = 1!/(1!)(0!) = 1

(2) Assume it is true for all r up to some n.

(3) To complete the proof, we only need to show that it is true for all r for n+1.

(4) We can do this using Pascal's Rule (see Theorem, here) which gives us:

C(n,k) + C(n,k-1) = C(n+1,k)

(5) We can now show that C(n+1,r) is an integer for all r ≤ n since:

C(n+1,r) = C(n,r) + C(n,r-1)

and C(n,r) is an integer and C(n,r-1) is an integer by step #2.

If r = n+1, then we have C(n+1,n+1) = (n+1)!/(n+1)!0! = 1

(6) By induction, we are done.

QED