how to inverse a matrix step by step using following example

Question

i m making a program for hill cipher encrytion and decryption. for that i am trying to understand the logic behind it. The best example I have been given is in the following link.

http://en.wikipedia.org/wiki/Hill_cipher

the problem is that i m not able to understand how the inverse of the matrix has been done in this example. can any one explain it to me step by step. I tried my level best to understand it even one of my friend was trying to sort this out. but he was not able to. so he actually referred me to this site.

Please help. thanks in advance. Spreet

Answer 1

To make a small example for a 2x2 matrix so you can work on your program:

$B=A^{-1}$ => $AB=I$ as we want.

Suppose $A=\begin{pmatrix} 1&2 \\ -1&1 \end{pmatrix}$

Then $B=A^{-1}$ => $AB=I$ is solvable by a form of row reducing:

$$[A I]=\begin{pmatrix} 1&2&1&0 \\ -1&1&0&1 \end{pmatrix}$$ note: first 2 columns are $A$, last two are $I_2$

Now we "change" $[A I]$ to $[I B]$ with $B=A^{-1}$ $$\begin{pmatrix} 1&2&1&0 \\ -1&1&0&1 \end{pmatrix} => \begin{pmatrix} 1&2&1&0 \\ 0&3&1&1 \end{pmatrix}$$ (add row 1 to row 2)

Divide row 2 by 3: $$\begin{pmatrix} 1&2&1&0 \\ 0&1&\frac{1}{3}&\frac{1}{3} \end{pmatrix}$$

And last, substract row 2 twice from row 1 in order to find I. $$\begin{pmatrix} 1&0&\frac{1}{3}&- \frac{2}{3} \\ 0&1&\frac{1}{3}&\frac{1}{3} \end{pmatrix}$$

Thus we found the form $[I B]$ with $$B=A^{-1}= \frac{1}{3} \cdot \begin{pmatrix} 1&-2 \\ 1&1\end{pmatrix}$$