Results 1 to 10 of 10

Math Help - Inverse of a matrix in GL(r,Zn)

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    26

    Inverse of a matrix in GL(r,Zn)

    I want to find the inverse of a matrix in GL(r,Zn). (as you are aware r is rank of matrix and GL is a closed linear group of invertible matrices). The matrices are all modulo of the product of two prime numbers say 7 and 11. So the modulus is 77. Please explain with a simple 2 x 2 example how to find the inverse. Thanks in advance...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    17
    If you know how to find a matrix inverse using gaussian elimination, this is going to be a piece of cake! For \mathbb{Z}_n, you perform gaussian elimination on the matrix but instead of dividing you will multiply by the inverse of the element in question. Then after you perform calculations you will just mod out the modulus.

    Let A be your matrix with entries in \mathbb{Z}_5:

    \left[<br />
\begin{array}{cc}<br /> <br />
4 & 1 \\<br />
3 & 3<br /> <br />
\end{array}\right]<br />

    The determinant of this matrix is just 4.3 - 1.3 = 12 - 3 = 9 \equiv 4 \pmod{5} and is thus non-zero. Our matrix A is thus invertible.

    Set it up as for Gaussian elimination

    \left[<br />
\begin{array}{cc|cc}<br /> <br />
4 & 1 & 1 & 0\\<br />
3 & 3 & 0 & 1<br /> <br />
\end{array}\right]<br />

    The inverse of 4 in \mathbb{Z}_5 is 4 itself and the inverse of 3 is 2 so we can multiply each row by each of these respectively to get

    \left[<br />
\begin{array}{cc|cc}<br /> <br />
4.4 & 4.1 & 4.1 & 2.0\\<br />
2.3 & 2.3 & 2.0 & 2.1<br /> <br />
\end{array}\right] \equiv \left[<br />
\begin{array}{cc|cc}<br /> <br />
1 & 4 & 4 & 0\\<br />
1 & 1 & 0 & 2<br /> <br />
\end{array}\right] \pmod 5<br />

    Add -1 times the first row to the second to get

    [Math]\equiv \left[
    \begin{array}{cc|cc}

    1 & 4 & 4 & 0\\
    0 & -3 & -4 & 2

    \end{array}\right] \equiv \left[
    \begin{array}{cc|cc}

    1 & 4 & 4 & 0\\
    0 & 2 & 1 & 2

    \end{array}\right]\pmod 5
    [/tex]

    From here on you multiply the 2nd row by the inverse of 2, which is 3. Then subtract 4 times the second row times from the first

    [Math]\equiv \left[
    \begin{array}{cc|cc}

    1 & 4 & 4 & 0\\
    0 & 1 & 3 & 1

    \end{array}\right] \equiv \left[
    \begin{array}{cc|cc}

    1 & 0 & 4-4.3 & -4.1\\
    0 & 1 & 3 & 1

    \end{array}\right] \equiv \left[
    \begin{array}{cc|cc}

    1 & 0 & 2 & 1\\
    0 & 1 & 3 & 1

    \end{array}\right]\pmod 5
    [/tex]

    And that should be your inverse!(unless i've made a technical error)

    EDIT: Lets perform a check!

    <br />
\left[<br />
\begin{array}{cc}<br /> <br />
 4 & 1\\<br />
 3 & 3<br /> <br />
\end{array}\right]\left[<br />
\begin{array}{cc}<br /> <br />
 2 & 1\\<br />
 3 & 1<br /> <br />
\end{array}\right] = \left[<br />
\begin{array}{cc}<br /> <br />
 4.2+1.3 & 4.1+1.1\\<br />
 3.2+3.3 & 3.3+3.3<br /> <br />
\end{array}\right] = \left[<br />
\begin{array}{cc}<br /> <br />
 11 & 5\\<br />
 15 & 6<br /> <br />
\end{array}\right] \equiv \left[<br />
\begin{array}{cc}<br /> <br />
 1 & 0\\<br />
 0 & 1<br /> <br />
\end{array}\right] \pmod{5}<br /> <br />
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2010
    Posts
    26
    Quote Originally Posted by Vlasev View Post
    If you know how to find a matrix inverse using gaussian elimination, this is going to be a piece of cake! For \mathbb{Z}_n, you perform gaussian elimination on the matrix but instead of dividing you will multiply by the inverse of the element in question. Then after you perform calculations you will just mod out the modulus.

    Let A be your matrix with entries in \mathbb{Z}_5:

    \left[<br />
\begin{array}{cc}<br /> <br />
4 & 1 \\<br />
3 & 3<br /> <br />
\end{array}\right]<br />

    The determinant of this matrix is just 4.3 - 1.3 = 12 - 3 = 9 \equiv 4 \pmod{5} and is thus non-zero. Our matrix A is thus invertible.

    Set it up as for Gaussian elimination

    \left[<br />
\begin{array}{cc|cc}<br /> <br />
4 & 1 & 1 & 0\\<br />
3 & 3 & 0 & 1<br /> <br />
\end{array}\right]<br />

    The inverse of 4 in \mathbb{Z}_5 is 4 itself and the inverse of 3 is 2 so we can multiply each row by each of these respectively to get

    \left[<br />
\begin{array}{cc|cc}<br /> <br />
4.4 & 4.1 & 4.1 & 2.0\\<br />
2.3 & 2.3 & 2.0 & 2.1<br /> <br />
\end{array}\right] \equiv \left[<br />
\begin{array}{cc|cc}<br /> <br />
1 & 4 & 4 & 0\\<br />
1 & 1 & 0 & 2<br /> <br />
\end{array}\right] \pmod 5<br />

    Add -1 times the first row to the second to get

    [LaTeX ERROR: Convert failed]

    From here on you multiply the 2nd row by the inverse of 2, which is 3. Then subtract 4 times the second row times from the first

    [LaTeX ERROR: Convert failed]

    And that should be your inverse!(unless i've made a technical error)

    EDIT: Lets perform a check!

    <br />
\left[<br />
\begin{array}{cc}<br /> <br />
 4 & 1\\<br />
 3 & 3<br /> <br />
\end{array}\right]\left[<br />
\begin{array}{cc}<br /> <br />
 2 & 1\\<br />
 3 & 1<br /> <br />
\end{array}\right] = \left[<br />
\begin{array}{cc}<br /> <br />
 4.2+1.3 & 4.1+1.1\\<br />
 3.2+3.3 & 3.3+3.3<br /> <br />
\end{array}\right] = \left[<br />
\begin{array}{cc}<br /> <br />
 11 & 5\\<br />
 15 & 6<br /> <br />
\end{array}\right] \equiv \left[<br />
\begin{array}{cc}<br /> <br />
 1 & 0\\<br />
 0 & 1<br /> <br />
\end{array}\right] \pmod{5}<br /> <br />
    Thank you Sir....its very kind of you...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Or, you could just do it the way you do for a normal matrix, using the determinant, but you need to work out 1 over the determinant modulo n.

    For example, if \frac{1}{det(A)}=1/2 and n is 7 then you just need to find the inverse of 2 mod 7. This is 4. Therefore, \frac{1}{det(A)} is 4.

    So, to work out the inverse of \left(\begin{array}{cc} 4&1\\3&3\end{array}\right) one simply calculates the determinant, which is 12-3=9, and \frac{1}{9} = \frac{1}{4}=4 modulo 5.

    Thus, our inverse is

    4\cdot \left(\begin{array}{cc} 3&-1\\-3&4\end{array}\right)
    =4\cdot \left(\begin{array}{cc} 3&4\\2&4\end{array}\right)
    =\left(\begin{array}{cc} 12&16\\8&16\end{array}\right)
    =\left(\begin{array}{cc} 2&1\\3&1\end{array}\right)

    as required.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    17
    Swlabr, your method works great if you have already calculated the determinant for the matrix, then you just find the inverse as you said, multiply all elements and mod out. However, if you need to start from scratch on a bigger matrix, the method I showed will be the fastest to do by hand.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Vlasev View Post
    Swlabr, your method works great if you have already calculated the determinant for the matrix, then you just find the inverse as you said, multiply all elements and mod out. However, if you need to start from scratch on a bigger matrix, the method I showed will be the fastest to do by hand.
    I'm not sure I agree - Gaussian elimination is awful to do, especially on larger matrices, and mistakes can creep in easily. Anyway, you should calculate the determinant to begin with for either method!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Mar 2010
    Posts
    26
    Quote Originally Posted by Swlabr View Post
    Or, you could just do it the way you do for a normal matrix, using the determinant, but you need to work out 1 over the determinant modulo n.

    For example, if \frac{1}{det(A)}=1/2 and n is 7 then you just need to find the inverse of 2 mod 7. This is 4. Therefore, \frac{1}{det(A)} is 4.

    So, to work out the inverse of \left(\begin{array}{cc} 4&1\\3&3\end{array}\right) one simply calculates the determinant, which is 12-3=9, and \frac{1}{9} = \frac{1}{4}=4 modulo 5.

    Thus, our inverse is

    4\cdot \left(\begin{array}{cc} 3&-1\\-3&4\end{array}\right)
    =4\cdot \left(\begin{array}{cc} 3&4\\2&4\end{array}\right)
    =\left(\begin{array}{cc} 12&16\\8&16\end{array}\right)
    =\left(\begin{array}{cc} 2&1\\3&1\end{array}\right)

    as required.
    One more doubt.... The elements of the example matrix are less than 5.as in your example you take the modulus 5 a prime so obviously the elements are relatively prime. What if I take a modulus say 33. Do the elements of matrix need to be relatively prime? I Think so..for a inverse to exist GCD(a,b)=1 for integers.Is it the case for GL(r,Zn)?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    What do you mean? I mean, the element 11 is \mathbb{Z}_{33} doesn't have an inverse, and so we have linear transformations over a ring, not a field. There will be some matrices without inverses which would have inverses in \mathbb{R}. For example,

    \left(\begin{array}{cc}11 & 0\\ 0 & 3 \end{array}\right).

    Both methods are equally valid. It just depends whether you think one is faster than the other...
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    17
    jsr, the elements being non coprime doesn't guarantee an inverse as swlabr showed. However, if the determinant is non-zero you should have an inverse. For the actual gaussian elimination, it's definitely going to work if all the matrix elements are invertible elements. If not, then maybe you might get multiple solutions or none at all, i'm not sure.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Vlasev View Post
    jsr, the elements being non coprime doesn't guarantee an inverse as swlabr showed. However, if the determinant is non-zero you should have an inverse. For the actual gaussian elimination, it's definitely going to work if all the matrix elements are invertible elements. If not, then maybe you might get multiple solutions or none at all, i'm not sure.
    Your inverse must be unique, because it is an inverse (if ab=cb=1 then you can cancel the b's to get that a=c). Of course, because you are working over a ring you may have left and right inverses; these too are always unique (by the same logic), and if you have both a left and a right inverse then they must be the same element, as a_l=a_laa_r=a_r.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Finding the inverse of a matrix using it's elementary matrix?
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: March 7th 2011, 07:08 PM
  2. [SOLVED] Derivative of a matrix inverse and matrix determinant
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 24th 2011, 09:18 AM
  3. inverse matrix
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 2nd 2010, 09:13 PM
  4. 3x3 matrix inverse
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: June 1st 2010, 06:01 AM
  5. Replies: 3
    Last Post: March 1st 2010, 07:22 AM

Search Tags


/mathhelpforum @mathhelpforum