Social ChangeModern World
Social ChangeModern World SOCL 20
Popular in Course
Popular in Sociology
This 16 page Class Notes was uploaded by Camron Koelpin I on Thursday October 22, 2015. The Class Notes belongs to SOCL 20 at University of California - San Diego taught by Staff in Fall. Since its upload, it has received 8 views. For similar materials see /class/226784/socl-20-university-of-california-san-diego in Sociology at University of California - San Diego.
Reviews for Social ChangeModern World
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/22/15
Some proofs about determinants Samuel R Buss Spring 2003 Revision 21 Preliminary corrections appreciated These notes are written to supplement sections 21 and 22 of the textbook Linear Algebra with Applications by S Leon for my Math 20F class at UCSD In those sections the de nition of determinant is given in terms of the cofactor expansion along the rst row and then a theorem Theorem 211 is stated that the determinant can also be computed by using the cofactor expansion along any row or along any column This fact is true of course but its proof is certainly not obvious Unfortunately Leonls text does not give any proof of this theorem and then uses it heavily in subsequent proofs Since most of the book is good about giving proofs or at least proof sketches it is galling that such a fundamental result is stated without proof Accordingly the following notes give a sketch of how to prove the theorems in sections 21 and 22 without depending on any unproved theorems The intent is that the reader can read this in conjunction with Leon7s textbook By following the sequence of de nitions and theorems given below and by lling the details of the proofs the reader can give a complete proof of all the results 1 De nition of determinants For our de nition of determinants we express the determinant of a square matrix A in terms of its cofactor expansion along the rst column of the matrix This is different than the de nition in the textbook by Leon Leon uses the cofactor expansion along the rst row It will take some work but we shall later see that this is equivalent to our de nition Formally we de ne the determinant as follows De nition Let A be a n X n matrix Then the determinant of A is de ned by the following If A is l X 1 so that A aLl then detA a11 Otherwise if n gt 1 CHM Zai1Ai17 1 i1 where AM is the ijcofact0r associated with A In other words it is the scalar value I V Am 41 detMij7 where MM is the n 7 l X n 7 1 matrix obtained from A by removing its ith row and jth column The MiJ s are called the minors of i In this note we assume that all matrices are square We use the notations AM and MM to refer to the cofactors and minors of A When working with multiple matrices we use also use M5 to denote the minor MW of Al Likewise for B a matrix we use BM and ME to denote the cofactors and minors of B i 2 How row operations affect determinants We now present a series of theorems about determinants that should be proved in the order presented These theorems are aime at showing how row an column operations affect determinantsi Indeed as we shall see row and column operations preserve the property of the determinant being nonzeroi More generally there are simple rules that tell how a determinant when a row or column operation is applied Theorem 1 Multiplying a row by a scalar Let A be a square matrix Let B be obtained from A by multiplying the kth row of A by 1 Then detB adetAi Proof We prove the theorem by induction on n The base case where A is 1X 1 is very simple since detB blyl aalyl adetA For the induction step we assume the theorem holds for all n7 1 X n 7 1 matrices and prove it for the n X 71 matrix A Recall that the determinant of A is detA Z ai1Ai1 21 Likewise the determinant of B is detB Zanzb i1 Consider the ith term in these two summations First suppose i k Then bi1 dam Also since A and B diHer in only their kth rows M51 fl and thus Am BM Thus for i k bileiyl aaiylAiyl Second suppose i 7 k Then bi1 am Also M51 is obtained from M53 by multiplying one of its rows by 0 Therefore by the induction hypothesis BM 1AM Thus we again have bileiyl 04am m Since bileiyl aaiylAiyl holds for all i we conclude that detB a detA and the theorem is proved D Corollary 2 Let A be a square matrix If any row of A is all zero then det A 0 Proof This is an immediate corollary of Theorem 1 using a O B Our next theorems use matrices A B and C These are always assumed to be square and have the same dimensions Furthermore our proofs will use the notations AM EM and CM for the cofactors of A B and C We also use the notations Mfg Mg and for the minors of the three matricesi Recall that ad by and Ci denote the ith rows of the matrices A B and Cl Theorem 3 Suppose i0 is a xed number such that 1 S h S n Also suppose A B and C satisfy Ck akbk and that for all i f h Then detC detA detB The hypotheses of the theorem say that A B and C are the same except that the h row of C is the sum of the corresponding rows of A and B Proof The proof uses induction on n The base case n 1 is trivially true For the induction step we assume that the theorem holds for all n7 1 X n7 1 matrices and prove it for the n X n matrices ABC From the de nitions detA detB and detC it will su 39ice to prove that Ci10i1 ai1Ai1bi1Bi1 2 holds for all i 1n First suppose i h Then cm ai1 bu Also since the matrices di er only in their kth rows Cm Am BM Thus equation 2 holds for i k Second suppose i 7 h Then cm am bu Also by the induction hypothesis we have that Cm Ai1 B This is because Mm M51 and Mm in equal all but one of their rows the remaining row in M51 is the sum of the corresponding rows in Mm and M231 So again 2 holds Theorem 4 Suppose that B is obtained from A by swapping two of the rows of A Then detB idetA Proof We shall rst prove the theorem under the assumption that row 1 is swapped with row k for k gt 1 This will be su 39icient to prove the theorem for swapping any two rows since swapping rows k and k is equivalent to performing three swaps rst swapping rows 1 and k then swapping rows 1 and k and nally swapping rows 1 and k The proof is by induction on n The base case n 1 is completely trivial Or if you prefer you may take 71 2 to be the base case and the theorem is easily proved using the formula for the determinant of a 2 X 2 matrix he de nitions of the determinants of A and B are detAZa1A1 and detBZbi131 i1 i1 First suppose 139 116 In this case it is clear that Mfl and M51 are the same except for two rows being swapped Therefore Am 73 Since also am bu we have that mem iaiylAiyl It remains to consider the i 1 and i k terms We claim that ak1Ak1 meiu and 111A11 bkuBhb In fact once we prove these two identities the theorem will be proved By symmetry it will suf ce to prove the rst identity For this rst note that akyl blyl Second note that M51 is obtained from M l by reordering the rows 12 71 of Mal into the order 23 k7 l 1 This reordering can be done by swapping row 1 with row 2 then swapping that row with row 3 etc ending with swap with row k 7 1 This is a total of k 7 2 row swaps So by the induction hypothesis detltMflgt lt71 detltsz1gt 71 datum Since Bk 71k1detMfl and 1411 det M1A1 we have established that Akyl 7 11 Thus akylAkyl 7 V V This completes the proof of the theorem D Corollary 5 If two rows of A are equal then detA 0 Proof This is an immediate consequence of Theorem 4 since if the two equal rows are switched the matrix is unchanged but the determinant is negated D Corollary 6 If B is obtainedfmm A by adding 1 times row i to row j where i f j then detB detA This is a row operation of type Proof Let C be the matrix obtained from A by replacing row j with row i Then by Theorem 5 detC 0 Now modify 0 by multiplying row j by a to obtain D By Theorem 1 detD adetC 0 Now by Theorem 3 detB detA detD detAO detA E Summary of section Among other things we have shown how the determinant matrix changes under row operations and column operations For row operations this can be summarized as follows R1 If two rows are swapped the determinant of the matrix is negated Theorem 4 R2 If one row is multiplied by a then the determinant is multiplied by 1 Theorem 1 R3 If a multiple of a row is added to another row the determinant is unchanged Corollary 6 R4 If there is a row of all zeros or if two rows are equal then the determinant is zero Corollary 2 and Corollary 5 For column operations we have similar facts which we list here for conve nience To prove them we must rst prove that detA detAT which will be done later as Theorem 15 C1 If two columns are swapped the determinant of the matrix is negated Theorem 22 C2 If one column is multiplied by a then the determinant is multiplied by 1 Theorem 19 C3 If a multiple of a column is added to another column the determinant is unchanged Corollary 24 C4 If there is a column of all zeros or if two columns are equal then the determinant is zero Corollary 20 and Corollary 23 3 Diagonal and tridiagonal matrices The next theorem states that the determinants of upper and lower triangular matrices are obtained by multiplying the entries on the diagonal of the matrix Theorem 7 Let A be an upper triangular matrix or a lower triangular matrix Then detA is the product of the diagonal elements of A namely detA aw i1 Proof The proof is by induction on n For the base case n 1 the theorem is obviously true Now consider the induction case n gt 1 with A upper triangular or lower triangular By the induction hypothesis Mfl is the product of all the entries on the diagonal of A except am Thus IMAM is the product of the diagonal entries of A Therefore from the formula 1 for the determinant of A it will suf ce to prove that ai1Ai1 0 for i gt 1 Now if A is upper triangular then am 0 when i gt 0 On the other hand if A is lower triangular and i gt 1 then the rst row of Mfl contains all zeros so Am O by Theorem 2 That completes the proof by induction D Since a diagonal matrix is both upper triangular and lower triangular Theorem 7 applies also to diagonal matrices Corollary 8 Let I be an identity matrix Then detI 1 4 Determinants of elementary matrices Theorem 9 Let E be an elementary matrix of type I Then detE 71 Proof Any such E is obtained from the identity matrix by interchanging two rows Thus detE 71 follows from the facts that the identity has determinant 1 Corollary 8 and that swapping two rows negates the determinant Theorem 4 D Theorem 10 Let E be an elementary matrix of Type U with em 1 Then det a Proof This is an immediate consequence of Theorem 7 D Theorem 11 Let E be an elementary matrix of Type UL Then detE 1 Proof This is immediate from Theorem 7 D The next two corollaries will come in handy Corollary 12 Let E be an elementary matrix Then detET detE Corollary 13 Let E be an elementary matrix Then detE 1 ldetE As we shall see Corollary 12 actually holds for any square matrix A not just for elementary matrices And Corollary 13 holds for any invertible matrix Both corollaries are easily proved from the previous three theorems The next theorem is an important technical tool It will be superseded by Theorem 17 below Theorem 14 Let A be a square matrix and let E be an elementary matrix Then detEA detE detAl Proof This is an immediate consequence of Theorems 911 and Theorems 1 4 and 6 D 5 How to compute a determinant ef ciently We know that any matrix can be put in row echelon form by elementary operations That is to say any matrix A can be transformed into a row echelon form matrix B by elementary row operations This gives us B EkEk1E2E1A where B is in row echelon form and hence upper triangularl Since B is upper triangular we can easily compute its determinant By Theorem 14 detB detEk detEk1 detE2 detE1 detAl Then by Corollary 13 detA detEz 1 detEz 1 1detE2 1 detE1 1 detB This gives an algorithm for computing the determinant detA of Al This algorithm is quite ef cient however for hand calculation it is sometimes easier to not put A in row echelon form but instead to only get B upper triangularl In this case the determinant of B is still easily computable in addition the upper triangular B can be obtained using only row operations of types I and lll each of the elementary matrices Ei has determinant i1 and thus detEi detEl 1 i1 so we need only keep track of the sign changes This latter algorithm is the one we advocate in class lecture as being the best one to user 6 Determinants and invertibility Theorem 15 A square matrix A is invertible if and only if its reduced row echelon form is the identity matrix Furthermore it is invertible and only if its row echelon form does not have any free variab es Proof To prove this theorem note that the conditions are satis ed if and only if there is no row of zeros in the reduced row echelon form of A This is equivalent to the condition that the equation Ax 0 has only the trivial solution B Corollary 16 A is invertible if and only if detA y 0 Proof By the discussion at the beginning of this section A has determinant zero if and only if its reduced row echelon form B has determinant zero Now if A is invertible B is the identity and hence has determinant equal to one ie if A is invertible A has nonzero determinant Otherwise B has a row of all zeros and thus has determinant zero so A has determinant equal to zero D 7 Determinants of products of matrices A very important fact about matrices is that detAB detA detBl Theorem 17 Let A and B be n X n matrices Then detAB detA detBl Proof First suppose detB 0 Then detB is not invertible so there is a nontrivial solution to Bx 0 his is also a nontrivial solution to ABx 0 so AB is not invertible and thus has determinant 0 Then detAB O detA detB in this case Second suppose detA O and detB 7 0 Since A is not invertible there is a nontrivial solution y 7 0 to Ay 0 But then x B 1y is a nontrivial solution to ABx 0 Therefore AB is not invertible so detAB 0 So again detAB O detA detB Now suppose that detA 7 0 Then the rref form of A is just the identity I This means there are elementary matrices Ei so t at A EkEk71quot39E2E1 Then detA detEk detEk1 detE2 detE1 by Theorem 14 Using Theorem 14 again gives detAB detEk detEk71 detE2 detE1 detB detA detB So the Theorem is proved D 8 Determinants of transposes Theorem 18 detAT detA Proof Ebrpress A in row echelon form B ie A EkEk1 E2ElB So by Theorem 17 detA detEk detEk1 detE2 detE1detB The matrix B is upper triangular so ET is lower triangular In addition BT and B have the same diagonal entries and thus the same determinant We also have AT BTEITEzT 351575 Using Theorem 17 again detAT dean detEkT1 detEfdetE1T detBT The theorem now follows from Corollary 12 D 9 How column operations effect determinants Now that we have proved Theorem 18 that determinants are preserved under taking transposes we automatically know that all the facts established in section 2 for row operations also hold for column operations Theorem 19 Multiplying a column by a scalar Let A be a square matrix Let B be obtained from A by multiplying the hth column of A by 1 Then detB adetA Recall that ai bi and Ci denote the ith columns of the matrices A B and C Corollary 20 Let A be a square matrix If any column of A is all zero then det A 0 Theorem 21 Suppose jo is a xed number such that 1 S jo S n Also suppose A B and C satisfy Cjo ajo l bjo and that for all j jg Then detC detA detB Temperature VF Mesosphere Altitude Altitude km miles Highest Ozone Concentration Stramphere in Stratosphere Trapasphere Temperature 0 Ozone 03 0 Most ozone in stratosphere 0 Ozone absorbs harmful UV radiation 0 Human activities have disturbed ozone balance in past 03 consumption 2 03 production recently 03 consumption gt 03 production WHY gt Chloro uorocarbons CFCs 0 CFCs released in troposphere spray can propellants 0 Diffuse slowly up to stratosphere 0 UV radiation breaks up CFCs gt releases chlorine 0 Chlorine very efficient at destroying ozone CFCS Reached Peak in mid 19905 235 2311 25 7 2m 2 65 E 2613 255 251 7 D g 1 2411 39 335 I I 1985 1990 1995 2000 Elm Antarctic Ozone Hole TOMS Ozone DU Oc39iquot Total Ozone DU South Pole Dobson Ozone Spectrophotometer October 1531 Average 0 L HAT 9 S H4 A A 9 1960 1970 1980 99 2 000 2010 Minimum ozone DU 180 100 80 2n9 Antarctic ozone um 60 90v 5 19794992 anus 7 TOMS 19934994 Manama TOMS nu TOMS m urth Earth Pube TOMS OMT T995 1996mm 2on5 1980 1985 1990 1995 2000 2005 71909 Math 20B Lecture Examples Sections 106 and 107 Power series and Taylor seriesT A POWER SERIES is an in nite series of the form 0 Zan 7c a0a17ca27c2a3x7c3i n0 Because the terms are constant multiples of powers of x 7 c we say that this series is CENTERED at x Ci Example 1 For what values of X does the power series w 1n1 2 3 4 Eixnx7x X 7X n n1 converge Answer The series converges for 1 lt 12 S 1 N 707L471 Graphs of partial sums SN E 7 In from Example I are shown in Figure I for x 0757 n n1 where the series converges quickly7 in Figure 2 for x 17 where the convergence is relatively slow7 and in Figure 3 for x 127 where the series diverges y8N ysN x 075 x 1 20 N 10 20 N FIGURE 1 FIGURE 2 FIGURE 3 0 Theorem 1 For each power series Z an X7 Cquot there are three possibilities Either n0 a there is a positive number R such that the series converges absolutely for X 7 Cl lt R and diverges for X 7 Cl gt R b the series converges absolutely for all X or c the series converges only for X C The number R in part a of Theorem I is called the RADIUS OF CONVERGENCE of the series In case b7 where the series converges for all x we set R 007 and in case c7 where the series converges only at x c we set R 0 The set of x s where the series converges is called its INTERVAL OF CONVERGENCE In Example 1 above the radius of convergence is R I and the interval of convergence is 7171 ILectuIe notes to accompany Sections 106 and 107 of Calculus Early Transcendentals by Rogawski Math 2013 Lecture Examples 71909 Sections 1016 and 10177 p 2 If the radius of convergence R is a positive number7 then the series may or may not converge at the endpoints x c i R of the interval of convergence This is illustrated in Example 17 Where the series converges at the right endpoint but not at the left endpoint of the interval 7171 of convergence Example 2 Find a the radius of convergence and b the interval of convergence of i 1 X 7 f n1 n Answer a Radius of convergence 2 b Interval of convergence 727 2 0 Example 3 What is the radius of convergence of Z 7 1quot n0 Answer The radius of convergence is 0 0 Example 4 What is the radius of convergence of Z n Xquot n1 Answer The radius of convergence is 0 Taylor and MacLaurin series Recall from Section 814 that the Nth degree Taylor Polynomial approximation of y centered at c is N was 7 Z fltngtltcgtltz 7 a 7 M f ltcgtltz 7 c f cr 7 a n0 flt3gtltcgtltz 7 cf moe 7 a The corresponding in nite series7 Z fltngtltcgtltz 7 a 7 m New 7 c f cr 7 a n0 1 1 f36x 7 cf Iflt4gtltcgtltac 7 a is called the TAYLOR SERIES of f centered at at The Taylor series centered at c 0 is also called the MACLAURIN SERIES of f Example 5 a Give the MacLaurin series of y equot b Find its radius of convergence 00 1 1 1 Answeray 7mquot1271374b Roo TL 3 4 710 Sections 1016 and 10177 p 3 Math 203 Lecture Examples 71909 The MacLaurin series for y ea in Example 4 equals ea 7 as in the rst of the following formulas Similar calculations give the second and third formulas7 and the last is the geometric seriesi gt0 erZixn1xx2x3 x4n forallx 2 n0 X n sinx2x2nlx7xg x57 for allx 3 n0 gt0 7 Dn 2n 7 1 2 1 4 cosx7zmx 717 x Jrlx forallx 4 n0 1 gt0 7 n 7 2 3 I I I 7 17I7Zx 71 x for 1ltIlt1 5 n0 Example 6 Give the MacLaurin series of fX e x Answer 6 96 xquot n n0 Example 7 Find the MacLaurin series of 1 t2 Jr 1 00 n 271 A 71 t nswer 1 t2 Z n0 Theorem 3 TNT quot quot and 39 quot 7 T 39 series Suppose that a MacLaurin series fX Z anxquot has a positive or in nite radius of convergence R Then derivatives of fX for X irr1R7 R may be found by differentiating the power series term by term Moreover integrals fX dX of fX with 7R lt oz lt 5 lt R can be found by integrating the power a series term by term Example 8 Use the differentiation formula 1 7 X 2 7 X71 to nd the MacLaurin series for fX 1 7 X72 0 Answer 1 7 If E nmnil 711