# Finite fields: Compute the inverse of a matrix

I am working with finite fields in Python. I have a matrix containing polynomials, each polynomial is represented as an integer. For example, the polynomial x^3 + x + 1 is represented as 11, because:

x^3 + x + 1 ==> (1,0,1,1) ==> (8,0,2,1) ==> 8 + 0 + 2 + 1 ==> 11


Given a matrix, for example:

6, 2, 1
7, 0, 4
1, 7, 3


How can I compute the inverse of a matrix in Python (or pseudo-code) ? I have already implemented the following functions (for polynomials, not matrices of polynomials): add(), sub(), mul(), div(), inv()

• The algorithm you learned in Linear Algebra works over any field. You augment the matrix and then perform elementary row operations - arranging $1$ and $0$s to appear at the right places. Only this time the arithmetic on the entries is done using the functions you implemented yourself instead of the built-in floating point/single/double/whatever operations. Here I handled an example. That field was easy, because its arithmetic was just modular arithmetic. But you already have the proper substitutes for those! Aug 17, 2017 at 5:01
• @JyrkiLahtonen How do I arrange 1 and 0s to appear at the right places? Is there an algorithm to do that though? Aug 17, 2017 at 5:14
• @JyrkiLahtonen Would this work if I used my arithmetic operations? stackoverflow.com/questions/32114054/… ? Aug 17, 2017 at 5:21
• Divide/multiply entire rows by constants, add multiples of a row to another, swap two rows. Aug 17, 2017 at 5:22
• Sure, with 3x3 matrices you can just use the formula with determinants and cofactors. However, for larger matrices using Gaussian elimination becomes progressively faster. It is a case of polynomial vs. exponential computational complexity. Aug 17, 2017 at 5:25