# how to invert a matrix step by step using following example

i'm making a program for hill cipher encryption 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.

-
The easiest way is to solve the system $AB=I$, such that $B=A^{-1}$. You know how row-reducing works? (gaussian elimination // row echelon form)? –  Bob Jan 22 '13 at 17:16
no buddy i m programmer actually only hill ciphar is in my subject not math as such still i m trying to understand it. so that i could make a program for it. –  spreet Jan 22 '13 at 17:19
If you know nothing about linear algebra, especially over rings other than $\mathbb{R}$, it's probably not a good idea to implement a matrix inverse routine yourself. Use one of the many high-quality freely available libraries for numerical linear algebra. –  mrf Jan 22 '13 at 18:05
Someone correct me if I'm wrong, but isn't there no finite field over a domain with 26 elements? Doesn't the domain of a finite field have to be a prime power? I'm not sure that matrix inversion is even defined for this. –  DanielV May 30 '14 at 4:43

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}$$

-
This works for all square matrices. If you are only considering 2x2 matrices I'd advise you to just skip what I wrote and use the rule: $$A^{-1}=\frac{1}{\det(A)(=ad-bc)} \cdot \begin{pmatrix} d&-b \\ -c&a \end{pmatrix}$$ with $$A=\begin{pmatrix} a&b \\ c&d \end{pmatrix}$$ –  Bob Jan 22 '13 at 17:48
Just so it is stated somewhere, the general formula is $A^{-1} = \frac{1}{\text{det}(A)}\text{adj}(A)$, with adj($A$) the adjugate matrix of $A$. –  Olivier May 30 '14 at 3:01