Take the 2-minute tour ×

I'd like to take the modular inverse of a matrix like [[1,2],[3,4]] mod 7 in Python. I've looked at numpy (which does matrix inversion but not modular matrix inversion) and I saw a few number theory packages online, but nothing that seems to do this relatively common procedure (at least, it seems relatively common to me).

By the way, the inverse of the above matrix is [[5,1],[5,3]] (mod 7). I'd like Python to do it for me though.

share|improve this question
Have you look at Sage? –  Alejandro Nov 27 '10 at 3:22
If you end up writing your own little piece of code. Please consider sharing it here as I think a lot of us might be interested :). –  bastijn Nov 27 '10 at 12:42

5 Answers 5

A hackish way to do it for your purposes is to take the regular inverse, which is already implemented in numpy. Now find the determinant, which is implemented in numpy. Now multiply the regular inverse by the determinant, round to integers, and then multiply everything by the determinant's multiplicative inverse (modulo your modulus). Below, I have code for finding multiplicative inverses using the generalized euclidian algorithm. This is fine as long as rounding errors don't kill you....

A less hackish way is to actually implement gaussian elimination. Here's my code using Gaussian elimination, which I wrote for my own purposes (rounding errors were an issue for me). q is the modulus, which is not necessarily prime

def generalizedEuclidianAlgorithm(a, b):
    if b > a:
        #print a, b
        return generalizedEuclidianAlgorithm(b,a);
    elif b == 0:
        return (1, 0);
        #print a,b
        (x, y) = generalizedEuclidianAlgorithm(b, a % b);
        return (y, x - (a / b) * y)

def inversemodp(a, p):
    a = a % p
    if (a == 0):
        print "a is 0 mod p"
        return 0
    (x,y) = generalizedEuclidianAlgorithm(p, a % p);
    return y % p

def identitymatrix(n):
    return [[long(x == y) for x in range(0, n)] for y in range(0, n)]

def inversematrix(matrix, q):
    n = len(matrix)
    A = np.matrix([[ matrix[j, i] for i in range(0,n)] for j in range(0, n)], dtype = long)
    Ainv = np.matrix(identitymatrix(n), dtype = long)
    for i in range(0, n):
        factor = inversemodp(A[i,i], q)
        A[i] = A[i] * factor % q
        Ainv[i] = Ainv[i] * factor % q
        for j in range(0, n):
            if (i != j):
                factor = A[j, i]
                A[j] = (A[j] - factor * A[i]) % q
                Ainv[j] = (Ainv[j] - factor * Ainv[i]) % q
                # print A, Ainv
                # print i, j, factor
    return Ainv
share|improve this answer
Thanks for the code. I'm long past needing the solution now (took the class last fall), but I appreciate your effort, as does the community I'm sure. I really like your suggestions--nice mathematical reasoning, especially on your first suggestion. For your Gaussian elimination solution, the code you supplied is about the same amount of work as the code I gave, but you could make a case that it's more elegant (though it sounds like both of us had rounding issues). Either way, great work!! Thanks for taking the time to answer the question. –  John Jul 18 '11 at 20:49
My code doesn't cause rounding issues at all. The first "hackish" suggestion does, though. No problem though! –  WuTheFWasThat Jul 26 '11 at 3:07
Thanks for this helpful module!!! –  SAbbasizadeh Oct 21 '13 at 7:53
To make this work in Python 3, replace long with int and / with // (the last one really caught me off guard). –  Oleh Prypin May 24 at 21:32

Okay...for those who care, I solved my own problem. It took me a while, but I think this works. It's probably not the most elegant, and should include some more error handling, but it works:

import numpy
import math
from numpy import matrix
from numpy import linalg

def modMatInv(A,p):       # Finds the inverse of matrix A mod p
  for i in range(0,n):
    for j in range(0,n):
  return (modInv(int(round(linalg.det(A))),p)*adj)%p

def modInv(a,p):          # Finds the inverse of a mod p, if it exists
  for i in range(1,p):
    if (i*a)%p==1:
      return i
  raise ValueError(str(a)+" has no inverse mod "+str(p))

def minor(A,i,j):    # Return matrix A with the ith row and jth column deleted
  for s in range(0,len(minor)):
    if p==i:
    for t in range(0,len(minor)):
      if q==j:
  return minor
share|improve this answer
It's not perfect yet. I just realized that int(linalg.det(A)) doesn't always give you the correct determinant. Hmm..not a big fan of numpy's determinant algorithm. For the matrices I'm dealing with (right now just small 3x3 matrices), the determinant should just be an integer! Why is numpy's det algorithm getting it wrong?? –  John Nov 27 '10 at 18:49
I'm now using int(round(linalg.det(A))). Gross. But I think it works. –  John Nov 27 '10 at 18:55
Thanks for sharing, saved it so I can use it in a later stadium :). –  bastijn Nov 28 '10 at 12:25

This little piece of code seems to do it: link

Note the comment below for a little improvement. Seems to do the correct linear algebra as far as I can see. I have never found any option in regular packages so probably taking a code snippet from the web (there are a lot more available) is the easiest approach.

share|improve this answer
Not too helpful. I need to be able to find the inverse of a matrix, not just an integer. Thanks, though! –  John Nov 26 '10 at 19:34
woops, my bad. I should read more carefully, bad habit :(. –  bastijn Nov 26 '10 at 22:07

Unfortunately numpy does not have modular arithmetic implementations. You can always code up the proposed algorithm using row reduction or determinants as demonstrated here. A modular inverse seems to be quite useful for cryptography.

share|improve this answer
Right, cryptography is correct. I'm implementing a variant of the Hill Cipher which requires this matrix operation. I'd rather not write my own modular inverse function, though I will if I can't find one online. –  John Nov 26 '10 at 19:52
Sometimes there is not free lunch :) –  whatnick Nov 27 '10 at 1:51

It can be calculated using Sage (www.sagemath.org) as

Matrix(IntegerModRing(7), [[1, 2], [3,4]]).inverse()

Although Sage is huge to install and you have to use the version of python that comes with it which is a pain.

share|improve this answer

Your Answer


