Thus,A is obtained from A by letting row 1 of A be column 1 of 4',letting row 2 of A be column 2 of 47,and so on.For example, [14 if 4=斗 then A=25 36 Observe that ()T=4.Let B =[1 2];then BT= and 2 (BT=[12]=B As indicated by these two examples,for any matrix A,(4)T=A. Matrix Multiplication Given two matrices 4 and B,the matrix product of A and B(written AB)is defined if and only if Number of columns in 4=number of rows in B ) For the moment,assume that for some positive integer r,A has r columns and B has r rows.Then for some m and n,A is an m X r matrix and B is an r X n matrix. DEFINITION■ The matrix product C=AB of A and B is the m X n matrix C whose ijth element is determined as follows: ijth element of C scalar product of row i of A X column j of B(2) If Equation (1)is satisfied,then each row of A and each column of B will have the same number of elements.Also,if(1)is satisfied,then the scalar product in Equation(2) will be defined.The product matrix C=4B will have the same number of rows as 4 and the same number of columns as B. EXAMPLE 1 Matrix Multiplication Compute C=AB for [11 A= 「112] and 213 B=23 [12 Solution Because 4 is a 2 x 3 matrix and B is a 3 x 2 matrix,AB is defined,and C will be a 2 X 2 matrix.From Equation (2), [1 c11=[112] 2 1(1)+1(2)+2(1)=5 c12=[112]3 1(1)+1(3)+2(2)=8 2 [ c21=[213] 2=2(1)+1(2)+3(1)=7
Thus, AT is obtained from A by letting row 1 of A be column 1 of AT , letting row 2 of A be column 2 of AT , and so on. For example, if A , then AT Observe that (AT ) T A. Let B [1 2]; then BT and (BT ) T [1 2] B As indicated by these two examples, for any matrix A, (AT ) T A. Matrix Multiplication Given two matrices A and B, the matrix product of A and B (written AB) is defined if and only if Number of columns in A number of rows in B (1) For the moment, assume that for some positive integer r, A has r columns and B has r rows. Then for some m and n, A is an m r matrix and B is an r n matrix. DEFINITION ■ The matrix product C AB of A and B is the m n matrix C whose ijth element is determined as follows: ijth element of C scalar product of row i of A column j of B ■ (2) If Equation (1) is satisfied, then each row of A and each column of B will have the same number of elements. Also, if (1) is satisfied, then the scalar product in Equation (2) will be defined. The product matrix C AB will have the same number of rows as A and the same number of columns as B. Compute C AB for A and B Solution Because A is a 2 3 matrix and B is a 3 2 matrix, AB is defined, and C will be a 2 2 matrix. From Equation (2), c11 [1 1 2] 1(1) 1(2) 2(1) 5 c12 [1 1 2] 1(1) 1(3) 2(2) 8 c21 [2 1 3] 2(1) 1(2) 3(1) 7 1 2 1 1 3 2 1 2 1 1 3 2 1 2 1 2 3 1 1 1 2 1 2 4 5 6 1 2 3 3 6 2 5 1 4 16 CHAPTER 2 Basic Linear Algebra EXAMPLE 1 Matrix Multiplication
[ c22=[213] 3 =2(1)+1(3)+3(2)=11 2 C=AB 5 81 > 11 EXAMPLE 2 Column Vector Times Row Vector Find AB for A= [ and B=[12] Solution Because A has one column and B has one row,C=AB will exist.From Equation(2),we know that C is a 2 X 2 matrix with c11=3(1)=3 c21=4(1)=4 c12=3(2)=6 C22=4(2)=8 Thus, c- EXAMPLE 3 Row Vector Times Column Vector Compute D B4 for the A and B of Example 2. Solution In this case,D will be a 1 X 1 matrix (or a scalar).From Equation(2), d=1 T31 24=13)+244=11 Thus,D=[11].In this example,matrix multiplication is equivalent to scalar multiplica- tion of a row and column vector. Recall that if you multiply two real numbers a and b,then ab =ba.This is called the commutative property of multiplication.Examples 2 and 3 show that for matrix multipli- cation,it may be that 4B BA.Matrix multiplication is not necessarily commutative.(In some cases,however,AB =BA will hold.) EXAMPLE 4 Undefined Matrix Product Show that 4B is undefined if 4-6 [1 and B=01 12 Solution This follows because 4 has two columns and B has three rows.Thus,Equation(1)is not satisfied
c22 [2 1 3] 2(1) 1(3) 3(2) 11 C AB Find AB for A and B [1 2] Solution Because A has one column and B has one row, C AB will exist. From Equation (2), we know that C is a 2 2 matrix with c11 3(1) 3 c21 4(1) 4 c12 3(2) 6 c22 4(2) 8 Thus, C Compute D BA for the A and B of Example 2. Solution In this case, D will be a 1 1 matrix (or a scalar). From Equation (2), d11 [1 2] 1(3) 2(4) 11 Thus, D [11]. In this example, matrix multiplication is equivalent to scalar multiplication of a row and column vector. Recall that if you multiply two real numbers a and b, then ab ba. This is called the commutative property of multiplication. Examples 2 and 3 show that for matrix multiplication, it may be that AB BA. Matrix multiplication is not necessarily commutative. (In some cases, however, AB BA will hold.) Show that AB is undefined if A and B Solution This follows because A has two columns and B has three rows. Thus, Equation (1) is not satisfied. 1 1 2 1 0 1 2 4 1 3 3 4 6 8 3 4 3 4 8 11 5 7 1 3 2 2.1 Matrices and Vectors 17 EXAMPLE 3 Row Vector Times Column Vector EXAMPLE 4 Undefined Matrix Product EXAMPLE 2 Column Vector Times Row Vector
TABLE 1 Gallons of Crude Oil Requiredto Produce1 Gallon of Gasoline Crude Premium Regular Reqular Unleaded Unleaded Leaded 14 Many computations that commonly occur in operations research(and other branches of mathematics)can be concisely expressed by using matrix multiplication.To illustrate this,suppose an oil company manufactures three types of gasoline:premium unleaded, regular unleaded,and regular leaded.These gasolines are produced by mixing two types of crude oil:crude oil 1 and crude oil 2.The number of gallons of crude oil required to manufacture 1 gallon of gasoline is given in Table 1. From this information,we can find the amount of each type of crude oil needed to manufacture a given amount of gasoline.For example,if the company wants to produce 10 gallons of premium unleaded,6 gallons of regular unleaded,and 5 gallons of regular leaded,then the company's crude oil requirements would be Crude1 required=((10)+(f)(⑥)+（分5=12.75 gallons Crude 2 required =((10)+()(6)+()5 =8.25 gallons More generally,we define pu=gallons of premium unleaded produced ru gallons of regular unleaded produced rL=gallons of regular leaded produced cI=gallons of crude 1 required c2 gallons of crude 2 required Then the relationship between these variables may be expressed by c=(经)Pu+()ru+()rL c2=()Pu+(ru+(孕rz Using matrix multiplication,these relationships may be expressed by 3 21 Properties of Matrix Multiplication To close this section,we discuss some important properties of matrix multiplication.In what follows,we assume that all matrix products are defined. 1 Row i of 4B =(row i of A)B.To illustrate this property,let 「117 4-61 and B=23 L12 Then row 2 of the 2 X 2 matrix AB is equal to
Many computations that commonly occur in operations research (and other branches of mathematics) can be concisely expressed by using matrix multiplication.To illustrate this, suppose an oil company manufactures three types of gasoline: premium unleaded, regular unleaded, and regular leaded. These gasolines are produced by mixing two types of crude oil: crude oil 1 and crude oil 2. The number of gallons of crude oil required to manufacture 1 gallon of gasoline is given in Table 1. From this information, we can find the amount of each type of crude oil needed to manufacture a given amount of gasoline. For example, if the company wants to produce 10 gallons of premium unleaded, 6 gallons of regular unleaded, and 5 gallons of regular leaded, then the company’s crude oil requirements would be Crude 1 required ( 3 4 ) (10) ( 2 3 ) (6) ( 1 4 ) 5 12.75 gallons Crude 2 required ( 1 4 ) (10) ( 1 3 ) (6) ( 3 4 ) 5 8.25 gallons More generally, we define pU gallons of premium unleaded produced rU gallons of regular unleaded produced rL gallons of regular leaded produced c1 gallons of crude 1 required c2 gallons of crude 2 required Then the relationship between these variables may be expressed by c1 ( 3 4 ) pU ( 2 3 ) rU ( 1 4 ) rL c2 ( 1 4 ) pU ( 1 3 ) rU ( 3 4 ) rL Using matrix multiplication, these relationships may be expressed by Properties of Matrix Multiplication To close this section, we discuss some important properties of matrix multiplication. In what follows, we assume that all matrix products are defined. 1 Row i of AB (row i of A)B. To illustrate this property, let A and B Then row 2 of the 2 2 matrix AB is equal to 1 3 2 1 2 1 2 3 1 1 1 2 pU rU rL 1 4 3 4 2 3 1 3 3 4 1 4 c1 c2 18 CHAPTER 2 Basic Linear Algebra TAB LE 1 Gallons of Crude Oil Required to Produce 1 Gallon of Gasoline Crude Premium Regular Regular Oil Unleaded Unleaded Leaded 1 3 4 2 3 1 4 2 1 4 1 3 3 4
[11] [213]23=[711] 12 This answer agrees with Example 1. 2 Column j of AB A(column j of B).Thus,for A and B as given,the first column of AB is 1 1 3 21 [] Properties 1 and 2 are helpful when you need to compute only part of the matrix 4B. 3 Matrix multiplication is associative.That is,A(BC)=(4B)C.To illustrate,let A=[121, Then AB=[1013]and(AB)C=10(2)+13(1)=[33]. On the other hand, BC= 13 so A(BC)=1(7)+2(13)=[33].In this case,A(BC)=(4B)C does hold. 4 Matrix multiplication is distributive.That is,A(B C)=4B AC and(B+C)D BD+CD. Matrix Multiplication with Excel Using the Excel MMULT function,it is easy to multiply matrices.To illustrate,let's use Excel to find the matrix product AB that we found in Example 1 (see Figure 5 and file Mmult.xis Mmult.xls).We proceed as follows: Step 1 Enter A4 and B in D2:F3 and D5:E7,respectively. Step 2 Select the range(D9:E10)in which the product AB will be computed. Step 3 In the upper left-hand corner(D9)of the selected range,type the formula MMULT(D2:F3.D5:E7) Then hit Control Shift Enter (not just Enter),and the desired matrix product will be computed.Note that MMULT is an array function and not an ordinary spreadsheet func- tion.This explains why we must preselect the range for AB and use Control Shift Enter. A B 1 MatrixMultiplication 2 5 6 7 8 9 10 11 FIGURE 5 11
[2 1 3] [7 11] This answer agrees with Example 1. 2 Column j of AB A(column j of B). Thus, for A and B as given, the first column of AB is Properties 1 and 2 are helpful when you need to compute only part of the matrix AB. 3 Matrix multiplication is associative. That is, A(BC) (AB)C. To illustrate, let A [1 2], B , C Then AB [10 13] and (AB)C 10(2) 13(1) [33]. On the other hand, BC so A(BC) 1(7) 2(13) [33]. In this case, A(BC) (AB)C does hold. 4 Matrix multiplication is distributive. That is, A(B C) AB AC and (B C)D BD CD. Matrix Multiplication with Excel Using the Excel MMULT function, it is easy to multiply matrices. To illustrate, let’s use Excel to find the matrix product AB that we found in Example 1 (see Figure 5 and file Mmult.xls). We proceed as follows: Step 1 Enter A and B in D2:F3 and D5:E7, respectively. Step 2 Select the range (D9:E10) in which the product AB will be computed. Step 3 In the upper left-hand corner (D9) of the selected range, type the formula MMULT(D2:F3,D5:E7) Then hit Control Shift Enter (not just Enter), and the desired matrix product will be computed. Note that MMULT is an array function and not an ordinary spreadsheet function. This explains why we must preselect the range for AB and use Control Shift Enter. 7 13 2 1 3 5 2 4 5 7 1 2 1 2 3 1 1 1 2 1 3 2 1 2 1 2.1 Matrices and Vectors 19 1 2 3 4 5 6 7 8 9 10 11 ABCDEF MatrixMultiplication 112 A 213 B 11 2 3 1 2 5 8 C 7 11 FIGURE 5 Mmult.xls
PROBLEMS Group A Group B [1231 1 27 3 Prove that matrix multiplication is associative. 1 ForA=4 5 6 and B =0 -1.find: L789] L12 4 Show that for any two matrices A and B,(4B)T=BT A. a-A b 34 c A+2B 5 An n X n matrix A is symmetric if A =A. d T e B7 f AB a Show that for any n x n matrix,A4T is a symmet- ric matrix. g BA b Show that for any n x n matrix A,(A +A)is a 2 Only three brands of beer(beer 1,beer 2,and beer 3) symmetric matrix. are available for sale in Metropolis.From time to time, people try one or another of these brands.Suppose that at 6 Suppose that A and B are both n x n matrices.Show the beginning of each month,people change the beer they that computing the matrix product AB requires n are drinking according to the following rules: multiplications and n-n additions. 30%of the people who prefer beer 1 switch to beer 2. 7 The trace of a matrix is the sum of its diagonal 20%of the people who prefer beer 1 switch to beer 3. elements. 30%of the people who prefer beer 2 switch to beer 3. a For any two matrices A and B,show that trace 30%of the people who prefer beer 3 switch to beer 2. (A B)=trace A trace B. 10%of the people who prefer beer 3 switch to beer 1. b For any two matrices A and B for which the products AB and BA are defined,show that trace AB trace BA. For i=1,2,3,let x;be the number who prefer beer i at the beginning of this month and y:be the number who pre- fer beer i at the beginning of next month.Use matrix mul- tiplication to relate the following: [y [x1 2 x3」 2.2 Matrices and Systems of Linear Equations Consider a system of linear equations given by ax+a12x2+.+ainn =b1 a211+a22x2+…+a2mn=b2 3) amix1 am2x2+amnxn =bm In Equation (3),x1,x2,...,x are referred to as variables,or unknowns,and the ay's and bi's are constants.A set of equations such as (3)is called a linear system of m equa- tions in n variables. DEFINITION A solution to a linear system of m equations in n unknowns is a set of values for the unknowns that satisfies each of the system's m equations. To understand linear programming,we need to know a great deal about the properties of solutions to linear equation systems.With this in mind,we will devote much effort to studying such systems. We denote a possible solution to Equation (3)by an n-dimensional column vector x, in which the ith element of x is the value ofx,.The following example illustrates the con- cept of a solution to a linear system
2.2 Matrices and Systems of Linear Equations Consider a system of linear equations given by a11x1 a12x2 a1nxn b1 a21x1 a22x2 a2nxn b2 (3) am1x1 am2x2 amnxn bm In Equation (3), x1, x2, . . . , xn are referred to as variables, or unknowns, and the aij’s and bi’s are constants. A set of equations such as (3) is called a linear system of m equations in n variables. DEFINITION ■ A solution to a linear system of m equations in n unknowns is a set of values for the unknowns that satisfies each of the system’s m equations. ■ To understand linear programming, we need to know a great deal about the properties of solutions to linear equation systems. With this in mind, we will devote much effort to studying such systems. We denote a possible solution to Equation (3) by an n-dimensional column vector x, in which the ith element of x is the value of xi. The following example illustrates the concept of a solution to a linear system. 20 CHAPTER 2 Basic Linear Algebra 1 For A and B , find: a A b 3A c A 2B d AT e BT f AB g BA 2 Only three brands of beer (beer 1, beer 2, and beer 3) are available for sale in Metropolis. From time to time, people try one or another of these brands. Suppose that at the beginning of each month, people change the beer they are drinking according to the following rules: 30% of the people who prefer beer 1 switch to beer 2. 20% of the people who prefer beer 1 switch to beer 3. 30% of the people who prefer beer 2 switch to beer 3. 30% of the people who prefer beer 3 switch to beer 2. 10% of the people who prefer beer 3 switch to beer 1. For i 1, 2, 3, let xi be the number who prefer beer i at the beginning of this month and yi be the number who prefer beer i at the beginning of next month. Use matrix multiplication to relate the following: x1 x2 x3 y1 y2 y3 2 1 2 1 0 1 3 6 9 2 5 8 1 4 7 PROBLEMS Group A Group B 3 Prove that matrix multiplication is associative. 4 Show that for any two matrices A and B, (AB) T BT AT . 5 An n n matrix A is symmetric if A AT . a Show that for any n n matrix, AAT is a symmetric matrix. b Show that for any n n matrix A, (A AT ) is a symmetric matrix. 6 Suppose that A and B are both n n matrices. Show that computing the matrix product AB requires n3 multiplications and n3 n2 additions. 7 The trace of a matrix is the sum of its diagonal elements. a For any two matrices A and B, show that trace (A B) trace A trace B. b For any two matrices A and B for which the products AB and BA are defined, show that trace AB trace BA.