MATH 218 Problems Solution Manual Chapter 1.7, Fall 2011

1.7 Elementary Matrices and LU Factorization 27 48. 49. -12 -7 4-3 _ [8 i] 97 _ [38 4] _ 2% 7-10 —7 | ~ 36’ ey 1-3] 7 28° 12° 1l -§ 4 -10 -12 -1 4 [12 5] oar _ | -8 3| 29 = Tio 7] 8 Y= Toy os] 7 38 12 -§ 4 -8 1 -4 2 -§ 4 2 1 ~8 3-4 1 0 3 1 0 -4 3 _[-8 0 -1; 5 |4 -8 -1|. , |4 0 -8) 4 50. B= a ee a ep oe 0 -4 1 0 -4 1 0 -4 1 4 0 -1 4 0 -1 4 0 -1 2 3 2 2 -2 2 2 3 -2 2 -3 -8 =1 -2 ~8 ~1 -3 -2 2 2 -7 3.2 -7|_, -3 2 2 BL. = pg a = ye Se = | Te -1 ~3 -8 -1 -3 ~8 -1 -3 -8 ~3 2 ~7 ~3 2 ~7 -3 2 -7 4} 52, Suppose Ab = —A, Then det(A) = det(At) = det(—A) = (—1)" det(A). If n is odd, then det(A) = ~det(A) and hence det(A) = 0. Therefore, A is not invertible, 53, Expansion of the determinant of A across row one equals the expansion down column one of A’, so det(A) = det(A*). 54, If A = (aij) is upper triangular, then det(A) = a11@29°++ Grn. But At is lower triangular with the same diagonal entries, so det(A*) = a11422 +++ nn = det(A). : Exercise Set 1.7 A factorization of a matrix, like factoring a quadratic polynomial, refers to writing a matrix as the product of other matrices, Just like the resulting linear factors of a quadratic are useful and provide information about the original quadratic polynomial, the lower triangular and upper triangular factors in an LU factorization are easier to work with and can be used to provide information about the matrix. An elementary matrix is obtained by applying one row operation to the identity matrix. For example, oor Ore a) 1 0 0 (-1)Ry + Rg — Rg 0 1:07. Fd ee Elementary Matrix If a matrix A is multiplied by an elementary matrix E, the result is the same as applying to the matrix A the corresponding row operation that defined E. For example, using the elerlentary matrix above 1 00 13 1 1 8 4 0 10 21 0/=/2 % 0 -1 041 121 0 -1 0 t EA= Also since each elementary row operation can be reversed, elementary matrices are invertible, To find an LU factorization of A: 28 Chapter 1 Systems of Linear Equations and Matrices e Row reduce the matrix A to an upper triangular matrix U. e Use the corresponding elementary matrices to write U in the form Usa Ege EVA, ¢ If row interchanges are not required, then each of the elementary matrices is lower triangular, so that A= ET 1, Ee yy is an LU factorization of A, If row interchanges are required, then a permutation " matrix is also required. , When A = LU is an LU factorization of A, and A is invertible, then A = (LU)~' = U-!Z7', If the determinant of A is required, then since L and U are triangular, their determinants are simply the product of their diagonal entries and det(A) = det(LU) = det(L) det(U), An LU factorization can also be used to solve a linear system, To solve the linear system : 2, — XQ + 2x = Q . 201+ %we+et, =O0 ° 21 +29 = 1 : the first step is to find an LU factorization of the coefficient matrix of the linear system, That is, 1 00 1-1 2 A= LU = 2 1 0 0 4 -3], -101f,0 0 2 rEON Next solve the linear system Ly = b = | using forward substitution, so that y; = 2,y2 = —2y, = 2 —4,y3 = 1+ y1 = 3. As the final step solve Ux = y = | —4 | using back substitution, so that 23 = $,&2 = 3 cont q(—4 + 803) = $0, = 2+ a2 — ag = — Ml Solutions to Exercises f1 00 fo 1 6 lLaaE=|]2 1 0 2aB=]1 0 0 [9 0 1 Loo 4 pi 2 1 [3 1 2 b FA=]5 5 4 b, FA=}]1 2 1 fil 1 4 [1 1 ~4 fi 0 0 fy 1 0.0 3.a, B= |]0 1 0 4,aH=!] 0 1 0 [0 -3 1 [-1 0 4 Fio2 1 fr. 2 1 4, b. FA=|] 3 1 2 b FA=]3 1 2 |” | -8 -2 -10 LO -1 -5 5, a, The required row operations are 2R; +R —- Re, ple — Rg, and ~3R2+R, — R,. The corresponding elementary matrices that transform A to the identity are given in reonea-[} 4][3 £0] b. Since elementary matrices are invertible, we have that tpt pe 1 O0}f1 o]f1 3 Anzytey test =| ‘fo 0 | fo |: LZ Elementary Matrices and LU Factorization 29 6. a. The required row operations are Ri + Ro > Ro, $Re — Ro, -5Rp+R, > Ry, and -3R, ~— Ry. The corresponding elementary matrices that transform A to the identity are given in -4.0 1 - 1 0 1 0 reewooa-[) 113 “E][8 S11 t+ b. Since elementary matrices are invertible, we have that _petgetpetp-t_f 1 0]f1 O}f1 5 }f=2 0 a=e'es'e's'=[ 5 9 ][0 a 01 01" 7. a. The identity matrix can be written as I = Ey H4E3E,E,A, where the elementary matrices are 0 0 ,Eg=| 0 10 -1 01 10 0 By=|0 1 -5 |. b. A= Eyl eye; ley ey! 00 1 8, a. Row operations to reduce the matrix to the identity matrix are 8Ri + Reg—- Ro -2R,+R3 > R3 Rg «> Rg 4Ro+R3 —- Rg —-R,- Ry —Rg-> Ry —R3 — Rg Ro+ Ri > Rk, —Rg+Ry— Re with corresponding elementary matrices 10 0 L 0 0 38 1 0),£o=] 0 10 001 -2 0 1 -1 00 1 0 0 1 Es=|{ 0 1 0/,f=|0 -1 0],H=]0 1 0 Oo 1 0 0 1 1 0 -1 . b A= Ey; By By By By By By By test 00 1 9. a. The identity matrix can be written as [ = Eg-++E,A, where the elementary matrices are Ey = |O 1.0 1 -2 0 1 0 0 1 0 0 By=j}1 0 0)],2=/]0 1 O0f],2=}]0 1 O],Bg=)0 1-14, 00 1 0 0 1 QO -1 1 00 1 101 10 0 . Fy=|0 10], and B=]0 1 0 b, A= Ey By. Bg! 001 00 -1 . 10, a. There are only two row interchanges needed, R, > Rg and Rg + Rx. So [000 1]f1000 _ _ {0 10 0 0010 T=FalhA=| 9 9 1 o| fo 1 0 0 A. 100 0 000 4 30 Chapter 1 Systems of Linear Equations and Matrices b. A= Ey! Ey}. 1 11, The matrix A can be row reduced to an upper triangular matrix U = 0 “ , by means of the one operation 3R1 + Ry — Rz. The corresponding elementary matrix is E =. ; , , 80 that BA = U. Then the LU factorization of Ais A= LU = EU = 10 1-2 . -3 1 0 1 12. b= | 51 )%=(6 >| 1/6 1 0 -1/2 12 1 13, The matrix A can be row reduced to an upper triangular matrix U = | 0 1 3 |., by means of 00 1 the operations (~2)R, + Ry — Rez and 3R; + Rs — Rg. The corresponding elementary matrices are Ey = 1 0 0 100 -2 1 0] andE,=] 0 1 0 |,80 that Eyz,A =U. Then the LU factorization of Ais A= LU = 0 O01 301 1°00 121 EylEy'=| 2 1 0 01.3 -3 0 1 001 0 0 14, -|2 1 0}, 15, A= LU 2 01 144 1 0 0 1 4 -3 U=/01 -3 = 1 1 0 Oo 1 4 fo: 3 | a ayfed | 1000 1-2 1 8 —2 100 0 1. -1 = 1% A=IU=|) 7 oi o]]o 0 1 5 3 001 00 0 1 17. The first step is to determine an LU factorization for the coefficient matrix of the linear system A = ~ at |. We have that A = LU = 3 : - H |. Next we solve Ly = 5 | to obtain yi = —1 and ye = 3, The last step is to solve Ux = y, which has the unique solution a; = 2 and x = 3. 18. An LU factorization of the matrix A is given by A = - : ; 7 . Then the solution to 2 + Lon the enlation te 7 1 Ly = ~7/2 is y1 = 2,2 = 3, so the solution to Ux = y is 71 = 1, x = 5. 1 0 0 1 -l1 10 0 2 0 1 0 0 1 0 0} 0 1 0 0} 0 ~3 |---|] 0 1 0|-38 | —/} 0 1 0|-3 1 2 0 1) 1 0 0 1) 1 and hence, the solution is y1 = 0, ye = —38, and y3 = 1. Finally, the solution to Ux = y, which is the solution to the linear system, is 7 = 23,2 = —5, and wg = 1. : 4 -3 1 2 . To solve 0 1 19, An LU factorization of the coefficient matrix A is A= LU = 0 ly = | —3 | , we have that 1 1 0 0 -l1 10 2 01 1.7 Elementary Matrices and LU Factorization 31 1 0 0 20. An LU factorization of the matrix A is given by A = 2 1 -2 0 1 -2 0 0 ol 1 0 0 1 4 | . Then the solution 1 -1 to Ly = | 8 | is y1 = —1, yo = 10, y3 = 2, so the solution to Ux = y is a, = 1,49 = 2,03 = 2. 4 21. LU Factorization of the coefficient matrix: 1 0 0 0 1-2 3 1 1 1 00 Oo 1 2 2 . A=lU=| 5 9 1o0o}llo 011 -1 -1 0 1 0 0 0 1 5 Solution to Ly = QL 141 = 5, yo = 1,y3 = 4, y4 = -2 -8 Solution to Ux = y: #1 = ~25,29 = —7, a3 = 6,24 = —2 1 0 00 12 2 -1 vs + te Ate st _}| 0 tt 00 Oo 11-1] ,, 22. An LU factorization of the matrix A is given by A = -1 0 1.0 001 3 4° Then the 2 -2 0 1 0:0 0 2 5 ‘ solution to Ly = 7? is y1 = 5, yo = —2,y3 = 6,44 = —18, so the solution to Ux = y is 2 = Bay = 1 ~34,03 = Bay = — 1, 4 23, In order to row reduce the matrix A to an upper triangular matrix requires the operation of switching rows, This is reflected in the matrix P in the factorization 0 0 10 0 A=PLU=| 0 25 0 1 0 1 -% | 1 0 0 8 2 1-2], m0) 1 24, In order to row reduce the matrix A to an upper triangular matrix requires the operation of switching rows, This is reflected in the matrix P in the factorization 00 1]f71 00) A=PLU=|10 0]{4 1 0 o10}lLoo01] 25. Using the LU factorization A = LU = Ate=UOp = 26, oles nore elie nin | , we have that | 1-4) Hlat-l4 7) 32 Chapter 1 Systems of Linear Equations and Matrices 10 0 21 -1 27. Using the LU factorization A= LU =} 1 1 0 0 1 —1 |, we have that 111 00 8 : 3 -% 0 1 0 0 PF 1 3% 0 AteutEt=|0 1 3 -1 1 O0;/=f-1 2 3 1 0 0 3 0 -1 it O 3 3 28, 1 0 O}f-38 2 4)\7! P-h 2 -17 7100 Aut (LU)"t = ~l 1 0 0 12 =| 0% 1 ~2 110 1 o-1 1 0 01 0 0 fF 011 1 ib -} -1 =/ 1 -1 -2 0 1 1 29. Suppose a 0 de] _ /0 1 be Oo fi] t1 07f° This gives the system of equations ad = 0,ae = 1,bd = 1,be+cf =0. ‘The first two equations are satisfied only when a #0 and d= 0. But this incompatible with the third equation. 30. Since A is row equivalent to B there are elementary matrices such that B= E,... EA and since B is row equivalent to C there are elementary matrices such that C = D,,...D,B. Then C = Dn... D,B = Dn... Di Em...,A and hence, A is row equivalent to C. : 31, If A is invertible, there are elementary matrices Ey,...,£, such that J = E,-++: 1A. Similarly, there are elementary matrices D;,...,.De such that J = Dy:-.D,B. Then A =iB,' tee Ey'De: + D,B, so A is row equivalent to B, : 32. a, Since L is invertible, the diagonal entries are all nonzero. b. The determinant of A is the product of the diagonal entries of L and U, that is det(A) = ¢11+++Cnntiis++Unn. ¢. Since L is lower triangular and invertible it is row equivalent to the identity matrix and can be reduced to J using only replacement operations. Exercise Set 1.8 1, We need to find positive whole numbers 71, #2, 23, and «4 such that a@,Al3 + vgCuO —» xgAleO3 + wqCu is balanced, That is, we need to solve the linear system 3a, = 2x3 9 1 xq = 3e3.,which has infinitely many solutions given by a, = gras = g@a ks = Layo ER. tm = 04 9: Q A particular solution that balances the equation is given by v1 = 2,02 == 9,03 = 3,24 =9, 2. To balance the equation x Ip + w2NagS203 —> a3Nal + z4Nag$40¢, we solve the linear system 224 = 3 . 202 = @3 + 2a4 . a . . On 4 , 80 that 1 = 4,02 = 24,03 = 2x4,a4 € R. For a particular solution that balances CQ == 404 8a = ba4 the equation, let v4 = 1, so v1 = 1, x2 = 2, and a3 = 2,