How to Find the Inverse of a Matrix Modulo 26?

[SomeRandomGuy]

Hey guys, I was wondering if someone could give me a hand finding the inverse of a matrix Modulo 26. The matrix is as follows:

4 9 15
15 17 6
24 0 17

I am trying to get a 1 in the first slot, so I know that 4 can't go into 27 evenly to do that. I tried switching the first and the third row, then adding 1/5 of the second row to it to get 27 which = 1 mod 26, but this will get very messy very fast. Just wondering if this is the only way, or am I overlooking a more simplistic method?

 

[matt grime]

You're going at it the wrong way. I presume you're doing this by row operations (and column operations).

You should try and get the matrix in upper triangular form (ie forget the 1 bit), or lower triangular form, and there is no harm in multiplying rows by 5 instead of dealing with 5ths, and you could try using that zero in the middle of the bottom row.

 

[cronxeh]

Your best option is to set up an augmented matrix and get it to reduced row echelon form (rref):
keep in mind you are working in mod 26:
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25}

$$\left(\begin{array}{abcdef} 4 & 9 & 15 & 1 & 0 & 0\\ 15 & 17 & 6 & 0 & 1 & 0\\ 24 & 0 & 17 & 0 & 0 & 1 \end{array}\right)$$ ~ $$\left(\begin{array}{abcdef} 1 & 0 & 0 & x11 & x12 & x13\\ 0 & 1 & 0 & x21 & x22 & x23\\ 0 & 0 & 1 & x31 & x32 & x33 \end{array}\right)$$

$$A^{-1} = \left(\begin{array}{abcdef} x11 & x12 & x13\\ x21 & x22 & x23\\ x31 & x32 & x33 \end{array}\right)$$

Keep in mind when you use MATLAB you'll have to convert negative numbers and fractions into modulus 26 version

 

[matt grime]

Didn't notice that modulo 26 bit.

You definitely don't want have to divide at all then, since it won't be obvious what the reciprocals of the numbers will be (if they even exist - you can't divide by 2 for instance).

However notice that 24=-2 mod 26, so multiplying the bottom row by 2 and adding it to the top seems like a good way of getting more zeroes.

 

[SomeRandomGuy]

Your best option is to set up an augmented matrix and get it to reduced row echelon form (rref):
keep in mind you are working in mod 26:
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25}

$$\left(\begin{array}{abcdef} 4 & 9 & 15 & 1 & 0 & 0\\ 15 & 17 & 6 & 0 & 1 & 0\\ 24 & 0 & 17 & 0 & 0 & 1 \end{array}\right)$$ ~ $$\left(\begin{array}{abcdef} 1 & 0 & 0 & x11 & x12 & x13\\ 0 & 1 & 0 & x21 & x22 & x23\\ 0 & 0 & 1 & x31 & x32 & x33 \end{array}\right)$$

$$A^{-1} = \left(\begin{array}{abcdef} x11 & x12 & x13\\ x21 & x22 & x23\\ x31 & x32 & x33 \end{array}\right)$$

Keep in mind when you use MATLAB you'll have to convert negative numbers and fractions into modulus 26 version

Yeah, that's what I am using... Just this modulo 26 is a bit different than usual. Also, we can't use matlab... all this has to be done by hand :/

Thanks matt, i'll try that now.

 

[matt grime]

Here are some pairs of inverses of elements, which may help (3,9), (5,-5) or (5,21) (7,-11 ) or (7,15) (11,-7 ) or (11,19)

so, for instance, one could multiply row 2 by 7 to get a 1 in the first entry, also not that adding row 1 to row two results in a 26=0 in the middle position.

 

[SomeRandomGuy]

Thanks guys, I have managed to reduce my matrix to almost the inverse. I have managed to get the following:

1 0 6 | 14 5 0
0 1 23 | 25 2 0
0 0 22 | 2 10 1

Can anyone verify that I am on the right track? If someone would like, I can post each step I did to show how I arrived at this point. Problem now is, I can't figure out how to get a 1 where the 22 is.

 

[Hurkyl]

One thing that's sure to work (though it might not be the easiest) is to compute the adjoint (I think that's the word used) -- the matrix whose (i,j)-th entry is the (i,j)-th subdeterminant. The identity A * adj A = (det A) I will yield the inverse.

Another approach is to use the chinese remainder theorem. Work out the inverse mod 13 and mod 2, then combine them to get the mod 26 answer.

All that said, you probably made an arithmetic error -- I don't think that last row is correct. (Because if that 22 is right, all of the terms on the RHS should be even)

 

[SomeRandomGuy]

One thing that's sure to work (though it might not be the easiest) is to compute the adjoint (I think that's the word used) -- the matrix whose (i,j)-th entry is the (i,j)-th subdeterminant. The identity A * adj A = (det A) I will yield the inverse.

Another approach is to use the chinese remainder theorem. Work out the inverse mod 13 and mod 2, then combine them to get the mod 26 answer.

All that said, you probably made an arithmetic error -- I don't think that last row is correct. (Because if that 22 is right, all of the terms on the RHS should be even)

Thanks, yes it's called an adjoint. Although, I think that would just end up confusing me more. I will try and see if I made an arithmetic error right now... If I don't find one, I will post my steps towards solving this problem.

 

[SomeRandomGuy]

Thanks guys, I got the inverse. Turns out it was a simple arithmetic mistake like Hurkyl said. God row reducing sucks :)

 

[cronxeh]

Adjoint method is fun and easy for small matrices, but for a 3x3 - to find an inverse you'd have to divide adjoin by determinant.. in modulus 26 ! Thats too complicated imho

 

[SomeRandomGuy]

Well, I thought I had it, but I don't quite yet. The matrix I got when multiplied almost yields the identity, but 2 values are messed up. I really can't find my mistake either... does anyone know where I can post the picture of my work so someone can see where I went wrong?

here is the inverse I got:

20 1 8
15 24 15
10 20 1

When this is multiplied by the original matrix, I get the following:

1 0 0
0 23 0
0 14 1

As you can see, I'm almost there.

 

[cronxeh]

$$\left(\begin{array}{abcdef} 4 & 9 & 15 & 1 & 0 & 0\\ 15 & 17 & 6 & 0 & 1 & 0\\ 24 & 0 & 17 & 0 & 0 & 1 \end{array}\right)$$ -> R1 = R1 - 12*R3, R2 = R2 - 19*R3 ->>

$$\left(\begin{array}{abcdef} 2 & 9 & 19 & 1 & 0 & 14\\ 1 & 17 & 21 & 0 & 1 & 7\\ 24 & 0 & 17 & 0 & 0 & 1 \end{array}\right)$$ -> R1 = R1 - R2, R3 = R3 - 24*R2 ->>

$$\left(\begin{array}{abcdef} 1 & 18 & 24 & 1 & 25 & 7\\ 1 & 17 & 21 & 0 & 1 & 7\\ 0 & 8 & 7 & 0 & 2 & 15 \end{array}\right)$$ -> R2 = R2 - R1 ->>

$$\left(\begin{array}{abcdef} 1 & 18 & 24 & 1 & 25 & 7\\ 0 & 25 & 23 & 25 & 2 & 0\\ 0 & 8 & 7 & 0 & 2 & 15 \end{array}\right)$$ -> R1 = R1 - 12*R3, R2 = R2 - 3*R3 ->>

$$\left(\begin{array}{abcdef} 1 & 0 & 18 & 1 & 1 & 9\\ 0 & 1 & 2 & 25 & 22 & 7\\ 0 & 8 & 7 & 0 & 2 & 15 \end{array}\right)$$ -> R3 - R3 - 8*R2 ->>

$$\left(\begin{array}{abcdef} 1 & 0 & 18 & 1 & 1 & 9\\ 0 & 1 & 2 & 25 & 22 & 7\\ 0 & 0 & 17 & 8 & 8 & 11 \end{array}\right)$$ -> R1 = R1 - 24*R3, R2 = R2 - 20*R3 ->>

$$\left(\begin{array}{abcdef} 1 & 0 & 0 & 17 & 17 & 5\\ 0 & 1 & 0 & 21 & 18 & 21\\ 0 & 0 & 17 & 8 & 8 & 11 \end{array}\right)$$ -> R3 = 23*R3 ->>

$$\left(\begin{array}{abcdef} 1 & 0 & 0 & 17 & 17 & 5\\ 0 & 1 & 0 & 21 & 18 & 21\\ 0 & 0 & 1 & 2 & 2 & 19 \end{array}\right)$$

$$A^{-1} = \left(\begin{array}{abcdef} 17 & 17 & 5\\ 21 & 18 & 21\\ 2 & 2 & 19 \end{array}\right)$$


Edit: Ahhh thanks, matt, missed a step when copying from paper

 

[matt grime]

In step one, despite not altering row 3 apparently, you manage to put a zero in its first position.

 

[Hurkyl]

to find an inverse you'd have to divide adjoin by determinant.. in modulus 26 ! Thats too complicated imho

Yep, but then again, the matrix is invertible if and only if the determinant is invertible.

 

[SomeRandomGuy]

$$\left(\begin{array}{abcdef} 4 & 9 & 15 & 1 & 0 & 0\\ 15 & 17 & 6 & 0 & 1 & 0\\ 24 & 0 & 17 & 0 & 0 & 1 \end{array}\right)$$ -> R1 = R1 - 12*R3, R2 = R2 - 19*R3 ->>

$$\left(\begin{array}{abcdef} 1 & 18 & 24 & 1 & 25 & 7\\ 1 & 17 & 21 & 0 & 1 & 7\\ 0 & 8 & 7 & 0 & 2 & 15 \end{array}\right)$$ -> R2 = R2 - R1 ->>

$$\left(\begin{array}{abcdef} 1 & 18 & 24 & 1 & 25 & 7\\ 0 & 25 & 23 & 25 & 2 & 0\\ 0 & 8 & 7 & 0 & 2 & 15 \end{array}\right)$$ -> R1 = R1 - 12*R3, R2 = R2 - 3*R3 ->>

$$\left(\begin{array}{abcdef} 1 & 0 & 18 & 1 & 1 & 9\\ 0 & 1 & 2 & 25 & 22 & 7\\ 0 & 8 & 7 & 0 & 2 & 15 \end{array}\right)$$ -> R3 - R3 - 8*R2 ->>

$$\left(\begin{array}{abcdef} 1 & 0 & 18 & 1 & 1 & 9\\ 0 & 1 & 2 & 25 & 22 & 7\\ 0 & 0 & 17 & 8 & 8 & 11 \end{array}\right)$$ -> R1 = R1 - 24*R3, R2 = R2 - 20*R3 ->>

$$\left(\begin{array}{abcdef} 1 & 0 & 0 & 17 & 17 & 5\\ 0 & 1 & 0 & 21 & 18 & 21\\ 0 & 0 & 17 & 8 & 8 & 11 \end{array}\right)$$ -> R3 = 23*R3 ->>

$$\left(\begin{array}{abcdef} 1 & 0 & 0 & 17 & 17 & 5\\ 0 & 1 & 0 & 21 & 18 & 21\\ 0 & 0 & 1 & 2 & 2 & 19 \end{array}\right)$$

$$A^{-1} = \left(\begin{array}{abcdef} 17 & 17 & 5\\ 21 & 18 & 21\\ 2 & 2 & 19 \end{array}\right)$$

I think you may have made a mistake somewhere also, like someone already said... I just checked by multiplying your matrix by the original in hopes to get the identity, but I got a 9 in the first position :/

 

[cronxeh]

you mean a square matrix is invertible iff matrix is not singular (det != 0), in particular the $$A^{-1}$$ here is:

$$\frac{1}{\det{\left(\begin{array}{abcdef} 4 & 9 & 15\\ 15 & 17 & 6\\ 24 & 0 & 17 \end{array}\right)}}$$$$\left(\begin{array}{abcdef} 17*17-6*0 & 15*0-9*17 & 9*6-15*17 \\ 6*24-15*17 & 4*17-15*24 & 15*15-4*6 \\ 15*0-17*24 & 9*24-4*0 & 4*17-9*15 \end{array}\right)$$ ->>

$$\frac{1}{4*17*17+9*6*24-15*17*24-9*15*17}\left(\begin{array}{abcdef} 3 & 3 & 19 \\ 19 & 20 & 19 \\ 8 & 8 & 11 \end{array}\right)$$

$$\frac{1}{17}\left(\begin{array}{abcdef} 3 & 3 & 19 \\ 19 & 20 & 19 \\ 8 & 8 & 11 \end{array}\right)$$

and now just to multiply each matrix entry by 1/17 ...


Somerandomguy:
$$\left(\begin{array}{abcdef} 4 & 9 & 15 \\ 15 & 17 & 6 \\ 24 & 0 & 17 \end{array}\right)$$$$\left(\begin{array}{abcdef} 17 & 17 & 5\\ 21 & 18 & 21\\ 2 & 2 & 19 \end{array}\right)$$ = $$\left(\begin{array}{abcdef} 4*17+9*21+15*2 & 4*17+9*18+15*2 & 4*5+9*21+15*19 \\ 15*17+17*21+6*2 & 15*17+17*18+6*2 & 15*5+17*21+6*19\\ 24*17+17*2 & 24*17+17*2 & 24*5+0*21+17*19 \end{array}\right)$$ ->>

$$\left(\begin{array}{abcdef} 16+7+4 & 16+6+4 & 20+7+25 \\ 21+19+12 & 21+20+12 & 23+19+10\\ 18+8 & 18+8 & 16+11 \end{array}\right)$$ ->>

$$\left(\begin{array}{abcdef} 1 & 0 & 0 \\ 0 & 1 & 0\\ 0 & 0 & 1 \end{array}\right)$$

 

[matt grime]

So, find the inverse of 17 mod 26, it's no harder than doing Euclid's algorthim (or being clever and just checking my list on the last page)

( from scratch, less than one minutes thinking gives 23 as the inverse, or -3, equivalently)

 

[cronxeh]

I tried coming up with general number of operations you'd perform with either method to determine which is faster, and I just don't have time right now..

matt, which one is faster - augmented matrix or adjoint/determinant method? I've counted about 47 operations on adj/det method, and I'm guessing there is more in augmented method

 

[ComputerGeek]

One thing that's sure to work (though it might not be the easiest) is to compute the adjoint (I think that's the word used) -- the matrix whose (i,j)-th entry is the (i,j)-th subdeterminant. The identity A * adj A = (det A) I will yield the inverse.

Another approach is to use the chinese remainder theorem. Work out the inverse mod 13 and mod 2, then combine them to get the mod 26 answer.

All that said, you probably made an arithmetic error -- I don't think that last row is correct. (Because if that 22 is right, all of the terms on the RHS should be even)

the second option might be best because then every element on mod 2 and mod 13 will be a unit and you can find an inverse for every number. mod 26 is harder because not every element will have an inverse and you may need to do some careful row switches.

 

[ComputerGeek]

Yep, but then again, the matrix is invertible if and only if the determinant is invertible.

don't you mean not equal to zero?

 

[Data]

Not equal to zero and invertible mean the same thing for elements of a field~

 

[matt grime]

But we aren't dealing with a field. Invertible is indeed the correct term.

 

[Hurkyl]

For example, an integer matrix has an integer inverse if and only if its determinant is 1 or -1 --- because those are the only invertible integers!

 

[ComputerGeek]

ah... that makes sense.