Linear Algebra - Determinants PDF Free Download

1y ago

33 Views

1 Downloads

771.43 KB

61 Pages

Report/dmca

Download PDF

Transcription

Linear AlgebraDeterminants PreliminariesDefinitionProperties of DeterminantsCofactor ExpansionInverse of a MatrixOther Applications of DeterminantsComputing DeterminantsTopics

Linear AlgebraPreliminariesDeterminants Consider the system of linear equationsax1 bx2 y1cx1 dx2 y2which can be written in matrix form as a cb x1 y1 d x2 y2 Can show that this system has a solution if andonly if ad - bc 0. The number ad - bc, whichalso appears in the solution of the aboveequations, is called the determinant of thecoefficient matrix Want to generalize this to a square matrix of anysize

Linear AlgebraPreliminariesDeterminantsUses of Determinants Condition for singularity is det ( A) 0.Eigenvalues of A are those values l that make thematrix A – lI singular. Condition det (A – lI) 0gives a polynomial whose roots are the eigenvalues Explicit formulas for solutions of long-standingproblems:– solution of linear systems– computation of matrix inverse Explicit formula for A–1 is of limited computational utility, but it doesshow how A–1 depends on the n 2 entries of A and how it varies whenthose entries vary

Linear AlgebraDeterminants PreliminariesDefinitionProperties of DeterminantsCofactor ExpansionInverse of a MatrixOther Applications of DeterminantsComputing DeterminantsTopics

Linear AlgebraDeterminantsDefinition Defn - Let S { 1, 2, , n } be the integers 1through n, arranged in ascending order. Arearrangement j1 j2 jn of the elements of S iscalled a permutation of S. A permutation of S is aone to one mapping of S onto itself. The number of permutations of S { 1, 2, , n }is n! The set of all permutations of the elements of S isdenoted by Sn It will be helpful to classify permutations as evenor odd

Linear AlgebraDeterminantsDefinition Defn - A permutation j1 j2 jn of S is said to havean inversion if a larger integer, jr, precedes asmaller one, js. Example - Let S { 1, 2, 3 }. ThenS3 {123, 132, 213, 231, 312, 321 }123 - 0 inversions132 - 1 inversion213 - 1 inversion231 - 2 inversions312 - 2 inversions321 - 3 inversions

Linear AlgebraDeterminantsDefinition Defn - A permutation is called even if the totalnumber of inversions is even Defn - A permutation is called odd if the totalnumber of inversions is odd Example - 4312 contains 5 inversions and is anodd permutation. 1423 contains 2 inversions and isan even permutation

Linear AlgebraDefinitionDeterminants Defn - Let A [ aij ] be an nxn matrix. Thedeterminant of A is defined asdet A a1 j a2 j12anjnwhere the summation is over all permutationsj1 j2 jn of S { 1, 2, , n }. The sign is ifj1 j2 jn is an even permutation and is - ifj1 j2 jn is an odd permutation

Linear AlgebraDeterminantsDefinitionComments det (A) is a function from the set of nxn matricesinto the real numbers Each term a1 j1a2 j2 anjn of det (A) has rowsubscripts in natural order and column subscriptsin the order j1 j2 jn . Thus each term is a productof n elements of A, with exactly one entry fromeach row of A and exactly one entry from eachcolumn of A. det (A) is also written A

Linear AlgebraDeterminantsDefinitionExamples Let A [ a11 ], a 1x1 matrix, then det (A) a11 a11 Let A a21a12 det (A) a11 a22 - a12 a21a22

Linear AlgebraDefinitionDeterminantsExamples a11 a12 a13 Let A a21 a22 a23 a 31a32 a33 det (A) a11 a22 a33 a12 a23 a31 a13 a21 a32-a11 a23 a32 - a12 a21 a33 -a13 a22 a31

Linear AlgebraDeterminants PreliminariesDefinitionProperties of DeterminantsCofactor ExpansionInverse of a MatrixOther Applications of DeterminantsComputing DeterminantsTopics

Linear AlgebraProperties of DeterminantsDeterminants Theorem - Let A be a square matrix. Thendet (A) det (AT ) Proof - Let A [ aij ] and AT [ bij ] where bij ajidet AT b1 j b2 j12bnjn a j 1a j122a jnnConsider a term of the sumb1 j b2 j12bnjn a j 1a j122a jnn a1k a2k12anknwhere k1 k2 kn is a permutation of 1, 2, , n. So,det (A) and det (AT ) contain the same terms withpossibly a difference in sign. Can argue thatk1 k2 kn is the inverse of j1 j2 jn , thus both havethe same parity. So, the signs of corresponding termsin det (A) and det (AT ) are the same anddet (A) det (AT ).QED

Linear AlgebraDeterminantsProperties of Determinants Comment - Since det (A) det (AT ), theproperties of determinants with respect to rowmanipulations are true also for the correspondingcolumn manipulations

Linear AlgebraProperties of DeterminantsDeterminants Theorem - If matrix B is obtained from matrix Aby interchanging two rows (columns) of A, thendet (B) - det (A) Proof - Suppose B is obtained from A byinterchanging rows r and s of A. Without loss ofgenerality, let r s. Then brj asj, bsj arj, for all jand bij aij for all j if i r, i s.det B b1 j b2 jbrjrbsjs a1 j a2 j2asjsarjranjn a1 j a2 j2arjrasjsanjn1112bnjn

Linear AlgebraDeterminantsProperties of Determinants Proof (continued)The permutation j1 j2 js jr jn results fromthe permutation j1 j2 jr js jn by aninterchange of two numbers. Can show that thenumber of inversions in the first permutationdiffers from the number of inversions in thesecond permutation by an odd number. So eachterm in det (B) has the opposite sign of thecorresponding term in det ( A). Thereforedet (B) - det (A)QED

Linear AlgebraDeterminantsProperties of Determinants Theorem - If two rows (columns) of A are equal,then det (A) 0. Proof - Suppose rows r and s of A are equal.Interchange rows r and s to obtain matrix B. Thendet (B) - det (A). However, B A sodet (B) det (A). Thus det (A) 0.QED

Linear AlgebraDeterminantsProperties of Determinants Theorem - If a row (column) of A consists entirelyof zeros, then det (A) 0. Proof - Let the ith row of A be all zeros. Eachterm of det (A) contains a factor from the ith rowof A. So, det (A) 0.QED

Linear AlgebraDeterminantsProperties of Determinants Theorem - If B is obtained from A by multiplyinga row (column) of A by a real number c, thendet ( B ) c det ( A ). Proof - Suppose the ith row of A is multiplied byc to get B. Each term of det ( B ) contains a singlefactor from the ith row of B. Thus, each term ofdet ( B ) consists of a single factor of c times thecorresponding term of det ( A ). So,det ( B ) c det ( A ).QED

Linear AlgebraDeterminantsProperties of Determinants Theorem - If B [ bij ] is obtained from A [ aij ]by adding to each element of rth row (column) ofA, c times the corresponding element of the sthrow (column), r s, of A, then det(B) det(A) Proof - Note that bij aij for i r. For row r(r s), have brj arj c asj . Without loss ofgenerality, suppose that r s.

Linear AlgebraProperties of DeterminantsDeterminants Proof (continued)Then det B b1 j b2 j12brjrbsjs a1 j a2 j2 arj casj a1 j a2 jasjsanjn a1 j a2 j2arjr2casjrasjsanjn2arjrasjsanjn111r a1 j a2 j1 c a1 j a2 j12asjrrasjsasjsbnjnanjnanjnFirst summation is det(A). Second summation is thedeterminant of a matrix having row r equal to row s, soQEDits determinant is 0. Thus det(B ) det(A)

Linear AlgebraDeterminantsProperties of DeterminantsComment The previous three theorems describe whathappens to the determinant of a matrix A when thefollowing elementary row (column) operations areperformed on it– Type I - Interchange two rows (columns) of A– Type II - Multiply row (column) i of A by c 0.(Theorem also covers the case c 0)– Type III - Add c times row (column) i of A to row(column) j of A, i j

Linear AlgebraDeterminantsProperties of Determinants Theorem - Let A [ aij ] be an upper (lower)triangular matrix, then det(A) a11a22 ann. Thatis, the determinant of a triangular matrix is just theproduct of the elements on the main diagonal. Proof - Let A [ aij ] be upper triangular, i.e. aij 0for i j. Then det A a1 j a2 j anjn12In each term, the factor aij 0 if i ji . So the onlyisurviving terms must have i ji for all i. Sincej1 j2 jn is a permutation of { 1, 2, , n }, there is asingle surviving term j1 1, j2 2, , jn n.Therefore det(A) a11a22 ann.QED

Linear AlgebraDeterminantsProperties of DeterminantsComment The three elementary row operations are– Type I - Interchange two rows (columns) of A– Type II - Multiply row (column) i of A by c 0. (Theoremalso covers the case c 0)– Type III - Add c times row (column) i of A to row(column) j of A, i j Each elementary row operation may be accomplishedby multiplying A by the appropriate elementarymatrix, which is obtained by performing theoperation on the identity matrix I. By the precedingtheorem, det(I) 1. Let EI, EII and EIII beelementary matrices of Type I, Type II and Type IIIrespectively. Then, by the theorems proved recentlydet(EI ) – 1 det(EII ) c det(EIII ) 1

Linear AlgebraDeterminantsProperties of Determinants Theorem - Let E be an elementary matrix. Thendet(EA) det(E) det(A) anddet(AE) det(A) det(E) Proof If E is Type I, det(EA) – det(A). Sincedet(E) – 1, det(EA) det(E) det(A)If E is Type II, det(EA) c det(A). Sincedet(E) c, det(EA) det(E) det(A)If E is Type III, det(EA) det(A). Sincedet(E) 1, det(EA) det(E) det(A)The proof for det(AE) follows fromconsideration of elementary column operationsQED

Linear AlgebraDeterminantsProperties of Determinants Theorem - Let A be a nxn matrix. Then A isnonsingular if and only if det(A) 0 Proof - Let A be nonsingular. Then A can beexpressed as the product of elementary matrices,A E1E2 L Ek. Then det(A) det(E1E2 L Ek ) det(E1 ) det(E2 ) L det(Ek ) 0 Let det(A) 0. Suppose A is singular. Then Ais row equivalent to a matrix B with a row of zeros.A E1E2 L Ek B where E1 , E2 , , Ek areelementary matrices. Since B has a row of zeros,det(B) 0. Now, det(A) det(E1E2 L Ek B) det(E1 ) det(E2 ) L det(Ek ) det(B) 0, which is acontradiction. So, A is nonsingular.QED

Linear AlgebraDeterminantsProperties of Determinants Theorem - If A is an nxn matrix, then Ax 0 hasa nontrivial solution if and only if det( A) 0. Proof - Ax 0 has a nontrivial solution if andonly if A is singular. If A is singular, thendet(A) 0.QED

Linear AlgebraDeterminantsProperties of Determinants Theorem - If A and B are n x n matrices, thendet(AB) det(A) det(B) Proof - If A or B is singular, then AB is singular andthe result follows immediately. So, suppose that A andB are both nonsingular. Then A and B can beexpressed as the product of elementary matrices.A E1E2 L Ep and B F1F2 L Fqdet(A) det(E1 ) det(E2 ) L det(Ep )det(B) det(F1 ) det(F2 ) L det(Fq )det(AB) det(E1E2 L Ep F1F2 L Fq ) det(E1 ) det(E2 ) L det(Ep ) det(F1 ) det(F2 ) L det(Fq )QED det(A) det(B)

Linear AlgebraDeterminantsProperties of Determinants Theorem - If A is nonsingular, thendet(A–1 ) 1/det(A) Proof - Let In be the nxn identity. Then AA–1 Inand det(In ) 1. By the preceding theorem,det(A) det(A–1 ) 1, so det(A–1 ) 1/det(A)QED

Linear AlgebraDeterminantsProperties of Determinants Theorem - If A and B are similar matrices, thendet(A) det(B) Proof - A and B are similar if there exists anonsingular matrix P such that B P–1 AP. Thendet(B) det(P–1 AP) det(P–1 ) det(A) det(P) det(A)QED

Linear AlgebraDeterminants PreliminariesDefinitionProperties of DeterminantsCofactor ExpansionInverse of a MatrixOther Applications of DeterminantsComputing DeterminantsTopics

Linear AlgebraCofactor ExpansionDeterminants Comment - To this point, there has been only oneway to calculate the determinant, i.e. from thedefinitiondet A a1 j a2 j12anjnThere are other ways of calculating thedeterminant that can be useful for calculations andfor proofs

Linear AlgebraDeterminantsCofactor Expansion Defn - Let A [ aij ] be an n x n matrix. Let Mpqbe the (n – 1) x (n – 1) submatrix of A obtained bydeleting the pth row and qth column of A. Thedeterminant det(Mpq ) is called the minor of apq Defn - Let A [ aij ] be an n x n matrix. The cofactorApq of apq is defined as Apq (–1) p q det(Mpq )

Linear AlgebraCofactor ExpansionDeterminantsExample 1 2 3 A 456 Let 7 8 9 5M11 826 A11 1 det M11 39 4M12 7 2M31 536 A12 1 det M12 69 43 A31 1 det M 31 36

Linear AlgebraCofactor ExpansionDeterminantsComment Examine pattern of signs of term ( –1) p q n 3 n 4When using cofactors, don’t have to evaluate (–1) p qJust remember the pattern

Linear AlgebraDeterminantsCofactor Expansion Theorem - Let A [ aij ] be an n x n matrix. Thendet(A) ai1A i1 ai2A i2 L ain A in(expansion of det(A) with respect to row i )det(A) a1j A 1j a2j A 2j L anj A nj(expansion of det(A) with respect to column j )

Linear AlgebraCofactor ExpansionDeterminantsExample Expand the determinant of a 3 x 3 matrix a 11A a21 a 31a12 a13 a22 a23 a32 a33 det(A) a11a22a33 a12a23a31 a13a21a32– a11a23a32 – a12a21a33 – a13a22a31Reorganize expression with respect to first rowdet(A) a11 (a22a33 – a23a32 ) a12 (a23a31 – a21a33 ) a13 (a21a32 – a22a31 )

Linear AlgebraCofactor ExpansionDeterminantsExample (continued)Try to recognize the terms in parentheses1 1a22 a23 a22a33 a23a32 a32 a331 2a21 a23 a21a33 a23a31 a31 a331 3a21 a22 a21a32 a22a31 a31 a32A11 1 A12 1 A13 1 So det(A) a11 A11 a12 A12 a13 A13

Linear AlgebraCofactor ExpansionDeterminantsExample (continued)Regroup det(A) with respect to the first column of Adet(A) a11 (a22a33 – a23a32 ) a21 (a13 a32 – a12a33 ) a31 (a12a23 – a13a22 )1 1A11 1 A21 1 a22 a23 a22a33 a23a32 a32 a332 1 a12a323 1 a12A31 1 a22a13 a13a32 a12a33 a33a13 a12a23 a13a22 a23So det(A) a11 A11 a21 A21 a31 A31

Linear AlgebraCofactor ExpansionDeterminantsExample1 4 Evaluate det A 322 3 42 1 30 0 30 2 3Pick row or column with large number of zeros,such as column 2

Linear AlgebraCofactor ExpansionDeterminantsExample (continued)det A 2 A12 2 A22 0 A32 0 A42 4 1 31 3 41 22 2 2 1 3 0 3 2 1 3 0 32 2 32 2 3 3 3 2 3 2 1 4 3 3 3 1 23 2 2 3 1 3 3 2 3 2 1 1 3 3 4 2 9 6 2 12 9 2 3 9 6 2 3 12 1 2 2 1 1 3 2 2 15 6 2 45 30 2 9 2 15 48

Linear AlgebraDeterminants PreliminariesDefinitionProperties of DeterminantsCofactor ExpansionInverse of a MatrixOther Applications of DeterminantsComputing DeterminantsTopics

Linear AlgebraInverse of a MatrixDeterminants Have seen an explicit formula for inverse of a 2 x2matrix a c 1 db 1 ad bc cd d b ad bc a c ad bc b ad bc a ad bc In terms of more general notation this is a11 a21 1 A11 A21 a22 a12 a12 11 a22 a11a22 a12a21 a21 a11 det A A12 A22

Linear AlgebraDeterminantsInverse of a Matrix Theorem - Let A [ aij ] be an n x n matrix. Thenai1Ak1 ai2Ak2 L ainAkn 0 for i ka1jA1k a2jA2k L anjAnk 0 for j ki.e. sum of row or column times cofactors of anotherrow or column is 0 Proof - Consider matrix B obtained from A byreplacing kth row of A with ith row of A. Matrix Bhas two identical rows, the ith and the kth, sodet(B) 0. Expand det(B) with respect to kth row.The elements of the kth row of B are ai1, ai2 , , ain .So 0 det(B) ai1Ak1 ai2Ak2 L ainAkn . Thesecond result follows from det(BT ) det(B) QED

Linear AlgebraInverse of a MatrixDeterminants Defn - Let A [ aij ] be an n x n matrix. Thematrix A11 A12 A1nA21A22A2nAn1 An 2 Ann is called the transpose of the matrix of cofactors or(book’s term) adjoint of A, notation adj(A)

Linear AlgebraInverse of a MatrixDeterminantsExample 1 2 3 A 456 Let 7 8 0 5 64 6A11 48 A12 428 07 04 5A13 37 82 3A21 248 01 31 2A22 21 A23 67 07 82 3A31 35 61 3A32 64 61 2A33 34 5

Linear AlgebraInverse of a MatrixDeterminantsExample (continued)adj A A 11 A12 A 13A21 A31 48 24 3 A22 A32 42 21 6 A23 A33 36 3 det A 7 A31 8 A32 7 3 8 6 27 1 4 7 2 3 48 24 3 27 0 0 5 6 42 21 6 0 27 0 8 0 36 3 0 0 27

Linear AlgebraInverse of a MatrixDeterminants Theorem - Let A [ aij ] be an n x n matrix. ThenA( adj(A) ) ( adj(A) )A det(A)In Proof - Consider the elements of the matrix that isthe product of A and adj(A). A adj A a11 a21 an1a12a22a1n A11 A21 a2n A12 A22an 2A2n ann A1nAn1 An 2 Ann The (i, j) entry of A( adj(A) ) is just the i th rowof A times the j th column of adj(A).

Linear AlgebraInverse of a MatrixDeterminants Proof (continued)From two earlier theoremsai1 Aj1 ai 2 Aj 2 det A ain Ajn 0 A adj A det A 0 0 if i jif i j00det A 00det A det A In

Linear AlgebraInverse of a MatrixDeterminants Proof (continued)By a similar argument, the (i, j) entry of (adj(A)) AisA1i a1 j A2i a2 j det A Ani anj 0if i jif i jso (adj(A)) A det(A)InQED

Linear AlgebraInverse of a MatrixDeterminants Theorem - Let A be an n x n matrix with det(A) 0.An1 A11A21Then det A det A detA AAn 2 A2212 1 1det A A adj A det A det A det A A1n det A Ann det A A2ndet A Proof - By the preceding theorem,A( adj(A) ) det(A)In then adj(A) det(A) A–1and A 1 1 adj A det A QED

Linear AlgebraInverse of a MatrixDeterminantsExample 1 4 7 258 48 27 1 3 42 6 27 0 3 272427 2127627 3 16 8 1 27 999 6 14 7 2 27 99 9 3 1 2 1 9 9 27 9

Linear AlgebraDeterminants PreliminariesDefinitionProperties of DeterminantsCofactor ExpansionInverse of a MatrixOther Applications of DeterminantsComputing DeterminantsTopics

Linear AlgebraOther Applications of DeterminantsDeterminants Theorem - (Cramer’s Rule) Consider the linearsystem of n equations in n unknownsa11x1 a12 x2 a1n xn b1a21x1 a22 x2 a2n xn b2an1x1 an 2 x2 ann xn bnLet A [ aij ] be the coefficient matrix, so that thesystem may be expressed as Ax b. If det(A) 0,then the system has a unique solutiondet A1 det A 2 x1 , x2 ,det A det A det An , xn det A Where Ai is the matrix obtained from A byreplacing its ith column with b

Linear AlgebraOther Applications of DeterminantsDeterminants Proof - If det(A) 0, then A is nonsingular. So A11 det A x1 A12 x2 x A 1b det A xn A1n det A A21det A A22det A A2ndet A A1iA2ixi b1 b2 det A det A An1 det A b1 An 2 b2 det A bn Ann det A Ani bn 1 i ndet A

Linear AlgebraOther Applications of DeterminantsDeterminants Proof (continued)Define Ai as A with the ith column replaced by b a 11 a 21Ai a n1 a12a22a1 i 1 b1 a1 i 1 a2 i 1 b2 a2 i 1 an 2an i 1 bn an i 1 a1n a2n ann Evaluate det(Ai ) by expanding with respect to ithcolumn, then det Ai A1ib1 A2ib2 Anibndet Ai QED1 i nSo xi det A

Linear AlgebraDeterminantsOther Applications of Determinants 12Examplex1 2 x2 3x3 6 A Solve the system 2 x1 3x2 2 x3 14 2 33x1 x2 x3 2 3 3 2 1 1 1 6 3 det A 506 2 32 14 214 3 23 2 1 100 2 1 1 50x1 1 x2 25050det A det A 1 2 62 3 143 1 2 150x3 350det A

Linear AlgebraDeterminants PreliminariesDefinitionProperties of DeterminantsCofactor ExpansionInverse of a MatrixOther Applications of DeterminantsComputing DeterminantsTopics

Linear AlgebraDeterminantsComputing Determinants It is practical to use determinants for computationsinvolving an nxn matrix A when n 4 For larger systems, other methods such asGaussian elimination run much more quickly

Linear Algebra Determinants Properties of Determinants Theorem - Let A be a square matrix. Then det (A) det (AT) Proof - Let A [ a ij] and AT [ b ij] where b ij a ji Consider a term of the sum where k 1 k 2 k n is a permutation of 1, 2, , n. So, det (A) and det (AT) contain the same terms with possibly a difference in sign.