How to Find the Inverse of a Matrix Modulo 26?

  • Context: Undergrad 
  • Thread starter Thread starter SomeRandomGuy
  • Start date Start date
  • Tags Tags
    Inverse Matrices
Click For Summary

Discussion Overview

The discussion revolves around finding the inverse of a 3x3 matrix modulo 26. Participants explore various methods for achieving this, including row operations, the use of augmented matrices, and alternative approaches like the adjoint method and the Chinese remainder theorem. The conversation includes both theoretical considerations and practical challenges encountered during the calculations.

Discussion Character

  • Technical explanation
  • Mathematical reasoning
  • Debate/contested
  • Homework-related

Main Points Raised

  • One participant suggests starting with row operations to achieve a 1 in the first position, noting that switching rows and adding fractions complicates the process.
  • Another participant recommends transforming the matrix into upper or lower triangular form and emphasizes avoiding division due to complications with modular arithmetic.
  • Multiple participants propose setting up an augmented matrix and reducing it to reduced row echelon form (rref), while keeping in mind the modulo 26 context.
  • One participant mentions the difficulty of dividing in modulo 26 and suggests using the zero in the matrix to simplify calculations.
  • Several participants discuss pairs of inverses of elements that could assist in the row operations.
  • One participant shares their progress in reducing the matrix and seeks verification of their steps, indicating they are close to finding the inverse but struggling with a specific entry.
  • Another participant introduces the adjoint method as a potential solution, while also cautioning about the complexity of dividing by the determinant in modular arithmetic.
  • Concerns are raised about potential arithmetic errors in the calculations, with participants offering to review each other's work.
  • One participant expresses frustration with row reduction but ultimately finds the inverse after correcting a simple arithmetic mistake.
  • There are discussions about the implications of the determinant's invertibility for the matrix's overall invertibility.

Areas of Agreement / Disagreement

Participants generally agree on the methods to approach the problem, but there are varying opinions on the best techniques and the challenges posed by modular arithmetic. Some participants express uncertainty about specific steps and calculations, indicating that the discussion remains unresolved in certain areas.

Contextual Notes

Limitations include the complexity of performing operations in modular arithmetic, particularly regarding division and the existence of inverses. Some steps in the calculations are noted to be potentially erroneous, and participants express the need for careful verification of their work.

SomeRandomGuy
Messages
55
Reaction score
0
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?
 
Physics news on Phys.org
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.
 
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}

[tex]\left(\begin{array}{abcdef}<br /> 4 & 9 & 15 & 1 & 0 & 0\\<br /> 15 & 17 & 6 & 0 & 1 & 0\\<br /> 24 & 0 & 17 & 0 & 0 & 1<br /> \end{array}\right)[/tex] ~ [tex]\left(\begin{array}{abcdef}<br /> 1 & 0 & 0 & x11 & x12 & x13\\<br /> 0 & 1 & 0 & x21 & x22 & x23\\<br /> 0 & 0 & 1 & x31 & x32 & x33<br /> \end{array}\right)[/tex]

[tex]A^{-1} = \left(\begin{array}{abcdef}<br /> x11 & x12 & x13\\<br /> x21 & x22 & x23\\<br /> x31 & x32 & x33<br /> \end{array}\right)[/tex]

Keep in mind when you use MATLAB you'll have to convert negative numbers and fractions into modulus 26 version
 
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.
 
cronxeh said:
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}

[tex]\left(\begin{array}{abcdef}<br /> 4 & 9 & 15 & 1 & 0 & 0\\<br /> 15 & 17 & 6 & 0 & 1 & 0\\<br /> 24 & 0 & 17 & 0 & 0 & 1<br /> \end{array}\right)[/tex] ~ [tex]\left(\begin{array}{abcdef}<br /> 1 & 0 & 0 & x11 & x12 & x13\\<br /> 0 & 1 & 0 & x21 & x22 & x23\\<br /> 0 & 0 & 1 & x31 & x32 & x33<br /> \end{array}\right)[/tex]

[tex]A^{-1} = \left(\begin{array}{abcdef}<br /> x11 & x12 & x13\\<br /> x21 & x22 & x23\\<br /> x31 & x32 & x33<br /> \end{array}\right)[/tex]

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.
 
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.
 
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.
 
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)
 
Hurkyl said:
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.
 
Last edited:
  • #10
Thanks guys, I got the inverse. Turns out it was a simple arithmetic mistake like Hurkyl said. God row reducing sucks :)
 
  • #11
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
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
[tex]\left(\begin{array}{abcdef}<br /> 4 & 9 & 15 & 1 & 0 & 0\\<br /> 15 & 17 & 6 & 0 & 1 & 0\\<br /> 24 & 0 & 17 & 0 & 0 & 1<br /> \end{array}\right)[/tex] -> R1 = R1 - 12*R3, R2 = R2 - 19*R3 ->>

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

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

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

[tex]\left(\begin{array}{abcdef}<br /> 1 & 0 & 18 & 1 & 1 & 9\\<br /> 0 & 1 & 2 & 25 & 22 & 7\\<br /> 0 & 8 & 7 & 0 & 2 & 15<br /> \end{array}\right)[/tex] -> R3 - R3 - 8*R2 ->>

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

[tex]\left(\begin{array}{abcdef}<br /> 1 & 0 & 0 & 17 & 17 & 5\\<br /> 0 & 1 & 0 & 21 & 18 & 21\\<br /> 0 & 0 & 17 & 8 & 8 & 11<br /> \end{array}\right)[/tex] -> R3 = 23*R3 ->>

[tex]\left(\begin{array}{abcdef}<br /> 1 & 0 & 0 & 17 & 17 & 5\\<br /> 0 & 1 & 0 & 21 & 18 & 21\\<br /> 0 & 0 & 1 & 2 & 2 & 19<br /> \end{array}\right)[/tex]

[tex]A^{-1} = \left(\begin{array}{abcdef}<br /> 17 & 17 & 5\\<br /> 21 & 18 & 21\\<br /> 2 & 2 & 19<br /> \end{array}\right)[/tex]


Edit: Ahhh thanks, matt, missed a step when copying from paper :smile:
 
Last edited:
  • #14
In step one, despite not altering row 3 apparently, you manage to put a zero in its first position.
 
  • #15
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. :smile:
 
  • #16
cronxeh said:
[tex]\left(\begin{array}{abcdef}<br /> 4 & 9 & 15 & 1 & 0 & 0\\<br /> 15 & 17 & 6 & 0 & 1 & 0\\<br /> 24 & 0 & 17 & 0 & 0 & 1<br /> \end{array}\right)[/tex] -> R1 = R1 - 12*R3, R2 = R2 - 19*R3 ->>

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

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

[tex]\left(\begin{array}{abcdef}<br /> 1 & 0 & 18 & 1 & 1 & 9\\<br /> 0 & 1 & 2 & 25 & 22 & 7\\<br /> 0 & 8 & 7 & 0 & 2 & 15<br /> \end{array}\right)[/tex] -> R3 - R3 - 8*R2 ->>

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

[tex]\left(\begin{array}{abcdef}<br /> 1 & 0 & 0 & 17 & 17 & 5\\<br /> 0 & 1 & 0 & 21 & 18 & 21\\<br /> 0 & 0 & 17 & 8 & 8 & 11<br /> \end{array}\right)[/tex] -> R3 = 23*R3 ->>

[tex]\left(\begin{array}{abcdef}<br /> 1 & 0 & 0 & 17 & 17 & 5\\<br /> 0 & 1 & 0 & 21 & 18 & 21\\<br /> 0 & 0 & 1 & 2 & 2 & 19<br /> \end{array}\right)[/tex]

[tex]A^{-1} = \left(\begin{array}{abcdef}<br /> 17 & 17 & 5\\<br /> 21 & 18 & 21\\<br /> 2 & 2 & 19<br /> \end{array}\right)[/tex]

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
you mean a square matrix is invertible iff matrix is not singular (det != 0), in particular the [tex]A^{-1}[/tex] here is:

[tex]\frac{1}{\det{\left(\begin{array}{abcdef}<br /> 4 & 9 & 15\\<br /> 15 & 17 & 6\\<br /> 24 & 0 & 17<br /> \end{array}\right)}}[/tex][tex]\left(\begin{array}{abcdef}<br /> 17*17-6*0 & 15*0-9*17 & 9*6-15*17 \\<br /> 6*24-15*17 & 4*17-15*24 & 15*15-4*6 \\<br /> 15*0-17*24 & 9*24-4*0 & 4*17-9*15<br /> \end{array}\right)[/tex] ->>

[tex]\frac{1}{4*17*17+9*6*24-15*17*24-9*15*17}\left(\begin{array}{abcdef}<br /> 3 & 3 & 19 \\<br /> 19 & 20 & 19 \\<br /> 8 & 8 & 11<br /> \end{array}\right)[/tex]

[tex]\frac{1}{17}\left(\begin{array}{abcdef}<br /> 3 & 3 & 19 \\<br /> 19 & 20 & 19 \\<br /> 8 & 8 & 11<br /> \end{array}\right)[/tex]

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


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

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

[tex]\left(\begin{array}{abcdef}<br /> 1 & 0 & 0 \\<br /> 0 & 1 & 0\\<br /> 0 & 0 & 1<br /> \end{array}\right)[/tex]
 
Last edited:
  • #18
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:
  • #19
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
 
  • #20
Hurkyl said:
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.
 
  • #21
Hurkyl said:
Yep, but then again, the matrix is invertible if and only if the determinant is invertible. :smile:

don't you mean not equal to zero?
 
  • #22
Not equal to zero and invertible mean the same thing for elements of a field~
 
  • #23
But we aren't dealing with a field. Invertible is indeed the correct term.
 
  • #24
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!
 
  • #25
ah... that makes sense.
 

Similar threads

Undergrad How can I convince myself that I can find the inverse of this matrix?
  • · Replies 34 ·
2
Replies
34
Views
4K
Undergrad Getting eigenvalues of an arbitrary matrix with programming
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Matrix diagonalization algorithm
  • · Replies 5 ·
Replies
5
Views
3K
MHB How Do You Find the Inverse of a Matrix Using the Adjoint Method?
  • · Replies 15 ·
Replies
15
Views
3K
Undergrad Intuition behind elementary operations on matrices
  • · Replies 48 ·
2
Replies
48
Views
7K
MHB Finding element of inverse matrix
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Factoring Matrices with Elementary Row Operations
  • · Replies 4 ·
Replies
4
Views
2K
High School Is the Inverse of this Matrix Possible?
  • · Replies 12 ·
Replies
12
Views
2K
Undergrad Eigenproblem for non-normal matrix
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad Jacobi matrix diagonalization problems
  • · Replies 5 ·
Replies
5
Views
3K