Cofactor Expansion

In today's blog, I provide a general method for computing the determinant using cofactor expansion. This is taken from Matrices and Linear Transformations by Charles G. Cullen.

Lemma 1R:

If the rows of an n x n matrix A are linearly dependent, det(A)=0

Proof:

(1) Let A be an n x n matrix with rows that are linearly dependent.

[See Definition 1, here for review of linearly independent]

(2) Then, there exists α_i such that:

α₁R₁ + ... + α_nR_n = 0.

(3) Then, it is possible to use elementary operations to set R₁ = 0 since:

(a) Multiply R₁ with α₁

(b) For each row i (where i = 2 .. n), add α_i*R_i to R₁.

(c) By step #2, it is clear after (a) and after each addition (b), R₁ = 0.

(4) So we have:

A_(0R1) = E_nE_n-1...E₂E₁A where E_i is an elementary operation. [See Theorem 5, here for review of how elementary operations map to multiplication]

(5) Using the definition of determinants [See Definition 4, here], we have:

det(A_(0R1)) = 0 [See Lemma Corollary 4.2, here]

(6) Using our previous results, we know that all det(E_i) ≠ 0. (See Lemma 4, Lemma 7, and Lemma 9 here)

(7) It therefore follows that det(A) = 0 since det(A_(0R1)) = det(E_n)det(E_n-1)...det(E₂)det(E₁)det(A)

QED

Corollary 1.1R: If A is a matrix with two identical rows, then det(A)=0

Proof:

(1) Let A be an n x m matrix where row i = row j and i ≠ j.

(2) We can define the set α_k such that:

if k = i, then α_k=1
if k = j, then α_k=-1
otherwise, α_k=0

(3) Clearly, α₁R₁ + ... + α_nR_n=0 where not all α_k = 0.

(4) Therefore, the rows of A of linearly dependent and using Lemma 1 above, det(A)=0.

QED

Lemma 1C:

If the columns of an n x n matrix A are linearly dependent, det(A)=0

Proof:

(1) Let A be an n x n matrix with columns that are linearly dependent.

[See Definition 1, here for review of linearly independent]

(2) Then, there exists α_i such that:

α₁C₁ + ... + α_nCn = 0.

(3) Then, it is possible to use elementary operations to set C₁ = 0 since:

(a) Multiply C₁ with α₁

(b) For each column i (where i = 2 .. n), add α_i*C_i to C₁.

(c) By step #2, it is clear after (a) and after each addition (b), C₁ = 0.

(4) So we have:

A_(0C1) = AE_nE_n-1...E₂E₁ where E_i is an elementary operation. [See Theorem 5, here for review of how elementary operations map to multiplication]

(5) Using the definition of determinants [See Definition 4, here], we have:

det(A_(0C1)) = 0 [See Lemma Corollary 4.2, here]

(6) Using our previous results, we know that all det(E_i) ≠ 0. (See Lemma 4, Lemma 7, and Lemma 9 here)

(7) It therefore follows that det(A) = 0 since det(A_(0C1)) = det(E_n)det(E_n-1)...det(E₂)det(E₁)det(A)

QED

Corollary 1.1C: If A is a matrix with two identical columns, then det(A)=0

Proof:

(1) Let A be an n x m matrix where row i = row j and i ≠ j.

(2) We can define the set α_k such that:

if k = i, then α_k=1
if k = j, then α_k=-1
otherwise, α_k=0

(3) Clearly, α₁R₁ + ... + α_nR_n=0 where not all α_k = 0.

(4) Therefore, the rows of A of linearly dependent and using Lemma 1 above, det(A)=0.

QED

Lemma 2: det(A) is a linear function of the rows of A

That is,

if three matrices A,B,C are exactly the same except for one row where this row is α for A, β for B, and (α + β) for C, then:

det(C) = det(A) + det(B)

Proof:

(1) Assume that the rows which are the same in A,B, and C are linearly dependent. [See Definition 1, here]

(2) Then det(A)=0, det(B)=0, and det(C)=0. [See Lemma 1 above]

(3) So that we have 0 = det(C) = det(A) + det(B) = 0 + 0

(4) Assume that all the rows but the first row are the same and that none of these rows are linearly dependent.

(5) Let F_{1 x n} be the set of all possible rows of length n.

(6) F_{1 x n} is a vector space. [See Definition 2, here for definition of vector space]

(7) Since [ R₂, R₃, ..., R_n ] are linearly independent, we can use this list to build a basis: [ ε, R₂, R₃, ..., R_n]. [See Theorem 1, here]

(8) Since [ ε, R₂, R₃, ..., R_n] is a basis (see Definition 2, here for definition of basis), we have:

Row₁(A) = α = a₁ε + a₂R₂ + ... + a_nR_n

Row₁(B) = β = b₁ε + b₂R₂ + ... + b_nR_n

Row₁(C) = (α + β) = (a₁ + b₁)ε + (a₂ + b₂)R₂ + ... + (a_n + b_n)R_n

(9) For A,B,C we can use I_{(kRj + Ri)} to simplify the first row [See Definition 3, here for definition of A_{(kRj + Ri)}].

For A, we set each k=a_i and then use R_i. In this way, we can reduce α to a₁*ε. Likewise, we can reduce β to b₁*ε and finally, we can reduce (α + β) to (a₁ + b₁)ε.

(10) Since det(AB) = det(A)det(B) [See Definition 4, here] and since det(I_{(kRj + Ri)} = 1 [See Lemma 7, here] , it follows that:

det(A) =



det(B) =



det(C) =



(11) It is also true that (see Definition 4, here):

det(A) =



det(B) =



det(C) =



(12) And it is true that:

det(C) = det(A) + det(B)

(13) Now, we have one last case to deal with. In this case, A,B,C are all the same except for a row r that is not the first row and all other rows are linearly independent.

(14) Now, from the elementary operations (see Lemma 9, here), we know that:

det(A*I_{(Ri ↔ R1)}) = det(A)*(-1)

det(B*I_{(Ri ↔ R1)}) = det(B)*(-1)

det(C*I_{(Ri ↔ R1)}) = det(C)*(-1)

(15) Now from step #4 thru step #12, we know that:

det(C*I_{(Ri ↔ R1)}) = det(A*I_{(Ri ↔ R1)}) + det(B*I_{(Ri ↔ R1)}) =

= -det(C) = -det(A) + -det(B)

(16) Multiplying both sides by -1 gives us:

det(C) = det(A) + det(B)

QED

Corollary 2.1: det(A) is a linear function of the rows of A

That is,

if three matrices A,B,C are exactly the same except for one column where this row is α for A, β for B, and (α + β) for C, then:

det(C) = det(A) + det(B)

Proof:

(1) Using Lemma 2 above, we have:

det(C^T) = det(A^T) + det(B^T)

(2) Using Theorem 9 here, we have:

det(C^T) = det(C) det(A^T) = det(A)' det(B^T) = det (B)
(3) Putting this all together gives us:
det(C) = det(A) + det(B)

QED

Definition 1: Minor M_i,j(A)

For an n x n matrix A, the minor of a_i,j, M_i,j(A), is the n-1 x n-1 submatrix of A obtained by deleting row i and column j of A.

Definition 2: Cofactor

For an n x n matrix A, the cofactor of a_i,j, cof_i,j(A), is defined as (-1)^i+jdet(M_i,j(A)).

Lemma 3:

Let B be an F_{n x n} matrix of the form:



then:

det(B) = det(M_1,1(B)) = cof_1,1(B).

Proof:

(1) Using the elementary row operation I_{(kRj + Ri)} [See Definition 3, here] we can reduce B to the following form:



(2) Let E₁*....*E_t be a representation of M_1,1(B) as a product of n-1 x n-1 elementary matrices. [See Theorem 6, here]

(3) Now, we have:









det(E₁)*...*det(E_t) = det(E₁*...*E_t) = det(M₁₁(B))

QED

Corollary 3.1:

Let B be an F_{n x n} matrix of the form:



then:

det(B) = det(M_1,1(B)) = cof_1,1(B).

Proof:

(1) Using Lemma 3 above, we have:

det(B^T) = det(M_1,1(B)) = cof_1,1(B).

(2) Using Theorem 9 here, we have:

det(B) = det(B^T)

QED

Theorem 4: Cofactor Expansion of rows

The determinant of an n x n matrix can be computed as the sum of products of the elements of any row and their cofactors.

That is:

det(A) = ∑(j=1,n) a_i,jcof_i,j(A)

Proof:

(1) Let A be an n x n matrix.

(2) Let i be the row that we wish to use to compute det(A).

(3) Using Row operation II (I_{(Ri ↔ Rj)}), we move row i to row 1 by switching row i ↔ row (i-1) and row (i-1) ↔ row (i-2) ↔ ... ↔ row(2) ↔ row(1).

(4) We can see that there are i-1 such operations and at the end of it, we are left with the following order:



(5) Since det(I_{(Ri ↔ Rj)}) = -1, the (i-1) row operations gives us:





(6) Using Lemma 2 above, we have:
det(A) =



(7) Using Column Operation II, we can move the nonzero column at column j (where j represents the current column) to column 1. This consists of the same type of operation as before:

column i ↔ column (j-1) and column (j-1) ↔ column (j-2) ↔ ... ↔ column(2) ↔ column(1).

(8) This gives us (-1)⁰ for j=1, (-1)¹ for j=2, and so on so that we get:

det(A) = (-1)^(i-1)[(-1)^(1-1)det([a_i,1*]) + (-1)^(2-1)det([a_i,2*]) + ... + (-1)^(n-1)det([a_i,n*]) ]

where [a_i,j*] is the determinant of the [a_i,j] after it has been moved to column 1 using column operations.

(9) Since (-1) to an even number = 1 and (-1) to an odd number = -1, we can simplify step #8 to the following:

det(A) = (-1)^i-1[



]

(10) Using row operation I (I_(kRi)), we further get:

det(A) = (-1)^i-1[



]

(11) We can now plug in Lemma 3 above to complete the proof:

det(A) =
(-1)^i-1[a_i,1det(M_i,1(A)) - a_i,2det(M_i,2(A)) + a_i,3det(M_i,3(A)) - a_i,4det(M_i,4(A)) + ...] =

(-1)^i-1[a_i,1cof_i,1(A) - a_i,2cof_i,2(A) + a_i,3cof_i,3(A) - a_i,4cof_i,4(A) + ... ]

QED

The implication of Theorem 4 is that we can now establish a recursive method for obtaining the determinant of an n x n matrix.

Algorithm 1: Find the determininant of any n x n matrix

(1) If n x n is a 2 x 2 matrix, then the determinant is:



(2) If n x n is not a 2 x 2 matrix, then the determinant can be derived from the determinant of the Minor of n x n so that:

det(n x n) = a_1,1det(M_1,1) - a_1,2det(M_1,2) + ... + (-1)^(n-2)a_1,(n-1)det(M_1,(n-1) + (-1)^(n-1)a_1,ndet(M_1,n).

Corollary 4.1: Cofactor Expansion of columns

The determinant of an n x n matrix can be computed as the sum of products of the elements of any column and their cofactors.

That is:

det(A) = ∑(i=1,n) a_i,jcofactor_i,j(A)

Proof:

(1) Let A be an n x n matrix.

(2) Let j be the column that we wish to use to compute det(A).

(3) Using Column operation II (I_{(Ci ↔ Cj)}), we move column j to column 1 by switching column j ↔ column (j-1) and column (j-1) ↔ column (j-2) ↔ ... ↔ column(2) ↔ column(1).

(4) We can see that there are j-1 such operations and at the end of it, we are left with the following order:



(5) Since det(I_{(Ci ↔ Cj)}) = -1,

det(A) = (-1)^(j-1)det([Col_j Col₁ ... Col_n])

(6) Using Corollary 2.1 above, we have:
det(A) = (-1)^(j-1)[det([a_1,j]) + det([a_2,j]) + ... + det([a_n,j])]

where [a_i,j] is the matrix derived from A where all values in column j are empty except for a_i,j.

(7) Using Row Operation II (I_{(Ri ↔ Rj)}), we can move this nonzero row at row i to row 1. This consists of the same type of operation as before:

row i ↔ row (i-1) and row (i-1) ↔ row (i-2) ↔ ... ↔ row(2) ↔ row(1).

(8) This gives us (-1)⁰ for i=1, (-1)¹ for i=2, and so on so that we get:

det(A) = (-1)^(j-1)[(-1)^(1-1)det([a_1,j*]) + (-1)^(2-1)det([a_2,j*]) + ... + (-1)^(n-1)det([a_n,j*]) ]

where [a_i,j*] is the determinant of the [a_i,j] after it has been moved to row 1 using row operations.

(9) Since (-1) to an even number = 1 and (-1) to an odd number = -1, we can simplify step #8 to the following:

det(A) = (-1)^(j-1)[det([a_1,j*]) - det([a_2,j*]) + ... {+/-} det([a_n,j*]) ]

where [a_i,j*] is the determinant of the [a_i,j] after it has been moved to row 1 using row operations.

(10) We can use column operation I (I_(kCi))to convert each matrix into this form:

det(A) = (-1)^(j-1)[a_1,jdet([a_i,j**]) - a_2,jdet([a_2,1**] + ... ]

where a_i,jdet([a_i,j**]) = det([a_i,j*])

(11) We can now plug in Corollary 3.1 above to complete the proof:

det(A) = (-1)^i-1[a_i,1det(M_i,1(A)) - a_i,2det(M_i,2(A)) + a_i,3det(M_i,3(A)) - a_i,4det(M_i,4(A)) + ...] =

(-1)^i-1[a_i,1cof_i,1(A) - a_i,2cof_i,2(A) + a_i,3cof_i,3(A) - a_i,4cof_i,4(A) + ... ]

QED

References

• Charles G. Cullen, Matrices and Linear Transformations, Dover Publications, Inc., 1972.

Determinant of an n x n matrix

In a previous blog, I defined the determinant of a 2 x 2 matrix as:



In today's blog, I will offer a more general definition that is taken from Matrices and Linear Transformations by Charles G. Cullen.

Before offering this definition, I need to establish some notation for elementary operations of matrices. See here for review of these elementary operations.

Definition 1: A_(kRi)

This is the matrix that results from multiplying a scalar k to the ith row of the matrix A.

Definition 2: A_{(Ri ↔ Rj)}

This is the matrix that results from interchanging row i with row j in the matrix A.

Definition 3: A_{(kRj + Ri)}

This is the matrix that results from adding (a scalar k * row j) to row i in the matrix A.

Now, I can use these definitions to offer a more general definition of the determinant of an n x n matrix:

Definition 4: Determinant of an n x n matrix A det(A)

A function is said to be the determinant of an n x n matrix if:
(I) det(AB) = det(A)*det(B)
(II) det(I_(kR1)) = k

NOTE: I_(kR1) is the identity matrix I_n with k multiplied to row 1 in I. [See here for details on how modifying the identity matrix and how this relates to elementary operations.]

For example, I_(5R1) =



since for identity I₂:




Now, from our previous result, we have shown that the above rule applies to 2 x 2 matrices.

Lemma 1: 2 x 2 matrices are determinants by Definition 4 above

Proof:

(1) Let A, B be 2 x 2 matrices.

(2) det(AB) = det(A)det(B) [See Lemma 1 here]

(3) I_(kR1) =



(4) Using the definition of determinant for 2 x 2 matrices gives us:

k*1 - 0*0 = k

(5) Thus, we have shown that our proposed definition is consistent with the previous definition for 2 x 2 matrices.

QED

Lemma 2: I_(kRj) = I_{(Rj ↔ R1)}I_(kR1)I_{(Rj ↔ R1)}

Proof:

(1) I =




(2) I_{(Rj ↔ R1)} =



(3) I_(kR1)I_{(Rj ↔ R1)}



(4) I_{(Rj ↔ R1)}I_(kR1)I_{(Rj ↔ R1)}



QED

Lemma 3: I_{(Rj ↔ R1)}I_{(Rj ↔ R1)} = I.

Proof:

(1) I =



(2) I_{(Rj ↔ R1)} =



(3) I_{(Rj ↔ R1)}I_{(Rj ↔ R1)} =



QED

Lemma 4: det(I_(kRj)) = k

Proof:

(1) det(I_(kRj)) = det( I_{(Rj ↔ R1)}I_(kR1)I_{(Rj ↔ R1)} ) [See Lemma 2 above]

(2) det( I_{(Rj ↔ R1)}I_(kR1)I_{(Rj ↔ R1)} ) = det( I_{(Rj ↔ R1)} )det( I_(kR1) )det( I_{(Rj ↔ R1)} ) [See Definition 4 above]

(3) det( I_{(Rj ↔ R1)} )det( I_(kR1) )det( I_{(Rj ↔ R1)} ) = det( I_(kR1) )det( I_{(Rj ↔ R1)} )det( I_{(Rj ↔ R1)} ) [from the Commutativity of scalars]

(4) det( I_(kR1) )det( I_{(Rj ↔ R1)} )det( I_{(Rj ↔ R1)} ) = det( I_(kR1) )det( I_{(Rj ↔ R1)}I_{(Rj ↔ R1)} ) [ See Definition 4 above]

(5) det( I_(kR1) )det( I_{(Rj ↔ R1)}I_{(Rj ↔ R1)} ) = det( I_(kR1) )det(I) [See Lemma 3 above]

(6) det( I_(kR1) )det(I) = det(I_(kR1))det(I_(1R1))

(7) det( I_(kR1))det(I_(1R1)) = k*1 = k [See Definition 4 above]

QED

Corollary 4.1: A = I_(kRj)B → det(A) = k*det(B)

Proof:

(1) A = I_(kRj)B

(2) det(A) = det(I_(kRj)B) = det(I_(kRj))det(B) = k*det(B) [See Lemma 4 above]

QED

Corollary 4.2: det(I_(0Ri)) = 0

Proof:

(1) det(I_(0Ri)) = 0 [This follows directly from Lemma 4 above for k=0]

QED

Corollary 4.3: det(I) = 1

Proof:

(1) det(I) = det(I_(1Ri)) = 1. [This follows directly from Lemma 4 above for k = 1]

QED

Lemma 5: I_{(kRj + Ri)} = I_(k^-1Rj)I_{(1Rj + Ri)}I_(kRj)

Proof:

(1) I_{(kRj + Ri)} =



(2) I_(kRj) =




(3) I_{(1Rj + Ri)}I_(kRj) =



(4) I_(k^-1Rj)I_{(1Rj + Ri)}I_(kRj) =




QED

Lemma 6: I_(k^-1Rj)I_(kRj) = I

Proof:

(1) I_(kRj) =



(2) I_(k^-1Rj)I_(kRj) =



QED

Lemma 7: det(I_{(kRj + Ri)}) = 1

Proof:

(1) Assume k = 0

(2) det(I_{(kRj + Ri)}) = det(I_{(0Rj + Ri)}) = det(I) = det(I_(kR1)) = 1 [See Definition 4 above]

(3) Assume k ≠ 0

(4) det(I_{(kRj + Ri)}) =det( I_(k^-1Rj)I_{(1Rj + Ri)}I_(kRj) ) [See Lemma 5 above]

(5) det( I_(k^-1Rj)I_{(1Rj + Ri)}I_(kRj) ) = det( I_(k^-1Rj) )det( I_{(1Rj + Ri)} )det( I_(kRj) ) [See Definition 4 above]

(6) det( I_(k^-1Rj) )det( I_{(1Rj + Ri)} )det( I_(kRj) ) = det( I_{(1Rj + Ri)} )det( I_(k^-1Rj) )det( I_(kRj) ) [from the Commutativity of scalars]

(7) det( I_{(1Rj + Ri)} )det( I_(k^-1Rj) )det( I_(kRj) ) = det( I_{(1Rj + Ri)} )det( I_(k^-1Rj) I_(kRj) ) [see Definition 4 above]

(8) det( I_{(1Rj + Ri)} )det( I_(k^-1Rj) I_(kRj) ) = det( I_{(1Rj + Ri)} )det( I ) [See Lemma 6 above]

(9) det( I_{(1Rj + Ri)} )det( I ) = det( I_{(1Rj + Ri)} I) = det(I_{(1Rj + Ri)}) [See Definition 4 above]

(10) So, we have shown that: det(I_{(kRj + Ri)}) = det(I_{(1Rj + Ri)})

(11) Now, (I_{(1Rj + Ri)})² = (I_{(1Rj + Ri)})(I_{(1Rj + Ri)}) = I_{(2Rj + Ri)}

(12) But for k=2, we have:

det( (I_{(1Rj + Ri)})(I_{(1Rj + Ri)})) = det(I_{(2Rj + Ri)} ) = det(I_{(1Rj + Ri)})

(13) Now, this can only be true if det(I_{(1Rj + Ri)}) = 0 or det(I_{(1Rj + Ri)}) = 1.

(14) We note that I_{(1Rj + Ri)}I_{(-1Rj + Ri)} = I.

(15) Since det(I) = 1, it follows that det(I_{(1Rj + Ri)}I_{(-1Rj + Ri)}) = 1 so it is impossible for det(I_{(1Rj + Ri)}) = 0.

(16) Therefore, det(I_{(1Rj + Ri)}) = 1.

QED

Corollary 7.1: A = I_{(kRj + Ri)}B → det(A) = det(B)

Proof:

(1) A = I_{(kRj + Ri)}B

(2) det(A) = det(I_{(kRj + Ri)}B) = det(I_{(kRj + Ri)})det(B) = 1*det(B) = det(B) [See Lemma 7 above]

QED

Lemma 8: I_{(Ri ↔ Rj)} = I_(-Ri)I_{(1Ri + Rj)}I_{(-Rj + Ri)}I_{(1Ri + Rj)}

Proof:

(1) I_{(Ri ↔ Rj)} =



(2) I_{(1Ri + Rj)} =



(3) I_{(-Rj + Ri)}I_{(1Ri + Rj)} =



(4) I_{(1Ri + Rj)}I_{(-Rj + Ri)}I_{(1Ri + Rj)} =



(5) I_(-Ri)I_{(1Ri + Rj)}I_{(-Rj + Ri)}I_{(1Ri + Rj)} =



QED

Lemma 9: det(I_{(Ri ↔ Rj)}) = -1.

Proof:

(1) det( I_{(Ri ↔ Rj)} ) = det( I_(-Ri)I_{(1Ri + Rj)}I_{(-Rj + Ri)}I_{(1Ri + Rj)} ) [See Lemma 8 above]

(2) det( I_(-Ri)I_{(1Ri + Rj)}I_{(-Rj + Ri)}I_{(1Ri + Rj)} ) = det( I_(-Ri) )det( I_{(1Ri + Rj)} )det( I_{(-Rj + Ri)} )det( I_{(1Ri + Rj)} ) [See Definition 4 above]

(3) det( I_(-Ri) ) = -1 [See Lemma 4 above]

(4) det( I_{(1Ri + Rj)} ) = det( I_{(-Rj + Ri)} ) = 1 [See Lemma 7 above]

(5) So, det( I_(-Ri) )det( I_{(1Ri + Rj)} )det( I_{(-Rj + Ri)} )det( I_{(1Ri + Rj)} ) = (-1)*(1)*(1)*(1) = -1.

QED

Corollary 9.1: A =I_{(Ri ↔ Rj)}B → det(A) = -det(B).

Proof:

(1) A =I_{(Ri ↔ Rj)}B

(2) det(A) = det(I_{(Ri ↔ Rj)}B) = det(I_{(Ri ↔ Rj)})det(B) = (-1)*det(B) = -det(B)

QED

Lemma 10:

Let E_i be an elementary matrix

Let A =



then:

det(A) = det(E_i)

Proof:

(1) There are only three types of elementary matrices so this proof is complete if I show it is true for each type.

(2) Type I: E_i = I_(kRi)

(a) From Lemma 4 above, det(E_i) = k

(b) A, in this case, is equal to I_(kRi+1)

(c) Using Lemma 4 above, det(A) = k

(3) Type II: E_i = I_{(kRj + Ri)}

(a) From Lemma 7 above, det(E_i) = 1

(b) A, in this case, is equal to I_{(kRj+1 + Ri+1)}

(c) Using Lemma 7 above, det(A) = 1.

(4) Type III: E_i = I_{(Ri ↔ Rj)}

(a) From Lemma 9 above, det(E_i) = -1.

(b) A, in this case, is equal to I_{(Ri+1 ↔ Rj+1)}

(c) Using Lemma 9 above, det(A) = -1

QED

References

• Charles G. Cullen, Matrices and Linear Transformations, Dover Publications, Inc., 1972.