首页 ELEMENTARY MATRIX ALGEBRA

ELEMENTARY MATRIX ALGEBRA

举报
开通vip

ELEMENTARY MATRIX ALGEBRA 1 1 MATH CHAPTER 2: ELEMENTARY MATRIX ALGEBRA W. Erwin Diewert Reference: G. Hadley: Linear Algebra, Addision-Wesley, 1961. 1. The Algebra of Vectors and Matrices Definition: An N vector is a column of N numbers, e.g. x = 1 3 5 È Î Í ˘ ˚...

ELEMENTARY MATRIX ALGEBRA
1 1 MATH CHAPTER 2: ELEMENTARY MATRIX ALGEBRA W. Erwin Diewert Reference: G. Hadley: Linear Algebra, Addision-Wesley, 1961. 1. The Algebra of Vectors and Matrices Definition: An N vector is a column of N numbers, e.g. x = 1 3 5 È Î Í ˘ ˚ ˙ is a 3 dimensional vector. Geometrically speaking, with each vector x, we can associate a point in N dimensional space; the ith component of the vector x corresponds to the distance along the ith coordinate axis from the point x to the origin 0 = 0 0 :. 0 È Î Í Í ˘ ˚ ˙ ˙ e.g. x = 1 3 5 È Î Í ˘ ˚ ˙ = x1 x2 x3 È Î Í ˘ ˚ ˙ x3 x 5 3 1 x1 x2 Definition: An M x N matrix A is a rectangular array of numbers with M rows and N columns. e.g. 2 2 A = a11 a12 . . . a1N a21 a22 . . . a2N :. :. :. aM1 aM2 aMN È Î Í Í Í ˘ ˚ ˙ ˙ ˙ where aij is a number for i = 1, 2, . . ., M (row index) and j = 1, 2, . . ., N (column index) Note that a vector can now be defined to be a matrix with only 1 column. There are various operations which we can perform on matrices (and vectors): Definition of Matrix Addition: If A and B are two M by N matrices, then A + B ≡ a11 + b11, a12 + b12 , . . ., a1N + b1N :. aM1 + bM1, aM2 + bM2 , . . ., aMN + bMN È Î Í Í ˘ ˚ ˙ ˙ i.e., we simply add the corresponding components of the two matrices. A = 1 2 45 6 8 È Î ˘ ˚ B = 0 1 01 0 1 È Î ˘ ˚ then A + B = 1 3 46 6 9 È Î ˘ ˚ e.g. A = 10 È Î ˘ ˚ , B = 11 È Î ˘ ˚ , A + B = 21 È Î ˘ ˚ Definition of Scalar Multiplication: If A is an M by N matrix and l is a scalar (i.e., a number), then lA ≡ la11, la12, . . . ,la1N :. laM1, laM2 , . . . ,laMN È Î Í Í ˘ ˚ ˙ ˙ e.g. l = 2, A = 10 È Î ˘ ˚ , lA = 20 È Î ˘ ˚ Definition of Matrix Multiplication: If A is an M by N matrix and B is an N by K matrix (note that the number of columns in A is equal to the number of rows in B), then 3 3 AB = a11 . . . a1N :. aM1 . . . aMN È Î Í Í ˘ ˚ ˙ ˙ b11 . . . b1K :. :. bN1 . . . bMK È Î Í Í ˘ ˚ ˙ ˙ ≡ c11 . . . c1K :. :. cM1 cMK È Î Í Í ˘ ˚ ˙ ˙ where cmk ≡ amn n=1 N Â bn k Thus we end up with M by K matrix. e.g. ˙ ˚ ˘ Í Î È ++ ++ = ˙ ˙ ˙ ˚ ˘ Í Í Í Î È =˙ ˚ ˘ Í Î È = 321 321 3 2 1 865 421 , 865 421 xxx xxx AB x x x BA We can now begin to see why matrix algebra is useful in the study of systems of simultaneous linear equations. For example suppose we were given the following system of M equations in the N unknowns x1, x2, . . ., xN: a11x1 + a12x2 + . . . . + a1N xN = b1 a21x1 + a22x2 + . . . . + a2N xN = b2 :. aM1x1 + aM2x2 + . . . . + aMN xN = bM (The aij's and the bM's are given fixed numbers). The above system of equations can be written much more compactly using matrix notation as Ax = b where A = a11 . . . a1N :. aM1 . . . aMN È Î Í Í ˘ ˚ ˙ ˙ , x = x1 :. xN È Î Í Í ˘ ˚ ˙ ˙ , b = b1 :. bM È Î Í Í ˘ ˚ ˙ ˙ We are implicitly making use of another definition in the above representation Ax = b: Definition of Matrix Equality: Two M by N matrices A, B are equal (written A = B), if and only if the corresponding components of A and B are equal, i.e., if we have aij = bij for i = 1, . . ., M j = 1, . . . , N. 4 4 There are a few more definitions which will be useful in what follows. Definition: An M by N matrix A is square is M = N: i.e., if the number of rows = number of columns. (Typically in the system of simultaneous linear equations Ax = b, we have A square; i.e., the number of equations = the number of unknowns). Definition: The N by N identity matrix IN (or I for short) is the following matrix: IN ≡ 1 0 0 . . . 0 0 1 0 . . . 0 0 0 1 . . . 0 :. . . . 0 0 0 . . . 1 È Î Í Í Í ˘ ˚ ˙ ˙ ˙ ¸ ˝ Ô Ô ˛ Ô Ô N rows with zeros everywhere except on the main diagonal Definition of the Transpose of a Matrix: Let A = a11a12 . . . a1N :. aM1aM2 . . . aMN È Î Í Í ˘ ˚ ˙ ˙ . Then AT = a11 . . . aM1 a12 . . . aM1 :. :. a1N . . . aMN È Î Í Í Í ˘ ˚ ˙ ˙ ˙ i.e., the rows and columns of A have been interchanged. In order to acquire some facility in working with matrices, students are required to do the following problems. Problem 1: Let I = 1 00 1 È Î ˘ ˚ , A = 1 23 4 È Î ˘ ˚ , B = 0 11 0 È Î ˘ ˚ , C = -2 00 2 È Î ˘ ˚ (i) Calculate AB + 5I - 1C (ii) Show IA = AI = A (iii) Show that (AB)T = BT AT (iv) Does AB = BA? (v) (AB)C = A(BC)? 5 5 Problem 2: (More difficult). Let A = a11 . . . a1N :. aM1 . . . aMN È Î Í Í ˘ ˚ ˙ ˙ be an M by N matrix B = b11 . . . b1K :. :. bN1 . . . bNK È Î Í Í ˘ ˚ ˙ ˙ be an N by K matrix, and C = c11 . . . cIL :. :. cK1 . . . cKL È Î Í Í ˘ ˚ ˙ ˙ be a K by L matrix. Show that (AB)C = A(BC). Hint: Take the ijth element of (AB)C (which is equal to ainbn1, ainbn2, . . ., ainbnK n=1 N Â n=1 N Â n=1 N Â È Î Í ˘ ˚ ˙ . c1j c2j :. cKj È Î Í Í Í ˘ ˚ ˙ ˙ ˙ and show that it is equal to the ijth element of A(BC). Definition: Let A be a square N by N matrix. Then we say that an N by N B matrix is a (left) inverse of A if BA = IN An N by N matrix C is a (right) inverse of A if AC = IN. There are two points to note about the last definition: (i) the definition says nothing about whether a left or right inverse for A will in fact exist (they don't always as we shall see ) and (ii) we are forced at this stage to consider both left and right inverse as separate entities (if they exist) since problem 1 (iv) shows that it is not always the case that AB = BA. Now if we consider our system of simultaneous linear equations Ax = b (where A is square), it is clear that if we knew what a left inverse for A was (call it B assuming one exists), then if we premultiply both sides of the matrix equation Ax = b by B, we obtain: BAx = Bb or Ix = Bb or x = Bb (recall Problem 1 (ii)) 6 6 and thus we have a solution to the system of equations Ax = b, namely x* = Bb where B is a left inverse for A. Thus we are interested in two questions: (i) when will a left inverse for a square matrix A exist? (ii) how can we compute it if it exists? It turns out that the notion of a determinant is useful in answering both questions. 2. Determinants and their Properties We must first make some preliminary definitions before we define the determinant of an arbitrary square N by N matrix A. Definition: A transposition of the integers (i1, i2, . . ., iN) is a simple interchange of 2 of the numbers. e.g. (3, 2, 1) is a transposition of (3, 1, 2) Definition: A permutation of the integers (1, 2, . . ., N), say (i1, i2, . . ., iN) is an even permutation if it is obtained from (1, 2, . . ., N) by an even number of transpositions . . . is an odd permutation if it can be obtained from (1, 2, . . ., N) by an odd number of transpositions. e.g. (4, 1, 3, 2) is it an even or odd permutation? What we do is we start with (1, 2, 3, 4) and build towards (4, 1, 3, 2) by making a sequence of transpositions, filling in the appropriate elements starting at the left and working towards the right. (1, 2, 3, 4) (4, 2, 3, 1) First transposition, first component is 4 now (4, 1, 3, 2) Second transposition, second component is 1 now. No further transpositions are required so as it took only 2 transpositions from (1, 2, 3, 4) to attain (4, 1, 3, 2), thus the permutation is even. Definition: e(i1, i2, . . ., iN) ≡ 1 if the permutation (i1, i2, . . ., iN ) is even -1 if the permutation (i1,i2 , . . ., iN ) is odd Ï Ì Ó where (i1, i2, . . ., iN) is some permutation of the integers (1, 2, . . ., N). Definition: The determinant of an (N by N) square matrix A is defined as: Det A or |A| ≡ S e(i1, i2, . . ., iN) a1i1a2i2 . . . aNiN over all permutations (i1, i2, . . ., iN) E.g. A = a11 a12a21 a22 È Î ˘ ˚ ; |A| = e(1, 2) a11a22 + e(2, 1)a12a21 7 7 = + a11a22 - a12a21 As there are only 2! = 2 permutations of 2 numbers, a 2 by 2 matrix has a determinant with only 2 terms E.g. A = a11 a12 a13 a21 a22 a23 a31 a32 a33 È Î Í ˘ ˚ ˙ ; |A|= e(1, 2, 3)a11a22a33 (+) + e(2,1, 3)a12a21a33 (-) + e(3,2,1)a13a22a31 (-) + e(1,3, 2)a11a23a32 (-) + e(2,3,1)a12a23a31 (+) + e(3,1, 2)a13a21a32 (+) Thus a determinant is a mapping from an N by N array of numbers into a number. Problem 3: (Difficult) Let A = a1 b1 a2 b2 È Î ˘ ˚ . Let a1 a2 È Î ˘ ˚ , b1 b2 È Î ˘ ˚ be points in 2 dimensional space; e.g. x2 b1 b2 È Î ˘ ˚ b2 a1 a2 È Î ˘ ˚ a2 x1 b1 a1 Now use the origin 0 0 È Î ˘ ˚ and the 2 points a1 a2 È Î ˘ ˚ , b1 b2 È Î ˘ ˚ to form a parallelogram. 8 8 x2 [a1 + b1, a2 + b2] [b1, b2] [a1, a2] x1 Show that the area of the parallelogram is equal to |A| (except possibly for sign). Hint: the area of a parallelogram is equal to the product of the base times the height. Comment: the above property of 2 by 2 determinants generalizes to the N by N case. Write the matrix A as N column vector of dimension N, i.e., A = [A•1, A•2 , . . ., A•N ] where A•n = a1n a2n :. aNn È Î Í Í Í ˘ ˚ ˙ ˙ ˙ for n = 1, . . ., N. Now join each of the N points A•n to the origin and let these N vectors form the edges of a parallelepiped (the N dimensional generalization of a parallelogram). Then the volume which this parallelepiped encloses = |A|. We will prove this fact later after we have developed the concept of orthogonality (i.e., perpendicularity). Some Useful Properties of Determinants Lemma 1: If two rows of the N by N matrix A are identical, then |A| = 0. (N ≥ 2). Proof: Look at |A| = S e(i1, i2, . . ., iN) a1i1a2i2 . . . aNiN permutations (i1, i2, . . ., iN) 9 9 Let us suppose that rows 1 and 2 of A are identical. Pick an arbitrary term in the above summation, say e(i1, i2, . . ., iN) a1i1a2i2 . . . aNiN . Then the term e(i2, i1, . . ., iN) a1i2 a2i1 . . . aNiN is equal in absolute value to the first term (since rows 1 and 2 are identical and thus a1i1a2i2 = a2i1a1i1 = a1i2 a2i1 ) but it will be of opposite sign to the first term since the function e changes sign every time we make a transposition. We may carry on dividing the above summation into two separate summations, where each term in the first summation has a corresponding term in the second summation of opposite sign and thus |A| = 0. Q.E.D. Lemma 2: |AT|=|A| where A is an N by N matrix; i.e., the determinant of the transposed matrix is the same as the determinant of the matrix itself. Proof: |A| = S e(i1, i2, . . ., iN) a1i1a2i2 . . . aNiN (i1, i2, . . ., iN) = S e(i1, i2, . . ., iN) aj11aj2 2 . . . ajNN (i1, i2, . . ., iN) ↑ where we have rearranged terms so that the column subscript appears in natural order. Now if (i1, i2, . . ., iN) were an even permutation, it follows that (j1, j2, . . ., jN) is also even permutation since as we rearrange the indices (i1, i2, . . ., iN) by successive transpositions into (1, 2, . . ., N), we are simultaneously transposing (1, 2, . . ., N) into (j1, j2, . . ., jN). Thus we have = S e(j1, j2, . . ., jN) aj11aj2 2 . . . ajNN (j1, j2, . . ., jN) = |AT|. Q.E.D. The above two lemmas imply that if two columns of the N by N matrix A are identical, then |A|=0. Lemma 3: Let A by an N by N matrix, which has nth row equal to An• ; i.e. A = A1• A2• :. AN• È Î Í Í Í ˘ ˚ ˙ ˙ ˙ . Let k be a scalar. Then |[kA 1•T,A2•T,...,AN•T]|= k|A|, i.e., if we multiply a row of the matrix A by a scalar k, then the determinant of the resulting matrix = k|A|. 10 10 Proof: | kA1• A2• :. AN• È Î Í Í Í ˘ ˚ ˙ ˙ ˙ | = S (i1, i2, . . . , iN ) e(i1, i2, . . ., iN) (kali1 ) a2i2 . . . aNiN = k S e(i1, . . ., iN) a1i1a2i2 . . . aNiN (i1, . . ., iN) = k |A| Q.E.D. L e m m a 4 : | A1• + B1• A2• :. AN• È Î Í Í Í ˘ ˚ ˙ ˙ ˙ |= | A1• A2• :. AN• È Î Í Í Í ˘ ˚ ˙ ˙ ˙ | + | B1• A2• :. AN• È Î Í Í Í ˘ ˚ ˙ ˙ ˙ | where A1• = [a11 . . . a1N] B1• = [b11 . . . b1N] A2• = [a21 . . . a2N ] :. AN• = [aN1 . . . aNN] Proof: | A1• + B1• A2• :. AN• È Î Í Í Í ˘ ˚ ˙ ˙ ˙ | ≡ S (i1, i2, . . . , iN ) e(i1, i2, . . . , iN) (ali 1 + bli1 ) a2i2 . . . aNiN = S (i1, i2, . . . , iN ) e(i1, i2, . . ., iN) a1i1a2i2 . . . aNiN + S (i1, i2, . . . , iN ) e(i1, i2, . . ., iN) NNiii aab ...21 21 = | A1• A2• :. AN• È Î Í Í Í ˘ ˚ ˙ ˙ ˙ | + | B1• A2• :. AN• È Î Í Í Í ˘ ˚ ˙ ˙ ˙ | Q.E.D. Problem 4: Let A = a11 a12a21 a22 È Î ˘ ˚ , B = b11 b12b21 b22 È Î ˘ ˚ . Show |AB| = |A|•|B|. Problem 5: Suppose we are given N-1, N dimensional vectors 11 11 A•2 = a12 a22 :. aN2 È Î Í Í Í ˘ ˚ ˙ ˙ ˙ , A•3 = a13 a23 :. aN3 È Î Í Í Í ˘ ˚ ˙ ˙ ˙ , . . . , A•N = a1N a2N :. aNN È Î Í Í Í ˘ ˚ ˙ ˙ ˙ and we define A•1 by A•1 ≡ k2 A•2 + k3 A•3 + . . . + kN A•N where k2, k3, . . ., kN are numbers. Show that |A| = | A•1, A•2 , . . ., A•N | = 0. Hint: Use the definition of A•1 above and the previous 4 lemmas. Lemma 5: Let A be an N by N matrix. If two columns of A are interchanged and if we take the determinant of the resulting matrix, then the resulting determinant = - |A|. Proof: |.,..,,,.,..,,,.,..,|0 111121 Njijjijii AAAAAAAAAAA •+•••-•+•••-••• ++= (the determinant is 0 since 2 columns of the above matrix are equal; recall lemmas (1) and (2)) = |A•1 . . .A•i-1, A•i , A•i+1,. . .,A•j + A•i , . . .,A•N|+|A•1, . . .,A•i-1,A•j , A•i+1,A•j + A•i , . . . ,A•N| (using lemma (4) in conjunction with lemma (2)). = |A•1. . . A•i . . . A• j . . . A•N|+|A•1. . . A•i . . . A•i . . . A•N| + |A•1. . . A•j . . . A•j . . . A•N|+|A•1. . . A•j . . . A•i . . . A•N| (again using lemma (4) in conjunction with lemma (2) 2 times) = |A•1. . . A•i . . . A• j . . . A•N| + 0 + 0 + |A•1. . . A•j . . . A•i . . . A•N| Since matrices which have 2 identical columns have 0 determinants Therefore |A•1. . . A•i . . . A• j . . . A•N|= - |A•1. . . A•j . . . A•i . . . A•N| Q.E.D. Lemma 6: Let A and B be 2 N x N matrices. Then |AB| = |A| •"|B|. 12 12 Proof: Let A = [A•1 ,A•2 , . . . A•N] and B = b11 b12 . . . b1N b21 b22 . . . b2N :. bN1 bN1 . . . bNN È Î Í Í Í ˘ ˚ ˙ ˙ ˙ then |AB|=| A•k1 bk11,k1=1 N Â A•k2 bk2 2k2 =1 N Â , . . ., A•k N bkN Nk N =1 N Â | by definition of AB = k1=1 N Â . . . |A•k1 bk11k N =1 N Â k2 =1 N Â ,A•k2 bk2 2, . . . , A•kN bk NN | making repeated use of lemma (4) = k1=1 N Â . . . bk11k N =1 N Â k2 =1 N Â , bk2 2, . . . , bk NN|A•k1 , A•k2 , . . . , A•k N | making repeated used of lemma (3) (applied to transposes) = S bk11bk2 2 . . . bkN N|A•k1 ,A•k2 , . . .,A•kN | over all permutations (k1, k2, . . ., kN) of (1, 2, . . ., N) since by lemma (1), the determinant is zero if any two rows (or columns using lemma (2)) are identical. = S |..,..,,|).,..,,(... 212121 21 NNNkkk AAAkkkbbb N ••e permutations (k1, k2, . . ., kN) since by lemma (5) every time we interchange a column of A, we change the sign of the determinant . . . = |BT| • |A•1A•2 . . . A•N| = |B| • |A| (using the definition of) |BT| = |A| • |B| 13 13 since |B| and |A| are scalars the order of multiplication can be interchanged. Q.E.D. We note that the calculation of the determinant of a square matrix A using the permutation definition on page 10 above is not an easy matter if the size of A is greater than say 5 since when N = 5, the number of terms in the definition equals 120 = 1 ¥ 2 ¥ 3 ¥ 4 ¥ 5. When N = 10, the number of terms is 10! = 4, 536,000. Hence, in the next section, we develop a practical method for calculating determinants. The method relies on the properties of determinants that we developed in this section. 3. A Gaussian Method for Calculating Determinants A diagonal method A ≡ [aij] is a square matrix that has zero elements everywhere except possibly down the main diagonal which runs from the northwest corner of the matrix to the southeast corner; i.e., A ≡ [aij] is diagonal iff aij = 0 for all i ≠ j. From the definition of the determinant, it is clear that the determinant of a diagonal matrix is equal to the product of its main diagonal elements; i.e., |A| = Pi=1 N aii if A is diagonal. An upper triangular matrix A ≡ [aij] is a square matrix that has zero elements below the main diagonal; i.e., aij = 0 for all i and j such that 1 ≤ j < i ≤"N. It can be seen that the determinant of an upper triangular matrix is also equal to the product of its main diagonal elements, Pi=1 N aii . Why is this? Recall the definition of |A|: |A|= S (j1 , j2 , . . .,jN )a1j1a2j2 . . . aNjN .permutations Assume A is upper triangular. If we pick j1 ≥ 2, then eventually, one of the later indexes j2, j3, . . ., jN must be chosen to be 1. For the sake of definiteness, suppose j2 = 1 and hence a21 appears in the term under consideration. But since all elements below a11 in the first column of the matrix are 0, this term must be 0. Thus, in order to obtain a nonzero term, we must pick j1 = 1. Now consider the choices for the j2 index. Since we have chosen j1 = 1 in order to obtain nonzero terms, j2 can be any one of the indexes 2, 3, . . ., N. However, if we pick j2 ≥ 3, then one of the later indexes j3, j4, . . ., jN must be chosen to be 2 in order for (1, j2, j3, . . ., jN) to be a permutation of (1, 2, . . ., N). For the sake of definiteness, suppose j3 = 2 and hence a32 appears in the term under consideration. But since all elements below a22 in the second column must be zero by the definition of an upper triangular matrix, we have a32 = 0. Thus in order to obtain a nonzero term 14 14 in the definition of the determinant, we must pick j1 = 1 and j2 = 2. The same logic can be repeated to show that the only possible nonzero term in the definition of the determinant of an upper triangular A is the term where (j1, j2, . . ., jN) = (1, 2, . . ., N) so that |A| = Pi=1 N aii in this case. Let us call this result Lemma 7. A lower triangular matrix A ≡ [aij] is a square matrix that has zero elements above the main diagonal; i.e., aij = 0 for all i and j such that 1 ≤ i < j ≤ N. Problem 6: Show that if A is lower triangular, then |A|≡ Pi=1 N aii . Hint: Use Lemmas (2) and (7). Lemma (7) shows that it is very easy to calculate the determinant of an upper triangular matrix. Lemmas (3), (4) and (2) tell us that if we add a multiple of one row of a square matrix to another row, then the determinant of the matrix remains unchanged. This suggests an effective strategy for calculating the determinant of a square matrix A: add multiples of higher rows of A to lower rows of A in order to reduce or transform A into an upper triangular matrix U ≡ [uij]. Then |A| = Pi=1 N uii; i.e., the determinant of A is equal to the product of the main diagonal elements of the upper triangular matrix U. Algorithm: Stage 1: A ≡ [aij] is N by N. Case (i): a11 ≠ 0. Add - (a21/a11) A1• to row 2 of A; Add - (a31/a11) A1• to row 3 of A; :. Add - (aN1/a11) A1• to row
本文档为【ELEMENTARY MATRIX ALGEBRA】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_532626
暂无简介~
格式:pdf
大小:5MB
软件:PDF阅读器
页数:33
分类:经济学
上传时间:2013-01-29
浏览量:21