Linear Algebra Matrices and Determinants

how to solve linear algebra matrices and linear algebra matrix inverse properties and linear algebra matrix infinite solutions and Linear algebra matrices lecture notes
LexiWills Profile Pic
LexiWills,United Kingdom,Professional
Published Date:31-07-2017
Your Website URL(Optional)
Comment
LINEAR ALGEBRA W W L CHEN c W W L Chen, 1982, 2008. This chapter originates from material used by the author at Imperial College, University of London, between 1981 and 1990. It is available free to all individuals, on the understanding that it is not to be used for nancial gain, and may be downloaded and/or photocopied, with or without permission from the author. However, this document may not be kept on any information storage and retrieval system without permission from the author, unless such system is not accessible to any individuals other than its owners. Chapter 2 MATRICES 2.1. Introduction A rectangular array of numbers of the form 0 1 a ::: a 11 1n . . A . . (1) . . a ::: a m1 mn is called an mn matrix, with m rows and n columns. We count rows from the top and columns from the left. Hence 0 1 a 1j B C . . (a ::: a ) and i1 in A . a mj represent respectively the i-th row and the j-th column of the matrix (1), and a represents the entry ij in the matrix (1) on the i-th row and j-th column. Example 2.1.1. Consider the 3 4 matrix 0 1 2 4 3 1 A 3 1 5 2 : 1 0 7 6 Here 0 1 3 A ( 3 1 5 2 ) and 5 7 Chapter 2 : Matrices page 1 of 39c Linear Algebra W W L Chen, 1982, 2008 represent respectively the 2-nd row and the 3-rd column of the matrix, and 5 represents the entry in the matrix on the 2-nd row and 3-rd column. We now consider the question of arithmetic involving matrices. First of all, let us study the problem of addition. A reasonable theory can be derived from the following de nition. Definition. Suppose that the two matrices 0 1 0 1 a ::: a b ::: b 11 1n 11 1n . . . . A A . . . . A = and B = . . . . a ::: a b ::: b m1 mn m1 mn both have m rows and n columns. Then we write 0 1 a +b ::: a +b 11 11 1n 1n . . . . A A +B = . . a +b ::: a +b m1 m1 mn mn and call this the sum of the two matrices A and B. Example 2.1.2. Suppose that 0 1 0 1 2 4 3 1 1 2 2 7 A A A = 3 1 5 2 and B = 0 2 4 1 : 1 0 7 6 2 1 3 3 Then 0 1 0 1 2 + 1 4 + 2 3 2 1 + 7 3 6 1 6 A A A +B = 3 + 0 1 + 2 5 + 4 2 1 = 3 3 9 1 : 1 2 0 + 1 7 + 3 6 + 3 3 1 10 9 Example 2.1.3. We do not have a de nition for \adding" the matrices 0 1   2 4 3 2 4 3 1 A and 3 1 5 : 1 0 7 6 1 0 7 PROPOSITION 2A. (MATRIX ADDITION) Suppose that A;B;C are mn matrices. Suppose further that O represents the mn matrix with all entries zero. Then (a) A +B =B +A; (b) A + (B +C) = (A +B) +C; (c) A +O =A; and 0 0 (d) there is an mn matrix A such that A +A =O. Proof. Parts (a)(c) are easy consequences of ordinary addition, as matrix addition is simply entry-wise 0 addition. For part (d), we can consider the matrix A obtained from A by multiplying each entry of A by1. The theory of multiplication is rather more complicated, and includes multiplication of a matrix by a scalar as well as multiplication of two matrices. We rst study the simpler case of multiplication by scalars. Chapter 2 : Matrices page 2 of 39c Linear Algebra W W L Chen, 1982, 2008 Definition. Suppose that the matrix 0 1 a ::: a 11 1n . . A . . A = . . a ::: a m1 mn has m rows and n columns, and that c2R. Then we write 0 1 ca ::: ca 11 1n . . A . . cA = . . ca ::: ca m1 mn and call this the product of the matrix A by the scalar c. Example 2.1.4. Suppose that 0 1 2 4 3 1 A A = 3 1 5 2 : 1 0 7 6 Then 0 1 4 8 6 2 A 2A = 6 2 10 4 : 2 0 14 12 PROPOSITION 2B. (MULTIPLICATION BY SCALAR) Suppose thatA;B aremn matrices, and that c;d2R. Suppose further that O represents the mn matrix with all entries zero. Then (a) c(A +B) =cA +cB; (b) (c +d)A =cA +dA; (c) 0A =O; and (d) c(dA) = (cd)A. Proof. These are all easy consequences of ordinary multiplication, as multiplication by scalarc is simply entry-wise multiplication by the number c. The question of multiplication of two matrices is rather more complicated. To motivate this, let us consider the representation of a system of linear equations a x +::: + a x = b ; 11 1 1n n 1 . . (2) . a x +::: +a x =b ; m1 1 mn n m in the form Ax =b, where 0 1 0 1 a ::: a b 11 1n 1 . . . A A . . . A = and b = (3) . . . a ::: a b m1 mn m represent the coecients and 0 1 x 1 . A . x = (4) . x n Chapter 2 : Matrices page 3 of 39c Linear Algebra W W L Chen, 1982, 2008 represents the variables. This can be written in full matrix notation by 0 10 1 0 1 a ::: a x b 11 1n 1 1 . . . . A A A . . . . = : . . . . a ::: a x b m1 mn n m Can you work out the meaning of this representation? Now let us de ne matrix multiplication more formally. Definition. Suppose that 0 1 0 1 b ::: b a ::: a 11 1p 11 1n . . B C . . A . . A = and B = . . A . . . . a ::: a b ::: b m1 mn n1 np are respectively an mn matrix and an np matrix. Then the matrix product AB is given by the mp matrix 0 1 q ::: q 11 1p B C . . AB = . . ; A . . q ::: q m1 mp where for every i = 1;:::;m and j = 1;:::;p, we have n X q = a b =a b +::: +a b : ij ik kj i1 1j in nj k=1 Remark. Note rst of all that the number of columns of the rst matrix must be equal to the number of rows of the second matrix. On the other hand, for a simple way to work out q , the entry in the i-th ij row andj-th column ofAB, we observe that thei-th row ofA and thej-th column ofB are respectively 0 1 b 1j B C . . (a ::: a ) and : i1 in A . b nj We now multiply the corresponding entries from a withb , and so on, untila withb and then i1 1j in nj add these products to obtain q . ij Example 2.1.5. Consider the matrices 0 1 0 1 1 4 2 4 3 1 2 3 B C A A = 3 1 5 2 and B = : A 0 2 1 0 7 6 3 1 Note that A is a 3 4 matrix and B is a 4 2 matrix, so that the product AB is a 3 2 matrix. Let us calculate the product 0 1 q q 11 12 A AB = q q : 21 22 q q 31 32 Chapter 2 : Matrices page 4 of 39c Linear Algebra W W L Chen, 1982, 2008 Consider rst of allq . To calculate this, we need the 1-st row of A and the 1-st column ofB, so let us 11 cover up all unnecessary information, so that 0 1 0 1 0 1 1  2 4 3 1 q  11 2  B C A A     =   : A 0        3  From the de nition, we have q = 2 1 + 4 2 + 3 0 + (1) 3 = 2 + 8 + 0 3 = 7: 11 Consider nextq . To calculate this, we need the 1-st row ofA and the 2-nd column ofB, so let us cover 12 up all unnecessary information, so that 0 1 0 1 0 1  4 2 4 3 1  q 12  3 B C A A     =   : A  2        1 From the de nition, we have q = 2 4 + 4 3 + 3 (2) + (1) 1 = 8 + 12 6 1 = 13: 12 Consider nextq . To calculate this, we need the 2-nd row ofA and the 1-st column ofB, so let us cover 21 up all unnecessary information, so that 0 1 0 1 0 1 1        2  B C A A 3 1 5 2 = q  : A 21 0        3  From the de nition, we have q = 3 1 + 1 2 + 5 0 + 2 3 = 3 + 2 + 0 + 6 = 11: 21 Consider next q . To calculate this, we need the 2-nd row of A and the 2-nd column of B, so let us 22 cover up all unnecessary information, so that 0 1 0 1 0 1  4        3 B C A A 3 1 5 2 =  q : A 22  2        1 From the de nition, we have q = 3 4 + 1 3 + 5 (2) + 2 1 = 12 + 3 10 + 2 = 7: 22 Consider nextq . To calculate this, we need the 3-rd row ofA and the 1-st column ofB, so let us cover 31 up all unnecessary information, so that 0 1 0 1 0 1 1        B 2 C A A     A =   : 0  1 0 7 6 q  31 3  From the de nition, we have q = (1) 1 + 0 2 + 7 0 + 6 3 =1 + 0 + 0 + 18 = 17: 31 Chapter 2 : Matrices page 5 of 39c Linear Algebra W W L Chen, 1982, 2008 Consider nally q . To calculate this, we need the 3-rd row of A and the 2-nd column of B, so let us 32 cover up all unnecessary information, so that 0 1 0 1 0 1  4        3 B C A A     =   : A  2 1 0 7 6  q 32  1 From the de nition, we have q = (1) 4 + 0 3 + 7 (2) + 6 1 =4 + 0 +14 + 6 =12: 32 We therefore conclude that 0 1 0 1 0 1 1 4 2 4 3 1 7 13 2 3 B C A A AB = 3 1 5 2 = 11 7 : A 0 2 1 0 7 6 17 12 3 1 Example 2.1.6. Consider again the matrices 0 1 0 1 1 4 2 4 3 1 2 3 B C A A = 3 1 5 2 and B = : A 0 2 1 0 7 6 3 1 Note that B is a 4 2 matrix and A is a 3 4 matrix, so that we do not have a de nition for the \product" BA. We leave the proofs of the following results as exercises for the interested reader. PROPOSITION2C. (ASSOCIATIVE LAW) Suppose thatA is anmn matrix,B is annp matrix and C is an pr matrix. Then A(BC) = (AB)C. PROPOSITION 2D. (DISTRIBUTIVE LAWS) (a) Suppose that A is an mn matrix and B and C are np matrices. Then A(B +C) =AB +AC. (b) Suppose that A and B are mn matrices and C is an np matrix. Then (A +B)C =AC +BC. PROPOSITION 2E. Suppose that A is an mn matrix, B is an np matrix, and that c2R. Then c(AB) = (cA)B =A(cB). 2.2. Systems of Linear Equations Note that the system (2) of linear equations can be written in matrix form as Ax =b; where the matrices A, x and b are given by (3) and (4). In this section, we shall establish the following important result. PROPOSITION 2F. Every system of linear equations of the form (2) has either no solution, one solution or in nitely many solutions. Chapter 2 : Matrices page 6 of 39c Linear Algebra W W L Chen, 1982, 2008 Proof. Clearly the system (2) has either no solution, exactly one solution, or more than one solution. It remains to show that if the system (2) has two distinct solutions, then it must have in nitely many solutions. Suppose that x =u and x =v represent two distinct solutions. Then Au =b and Av =b; so that A(uv) =AuAv =bb =0; where 0 is the zero m 1 matrix. It now follows that for every c2R, we have A(u +c(uv)) =Au +A(c(uv)) =Au +c(A(uv)) =b +c0 =b; so that x =u +c(uv) is a solution for every c2R. Clearly we have in nitely many solutions. 2.3. Inversion of Matrices For the remainder of this chapter, we shall deal with square matrices, those where the number of rows equals the number of columns. Definition. The nn matrix 0 1 a ::: a 11 1n . . . . A I = ; n . . a ::: a n1 nn where  1 if i =j, a = ij 0 if i6=j, is called the identity matrix of order n. Remark. Note that 0 1 1 0 0 0 B 0 1 0 0C I = ( 1 ) and I = : 1 4 A 0 0 1 0 0 0 0 1 The following result is relatively easy to check. It shows that the identity matrixI acts as the identity n for multiplication of nn matrices. PROPOSITION 2G. For every nn matrix A, we have AI =I A =A. n n This raises the following question: Given annn matrixA, is it possible to nd anothernn matrix B such that AB =BA =I ? n We shall postpone the full answer to this question until the next chapter. In Section 2.5, however, we shall be content with nding such a matrix B if it exists. In Section 2.6, we shall relate the existence of such a matrix B to some properties of the matrix A. Chapter 2 : Matrices page 7 of 39c Linear Algebra W W L Chen, 1982, 2008 Definition. An nn matrix A is said to be invertible if there exists an nn matrix B such that 1 AB =BA =I . In this case, we say that B is the inverse of A and write B =A . n 1 PROPOSITION 2H. Suppose that A is an invertible nn matrix. Then its inverse A is unique. Proof. Suppose that B satis es the requirements for being the inverse of A. Then AB =BA =I . It n follows that 1 1 1 1 A =A I =A (AB) = (A A)B =I B =B: n n 1 Hence the inverse A is unique. 1 1 1 PROPOSITION 2J. Suppose that A and B are invertible nn matrices. Then (AB) =B A . 1 1 Proof. In view of the uniqueness of inverse, it is sucient to show that B A satis es the require- ments for being the inverse of AB. Note that 1 1 1 1 1 1 1 1 (AB)(B A ) =A(B(B A )) =A((BB )A ) =A(I A ) =AA =I n n and 1 1 1 1 1 1 1 1 (B A )(AB) =B (A (AB)) =B ((A A)B) =B (I B) =B B =I n n as required. 1 1 PROPOSITION 2K. Suppose that A is an invertible nn matrix. Then (A ) =A. 1 1 1 Proof. Note that both (A ) and A satisfy the requirements for being the inverse of A . Equality follows from the uniqueness of inverse. 2.4. Application to Matrix Multiplication In this section, we shall discuss an application of invertible matrices. Detailed discussion of the technique involved will be covered in Chapter 7. Definition. An nn matrix 0 1 a ::: a 11 1n . . A . . A = ; . . a ::: a n1 nn where a = 0 whenever i6=j, is called a diagonal matrix of order n. ij Example 2.4.1. The 3 3 matrices 0 1 0 1 1 0 0 0 0 0 A A 0 2 0 and 0 0 0 0 0 0 0 0 0 are both diagonal. Given an nn matrix A, it is usually rather complicated to calculate k A =A:::A: z k However, the calculation is rather simple when A is a diagonal matrix, as we shall see in the following example. Chapter 2 : Matrices page 8 of 39c Linear Algebra W W L Chen, 1982, 2008 Example 2.4.2. Consider the 3 3 matrix 0 1 17 10 5 A A = 45 28 15 : 30 20 12 98 Suppose that we wish to calculate A . It can be checked that if we take 0 1 1 1 2 A P = 3 0 3 ; 2 3 0 then 0 1 3 2 1 1 A P = 2 4=3 1 : 3 5=3 1 Furthermore, if we write 0 1 3 0 0 A D = 0 2 0 ; 0 0 2 1 then it can be checked that A =PDP , so that 0 1 98 3 0 0 98 1 1 98 1 1 98 A A = (PDP )::: (PDP ) =PD P =P 0 2 0 P : z 98 0 0 2 98 98 This is much simpler than calculating A directly. Note that this example is only an illustration. We have not discussed here how the matrices P and D are found. 2.5. Finding Inverses by Elementary Row Operations In this section, we shall discuss a technique by which we can nd the inverse of a square matrix, if the inverse exists. Before we discuss this technique, let us recall the three elementary row operations we discussed in the previous chapter. These are: (1) interchanging two rows; (2) adding a multiple of one row to another row; and (3) multiplying one row by a non-zero constant. Let us now consider the following example. Example 2.5.1. Consider the matrices 0 1 0 1 a a a 1 0 0 11 12 13 A A A = a a a and I = 0 1 0 : 21 22 23 3 a a a 0 0 1 31 32 33  Let us interchange rows 1 and 2 of A and do likewise for I . We obtain respectively 3 0 1 0 1 a a a 0 1 0 21 22 23 A A a a a and 1 0 0 : 11 12 13 a a a 0 0 1 31 32 33 Chapter 2 : Matrices page 9 of 39c Linear Algebra W W L Chen, 1982, 2008 Note that 0 1 0 10 1 a a a 0 1 0 a a a 21 22 23 11 12 13 A A A a a a = 1 0 0 a a a : 11 12 13 21 22 23 a a a 0 0 1 a a a 31 32 33 31 32 33  Let us interchange rows 2 and 3 of A and do likewise for I . We obtain respectively 3 0 1 0 1 a a a 1 0 0 11 12 13 A A a a a and 0 0 1 : 31 32 33 a a a 0 1 0 21 22 23 Note that 0 1 0 10 1 a a a 1 0 0 a a a 11 12 13 11 12 13 A A A a a a = 0 0 1 a a a : 31 32 33 21 22 23 a a a 0 1 0 a a a 21 22 23 31 32 33  Let us add 3 times row 1 to row 2 of A and do likewise for I . We obtain respectively 3 0 1 0 1 a a a 1 0 0 11 12 13 A A 3a +a 3a +a 3a +a and 3 1 0 : 11 21 12 22 13 23 a a a 0 0 1 31 32 33 Note that 0 1 0 10 1 a a a 1 0 0 a a a 11 12 13 11 12 13 A A A 3a +a 3a +a 3a +a = 3 1 0 a a a : 11 21 12 22 13 23 21 22 23 a a a 0 0 1 a a a 31 32 33 31 32 33  Let us add2 times row 3 to row 1 of A and do likewise for I . We obtain respectively 3 0 1 0 1 2a +a 2a +a 2a +a 1 0 2 31 11 32 12 33 13 A A a a a and 0 1 0 : 21 22 23 a a a 0 0 1 31 32 33 Note that 0 1 0 10 1 2a +a 2a +a 2a +a 1 0 2 a a a 31 11 32 12 33 13 11 12 13 A A A a a a = 0 1 0 a a a : 21 22 23 21 22 23 a a a 0 0 1 a a a 31 32 33 31 32 33  Let us multiply row 2 of A by 5 and do likewise for I . We obtain respectively 3 0 1 0 1 a a a 1 0 0 11 12 13 A A 5a 5a 5a and 0 5 0 : 21 22 23 a a a 0 0 1 31 32 33 Note that 0 1 0 10 1 a a a 1 0 0 a a a 11 12 13 11 12 13 A A A 5a 5a 5a = 0 5 0 a a a : 21 22 23 21 22 23 a a a 0 0 1 a a a 31 32 33 31 32 33  Let us multiply row 3 of A by1 and do likewise for I . We obtain respectively 3 0 1 0 1 a a a 1 0 0 11 12 13 A A a a a and 0 1 0 : 21 22 23 a a a 0 0 1 31 32 33 Chapter 2 : Matrices page 10 of 39c Linear Algebra W W L Chen, 1982, 2008 Note that 0 1 0 10 1 a a a 1 0 0 a a a 11 12 13 11 12 13 A A A a a a = 0 1 0 a a a : 21 22 23 21 22 23 a a a 0 0 1 a a a 31 32 33 31 32 33 Let us now consider the problem in general. Definition. By an elementarynn matrix, we mean annn matrix obtained fromI by an elementary n row operation. We state without proof the following important result. The interested reader may wish to construct a proof, taking into account the di erent types of elementary row operations. PROPOSITION 2L. Suppose that A is an nn matrix, and suppose that B is obtained from A by an elementary row operation. Suppose further that E is an elementary matrix obtained from I by the n same elementary row operation. Then B =EA. We now adopt the following strategy. Consider annn matrixA. Suppose that it is possible to reduce the matrix A by a sequence ; ;:::; of elementary row operations to the identity matrix I . If 1 2 k n E ;E ;:::;E are respectively the elementary nn matrices obtained fromI by the same elementary 1 2 k n row operations ; :::; , then 1 2 k I =E :::E E A: n k 2 1 We therefore must have 1 A =E :::E E =E :::E E I : k 2 1 k 2 1 n 1 It follows that the inverseA can be obtained fromI by performing the same elementary row operations n ; ;:::; . Since we are performing the same elementary row operations onA andI , it makes sense 1 2 k n to put them side by side. The process can then be described pictorially by 1 (AjI ) (E AjE I ) n 1 1 n 2 (E E AjE E I ) 2 1 2 1 n 3 ::: k 1 (E :::E E AjE :::E E I ) = (I jA ): k 2 1 k 2 1 n n In other words, we consider an array with the matrix A on the left and the matrix I on the right. We n now perform elementary row operations on the array and try to reduce the left hand half to the matrix 1 I . If we succeed in doing so, then the right hand half of the array gives the inverse A . n Example 2.5.2. Consider the matrix 0 1 1 1 2 A A = 3 0 3 : 2 3 0 1 To nd A , we consider the array 0 1 1 1 2 1 0 0 A (AjI ) = 3 0 3 0 1 0 : 3 2 3 0 0 0 1 Chapter 2 : Matrices page 11 of 39c Linear Algebra W W L Chen, 1982, 2008 We now perform elementary row operations on this array and try to reduce the left hand half to the matrix I . Note that if we succeed, then the nal array is clearly in reduced row echelon form. We 3 therefore follow the same procedure as reducing an array to reduced row echelon form. Adding3 times row 1 to row 2, we obtain 0 1 1 1 2 1 0 0 A 0 3 3 3 1 0 : 2 3 0 0 0 1 Adding 2 times row 1 to row 3, we obtain 0 1 1 1 2 1 0 0 A 0 3 3 3 1 0 : 0 5 4 2 0 1 Multiplying row 3 by 3, we obtain 0 1 1 1 2 1 0 0 A 0 3 3 3 1 0 : 0 15 12 6 0 3 Adding 5 times row 2 to row 3, we obtain 0 1 1 1 2 1 0 0 A 0 3 3 3 1 0 : 0 0 3 9 5 3 Multiplying row 1 by 3, we obtain 0 1 3 3 6 3 0 0 A 0 3 3 3 1 0 : 0 0 3 9 5 3 Adding 2 times row 3 to row 1, we obtain 0 1 3 3 0 15 10 6 A 0 3 3 3 1 0 : 0 0 3 9 5 3 Adding1 times row 3 to row 2, we obtain 0 1 3 3 0 15 10 6 A 0 3 0 6 4 3 : 0 0 3 9 5 3 Adding 1 times row 2 to row 1, we obtain 0 1 3 0 0 9 6 3 A 0 3 0 6 4 3 : 0 0 3 9 5 3 Multiplying row 1 by 1=3, we obtain 0 1 1 0 0 3 2 1 A 0 3 0 6 4 3 : 0 0 3 9 5 3 Chapter 2 : Matrices page 12 of 39c Linear Algebra W W L Chen, 1982, 2008 Multiplying row 2 by1=3, we obtain 0 1 1 0 0 3 2 1 A 0 1 0 2 4=3 1 : 0 0 3 9 5 3 Multiplying row 3 by1=3, we obtain 0 1 1 0 0 3 2 1 A 0 1 0 2 4=3 1 : 0 0 1 3 5=3 1 Note now that the array is in reduced row echelon form, and that the left hand half is the identity matrix 1 I . It follows that the right hand half of the array represents the inverse A . Hence 3 0 1 3 2 1 1 A A = 2 4=3 1 : 3 5=3 1 Example 2.5.3. Consider the matrix 0 1 1 1 2 3 B 2 2 4 5C A = : A 0 3 0 0 0 0 0 1 1 To nd A , we consider the array 0 1 1 1 2 3 1 0 0 0 2 2 4 5 0 1 0 0 B C (AjI ) = : A 4 0 3 0 0 0 0 1 0 0 0 0 1 0 0 0 1 We now perform elementary row operations on this array and try to reduce the left hand half to the matrix I . Adding2 times row 1 to row 2, we obtain 4 0 1 1 1 2 3 1 0 0 0 0 0 0 1 2 1 0 0 B C : A 0 3 0 0 0 0 1 0 0 0 0 1 0 0 0 1 Adding 1 times row 2 to row 4, we obtain 0 1 1 1 2 3 1 0 0 0 0 0 0 1 2 1 0 0 B C : A 0 3 0 0 0 0 1 0 0 0 0 0 2 1 0 1 Interchanging rows 2 and 3, we obtain 0 1 1 1 2 3 1 0 0 0 0 3 0 0 0 0 1 0 B C : A 0 0 0 1 2 1 0 0 0 0 0 0 2 1 0 1 Chapter 2 : Matrices page 13 of 39c Linear Algebra W W L Chen, 1982, 2008 At this point, we observe that it is impossible to reduce the left hand half of the array to I . For those 4 who remain unconvinced, let us continue. Adding 3 times row 3 to row 1, we obtain 0 1 1 1 2 0 5 3 0 0 B 0 3 0 0 0 0 1 0C A: 0 0 0 1 2 1 0 0 0 0 0 0 2 1 0 1 Adding1 times row 4 to row 3, we obtain 0 1 1 1 2 0 5 3 0 0 B 0 3 0 0 0 0 1 0 C A: 0 0 0 1 0 0 0 1 0 0 0 0 2 1 0 1 Multiplying row 1 by 6 (here we want to avoid fractions in the next two steps), we obtain 0 1 6 6 12 0 30 18 0 0 B 0 3 0 0 0 0 1 0 C : A 0 0 0 1 0 0 0 1 0 0 0 0 2 1 0 1 Adding15 times row 4 to row 1, we obtain 0 1 6 6 12 0 0 3 0 15 B 0 3 0 0 0 0 1 0 C : A 0 0 0 1 0 0 0 1 0 0 0 0 2 1 0 1 Adding2 times row 2 to row 1, we obtain 0 1 6 0 12 0 0 3 2 15 B 0 3 0 0 0 0 1 0 C : A 0 0 0 1 0 0 0 1 0 0 0 0 2 1 0 1 Multiplying row 1 by 1=6, multiplying row 2 by 1=3, multiplying row 3 by1 and multiplying row 4 by 1=2, we obtain 0 1 1 0 2 0 0 1=2 1=3 5=2 B 0 1 0 0 0 0 1=3 0 C : A 0 0 0 1 0 0 0 1 0 0 0 0 1 1=2 0 1=2 Note now that the array is in reduced row echelon form, and that the left hand half is not the identity matrix I . Our technique has failed. In fact, the matrix A is not invertible. 4 2.6. Criteria for Invertibility Examples 2.5.22.5.3 raise the question of when a given matrix is invertible. In this section, we shall obtain some partial answers to this question. Our rst step here is the following simple observation. PROPOSITION 2M. Every elementary matrix is invertible. Proof. Let us consider elementary row operations. Recall that these are: (1) interchanging two rows; (2) adding a multiple of one row to another row; and (3) multiplying one row by a non-zero constant. Chapter 2 : Matrices page 14 of 39c Linear Algebra W W L Chen, 1982, 2008 These elementary row operations can clearly be reversed by elementary row operations. For (1), we interchange the two rows again. For (2), if we have originally added c times rowi to rowj, then we can reverse this by addingc times row i to row j. For (3), if we have multiplied any row by a non-zero constant c, we can reverse this by multiplying the same row by the constant 1=c. Note now that each elementary matrix is obtained from I by an elementary row operation. The inverse of this elementary n matrix is clearly the elementary matrix obtained from I by the elementary row operation that reverses n the original elementary row operation. Suppose that an nn matrix B can be obtained from an nn matrix A by a nite sequence of elementary row operations. Then since these elementary row operations can be reversed, the matrix A can be obtained from the matrix B by a nite sequence of elementary row operations. Definition. Annn matrixA is said to be row equivalent to an nn matrixB if there exist a nite number of elementary nn matrices E ;:::;E such that B =E :::E A. 1 k k 1 1 1 Remark. Note that B = E :::E A implies that A = E :::E B. It follows that if A is row k 1 1 k equivalent to B, then B is row equivalent to A. We usually say that A and B are row equivalent. The following result gives conditions equivalent to the invertibility of an nn matrix A. PROPOSITION 2N. Suppose that 0 1 a ::: a 11 1n . . A . . A = ; . . a ::: a n1 nn and that 0 1 0 1 x 1 0 . . . A .A x = and 0 = . . x 0 n are n 1 matrices, where x ;:::;x are variables. 1 n (a) Suppose that the matrix A is invertible. Then the system Ax = 0 of linear equations has only the trivial solution. (b) Suppose that the system Ax =0 of linear equations has only the trivial solution. Then the matrices A and I are row equivalent. n (c) Suppose that the matrices A and I are row equivalent. Then A is invertible. n Proof. (a) Suppose that x is a solution of the system Ax =0. Then since A is invertible, we have 0 1 1 1 x =I x = (A A)x =A (Ax ) =A 0 =0: 0 n 0 0 0 It follows that the trivial solution is the only solution. (b) Note that if the system Ax = 0 of linear equations has only the trivial solution, then it can be reduced by elementary row operations to the system x = 0; :::; x = 0: 1 n This is equivalent to saying that the array 0 1 a ::: a 0 11 1n . . . .A . . . . . 0 a ::: a n1 nn Chapter 2 : Matrices page 15 of 39c Linear Algebra W W L Chen, 1982, 2008 can be reduced by elementary row operations to the reduced row echelon form 0 1 1 ::: 0 0 . . . . . .A : . . . 0 ::: 1 0 Hence the matrices A and I are row equivalent. n (c) Suppose that the matricesA andI are row equivalent. Then there exist elementarynn matrices n E ;:::;E such thatI =E :::E A. By Proposition 2M, the matrices E ;:::;E are all invertible, so 1 k n k 1 1 k that 1 1 1 1 A =E :::E I =E :::E n 1 k 1 k is a product of invertible matrices, and is therefore itself invertible. 2.7. Consequences of Invertibility Suppose that the matrix 0 1 a ::: a 11 1n . . A . . A = . . a ::: a n1 nn is invertible. Consider the system Ax =b, where 0 1 0 1 x b 1 1 . . A A . . x = and b = . . x b n n aren 1 matrices, wherex ;:::;x are variables andb ;:::;b 2R are arbitrary. SinceA is invertible, 1 n 1 n 1 let us consider x =A b. Clearly 1 1 Ax =A(A b) = (AA )b =I b =b; n 1 so that x =A b is a solution of the system. On the other hand, let x be any solution of the system. 0 Then Ax =b, so that 0 1 1 1 x =I x = (A A)x =A (Ax ) =A b: 0 n 0 0 0 It follows that the system has unique solution. We have proved the following important result. PROPOSITION 2P. Suppose that 0 1 a ::: a 11 1n . . A . . A = ; . . a ::: a n1 nn and that 0 1 0 1 x b 1 1 . . A A . . x = and b = . . x b n n are n 1 matrices, where x ;:::;x are variables and b ;:::;b 2 R are arbitrary. Suppose further 1 n 1 n that the matrix A is invertible. Then the system Ax = b of linear equations has the unique solution 1 x =A b. Chapter 2 : Matrices page 16 of 39c Linear Algebra W W L Chen, 1982, 2008 We next attempt to study the question in the opposite direction. PROPOSITION 2Q. Suppose that 0 1 a ::: a 11 1n . . A . . A = ; . . a ::: a n1 nn and that 0 1 0 1 x b 1 1 . . A A . . x = and b = . . x b n n are n 1 matrices, where x ;:::;x are variables. Suppose further that for every b ;:::;b 2 R, the 1 n 1 n system Ax =b of linear equations is soluble. Then the matrix A is invertible. Proof. Suppose that 0 1 0 1 1 0 B 0C B 0C B C B C . . B .C B .C b = ; :::; b = : 1 . n . B C B C A A 0 0 0 1 In other words, for everyj = 1;:::;n,b is ann1 matrix with entry 1 on rowj and entry 0 elsewhere. j Now let 0 1 0 1 x x 11 1n . . A A . . x = ; :::; x = 1 n . . x x n1 nn denote respectively solutions of the systems of linear equations Ax =b ; :::; Ax =b : 1 n It is easy to check that A (x ::: x ) = (b ::: b ) ; 1 n 1 n in other words, 0 1 x ::: x 11 1n . . A . . A =I ; n . . x ::: x n1 nn so that A is invertible. We can now summarize Propositions 2N, 2P and 2Q as follows. PROPOSITION 2R. In the notation of Proposition 2N, the following four statements are equivalent: (a) The matrix A is invertible. (b) The system Ax =0 of linear equations has only the trivial solution. (c) The matrices A and I are row equivalent. n (d) The system Ax =b of linear equations is soluble for every n 1 matrix b. Chapter 2 : Matrices page 17 of 39c Linear Algebra W W L Chen, 1982, 2008 2.8. Application to Economics In this section, we describe brie y the Leontief input-output model, where an economy is divided into n sectors. For every i = 1;:::;n, let x denote the monetary value of the total output of sector i over a xed i period, and let d denote the output of sector i needed to satisfy outside demand over the same xed i period. Collecting together x and d for i = 1;:::;n, we obtain the vectors i i 0 1 0 1 x d 1 1 . . n n A A . . x = 2R and d = 2R ; . . x d n n known respectively as the production vector and demand vector of the economy. On the other hand, each of the n sectors requires material from some or all of the sectors to produce its output. For i;j = 1;:::;n, let c denote the monetary value of the output of sector i needed by ij sector j to produce one unit of monetary value of output. For every j = 1;:::;n, the vector 0 1 c 1j B C . n . c = 2R j A . c nj is known as the unit consumption vector of sector j. Note that the column sum c +::: +c  1 (5) 1j nj in order to ensure that sector j does not make a loss. Collecting together the unit consumption vectors, we obtain the matrix 0 1 c ::: c 11 1n . . A . . C = (c ::: c ) = ; 1 n . . c ::: c n1 nn known as the consumption matrix of the economy. Consider the matrix product 0 1 c x +::: +c x 11 1 1n n . A . Cx = : . c x +::: +c x n1 1 nn n For everyi = 1;:::;n, the entryc x +:::+c x represents the monetary value of the output of sector i1 1 in n i needed by all the sectors to produce their output. This leads to the production equation x =Cx +d: (6) Here Cx represents the part of the total output that is required by the various sectors of the economy to produce the output in the rst place, and d represents the part of the total output that is available to satisfy outside demand. Clearly (IC)x =d. If the matrix IC is invertible, then 1 x = (IC) d represents the perfect production level. We state without proof the following fundamental result. Chapter 2 : Matrices page 18 of 39c Linear Algebra W W L Chen, 1982, 2008 PROPOSITION 2S. Suppose that the entries of the consumption matrix C and the demand vector d are non-negative. Suppose further that the inequality (5) holds for each column of C. Then the inverse 1 1 matrix (IC) exists, and the production vector x = (IC) d has non-negative entries and is the unique solution of the production equation (6). Let us indulge in some heuristics. Initially, we have demand d. To produce d, we need Cd as input. 2 2 To produce this extra Cd, we need C(Cd) = C d as input. To produce this extra C d, we need 2 3 C(C d) =C d as input. And so on. Hence we need to produce 2 3 2 3 d +Cd +C d +C d +::: = (I +C +C +C +:::)d in total. Now it is not dicult to check that for every positive integer k, we have 2 3 k k+1 (IC)(I +C +C +C +::: +C ) =IC : k+1 If the entries of C are all very small, then 2 3 k (IC)(I +C +C +C +::: +C )I; so that 1 2 3 k (IC) I +C +C +C +::: +C : 1 This gives a practical way of approximating (IC) , and also suggests that 1 2 3 (IC) =I +C +C +C +:::: Example 2.8.1. An economy consists of three sectors. Their dependence on each other is summarized in the table below: To produce one unit of monetary value of output in sector 1 2 3 monetary value of output required from sector 1 0:3 0:2 0:1 monetary value of output required from sector 2 0:4 0:5 0:2 monetary value of output required from sector 3 0:1 0:1 0:3 Suppose that the nal demand from sectors 1, 2 and 3 are respectively 30, 50 and 20. Then the production vector and demand vector are respectively 0 1 0 1 0 1 x d 30 1 1 A A A x = x and d = d = 50 ; 2 2 x d 20 3 3 while the consumption matrix is given by 0 1 0 1 0:3 0:2 0:1 0:7 0:2 0:1 A A C = 0:4 0:5 0:2 ; so that IC = 0:4 0:5 0:2 : 0:1 0:1 0:3 0:1 0:1 0:7 The production equation (IC)x =d has augmented matrix 0 1 0 1 0:7 0:2 0:1 30 7 2 1 300 A A 0:4 0:5 0:2 50 ; equivalent to 4 5 2 500 ; 0:1 0:1 0:7 20 1 1 7 200 Chapter 2 : Matrices page 19 of 39c Linear Algebra W W L Chen, 1982, 2008 and which can be converted to reduced row echelon form 0 1 1 0 0 3200=27 A 0 1 0 6100=27 : 0 0 1 700=9 This gives x  119, x  226 and x  78, to the nearest integers. 1 2 3 2.9. Matrix Transformation on the Plane 2 2 Let A be a 2 2 matrix with real entries. A matrix transformation T : R R can be de ned as 2 follows: For every x = (x ;x )2R, we write T (x) =y, where y = (y ;y )2R satis es 1 2 1 2     y x 1 1 =A : y x 2 2 0 00 0 0 0 00 2 Such a transformation is linear, in the sense that T (x +x ) =T (x ) +T (x ) for every x;x 2R and 2 T (cx) =cT (x) for every x2R and every c2R. To see this, simply observe that           0 00 0 00 x +x x x cx x 1 1 1 1 1 1 A =A +A and A =cA : 0 00 0 00 x +x x x cx x 2 2 2 2 2 2 We shall study linear transformations in greater detail in Chapter 8. Here we con ne ourselves to looking at a few simple matrix transformations on the plane. Example 2.9.1. The matrix          1 0 x 1 0 x x 1 1 1 A = satis es A = = 0 1 x 0 1 x x 2 2 2 2 for every (x ;x )2R , and so represents re ection across the x -axis, whereas the matrix 1 2 1          1 0 x 1 0 x x 1 1 1 A = satis es A = = 0 1 x 0 1 x x 2 2 2 2 for every (x ;x )2R , and so represents re ection across the x -axis. On the other hand, the matrix 1 2 2          1 0 x 1 0 x x 1 1 1 A = satis es A = = 0 1 x 0 1 x x 2 2 2 2 for every (x ;x )2R , and so represents re ection across the origin, whereas the matrix 1 2          0 1 x 0 1 x x 1 1 2 A = satis es A = = 1 0 x 1 0 x x 2 2 1 2 for every (x ;x )2R , and so represents re ection across the line x =x . We give a summary in the 1 2 1 2 table below: Transformation Equations Matrix   n y =x 1 1 1 0 Re ection across x -axis 1 y =x 2 2 0 1   n y =x 1 0 1 1 Re ection across x -axis 2 y =x 0 1 2 2   n y =x 1 0 1 1 Re ection across origin y =x 0 1 2 2   n y =x 1 2 0 1 Re ection across x =x 1 2 y =x 2 1 1 0 Chapter 2 : Matrices page 20 of 39

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.