Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
1  
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 at 4:43
add comment

1 Answer

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

share|improve this answer
    
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 at 3:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.