Module 17 - Matrix Analysis 2

FACULTY OF MATHEMATICAL STUDIES MATHEMATICS FOR PART I ENGINEERING Lectures MODULE 17 1. 2. 3. 4.

MATRICES II

Inverse of a matrix Systems of linear equations Solution of sets of linear equations – elimination methods Inverse of a matrix – using elimination method

1. Inverse of a matrix It is very important to be able to obtain the inverse of a matrix. Def. Given a square matrix A , if we can find a matrix B such that AB = BA = I, where I is the unit matrix, then B is called the inverse of A and written A−1 . [It can be proved that if the inverse exists then it is unique, i.e. the inverse has only one form.] Def. Def.

The matrix A is singular if |A| = 0 (i.e. detA = 0). The matrix A is non-singular if |A| 6= 0.

With this notation we can state: if A is singular then A−1 does not exist; adj A . |A| The above formula states the direct method (or cofactor method) of calculating the inverse. if A is non-singular then A−1 does exist and A−1 =

Property of inverse Provided the inverses exist, (AB)−1 = B−1 A−1 . [Proof If the expression on the RHS is the inverse then it must satisfy the rules stated earlier for an inverse. For verification, note that (B−1 A−1 )(AB) = B−1 (A−1 A)B = B−1 IB = B−1 B = I , (AB)(B−1 A−1 ) = A(BB−1 )A−1 = AIA−1 = AA−1 = I . ] The result can be extended to a string of matrices: (ABCD)−1 = D−1 C−1 B−1 A−1 .     5 2 4 1 2 2. , (b) B =  3 −1 Ex 1. Find A−1 and B−1 when (a) A = 3 3 1 4 −3 (a) As discussed in module 16 the minor associated with each element is found by deleting the row and column which passes through that element, and taking the determinant of what remains. The corresponding cofactor is then calculated using Aij = (−1)i+j Mij . Hence,       3 −3 3 3 (−1)1+1 3 (−1)1+2 3 = , (Mij ) = , (Aij ) = −2 1 (−1)2+1 2 (−1)2+2 1 2 1 |A| = 1(3) − 2(3) = 3 − 6 = −3,   3 −2 T adj A = (Aij ) = , −3 1 1



and therefore −1

A

=

3 −2 −3 1 −3

  =

−1 2/3 1 −1/3

 .

[The above result can easily be checked: AA−1 =



1 3

2 3



−1 23 1 − 13



 =

1 0

0 1

 .

In a similar way you can check A−1 A = I .] (b) Here the minors are more difficult to calculate since knocking out the row and column which passes through an element means that we must evaluate the determinant of a 2 × 2 matrix. Evaluating these determinants leads to the results     3−8 −9 − 2 12 − (−1) −5 −11 13 (Mij ) =  −6 − 16 −15 − 4 20 − 2  =  −22 −19 18  , 4 − (−4) 10 − 12 −5 − 6 8 −2 −11   −5 11 13 (Bij ) = ((−1)i+j Mij ) =  22 −19 −18  , 8 2 −11   −5 22 8 2 , adj B = (Bij )T =  11 −19 13 −18 −11 |B| = 5(−5) + 2(11) + 4(13) = −25 + 22 + 52 = 49, Thus finally B−1

by first row.

  −5 22 8 1  adj B = 11 −19 2 . = |B| 49 13 −18 −11

(Again you can verify that BB−1 = BB−1 = I.) Although the direct method is useful for inverting small matrices it is surprisingly inefficient using it for large matrices, since the method takes a large amount of time. A different method is required, therefore, for finding the inverse of a large matrix – see section 4. 2. Systems of linear equations Matrices are very important themselves, but their greatest use lies in solving sets of linear equations. Note first that the system of simultaneous linear equations ( n equations in n unknowns) a11 x1 a21 x1

+ + .. .

an1 x1

+

a12 x2 a22 x2 .. . an2 x2

+ +

+

... ... .. .

+ +

a1n xn a2n xn

...

+ ann xn

= =

b1 b2

=

bn

.. .

can be written AX = b , where 

 a1n a2n  , ..  . 

a11  a21 A=  ...

a12 a22 .. .

... ... .. .

an1

an2

. . . ann



 x1  x2   X=  ...  , xn 2



 b1  b2   b=  ...  . bn

In this module only systems which lead to a square matrix for A are considered. There are four cases which arise depending on whether, or not, |A| = 0 and b = 0 . Case (i)

b 6= 0, |A| 6= 0

In this case the matrix A is non-singular so A−1 exists and hence pre-multiplying both sides of the equation AX = b by A−1 gives A−1 AX = A−1 b,

→

IX = A−1 b,

→

X = A−1 b .

Thus we have a unique solution. Case (ii)

b = 0, |A| 6= 0

Again A−1 exists so the system AX = 0 has the unique solution X = A−1 0 = 0 (i.e. only the trivial (or zero) solution X = 0 ). Case (iii)

b 6= 0, |A| = 0

Since |A| = 0 the inverse matrix does not exist. This is the most complicated of the four cases and there are two possibilities: either we have no solution, or there are infinitely many solutions. To illustrate these two possibilities consider the two systems below (this case will be considered in more detail in module 18). The first system is 3x + 2y = 2 3x + 2y = 6

 or

    2 x . = 6 y

3 2 3 2

For this system b 6= 0 and |A| = 3(2) − 3(2) = 6 − 6 = 0. It is clear from inspection of the pair of equations that they are inconsistent (i.e. not compatible) so no solution exists. The second system is 3x + 2y = 2 6x + 4y = 4

 or

3 6

2 4

    2 x = . y 4

For this system also b 6= 0 and |A| = 3(2) − 3(2) = 6 − 6 = 0. Looking at the given pair of equations the second one is twice the first, and can be ignored since it provides nothing new. For solutions of the remaining 3 equation 3x + 2y = 2 choose x = C, any constant, and then 2y = 2 − 3C which implies y = 1 − C . 2 Thus the solution is     x C = , for any constant C. y 1 − 32 C Case (iv)

b = 0, |A| = 0

Here there are infinitely many solutions, as in the second possibility in case (iii) above. For example the system x + y = 0, αx + αy = 0 ,

    x C , for any in which b = 0 and |A| = 1(α) − 1(α) = 0, has the solution x = C, y = −C, i.e. = y −C constant C. Case (iv) is very important for it follows from cases (ii) and (iv) that the equation AX = 0 has a non-trivial (non-zero) solution if and only if |A| = 0. 3

Ex 2.

Find the value of α for which the equations αx + y − z = 0 y + 2z = 0 2y − z = 0

have non-trivial solutions. The system AX = 0 has non-trivial solutions only when |A| = 0. Expanding by the first column α |A| = 0 0

1 −1 1 2 = α(−1 − 4) + 0 + 0 = −5α, 2 −1

and hence non-trivial solutions exist only when α = 0. In this case the system of equations becomes y− z=0 y + 2z = 0 2y − z = 0 with solution y = z = 0 and no restriction on x. Hence the solution is     C x  y  =  0 , 0 z

for any constant C.

3. Solution of sets of linear equations – elimination methods The idea behind elimination methods for solving systems of equations can be seen from the well-known method for 2 simultaneous equations in 2 unknowns. x + 2y = 4 2x + y = 5

→

x + 2y = 4 − 3y = −3

(eqn. 2 − 2 × eqn. 1).

The second reduced equation implies y = 1 and hence substitution into the first reduced equation gives x = 4 − 2(1) = 2 . The solution, therefore, is     x 2 . = y 1

The basic elimination method for n linear equations in the n unknowns x1 , x2 , . . ., xn , which extends the method outlined above, is (i) retain the first equation for x1 in terms of x2 , . . ., xn and use this equation to eliminate x1 from the remaining equations; (ii) retain the second equation for x2 in terms of x3 , . . ., xn and use this equation to eliminate x2 from the remaining lower equations in the reduced set; (iii) repeat the process, until you arrive at the final equation in xn only, which you solve; (iv) substitute back into the equations in the reduced set, using them in reverse order to find in turn xn−1 , xn−2 , . . ., x1 . Let us illustrate the method with the following example for 3 equations in 3 unknowns. 4

Ex 3.

Use the elimination method to solve the equations = 3, x1 + x2 2x1 + x2 + x3 = 7, x1 + 2x2 + 3x3 = 14.

In the matrix form, AX = b , we have 

1 2 1

    3 1 0 x1 1 1   x2  =  7  . x3 14 2 3

The method described above is equivalent to reducing A to upper triangular form, i.e.  elimination  a b c  0 d e  with non-zero elements on the principal diagonal and all elements below it being zero. The 0 0 f elimination procedures rely on manipulation of the ROWS of the matrix, equivalent to manipulation of the original equations. The allowed row operations arise because of the operations which can be performed on equations and systems of equations. These row operations are: (i) any row can be multiplied by a constant; (ii) a row can be added to (or subtracted from) any other row; (iii) any two rows can be interchanged. The solution will now be found using these operations. 

1 2 1

1 1 2

    3 x1 0 1   x2  =  7  x3 14 3

 →

1 0 0

    1 0 x1 3 −1 1   x2  =  1  , x3 11 1 3

where we have used row 2 − 2 × row 1 and row 3 − row 1, in order to make the elements in the first column (apart from the leading element) zero. Note that it is the rows in the matrix of coefficients and the same rows in the column vector on the RHS that are changed, but the matrix of unknowns is unaltered. This follows immediately from consideration of the equivalent set of equations. Completing the reduction we obtain     x1 3 1 1 0  0 −1 1   x2  =  1  , 12 0 0 4 x3 

row 3 + row 2.

The reduced set of equations, therefore, is x1 + x2

= 3,

− x2 + x3 = 1, 4x3 = 12. Solving the final equation then implies x = 3 , and substituting into the second equation gives x2 = x3 − 1 = 3 − 1 = 2 . Finally from the first equation we deduce x1 = 3 − x2 = 3 − 2 = 1 . Thus the solution is    1 x1  x2  =  2 . x3 3 

[You should check that this solution satisfies the original set of three equations.] 5

The above elimination method can be modified to apply to special matrices, and the resulting algorithms can be found in various texts. The basic idea is unchanged, however, and the various specialised algorithms are not discussed further in this unit. 4. Inverse of a matrix – using the elimination method As mentioned earlier the cofactor method is not efficient when calculating the inverses of large matrices. Fortunately there are better methods available and one of these involves the elimination method. Suppose you require the inverse of an n × n square matrix A. Then you form a new matrix (A : I), in which the n × n unit matrix I is added to A as extra columns with the new matrix now n × 2n. The basic method is to use row operations (similar to those used in section 3) to reduce A to the unit matrix I. By simultaneously carrying out the same row operations on I the latter changes to A−1 . Hence the matrix (A : I) becomes (I : A−1 ). The elimination method discussed in section 3 reduces a matrix to upper triangular form. During this process the elements below the leading diagonal in a column were made zero. To reduce A to the unit matrix it is also necessary to make the elements along the principal diagonal all unity and make the elements above the leading diagonal zero. The modified procedure is as follows: (i) start with the first row and make the first element (in the first row and first column) zero; (ii) use this row to make the remaining elements in the first column zero; (iii) move to the second row and make the second element zero (i.e. the element in the second row and second column); (iv) use this amended second row to make the second element in ALL other rows zero; (v) consider each row in turn and continue with the same procedure. Let us illustrate the method with the example below.   1 2 3 Ex 4. If A =  −1 1 1  use the elimination 0 1 −1  1 2 3 1  −1 1 1 0 Start with the matrix (A : I) : 0 1 −1 0   1 2 3 1 0 0 4 1 1 0, row 1 + row 2. → 0 3 0 1 −1 0 0 1

method to determine A−1 .  0 0 1 0 0 1

Now move to the second row, where we need 1 as the second element and zeros both above and below this element. Thus,   1 2 3 1 0 0 1 × row 2 →  0 1 4/3 1/3 1/3 0  , 3 0 1 −1 0 0 1   1 0 1/3 1/3 −2/3 0 → 0 1 4/3 1/3 1/3 0  , row 1 − 2 × row 2 0 1 −1 0 0 1   1 0 1/3 1/3 −2/3 0 4/3 1/3 1/3 0  , → 0 1 row 3 − row 2 0 0 −7/3 −1/3 −1/3 1   1 0 1/3 1/3 −2/3 0 3 1/3 0 , − × row 3 →  0 1 4/3 1/3 7 0 0 1 1/7 1/7 −3/7 6

The first and second columns are now correct, so we must move on to the third row and third column. The third element in this row is already 1, so we only need to use the third row to produce zeros above this element in the third column   1 0 0 2/7 −5/7 1/7 1 →  0 1 4/3 1/3 1/3 0 , row 1 − × row 3 3 0 0 1 1/7 1/7 −3/7   1 0 0 2/7 −5/7 1/7 4 →  0 1 0 1/7 1/7 4/7  , row 2 − × row 3 3 0 0 1 1/7 1/7 −3/7 The matrix A has been changed to I, and the theory says that the right-hand side I will now be A−1 . Hence   2/7 −5/7 1/7 1/7 4/7 . A−1 =  1/7 1/7 1/7 −3/7 The evaluation of A−1 by the above method appears lengthy but for large matrices it can be shown that it is more efficient than determining the inverse using the cofactor method, and algorithms can be written for computer implementation. Before finishing this module another issue is briefly considered through the following example. Solve by elimination the equations      0.3 x 2 1 , = (a) 0.6 y 1 0.5001

Ex 5.

 (b)

2 1

1 0.4999

    0.3 x . = 0.6 y

(a) Dividing the first row by 2           2 1 x 0.3 1 0.5 x 0.15 = → = 1 0.5001 y 0.6 1 0.5001 y 0.60      0.15 x 1 0.5 , row 2 − row 1. = → 0.45 y 0 0.0001 The second reduced equation then states 0.0001y = 0.45 , which implies y = 4500. Substituting into the first equation then yields x = 0.15 − 0.5y = −2249.85. Thus the solution is     −2249.85 x = . 4500 y (b) The solution here follows an analogous pattern           0.15 x 1 0.5 0.3 x 2 1 = → = 0.60 y 1 0.4999 0.6 y 1 0.4999      0.15 x 1 0.5 , row 2 − row 1. = → 0.45 y 0 −0.0001 The second reduced equation now states −0.0001y = 0.45 , which implies y = −4500, and the first equation yields x = 0.15 − 0.5y = 2250.15. Hence the solution in this case is     2250.15 x = . −4500 y As you see the answers to (a) and (b) are hugely different despite the fact that the coefficients in the original systems were almost identical. Results of this type arise when the determinant of the coefficients on the LHS is 7

approximately zero, and great care has to be taken in these situations to get accurate answers. Geometrically, in each case above we are looking for the intersection of two straight lines. When the determinant is almost zero the lines are almost parallel and any small change in the slope of one line can lead to major changes in the point of intersection.

rec/00lm2

8