chapter 5 INTRODUCTION TO MATRIX ALGEBRA GOALS The purpose of this chapter is to introduce you to matrix algebra, which has many applications. You are already familiar with several algebras: elementary algebra, the algebra of logic, the algebra of sets. We hope that as you studied the algebra of logic and the algebra of sets, you compared them with elementary algebra and noted that the basic laws of each are similar. We will see that matrix algebra is also similar. As in previous discussions, we begin by defining the objects in question and the basic operations. 5.1 Basic Definitions Definition: Matrix. A matrix is a rectangular array of elements of the form A = a11 a21 a31 am1 a12 a22 a32 am2 a13 a23 a33 am3 a1 n a2 n a3 n amn A convenient way of describing a matrix in general is to designate each entry via its position in the array. That is, the entry a34 is the entry in the third row and fourth column of the matrix A. Depending on the situation, we will decide in advance to which set the entries in a matrix will belong. For example, we might assume that each entry aij (1 i m, 1 j n) is a real number. In that case we would use Mmn HRL to stand for the set of all m by n matrices whose entries are real numbers. If we decide that the entries in a matrix must come from a set S, we use Mmn HSL to denote all such matrices. Definition: Order of a Matrix. The matrix A that has m rows and n columns is called an m n (read "m by n") matrix, and is said to have order m n. Since it is rather cumbersome to write out the large rectangular array above each time we wish to discuss the generalized form of a matrix, it is common practice to replace the above by A = Aaij E. In general, matrices are often given names that are capital letters and the corresponding lower case letter is used for individual entries. For example the entry in the third row, second column of a matrix called C would be c32 . Example 5.1.1. 2 3 A =K O,B = 0 -5 0 1 2 5 6 -2 3 , and D = 2 4 2 8 15 1 are 2 2, 3 1, and 3 3 matrices, respectively Since we now understand what a matrix looks like, we are in a position to investigate the operations of matrix algebra for which users have found the most applications. Example 5.1.2. First we ask ourselves: Is the matrix A = K the matrix B = K 1 2 O equal to 3 4 1 2 O? No, they are not because the corresponding entries in the second row, second column of the two matrices are not 3 5 1 2 3 1 2 equal. Next, is A = K O equal to B = K O? No, although the corresponding entries in the first two columns are identical, B doesn't 4 5 6 4 5 Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution-Noncommercial-ShareAlike 3.0 United States License. Chapter 5 - Matrix Algebra have a third column to compart to that of A. We formalize these observations in the following definition. Definition; Equality of Matrices. A matrix A is said to be equal to matrix B (written A = B) if and only if: (1) A and B have the same order, and (2) all corresponding entries are equal: that is, aij = bij for all appropriate i and j. 5.2 Addition and Scalar Multiplication Example 5.2.1. Concerning addition, it seems natural that if A =K 1 0 3 4 1+3 0+4 4 4 O and B = K O , then A + B = K O=K O. 2 -1 2 - 5 -1 + 2 -5 2 -3 1 However, if A = K 1 2 3 3 0 O and B = K O, can we find A + B? No, the orders of the two matrices must be identical. 0 1 2 2 8 Definition: Matrix Addition. Let A and B be m n matrices. Then A + B is an m n matrix where HA + BLij = aij + bij (read "the ith jth entry of the matrix A + B is obtained by adding the ith jth entry of A to the ith jth entry of B"). If the orders of A and B are not identical, A + B is not defined. It should be clear from Example 5.2.1 and the definition of addition that A + B is defined if and only if A and B are of the same order. Another frequently used operation is that of multiplying a matrix by a number, commonly called a scalar in this context. Scalars normally come from the same set as the entries in a matrix. For example, if A Mmn HRL, a scalar can be any real number. Example 5.2.2. If c = 3 and if A = K 3A =K 1 -2 O and we wish to find c A, it seems natural to multiply each entry of A by 3 so that 3 5 3 -6 O , and this is precisely the way scalar multiplication is defined. 9 15 Definition: Scalar Multiplication. Let A be an m n matrix and c a scalar. Then c A is the m n matrix obtained by multiplying c times each entry of A; that is HcALij = c aij . 5.3 Multiplication of Matrices - For a video introduction to this section, go to http://faculty.uml.edu/klevasseur/ads2/videos/matrixmultiplication/ A definition that is more awkward to motivate (and we will not attempt to do so here) is the product of two matrices. In time, the reader will see that the following definition of the product of matrices will be very useful, and will provide an algebraic system that is quite similar to elementary algebra. Definition: Matrix Multiplication. Let A be an m n matrix and let B be an n p matrix. The product of A and B, denoted by AB, is an m p matrix whose ith row jth column entry is HA BLi j = ai 1 b1 j + ai 2 b2 j + + ai n bn j = \u0007 ai k bk j n k= 1 for 1 i m and 1 j p. The mechanics of computing one entry in the product of two matrices is illustrated in Figure 5.3.1. Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution-Noncommercial-ShareAlike 3.0 United States License. Chapter 5 - Matrix Algebra Figure 5.3.1 Computation of one entry in the product of two 3 by 3 matrices The computation of a product can take a considerable amount of time in comparison to the time required to add two matrices. Suppose that A and B are n n matrices; then HABLij is determined performing n multiplications and n - 1 additions. The full product takes n3 multiplications and n3 n2 additions. This compares with n2 additions for the sum of two n n matrices. The product of two 10 by 10 matrices will require 1,000 multiplications and 900 additions, clearly a job that you would assign to a computer. The sum of two matrices requires a more modest 100 additions. This analysis is based on the assumption that matrix multiplication will be done using the formula that is given in the definition. There are more advanced methods that, in theory, reduce operation counts. For example, Strassen's algorithm (http://mathworld.wolfram.com/StrassenFormulas.html) computes the product of two n by n matrices in 7 7log2 n - 6 4log2 n 7 n2.808 operations. There are practical issues involved in actually using the algorithm in many situations. For example, round-off error can be more of a problem than with the standard formula. Example 5.3.1. Let A = AB = Remarks: 1 0 6 3 2 , a 3 2 matrix, an let B = K O, a 2 1 matrix. Then A B is a 3 1 matrix: 1 -5 1 1 0 6 3 2 K O = 1 -5 1 16 + 01 21 + 3 6 -5 6 + 1 1 = 6 20 -29 (1) The product A B is defined only if A is an m n matrix and B is an n p matrix; that is, the two "inner" numbers must be the equal. Furthermore, the order of the product matrix A B is the "outer" numbers, in this case m p. (2) It is wise to first determine the order of a product matrix. For example, if A is a 3 2 matrix and B is a 2 2 matrix, then A B is a 3 2 matrix of the form c11 c12 A B = c21 c22 c31 c32 Then to obtain, for example, C31 , we multiply corresponding entries in the third row of A times the first column of B and add the results. Example 5.3.2. Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution-Noncommercial-ShareAlike 3.0 United States License. Chapter 5 - Matrix Algebra Let A = K 1 0 3 0 O, and B = K O . Then 0 3 2 1 AB =K Note: B A = K Remarks; 13 + 02 10 + 01 3 0 O= K O 03 + 32 00 + 31 6 3 3 0 O A B 2 3 (1) An n n matrix is called a square matrix. (2) If A is a square matrix, A A is defined and is denoted by A2 , and A A A = A3 , etc. (3) The m n matrices whose entries are all 0 are denoted by 0mn , or simply 0, when no confusion arises regarding the order. EXERCISES FOR SECTIONS 5.1 THROUGH 5.3 A Exercises 1. Let A = K 1 -1 0 1 0 1 -1 O, B = K O , and C = K O 2 3 3 -5 3 -2 2 (a) Compute A B and B A. (b) Compute A + B and B + A. (c) If c = 3, show that cHA + BL = c A + c B. (d) Show that HA BL C = A HB CL. (e) Compute A2 C. (f) Compute B + 0 (g) Compute A 022 and 022 A, where 022 is the 2 2 zero matrix, (h) Compute 0 A, where 0 is the real number (scalar) zero. (i) Let c = 2 and d = 3. Show that Hc + dL A = c A + d A. 2. Let A = 1 0 2 2 -1 5 3 2 1 Compute, if possible; ,B = 0 2 3 2 1 2 3 1 1 2 , and C = 4 0 1 1 -1 3 -2 3 -1 4 1 (a) A - B (b) A B (c) A C - B C (d) A HB CL (e) C A - C B x y (f) C z w 3. Let A = K 2 0 1 0 O . Find a matrix B such that A B = I and B A = I, where I = K O 0 3 0 1 4. Find A I and B I where I is as in Exercise 3, where A = K 1 8 -2 3 O and B = K O. 9 5 5 -7 What do you notice? Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution-Noncommercial-ShareAlike 3.0 United States License. Chapter 5 - Matrix Algebra 1 0 0 5. Find A3 if A = 0 2 0 0 0 3 . What is A15 equal to? B Exercises 6. (a) Determine I 2 and I 3 if I = 1 0 0 0 1 0 . 0 0 1 (b) What is I n equal to for any n 1? (c) Prove your answer to part (b) by induction. 7. (a) If A = K x1 2 1 3 O, X = K O, and B = K O , show that A X = B is a way of expressing the system x2 1 -1 1 (b) Express the following systems of equations using matrices: 2 x1 + x2 = 3 using matrices. x1 - x2 = 1 (i) 2 x1 - x2 = 4 x1 + x2 = 0 (ii) x1 + x2 + 2 x3 = 1 x1 + 2 x2 - x3 = -1 x1 + 3 x 2 + x 3 = 5 (iii) x1 + x2 = 3 x2 = 5 x1 + 3 x3 = 6 Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution-Noncommercial-ShareAlike 3.0 United States License. Chapter 5 - Matrix Algebra 5.4 Special Types of Matrices We have already investigated one special type of matrix, namely the zero matrix, and found that it behaves in matrix algebra in an analogous fashion to the real number 0; that is, as the additive identity. We will now investigate the properties of a few other special matrices. Definition: Diagonal Matrix. A square matrix D is called a diagonal matrix if dij = 0 whenever i j. Example 5.4.1. A = 1 0 0 0 2 0 , B= 0 0 5 3 0 0 0 0 0 , and I = 0 0 -5 1 0 0 0 1 0 0 0 1 are all diagonal matrices. In Example 5.4.1, the 3 3 diagonal matrix I whose diagonal entries are all 1's has the singular property that for any other 3 3 matrix A we have A I = I A = A. For example: Example 5.4.2. If A = 1 2 5 6 7 -2 , then 3 -3 0 1 2 5 A I = 6 7 -2 3 -3 0 IA = and 1 2 5 6 7 -2 . 3 -3 0 In other words, the matrix I behaves in matrix algebra like the real number 1; that is, as a multiplicative identity. In matrix algebra the matrix I is called simply the identity matrix. Convince yourself that if A is any n n matrix A I = I A = A. Definition: Identity Matrix. The n n diagonal matrix whose diagonal components are all 1's is called the identity matrix and is denoted by I or In . In the set of real numbers we realize that, given a nonzero real number x, there exists a real number y such that x y = y x = 1. We know that real numbers commute under multiplication so that the two equations can be summarized as x y = 1. Further we know that y = x-1 = 1 . Do we have an analogous situation in Mnn HRL? Can we define the multiplicative inverse of an n n matrix A? It seems natural to imitate the definition of multiplicative inverse in the real numbers. Definition: Matrix Inverse. Let A be an n n matrix. If there exists an n n matrix B such that A B = B A = I, then B is the multiplicative inverse of A (called simply the inverse of A) and is denoted by A-1 (read "A inverse"). x When we are doing computations involving matrices, it would be helpful to know that when we find A-1 , the answer we obtain is the only inverse of the given matrix. Remark: Those unfamiliar with the laws of matrices should go over the proof of Theorem 5.4.1 after they have familiarized themselves with the Laws of Matrix Algebra in Section 5.5. Theorem 5.4.1. The inverse of an n n matrix A, when it exists, is unique. Proof: Let A be an n n matrix. Assume to the contrary, that A has two (different) inverses, say B and C. Then B = BI = B HA C L = HB AL C = IC = C Identity property of I Assumption that C is an inverse of A Associativity of matrix multiplication Assumption that B is an inverse of A Identity property of I 2 0 Example 5.4.3. Let A = K O. 0 3 What is A -1 ? Without too much difficulty, by trial and error, we determine that A -1 = 1 0 0 1 2 3 . This might lead us to guess that the inverse is found by taking the reciprocal of all nonzero entries of a matrix. Alas, it isn't that easy! A =K 1 2 O , the "reciprocal rule" would tell us that the inverse of A is B = -3 5 1 -1 3 1 2 1 If . Try computing A B and you will see that you don't get 5 the identity matrix. So, what is A-1 ? In order to understand more completely the notion of the inverse of a matrix, it would be beneficial to have a formula that would enable us to compute the inverse of at least a 2 2 matrix. To do this, we need to recall the definition of the determinant of a 2 2 matrix. Appendix A gives a more complete description of the determinant of a 2 2 and higher-order matrices. Definition: Determinant of a 2 2 Matrix. Let A = K a b O. The determinant of A is the number det A = a d - b c. c d Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution-Noncommercial-ShareAlike 3.0 United States License. Chapter 5 - Matrix Algebra In addition to det A, common notation for the determinant of matrix A is A . This is particularly common when writing out the whole matrix, a b which case we would write for the determinant of the general 2 2 matrix. c d Example 5.4.4. If A = K If B = K 1 2 O then det A = 1 5 - 2 H-3L = 11. -3 5 1 2 O then det B = 1 4 - 2 2 = 0 2 4 Theorem 5.4.2. Let A = K a b O. If det A 0, then A-1 = c d Proof: See Exercise 4 at the end of this section. 1 det A K d -b O -c a Example 5.4.5. Can we find the inverses of the matrices in Example 5.4.4? 1 2 If A = K O then A-1 = -3 5 1 11 5 -2 K O= 3 1 5 11 3 11 - 2 11 1 11 The reader should verify that A A-1 = A-1 A = I. The second matrix, B has a determinant equal to zero. We we tried to apply the formula in Theorem 5.4.2, we would be dividing by zero. For this reason, the formula can't be applied and in fact B-1 does not exist. Remarks: (1) In general, if A is a 2 2 matrix and if det A = 0, then A-1 does not exist. (2) A formula for the inverse of n n matrices n 3 can be derived that also involves det A, Hence, in general, if the determinant of a matrix is zero, the matrix does not have an inverse. However the formula for even a 3 3 matrix is very long and is not the most efficient way to compute the inverse of a matrix. (3) In Chapter 12 we will develop a technique to compute the inverse of a higher-order matrix, if it exists. (4) Matrix inversion comes first in the hierarchy of matrix operations; therefore, A B-1 is AHB-1 L. EXERCISES FOR SECTION 5.4 A Exercises 1. For the given matrices A find A-1 if it exists and verify that A A-1 = A-1 A = I If A-1 does not exist explain why. (a) A = K (b) A = K 1 3 O 2 1 6 -3 O 8 -4 (c) A = K (d) A = K 1 -3 O 0 1 1 0 O 0 1 (e) Use the definition of the inverse of a matrix to find A-1 : 3 0 A= 0 1 2 0 0 0 0 -5 2. For the given matrices A find A-1 if it exists and verify that A A-1 = A-1 A = I If A-1 does not exist explain why. (a) A = K 2 -1 O -1 2 (b) A = K 0 1 O 0 2 Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution-Noncommercial-ShareAlike 3.0 United States License. Chapter 5 - Matrix Algebra (c) A = K (d) A = K 1 c O 0 1 a b O, were a > b > 0. b a 3. (a) Let A = K 2 3 3 -3 O and B = K O. Verify that HA BL-1 = B-1 A-1 . 1 4 2 1 (b) Let A and B be n n invertible matrices. Prove that HA BL-1 = B-1 A-1 . Why is the right side of the above statement written "backwards"? Is this necessary? Hint: Use Theorem 5.4.1. B Exercises 4. Let Let A = K a b O. Derive the formula for A-1 . c d 5. (a) Let A and B be as in problem 3 above. Show that detHA BL = Hdet AL Hdet BL. (b) It can be shown that the statement in part (a) is true for all n n matrices. Let A be any invertible n n matrix. Prove that detHA-1 L = Hdet AL-1 . Note: The determinant of the identity matrix In is 1 for all n, see Appendix A for details. (c) Verify that the equation in part (b) is true for the matrix in exercise l(a) of this section. 6. Prove by induction that for n 1, K a 0 n an 0 O = K O. 0 b 0 bn 7. Use the assumptions in exercise 5 to prove by induction that if n 1, detHAn L = Hdet ALn . 8. Prove: If the determinant of a matrix A is zero, then A does not have an inverse. Hint: Use the indirect method of proof and exercise 5. C Exercise 9. (a) Let A, B, and D be n n matrices. Assume that B is invertible. If A = B D B-1 , prove by induction that Am = B Dm B-1 is true for m 1. (b) Given that A = K -8 15 1 0 5 3 O B-1 where B = K O what is A10 ? O = BK 0 2 3 2 -6 11 Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution-Noncommercial-ShareAlike 3.0 United States License. Chapter 5 - Matrix Algebra 5.5 Laws of Matrix Algebra The following is a summary of the basic laws of matrix operations. Assume that the indicated operations are defined; that is, that the orders of the matrices A, B, and C are such that the operations make sense. (1) A + B = B + A (2) A + HB + CL = HA + BL + C (3) c HA + BL = c A + c B, where c R. (4) Hc1 + c2 L A = c1 A + c2 A, where c1 , c2 R. (5) c1 Hc2 AL = Hc1 c2 L A, where c1 , c2 R. (6) 0 A = 0, where 0 is the zero matrix. (7) 0 A = 0, where 0 on the left is the number 0. (8) A + 0 = A. (9) A + H-1L A = 0. (10) A HB + CL = A B + A C. (11) HB + CL A = B A + C A. (12) AHB CL = HA BL C. (13) I A = A and A I = A. (14) If A-1 exists, HA-1 L-1 = A. (15) If A-1 and B-1 exist, HA BL-1 = B-1 A-1 Example 5.5.1. If we wished to write out each of the above laws more completely, we would specify the orders of the matrices. For example, Law 10 should read: (10) Let A, B, and C be m n, n p, and n p matrices, respectively, then A HB + CL = A B + A C Remarks: (1) Notice the absence of the "law" A B = B A. Why? (2) Is it really necessary to have both a right (No. 11) and a left (No. 10) distributive law? Why? (3) What does Law 8 define? What does Law 9 define? EXERCISES FOR SECTION 5.5 A Exercises 1. Rewrite the above laws specifying as in Example 5.5.1 the orders of the matrices. 2. Verify each of the Laws of Matrix Algebra using examples. 3. Let A = K 1 2 3 7 6 0 -2 4 O, B = K O, and C = K O. Compute the following as efficiently as possible by using any of the Laws of 0 -1 2 -1 5 7 1 1 Matrix Algebra: (a) A B + A C (b) A-1 (c) A HB + CL Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution-Noncommercial-ShareAlike 3.0 United States License. Chapter 5 - Matrix Algebra (d) HA2 L-1 (e) HC + BL-1 A-1 4. Let A = K (a) A B 7 4 3 5 O and B = K O. Compute the following as efficiently as possible by using any of the Laws of Matrix Algebra: 2 1 2 4 (b) A + B (c) A2 + A B + B A + B 2 (d) B-1 A-1 (e) A2 + A B 5. Let A and B be n n matrices of real numbers. Is A2 - B2 = HA - BL HA + BL ? Explain Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution-Noncommercial-ShareAlike 3.0 United States License. Chapter 5 - Matrix Algebra 5.6 Matrix Oddities We have seen that matrix algebra is similar in many ways to elementary algebra. Indeed, if we want to solve the matrix equation A X = B for the unknown X, we imitate the procedure used in elementary algebra for solving the equation a x = b. Notice how exactly the same properties are used in the following detailed solutions of both equations. Solution of a x = b ax = b a-1 Ha xL = a-1 b Ha-1 aL x = a-1 b Solution of A X = B AX = B if a 0 A-1 HA XL = A-1 B if A-1 exists associative law HA-1 AL X = A-1 B 1 x = a-1 b definition of inverse I X = A-1 B definition of inverse x = a-1 b identity property of 1 X = A-1 B identity property of I associative law Certainly the solution process for A X = B is the same as that of a x = b. b The solution of x a = b is x = b a-1 = a-1 b. In fact, we usually write the solution of both equations as x = . In matrix algebra, the solution of a X A = B is X = B A-1 , which is not necessarily equal to A-1 B. So in matrix algebra, since the commutative law (under multiplication) is not true, we have to be more careful in the methods we use to solve equations. B It is clear from the above that if we wrote the solution of A X = B as X = , we would not know how to interpret the answer A-1 B or B A-1 ? Because of this, A-1 is never written as 1 A . A B A . Does it mean Some of the main dissimilarities between matrix algebra and elementary algebra are that in matrix algebra: (1) A B may be different from B A. (2) There exist matrices A and B such that A B = 0, and yet A 0 and B 0. (3) There exist matrices A where A 0, and yet A2 = 0. (4) There exist matrices A where A2 - A with A I and A 0 (5) There exist matrices A where A2 = I , where A I and A -I EXERCISES FOR SECTION 5.6 A Exercises 1. Discuss each of the above "oddities" with respect to elementary algebra. 2. Determine 2 2 matrices which show each of the above "oddities" are true. B Exercises 3. Prove the following implications, if possible: (a) A2 = A and det A 0 \u000e A = I (b) A2 = I and det A 0 \u000e A = I or A = -I. 4. Let Mnn HRL be the set of real n n matrices. Let P Mnn HRL be the subset of matrices defined by A P if and only if A2 = A. Let Q P be defined by A Q if and only if det A 0. (a) Determine the cardinality of Q. (b) Consider the special case n = 2 and prove that a sufficient condition for A P M22 HRL is that A has a zero determinant (i.e., A is singular) and tr HAL = 1 where tr HAL = a11 + a 22 is the sum of the main diagonal elements of A. (c) Is the condition of part b a necessary condition? Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution-Noncommercial-ShareAlike 3.0 United States License. Chapter 5 - Matrix Algebra C Exercises 5. Write each of the following systems in the form A X = B, and then solve the systems using matrices. (a) 2 x1 + x2 = 3 x1 - x2 = 1 (b) 2 x1 - x2 = 4 x1 - x2 = 0 (c) 2 x1 + x2 = 1 x1 - x2 = 1 (d) 2 x1 + x2 = 1 x1 - x2 = -1 (e) 3 x1 + 2 x2 = 1 6 x1 + 4 x2 = -1 6. Recall that p HxL = x2 - 5 x + 6 is called a polynomial, or more specifically, a polynomial over R, where the coefficients are elements of R and x R. Also, think of the method of solving, and solutions of, x2 - 5 x + 6 = 0. We would like to define the analogous situation for 2 2 matrices. First define where A is a 2 2 matrix p HAL = A2 - 5 A + 6 I. Discuss the method of solving and the solutions of A2 - 5 A + 6 I = 0. 7. (For those who know calculus) (a) Write the series expansion for a centered around a = 0. (b) Use the idea of exercise 6 to write what would be a plausible definion of A where A is an n n matrix. (c) If A = K 1 1 0 -1 -1 O and B = K O , use the series in part (b) to show that A = K O 0 0 0 0 0 1 and B = K 1 -1 O. 0 1 (d) Show that A B B A (e) Show that A+B = K 0 O 0 1 (f) Is A B = A+B ? Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution-Noncommercial-ShareAlike 3.0 United States License