Wednesday, July 04, 2007

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: Vi

Let Vi be a 1 x n matrix where for all j ≠ i, v1,j = 0 and v1,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 σ1(i), σ2(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).


det(A) = ∑ (k=1, n!) {(sign σk)[a1,σk(1)*...*an,σk(n)]}


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

Rowi(A) = ai,1*V1 + ai,2*V2 + ... + ai,n*Vn [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 Row2, we can further expand each of these sums in this way:

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

(5) Putting this all together gives us:

det(A) =

(6) Thus, we have nn 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:


where Pf(i) is a matrix derived from Vf(i). In other words:

Row1(Pf(i)) = Vf(1)
Row2(Pf(i)) = Vf(2)
Rown(Pf(i)) = Vf(n)

(8) Now if Pf(i) has any identical rows, then det(Pf(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 Pf(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 nn terms to obtain det(A).

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

(13) Putting this all together gives us that:

det(A) = ∑ (k=1, n!) {(sign σk)[a1,σk(1)*...*an,σk(n)]}

where σk is the permutation which corresponds with the permutation matrix Pf(i).



No comments :