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.

my question is related to matrix inverting and Hill cipher(you don't have to know what it is to help me)

My teacher gave me an example. First we have a matrix (the key matrix) that multiplied by a vector of letters is another vector with the previous letters encrypted. To decrypt it you need the inverse of the key matrix and then multiply it by the vector of the encrypted letters, thus you get the vector of the decrypted letters (the real message)

Well, this is the matrix, the key matrix that I have to multiply the vectors of letters by and get the encrypted message.

$$ \left[ \begin{array}{ c c } 22&27&18 \\ 18&28&5 \\ 4&17&1 \end{array} \right] $$

However, when I try to invert it using multiple calculators on the internet and even programming languages (e.g. Ruby) I get a matrix (the inverted one) with a lot of 0.decimals numbers. Not whole numbers

Why am I expecting to get whole numbers? Because my teacher gave me the inverse. This is it:

$$ \left[ \begin{array}{ c c } 1&18&8 \\ 2&8&11 \\ 20&24&14 \end{array} \right] $$

I don't get something like this one. I know the inverse matrix is unique, but then who is wrong? Calculators bring on the same matrix, however, the matrix my teacher gave is the right matrix, because it can decrypt the encrypted message well, so it must be the good one.

Not to forget to tell you, that the inverse is the matrix mod 29.

Any idea on how I could get to the same matrix as my teacher? Thanks a lot.

share|improve this question
2  
That's because the modular inverse of a matrix and the usual inverse are two very different things. –  J. M. Nov 26 '11 at 10:56
    
@J.M. Isn't the result the same as if I bring the matrix to the reduced row echelon form and then take mod 29? –  Andrew Nov 26 '11 at 10:59
    
Ah... a KCd blurb. See page 7 of this. –  J. M. Nov 26 '11 at 11:10
    
"I know the inverse matrix is unique" --> Yes, the matrix inverse is unique, but there is no guarantee of unique expression of the matrix. At the level of entries, $1/5 = 6$, for example, in $\mathbb{Z}/29\mathbb{Z}$. –  Shaun Ault Nov 26 '11 at 14:35
2  
Moreover, using the word "whole" for members of $\mathbb{Z}/n\mathbb{Z}$ is dubious. Whole numbers are defined as nonnegative integers. When doing modular arithmetic, we cannot rely on intuitions that only apply to the ring of integers. –  Shaun Ault Nov 26 '11 at 14:38

3 Answers 3

up vote 6 down vote accepted

All the calculators that you found do their arithmetic with rationals or reals, so they are quite the wrong technology for arithmetic in the field $F_{29}$. But the usual algorithm of inverting a matrix is immune to such trifles, and works the same. I walk you thru this one. As always, we start with the given matrix augmented with an identity block on the right $$ \pmatrix{22&27&18&1&0&0\cr18&28&5&0&1&0\cr4&17&1&0&0&1\cr}. $$ To get going we want a $1$ in the upper left corner. To that end we divide the first row by $22$. In $F_{29}$ we have $4\cdot22=88=1$, so $22^{-1}=4$, and we can as well multiply the first row by $4$ (and remember to reduce everything modulo $29$) to get $$ \pmatrix{1&21&14&4&0&0\cr18&28&5&0&1&0\cr4&17&1&0&0&1\cr}. $$ Now we can pivot the first column. So we add the first row to the second multiplied by $-18=11$ and to the third multiplied by $-4=25$. Reduce modulo $29$ and get $$ \pmatrix{1&21&14&4&0&0\cr0&27&14&15&1&0\cr0&20&3&13&0&1\cr}. $$ Next we need a $1$ at the $(2,2)$-position. This time $14\cdot27=378=1$ in $F_{29}$, so we multiply the second row by $14$. $$ \pmatrix{1&21&14&4&0&0\cr0&1&22&7&14&0\cr0&20&3&13&0&1\cr}. $$ Next we clear the second column by adding to the first row the second row multiplied by $8=-21$, and adding to the third row the second row multiplied by $9=-20$: $$ \pmatrix{1&0&16&2&25&0\cr0&1&22&7&14&0\cr0&0&27&18&10&1\cr}. $$ Multiplying the third row by $14=27^{-1}$ gives us $$ \pmatrix{1&0&16&2&25&0\cr0&1&22&7&14&0\cr0&0&1&20&24&14\cr}. $$ Then we can work on the third column, and add the third row (multiplied by the appropriate constant) to the two top rows, and we end with $$ \pmatrix{1&0&0&1&18&8\cr0&1&0&2&8&11\cr0&0&1&20&24&14\cr}. $$ The row reduction worked as expected so we can deduce that the given matrix was non-singular, and its inverse can be read from the right half of the above end result.

You should walk away from this exercise with the understanding that the algorithm given in a linear algebra course works over any field. Only the details of the field arithmetic vary case-by-case. Here in particular division looked very different, but also testing whether an entry is equal to zero, $0=29=\cdots$, appears occasionally. For extra credit review the algorithm, and observe that, all the operations and laws of algebra that the algorithm depends on, hold in all fields.

share|improve this answer
    
+1 for the walkthrough. :) –  J. M. Nov 28 '11 at 12:51

By Cramer's rule, each coefficient of the inverse matrix is the determinant of a submatrix divided by the determinant $D$ of the original matrix. Here $D=15\pmod{29}$, whose inverse is $2$ mod $29$, hence the coefficients of the inverse matrix are twice the determinants of submatrices, that is, integers mod $29$.

Note that since $29$ is a prime, every integer which is not $0$ mod $29$ has an integer inverse hence the only case when this can fail is when the determinant is $0$ mod $29$, and then there is no inverse matrix anyway.

share|improve this answer

You could use Maple to find the inverse of some matrix. You just write the command Inverse(A) mod n. The instructions can be found here.

To find the inverse of a matrix in the field of integers mod a prime number $p$, you proceed in an analogue way as you calculate the inverse of a matrix. The usual formula can be found, for example, here.

The only thing that you need to do is to find $1/\det(A)$ in the field $\Bbb{Z}_p$, i.e. solve the equation $\det(A) \cdot x =1$ in $\Bbb{Z}_p$, and instead of dividing the entries of $A^*$ with the determinant of $A$, you multiply the entries of $A$ with $x$, the solution of the previous equation in $\Bbb{Z}_p$.

share|improve this answer
2  
The modular inverse of a matrix can also be done in Mathematica: Inverse[{{22, 27, 18}, {18, 28, 5}, {4, 17, 1}}, Modulus -> 29]. Sadly, Wolfram Alpha is not able to recognize this syntax. –  J. M. Nov 26 '11 at 13:42

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.