Inverse of a MatrixDate: 12/05/97 at 00:05:24 From: N Sivaram,WASE 237,Wipro Systems Subject: Algorithm needed! Hi, I need an algorithm to compute the inverse of a matrix. Can you help me? I have to write a progam in C to evaluate it. Regards, Sivaram Date: 12/05/97 at 10:07:59 From: Doctor Rob Subject: Re: Algorithm needed! A fairly simple algorithm to compute the inverse of a matrix goes like this. Start with the n-by-n matrix. Expand it to an n-by-(2*n) matrix by appending an n-by-n identity matrix to the righthand side. Now do elementary row operations on the matrix until the left half has been reduced to the identity matrix. Elementary row operations are: 1. Multiply a row by a nonzero scalar constant. 2. Exchange two rows. 3. Add a scalar constant multiple of one row to another. Working with column j for j from 1 to n is a good systematic way to do that. In column j pick a nonzero element a(i,j) from rows j through n (if there are none, the inverse does not exist). Multiply row i by 1/a(i,j) to create a "1" in row i and column j. Subtract a(k,j) times row i from row k for 1 <= k <= n, but k different from i, to create "0"s in all other rows in column j. Finally swap row i and row j if i differs from j to put the "1" on the diagonal. Repeat this for all j from 1 to n. When you have finished, what is left in the right half is the inverse of the original matrix. Example: Invert A, where (3 5 0) A = (6 1 4) (1 1 2) Append the identity matrix to the right: (3 5 0 1 0 0) (6 1 4 0 1 0) (1 1 2 0 0 1) Now start doing elementary row operations to form an identity matrix on the left. Subtract 3 times the third row from the first, and 6 times the third row from the second. (0 2 -6 1 0 -3) (0 -5 -8 0 1 -6) (1 1 2 0 0 1) Swap the first and third rows. Multiply the third row by 1/2. (1 1 2 0 0 1) (0 -5 -8 0 1 -6) (0 1 -3 1/2 0 -3/2) Subtract the third row from the first row. Add 5 times the third row to the second. (1 0 5 -1/2 0 5/2) (0 0 -23 5/2 1 -27/2) (0 1 -3 1/2 0 -3/2) Swap the third row and the second. Multiply the third row by -1/23. (1 0 5 -1/2 0 5/2) (0 1 -3 1/2 0 -3/2) (0 0 1 -5/46 -1/23 27/46) Subtract 5 times the third row from the first row. Add three times the third row to the second row. (1 0 0 1/23 5/23 -10/23) (0 1 0 4/23 -3/23 6/23) (0 0 1 -5/46 -1/23 27/46) The last three columns of this array form the inverse of A: ( 1/23 5/23 -10/23) A^(-1) = ( 4/23 -3/23 6/23) (-5/46 -1/23 27/46) Check your work by multiplying this times A on each side to make sure you get the identity. -Doctor Rob, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/