# Finding the inverse of matrices

1. Mar 14, 2005

### 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?

2. Mar 15, 2005

### 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.

3. Mar 15, 2005

### 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

4. Mar 15, 2005

### 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.

5. Mar 15, 2005

### SomeRandomGuy

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.

6. Mar 15, 2005

### 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.

7. Mar 15, 2005

### 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.

8. Mar 15, 2005

### Hurkyl

Staff Emeritus
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)

9. Mar 15, 2005

### SomeRandomGuy

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.

Last edited: Mar 15, 2005
10. Mar 15, 2005

### SomeRandomGuy

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

11. Mar 15, 2005

### 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

12. Mar 15, 2005

### 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.

13. Mar 15, 2005

### 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 :rofl:

Last edited: Mar 16, 2005
14. Mar 16, 2005

### matt grime

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

15. Mar 16, 2005

### Hurkyl

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

16. Mar 16, 2005

### SomeRandomGuy

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 :/

17. Mar 16, 2005

### 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)$$

Last edited: Mar 16, 2005
18. Mar 16, 2005

### 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)

Last edited: Mar 16, 2005
19. Mar 16, 2005

### cronxeh

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

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

20. Mar 17, 2005

### ComputerGeek

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.