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.