Inverse of a Matrix

Date: 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/