“main”2007/2/16page 172iiiiiiii172 CHAPTER 2 Matrices and Systems of Linear Equations41. A =71315219 −2142317 −27 22 3119 −42 21 33.42. A is a randomly generated 5 × 5 matrix.43.  For the system in Problem 21, determine A−1anduse it to solve the system.44.  Consider the n × n Hilbert matrixHn=1i + j − 1, 1 ≤ i, j ≤ n.(a) Determine H4and show that it is invertible.(b) Find H−14and use it to solve H4x = b if b =[2, −1, 3, 5]T.2.7 Elementary Matrices and the LU FactorizationWe now introduce some matrices that can be used to perform elementary row operationson a matrix. Although they are of limited computational use, they do play a significantrole in linear algebra and its applications.DEFINITION 2.7.1Any matrix obtained by performing a single elementary row operation on the identitymatrix is called an elementary matrix.In particular, an elementary matrix is always a square matrix. In general we willdenote elementary matrices by E. If we are describing a specific elementary matrix, thenin keeping with the notation introduced previously for elementary row operations, wewill use the following notation for the three types of elementary matrices:Type 1: Pij—permute rows i and j in In.Type 2: Mi(k)—multiply row i of Inby the nonzero scalar k.Type 3: Aij(k)—add k times row i of Into row j of In.Example 2.7.2 Write all 2 × 2 elementary matrices.Solution: From Definition 2.7.1 and using the notation introduced above, we have1. Permutation matrix: P12=0110.2. Scaling matrices: M1(k) =k 001,M2(k) =100 k.3. Row combinations: A12(k) =10k 1,A21(k) =1 k01.We leave it as an exercise to verify that the n × n elementary matrices have thefollowing structure:“main”2007/2/16page 173iiiiiiii2.7 Elementary Matrices and the LU Factorization 173Pij: ones along main diagonal except (i, i) and (j, j), ones in the (i, j) and (j, i)positions, and zeros elsewhere.Mi(k): the diagonal matrix diag(1, 1,...,k,...,1), where k appears in the (i, i)position.Aij(k): ones along the main diagonal, k in the (j, i) position, and zeros elsewhere.A key point to note about elementary matrices is the following:Premultiplying an n × p matrix A by an n × n elementary matrix E has the effectof performing the corresponding elementary row operation on A.Rather than proving this statement, which we leave as an exercise, we illustrate withan example.Example 2.7.3 If A =3 −14275, then, for example,M1(k)A =k 0013 −14275=3k −k 4k275.Similarly,A21(k)A =1 k013 −14275=3 + 2k −1 + 7k 4 + 5k275. Since elementary row operations can be performed on a matrix by premultiplicationby an appropriate elementary matrix, it follows that any matrix A can be reduced to row-echelon form by multiplication by a sequence of elementary matrices. Schematically wecan therefore writeEkEk−1···E2E1A = U,where U denotes a row-echelon form of A and the Eiare elementary matrices.Example 2.7.4Determine elementary matrices that reduce A =2314to row-echelon form.Solution: We can reduce A to row-echelon form using the following sequence ofelementary row operations:23141∼14232∼140 −53∼1401.1. P122. A12(−2) 3. M2(−15)Consequently,M2(−15)A12(−2)P12A =1401,“main”2007/2/16page 174iiiiiiii174 CHAPTER 2 Matrices and Systems of Linear Equationswhich we can verify by direct multiplication:M2(−15)A12(−2)P12A =100 −1510−2101102314=100 −1510−211423=100 −15140 −5=1401. Since any elementary row operation is reversible, it follows that each elementarymatrix is invertible. Indeed, in the 2 × 2 case it is easy to see thatP−112=0110, M1(k)−1=1/k 001, M2(k)−1=1001/k,A12(k)−1=10−k 1, A21(k)−1=1 −k01.We leave it as an exercise to verify that in the n × n case, we have:Mi(k)−1= Mi(1/k), P−1ij= Pij, Aij(k)−1= Aij(−k)Now consider an invertible n × n matrix A. Since the unique reduced row-echelonform of such a matrix is the identity matrix In, it follows from the preceding discussionthat there exist elementary matrices E1,E2,...,Eksuch thatEkEk−1···E2E1A = In.But this implies thatA−1= EkEk−1···E2E1,and hence,A = (A−1)−1= (Ek···E2E1)−1= E−11E−12···E−1k,which is a product of elementary matrices. So any invertible matrix is a product of el-ementary matrices. Conversely, since elementary matrices are invertible, a product ofelementary matrices is a product of invertible matrices, hence is invertible by Corol-lary 2.6.10. Therefore, we have established the following.Theorem 2.7.5 Let A be an n ×n matrix. Then A is invertible if and only if A is a product of elementarymatrices.The LU Decomposition of an Invertible Matrix9For the remainder of this section, we restrict our attention to invertible n ×n matrices. Inreducing such a matrix to row-echelon form, we have always placed leading ones on themain diagonal in order that we obtain a row-echelon matrix. We now lift the requirementthat the main diagonal of the row-echelon form contain ones. As a consequence, thematrix that results from row reduction will be an upper triangular matrix but will notnecessarily be in row-echelon form. Furthermore, reduction to such an upper triangularform can be accomplished without the use of Type 2 row operations.9The material in the remainder of this section is not used elsewhere in the text.“main”2007/2/16page 175iiiiiiii2.7 Elementary Matrices and the LU Factorization 175Example 2.7.6 Use elementary row operations to reduce the matrixA =25 331−2−12 1to upper triangular form.Solution: The given matrix can be reduced to upper triangular form using the fol-lowing sequence of elementary row operations:25 331−2−12 11∼2520 −132−132092522∼2530 −132−13200−2.1. A12(−32), A13(12) 2. A23(913)When using elementary row operations of Type 3, the multiple of a specific row thatis subtracted from row i to put a zero in the (i, j ) position is called a multiplier anddenoted mij. Thus, in the preceding example, there are three multipliers—namely,m21=32,m31=−12,m32=−913.The multipliers will be used in the forthcoming discussion.In Example 2.7.6 we were able to reduce A to upper triangular form using only rowoperations