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()

  • 2
    $\begingroup$ 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! $\endgroup$ Aug 17, 2017 at 5:01
  • $\begingroup$ @JyrkiLahtonen How do I arrange 1 and 0s to appear at the right places? Is there an algorithm to do that though? $\endgroup$
    – dimitris93
    Aug 17, 2017 at 5:14
  • $\begingroup$ @JyrkiLahtonen Would this work if I used my arithmetic operations? stackoverflow.com/questions/32114054/… ? $\endgroup$
    – dimitris93
    Aug 17, 2017 at 5:21
  • $\begingroup$ Divide/multiply entire rows by constants, add multiples of a row to another, swap two rows. $\endgroup$ Aug 17, 2017 at 5:22
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 17, 2017 at 5:25


You must log in to answer this question.

Browse other questions tagged .