sympy
's Matrix
class supports modular inverses. Here's an example modulo 5:
from sympy import Matrix, pprint
A = Matrix([
[5,6],
[7,9]
])
#Find inverse of A modulo 26
A_inv = A.inv_mod(5)
pprint(A_inv)
#Prints the inverse of A modulo 5:
#[3 3]
#[ ]
#[1 0]
The rref
method for finding row-reduced echelon form supports a keyword iszerofunction
that indicates what entries within a matrix should be treated as zero. I believe the intended use is for numerical stability (treat small numbers as zero) although I am unsure. I have used it for modular reduction.
Here's an example modulo 5:
from sympy import Matrix, Rational, mod_inverse, pprint
B = Matrix([
[2,2,3,2,2],
[2,3,1,1,4],
[0,0,0,1,0],
[4,1,2,2,3]
])
#Find row-reduced echolon form of B modulo 5:
B_rref = B.rref(iszerofunc=lambda x: x % 5==0)
pprint(B_rref)
# Returns row-reduced echelon form of B modulo 5, along with pivot columns:
# ([1 0 7/2 0 -1], [0, 1, 3])
# [ ]
# [0 1 -2 0 2 ]
# [ ]
# [0 0 0 1 0 ]
# [ ]
# [0 0 -10 0 5 ]
That's sort of correct, except that the matrix returned by rref[0]
still has 5's in it and fractions. Deal with this by taking the mod and interpreting fractions as modular inverses:
def mod(x,modulus):
numer, denom = x.as_numer_denom()
return numer*mod_inverse(denom,modulus) % modulus
pprint(B_rref[0].applyfunc(lambda x: mod(x,5)))
#returns
#[1 0 1 0 4]
#[ ]
#[0 1 3 0 2]
#[ ]
#[0 0 0 1 0]
#[ ]
#[0 0 0 0 0]