Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding the inverse of matrices

  1. Mar 14, 2005 #1
    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. jcsd
  3. Mar 15, 2005 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Mar 15, 2005 #3

    cronxeh

    User Avatar
    Gold Member

    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}
    4 & 9 & 15 & 1 & 0 & 0\\
    15 & 17 & 6 & 0 & 1 & 0\\
    24 & 0 & 17 & 0 & 0 & 1
    \end{array}\right)[/tex] ~ [tex]\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)[/tex]

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

    Keep in mind when you use matlab you'll have to convert negative numbers and fractions into modulus 26 version
     
  5. Mar 15, 2005 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  6. Mar 15, 2005 #5
    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.
     
  7. Mar 15, 2005 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  8. Mar 15, 2005 #7
    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.
     
  9. Mar 15, 2005 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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)
     
  10. Mar 15, 2005 #9
    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
  11. Mar 15, 2005 #10
    Thanks guys, I got the inverse. Turns out it was a simple arithmetic mistake like Hurkyl said. God row reducing sucks :)
     
  12. Mar 15, 2005 #11

    cronxeh

    User Avatar
    Gold Member

    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
     
  13. Mar 15, 2005 #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.
     
  14. Mar 15, 2005 #13

    cronxeh

    User Avatar
    Gold Member

    [tex]\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)[/tex] -> R1 = R1 - 12*R3, R2 = R2 - 19*R3 ->>

    [tex]\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)[/tex] -> R1 = R1 - R2, R3 = R3 - 24*R2 ->>

    [tex]\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)[/tex] -> R2 = R2 - R1 ->>

    [tex]\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)[/tex] -> R1 = R1 - 12*R3, R2 = R2 - 3*R3 ->>

    [tex]\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)[/tex] -> R3 - R3 - 8*R2 ->>

    [tex]\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)[/tex] -> R1 = R1 - 24*R3, R2 = R2 - 20*R3 ->>

    [tex]\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)[/tex] -> R3 = 23*R3 ->>

    [tex]\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)[/tex]

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


    Edit: Ahhh thanks, matt, missed a step when copying from paper :rofl:
     
    Last edited: Mar 16, 2005
  15. Mar 16, 2005 #14

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

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

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yep, but then again, the matrix is invertible if and only if the determinant is invertible. :smile:
     
  17. Mar 16, 2005 #16
    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 :/
     
  18. Mar 16, 2005 #17

    cronxeh

    User Avatar
    Gold Member

    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}
    4 & 9 & 15\\
    15 & 17 & 6\\
    24 & 0 & 17
    \end{array}\right)}}
    [/tex][tex]\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)[/tex] ->>

    [tex]\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)[/tex]

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

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


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

    [tex]\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)[/tex] ->>

    [tex]\left(\begin{array}{abcdef}
    1 & 0 & 0 \\
    0 & 1 & 0\\
    0 & 0 & 1
    \end{array}\right)[/tex]
     
    Last edited: Mar 16, 2005
  19. Mar 16, 2005 #18

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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
  20. Mar 16, 2005 #19

    cronxeh

    User Avatar
    Gold Member

    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
     
  21. Mar 17, 2005 #20
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Finding the inverse of matrices
  1. Inverse of Matrices (Replies: 3)

Loading...