## Sunday, June 24, 2007

In today's blog, I present the proof that an n x n matrix is invertible if and only if its determinant is nonzero.

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

Lemma 1:

Let A be an n x n matrix.

If i ≠ k, then:

∑ (j=1,n) (ai,j)cofk,j(A) = 0

Proof:

(1) Assume that k ≠ i.

(2) Let B be the matrix given by:

if h ≠ k, then Rowh(B) = Rowh(A).

if h = k, then Rowh(B) = Rowi(A) where k ≠ i.

(3) It is clear that B contains two identical rows (Rowi and Rowk). A does not necessarily contain any identical rows.

(4) We can see that (see Definition 1, here for definition of Minor Mi,j):

Mk,j(A) = Mk,j(B)

This is true since Mk,j does not include Rowk or Columnj. A,B are only different at Rowk.

(5) Now, by the definition of Cofactor (see Definition 2, here for definition of cofactor):

cofk,j of B = (-1)k+jdet(Mk,j(B)) =

(-1)k+jdet(Mk,j(A))

(6) Since Rowk(B) = Rowi(A), we have:

∑ (j=1,n) bk,j = ∑ (j=1,n) ai,j

(7) Now using row k for the cofactor expansion of B, we have (see Theorem 4, here):

det B = ∑ (j=1,n) bk,jcofk,j(B)

(8) Since Mk,j(A) = Mk,j(B) and since cofk,j(A) = (-1)k+jdet(Mk,j(A)), we have:

∑ (j=1,n) bk,jcofk,j(B) = ∑ (j=1,n) bk,jcofk,j(A)

(9) Since Rowk(B) = Rowi(A), we have:

∑ (j=1,n) b
k,jcofk,j(A) = ∑ (j=1,n) ai,jcofk,j(A)

(10) Since B includes two duplicate rows: rowi and rowk, it is clear that det(B) = 0. [See Corollary 1.1R, here]

(11) Thus, we are left with:

∑ (j=1,n) ai,jcofk,j(A) = 0.

QED

Lemma 2:

Let A be an n x n matrix.

If j ≠ l, then:

∑ (i=1,n) (ai,j)cofactori,l(A) = 0

Proof:

(1) Assume that j ≠ l.

(2) Let B be the matrix given by:

if h ≠ k, then Columnh(B) = Columnh(A).

if h = k, then Columnh(B) = Columni(A) where k ≠ i.

(3) It is clear that B contains two identical columns (Columni and Columnk). A does not necessarily contain any identical columns.

(4) We can see that (see Definition 1, here for definition of Minor Mi,j):

Mi,k(A) = Mi,k(B)

This is true since Mi,k does not include Columnk or Rowi. A,B are only different at Columnk.

(5) Now, by the definition of Cofactor (see Definition 2, here for definition of cofactor):

cofi,k of B = (-1)i+kdet(Mi,k(B)) =

(-1)i+kdet(Mi,k(A))

(6) Since Columnk(B) = Columni(A), we have:

∑ (l=1,n) bl,k = ∑ (l=1,n) al,i

(7) Now using column k for the cofactor expansion of B, we have (see Corollary 4.1, here):

det B = ∑ (l=1,n) bl,kcofl,k(B)

(8) Since Mi,k(A) = Mi,k(B) and since cofi,k(A) = (-1)i+kdet(Mi,k(A), we have:

∑ (l=1,n) bl,kcofl,k(B) = ∑ (l=1,n) bl,kcofl,k(A)

(9) Since Columnk(B) = Columni(A), we have:

∑ (l=1,n) b
l,kcofl,k(A) = ∑ (l=1,n) al,icofl,k(A)

(10) Since B includes two duplicate columns: columni and columnk, it is clear that det(B) = 0. [See Corollary 1.1C, here]

(11) Thus, we are left with:

∑ (l=1,n) al,icofl,k(A) = 0.

QED

Definition 1: Adjoint of a matrix

Let A be an n x n matrix. The adjoint of A, written adj A, is the n x n matrix C, where ci,j = cofactorj,i, the cofactor of aj,i in det A.

Theorem 3:

Let A be an n x n matrix. Then A(adj A) = (det A)I and (adj A)A = (detA)I

Proof:

(1) Let D = A(adj A)

(2) Then,

di,k = ∑ (j=1,n) ai,jcofk,j(A).

[See Definition 1, here for definition of matrix multiplication; see definition 1 above for definition of adjoint]

(3) Now, if i ≠ k, then from Lemma 1 above:

∑ (j=1,n) (ai,j)cofk,j(A) = 0

(4) If i = k, then from Theorem 4, here:

det(A) = ∑(i=1,n) ai,jcofi,j(A)

(5) Putting this together, we have:

= det(A)I

(6) Let D = (adj A)A

(7) Then,

di,k = ∑ (j=1,n) cofk,j(A) ai,k

[See Definition 1, here for definition of matrix multiplication; see definition 1 above for definition of adjoint]

(8) Now, if i ≠ k, then from Lemma 2 above:

∑ (j=1,n) cofk,j(A)ai,k = 0

(9) If i = k, then from Theorem 4, here:

∑ (j=1,n) cofi,j(A)ai,i = det(A)

(10) Putting this together, we have:

= det(A)I

QED

Theorem 4: Criteria for Invertibility

An n x n matrix A is invertible if and only if det(A) ≠ 0

Proof:

(1) Assume that an n x n matrix A is invertible.

[See Definition 1, here for definition of invertible]

(2) Then AA-1 = I

(3) Thus, det(AA-1) = det(A)det(A-1) = det(I)

[See Definition 4, here for definition of the determinant function: det(A)]

(4) Since det(I) = 1 [see Corollary 4.3, here], this gives us that:

det(A)*det(A-1) = 1.

(5) Then det(A) ≠ 0 since 0*det(A-1) ≠ 1.

(6) Assume that for an n x n matrix A, det(A) ≠ 0

(7) Let X = (det A)-1(adj A) [We know that this value exists since det(A) ≠ 0. ]

(8) Multiplying A to the left of both sides of equation gives us:

(9) Using Theorem 3 above, we know that (adj A)A = (det A)*I

(10) So that we have:

XA = (det A)-1(det A)*I = 1*I = I

(11) Multplying A to the right of each side of the equation gives us:

(12) Using a property 3 of matrix multiplication (see Property 3, here), we have:

(13) Using Theorem 3 above, gives us:

AX = (det A)-1(det A)I = I

(14) So that we have AX = XA = I and by definition of inverse (see Definition 1, here), we can see that X = A-1.

QED

Corollary 4.1:

If det(A) ≠ 0, then A-1 = 1/(det A)*(adj A)

Proof:

(1) If det(A) ≠ 0, then A is invertible from Theorem 4 above.

(2) From Theorem 3 above:

(3) Multiplying A-1 to both sides gives: