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 am trying to learn the Hill Cipher and I am facing difficulties understanding how to find the inverse of a matrix in Modulo 26. What I've learnt so far is that I need to apply elementary row operations and apply modulo 26 after each operation until my matrix becomes in row echelon reduced form. I've taken the example matrix found in the upper link and tried to find its inverse following the algorithm, hoping that I would reach the result showed in wikipedia. Despite my effors no avail so far. Below are my steps, I've spent few nights banging my head against this. Please note that modulo 26 is applied after each elementary row operation:

Start:

\begin{array}{ccc|ccc} 6 & 24 & 1 & 1 & 0 & 0\\ 13 & 16 & 10 & 0 & 1 & 0\\ 20 & 17 & 15 & 0 & 0 & 1\\ \end{array}

R1 + R2 =

\begin{array}{ccc|ccc} 19 & 14 & 11 & 1 & 1 & 0\\ 13 & 16 & 10 & 0 & 1 & 0\\ 20 & 17 & 15 & 0 & 0 & 1\\ \end{array}

11R1,2R2 =

\begin{array}{ccc|ccc} 1 & 24 & 17 & 11 & 11 & 0\\ 0 & 6 & 20 & 0 & 2 & 0\\ 20 & 17 & 15 & 0 & 0 & 1\\ \end{array}

1/2R2 and then 9R2=

\begin{array}{ccc|ccc} 1 & 24 & 17 & 11 & 11 & 0\\ 0 & 1 & 12 & 0 & 9 & 0\\ 20 & 17 & 15 & 0 & 0 & 1\\ \end{array}

6R1 + R3=

\begin{array}{ccc|ccc} 1 & 24 & 17 & 11 & 11 & 0\\ 0 & 1 & 12 & 0 & 9 & 0\\ 0 & 5 & 13 &14 & 14 & 1\\ \end{array}

21R2 + R3=

\begin{array}{ccc|ccc} 1 & 24 & 17 & 11 & 11 & 0\\ 0 & 1 & 12 & 0 & 9 & 0\\ 0 & 0 & 5 & 14 & 21 & 1\\ \end{array}

21R3=

\begin{array}{ccc|ccc} 1 & 24 & 17 & 11 & 11 & 0\\ 0 & 1 & 12 & 0 & 9 & 0\\ 0 & 0 & 1 & 8 & 25 & 21\\ \end{array}

As you can see I've 8 24 21 in the third row, whereas according to wikipedia's example there should have been 21 12 8. I've checked multiple times my calculations and I cant see anything wrong. Can anyone shed some light on what I am doing wrong?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

It must be observed that determinant is initially $441= 25 \mod 26$ and it is a unit because $25\cdot 25=1 \mod 26$. And in the second step you multiply by $2$ that is a zero divisor in $\mathbb{Z}/~26\mathbb{Z}$. From this step the matrix has not inverse.

share|improve this answer

In the fourth step above you multiply by $1/2\,$: you can't do this as the inverse of $2$ doesn't exist in $\,\mathbb{Z}/26\mathbb{Z}\,$

share|improve this answer
    
Thank you guys so much! It didn't occur to me that I cant multiply by number that does not have inverse in Z/26Z. Thanks! –  Genady Sergeev Jun 6 '12 at 8:14

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.