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:
α1R1 + ... + αnRn = 0.
(3) Then, it is possible to use elementary operations to set R1 = 0 since:
(a) Multiply R1 with α1
(b) For each row i (where i = 2 .. n), add αi*Ri to R1.
(c) By step #2, it is clear after (a) and after each addition (b), R1 = 0.
(4) So we have:
A(0R1) = EnEn-1...E2E1A where Ei 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(Ei) ≠ 0. (See Lemma 4, Lemma 7, and Lemma 9 here)
(7) It therefore follows that det(A) = 0 since det(A(0R1)) = det(En)det(En-1)...det(E2)det(E1)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, α1R1 + ... + αnRn=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:
α1C1 + ... + αnCn = 0.
(3) Then, it is possible to use elementary operations to set C1 = 0 since:
(a) Multiply C1 with α1
(b) For each column i (where i = 2 .. n), add αi*Ci to C1.
(c) By step #2, it is clear after (a) and after each addition (b), C1 = 0.
(4) So we have:
A(0C1) = AEnEn-1...E2E1 where Ei 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(Ei) ≠ 0. (See Lemma 4, Lemma 7, and Lemma 9 here)
(7) It therefore follows that det(A) = 0 since det(A(0C1)) = det(En)det(En-1)...det(E2)det(E1)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, α1R1 + ... + αnRn=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 F1 x n be the set of all possible rows of length n.
(6) F1 x n is a vector space. [See Definition 2, here for definition of vector space]
(7) Since [ R2, R3, ..., Rn ] are linearly independent, we can use this list to build a basis: [ ε, R2, R3, ..., Rn]. [See Theorem 1, here]
(8) Since [ ε, R2, R3, ..., Rn] is a basis (see Definition 2, here for definition of basis), we have:
Row1(A) = α = a1ε + a2R2 + ... + anRn
Row1(B) = β = b1ε + b2R2 + ... + bnRn
Row1(C) = (α + β) = (a1 + b1)ε + (a2 + b2)R2 + ... + (an + bn)Rn
(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=ai and then use Ri. In this way, we can reduce α to a1*ε. Likewise, we can reduce β to b1*ε and finally, we can reduce (α + β) to (a1 + b1)ε.
(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) =
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjZi1ltHpge1K_2Rhns__AoYjL0U0__9rd2oPLBSaTkINFY51ZAV8cOK-oJx9KciHY3Q8l3tkP44tChRBLkANEs8NkuYuCd4QfU8WUEjUcbm_q-IjydkOn3kFOdI0Gw9gBfgUA/s400/det1.png)
det(B) =
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnyKCEU2miC1DzpMdDdNvbPkQ8QLQdhPu6mR79N4E34jV-2vLpxoY0rY8upXdEwRfTIHg1xywVyQeSjTB-fouVe81CRPrM0AOUZwWCXIfFrjMLlbuZ6MBng2KWG1jS8DAmfn4/s400/det2.png)
det(C) =
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjCn36fK3nbPSJZ5Sv6FynatkRuSdG0ukowgWg3Fmj4osl4WRcAI08kVyAqb8IeBL11F05Ah1ImsAfGQ9LYz9RLWct20E-G1Bzcxu66mXJZsRzUEnGXS7zXj6rYwMtefnPTSlI/s400/det3.png)
(11) It is also true that (see Definition 4, here):
det(A) =
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhHaFkOyN2QvyuvA5WDAWXimCUX8ZPh_t3RzwQd4w1uKZmNHDRqj4DZlgdGGr4ndHWJeMwQScv-tCQnc2cXlFmS88hn5ZKUzlg36ywYjiAQ4DvzYPuhE9rlmBmHWT_qSIBCwtk/s400/det4.png)
det(B) =
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgu6QSb5EwWDM849_oER_gN4dKsSQ8xB__G3ZuZ7MMw2YTrO5t-P_KYnhuQsqc57iwtXbGc8ZEwEMXBPxBeb0-Pmf6l-GG_PGIE6OBrN4BWj6HNnPllqNJhdP7jJ-w8QEBkX_g/s400/det5.png)
det(C) =
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh-z0fngKlukRZrlz2WHvyN6ewrXPigLtzcUkzzAuH17tdnJFx6cYXn5pzf_8quvvCdYTY2OgNgjV4WYme4Q6SF4ShzHVtjqYki5rY6dSRpCTAS1pkCiWc9i8hdsq-4Ovogifg/s400/det6.png)
(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(CT) = det(AT) + det(BT)
(2) Using Theorem 9 here, we have:
det(CT) = det(C) det(AT) = det(A)' det(BT) = det (B)
(3) Putting this all together gives us:
det(C) = det(A) + det(B)
QED
Definition 1: Minor Mi,j(A)
For an n x n matrix A, the minor of ai,j, Mi,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 ai,j, cofi,j(A), is defined as (-1)i+jdet(Mi,j(A)).
Lemma 3:
Let B be an Fn x n matrix of the form:
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjEMIkaUmkVHSOwEozpps71LlcayMfHVRbhrAje9dtwQkF7Mkj9KGOTsNImJdyG3zzZVSqq7VgGPTvJAX8pKCsUjGZ8zs5PYvSIjPyeSPI12qzKLPopo3i2E3bU-pJgvl5aP8Y/s400/matrix1.png)
then:
det(B) = det(M1,1(B)) = cof1,1(B).
Proof:
(1) Using the elementary row operation I(kRj + Ri) [See Definition 3, here] we can reduce B to the following form:
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgIUlTo2h-OuSthhvOVaX2V3_z21Ox2L63STWOQ5MtiYUM0lGlrD_TULso5kq7EDLFjKvGFNRx0UTn-XN-xfiU8smHEQ9hXu91DR1NboM3Z1rhGOE8OH5ZcjNCmvKzYpMzVf4k/s400/cofactor2.png)
(2) Let E1*....*Et be a representation of M1,1(B) as a product of n-1 x n-1 elementary matrices. [See Theorem 6, here]
(3) Now, we have:
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEikmZNAl4sRFfLRAA282n9A2Xi1c32HEx39jPa2K18b6LpO_ZBHUvq69Fw-TG_hpg7-jH9F9YrRYqTGH37l6Xplbk849-u07QMAQG2SKAOay8zqLfGJl8Or724LIPqLFux6Du4/s400/cofactor4.png)
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhUqwvcrFxwTRjngyTv9rWIMqTLhbWmcdRyEnL3A5SnMxASkdMcYMCMAVEv7vNULs8XePPM0PzIjUW08yOxx0VdDojEqflqFcyAe5afaxN7q8GqTmNKMdB2pYJAh9uHu64nhcg/s400/cofactor5.png)
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg07vmqcS83b1OzGBBipMV0OIrrocL5Aj8mjxkcBhR3UADdAlNtYoOv1mLX6U_kCLDHmml1JBozkeZvg9uOdY6E2o5nTNBjrliKhbS6GiNyN1sG3nmIOGjS4eYixjbtEXQmVqU/s400/cofactor6.png)
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh6dY8tJqU38hdegzXSdfasZace9PfX9AWdFrZo6Sceb6UNkeXJ6CSpAos7PwvhRLaR9tjwJEYKaK8XUaaclRijI3H7HhglNHgUArOzjUkIxMQhVSGis1CQHdyqIyxETHt0p48/s400/cofactor3.png)
det(E1)*...*det(Et) = det(E1*...*Et) = det(M11(B))
QED
Corollary 3.1:
Let B be an Fn x n matrix of the form:
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgns1M5bPYI_ly4q3FvZ7VOv9WGCTPcKC7kyp-PAwrscKydyOMwAFvcR4sM_k6a6U4-BEAxs9EQJ_xX0l8jG4gw8_QhERHEAcChAyMhmciEz-jVFMkHABVx2IJtZjWxSqqhY4s/s400/cofactor7.png)
then:
det(B) = det(M1,1(B)) = cof1,1(B).
Proof:
(1) Using Lemma 3 above, we have:
det(BT) = det(M1,1(B)) = cof1,1(B).
(2) Using Theorem 9 here, we have:
det(B) = det(BT)
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) ai,jcofi,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:
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj3ilWJynAT0Gawho0najTllFK1BxbCL5tKyVL6WRvA4hrUGeYVPBsLczbeLF1stFJ23lsy8JreRyn9S4AQDL9ajfsKOIAkwHHG-clT31Mz9vltJ-jlOayGCkz9DM51cXIegns/s400/row1.png)
(5) Since det(I(Ri ↔ Rj)) = -1, the (i-1) row operations gives us:
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjXreRPzZjNV8yCE2HlYpnJ0VO-syQa6U2wC5iGGRmwknsOX5HX9d1N0vG3tVU6r1EoSnCRdmRebZJKk7LWzyk6WSt2X3-7AMV37CSyoNzTlVHxIFCYVTlXEt5wd9EAI0VG9SM/s400/current.png)
(6) Using Lemma 2 above, we have:
det(A) =
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiSANPzYUl0_MiSCLrOgu7PeSdVrfH1lEtvazORBEDyz3nmdW51m9MCNaEHAnjraZruM4I629A6lgDmGpNBl0Ld5f2x8BF6XxV_bYnU8IgVhh4BE2XiJUJXvZFoM4ZCGgR-U3A/s400/current2.png)
(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)0 for j=1, (-1)1 for j=2, and so on so that we get:
det(A) = (-1)(i-1)[(-1)(1-1)det([ai,1*]) + (-1)(2-1)det([ai,2*]) + ... + (-1)(n-1)det([ai,n*]) ]
where [ai,j*] is the determinant of the [ai,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[
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjXaNFYXSO9l-i784vlAg9eHap3JJPswL34OAE1t9vXQowYQfwX4fseHn6yHbMW4Xz70Qv-TWQ1-MBXj2groXEjI_y6QpxDp_foDqBj4JBKVWWeicoJfWKCqAdnpEEbx1jH-ps/s400/current3.png)
]
(10) Using row operation I (I(kRi)), we further get:
det(A) = (-1)i-1[
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhat-uRkZmqcD6OT_wNxd9NLc2DKlWxKpcATMqIQXKZvCFyFg34XNhIuwjz9WsGVgXyz56ujAMzsOML4dlZ_gAj5i5MYRpzMwdHsatyc_1Z7brjgaCa67kit5L92f3v_gW3P74/s400/current4.png)
]
(11) We can now plug in Lemma 3 above to complete the proof:
det(A) =
(-1)i-1[ai,1det(Mi,1(A)) - ai,2det(Mi,2(A)) + ai,3det(Mi,3(A)) - ai,4det(Mi,4(A)) + ...] =
(-1)i-1[ai,1cofi,1(A) - ai,2cofi,2(A) + ai,3cofi,3(A) - ai,4cofi,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:
![](http://photos1.blogger.com/blogger/4608/663/320/first8.png)
(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) = a1,1det(M1,1) - a1,2det(M1,2) + ... + (-1)(n-2)a1,(n-1)det(M1,(n-1) + (-1)(n-1)a1,ndet(M1,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) ai,jcofactori,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:
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhgUieQu8pSVn6twrpUNO4_wrzORUc6pXFY4RmoWP3rxZx7W8AckO_ZGu_7xwN_Zya7l0zPmEi8MU5burVMHR0S2wt7B6_J3GYpKSzZXrLlpZZdlxnacPu8RhewA1HOD0wbheM/s400/cofactor8.png)
(5) Since det(I(Ci ↔ Cj)) = -1,
det(A) = (-1)(j-1)det([Colj Col1 ... Coln])
(6) Using Corollary 2.1 above, we have:
det(A) = (-1)(j-1)[det([a1,j]) + det([a2,j]) + ... + det([an,j])]
where [ai,j] is the matrix derived from A where all values in column j are empty except for ai,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)0 for i=1, (-1)1 for i=2, and so on so that we get:
det(A) = (-1)(j-1)[(-1)(1-1)det([a1,j*]) + (-1)(2-1)det([a2,j*]) + ... + (-1)(n-1)det([an,j*]) ]
where [ai,j*] is the determinant of the [ai,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([a1,j*]) - det([a2,j*]) + ... {+/-} det([an,j*]) ]
where [ai,j*] is the determinant of the [ai,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)[a1,jdet([ai,j**]) - a2,jdet([a2,1**] + ... ]
where ai,jdet([ai,j**]) = det([ai,j*])
(11) We can now plug in Corollary 3.1 above to complete the proof:
det(A) = (-1)i-1[ai,1det(Mi,1(A)) - ai,2det(Mi,2(A)) + ai,3det(Mi,3(A)) - ai,4det(Mi,4(A)) + ...] =
(-1)i-1[ai,1cofi,1(A) - ai,2cofi,2(A) + ai,3cofi,3(A) - ai,4cofi,4(A) + ... ]
QED
References
- Charles G. Cullen, Matrices and Linear Transformations
, Dover Publications, Inc., 1972.
No comments :
Post a Comment