# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Perform matrix operations over a finite field

Contributed by:
Daniel Lichtblau

ResourceFunction["LinearAlgebraMod"][ performs the operation | |

ResourceFunction["LinearAlgebraMod"][LinearSolve, solves | |

ResourceFunction["LinearAlgebraMod"][CharacteristicPolynomial, computes the characteristic polynomial for square matrix | |

ResourceFunction["LinearAlgebraMod"][ represents an operator form that can be applied to matrix and modulus arguments. | |

ResourceFunction["LinearAlgebraMod"][ represents an operator form, with the operation and modulus both specified, that can be applied to a matrix. |

Allowed operations *op* include Inverse, LinearSolve, NullSpace, RowReduce, Det, CharacteristicPolynomial and MatrixRank.

When LinearSolve is the operation, a vector or second matrix must be given as the right-hand side.

The operation names can be given either as symbols or strings.

The modulus is 0 by default.

ResourceFunction["LinearAlgebraMod"] accepts an Extension option. It must be a univariate polynomial that is irreducible modulo the prime *p*, or irreducible over the rationals if the modulus is 0.

ResourceFunction["LinearAlgebraMod"] performs linear algebra over a finite field or an algebraic extension of the rationals, with an input matrix comprised of (not necessarily univariate) polynomial functions.

Start with a 2×3 polynomial matrix in two variables, one of which will be used as an algebraic extension:

In[1]:= |

The polynomial defining the extension:

In[2]:= |

Reduce to row echelon form over the finite extension field of integers mod 7 with 7^{3}=343 elements, given as :

In[3]:= |

Out[3]= |

Compute the inverse of the submatrix comprised of the first two columns:

In[4]:= |

Out[4]= |

Check that this inverse multiplied by *mat* gives the 2×2 identity matrix:

In[5]:= |

Out[5]= |

Use the last column as a right-hand side for a matrix equation:

In[6]:= |

Out[6]= |

Check the result:

In[7]:= |

Out[7]= |

Find a basis for the null space of the full matrix:

In[8]:= |

Out[8]= |

Check that it has only null vectors for *mat*:

In[9]:= |

Out[9]= |

Since there are three columns and the null space is generated by one vector, the rank must be 2:

In[10]:= |

Out[10]= |

Compute the characteristic polynomial for the matrix augmented by a row of ones:

In[11]:= |

Out[11]= |

One need not use an extension field:

In[12]:= |

In[13]:= |

Out[13]= |

Verify the inverse:

In[14]:= |

Out[14]= |

Apart from cancellation of factors, the denominators in the inverse will be constant multiples of the matrix determinant:

In[15]:= |

Out[15]= |

Use an operator form of LinearAlgebraMod:

In[16]:= |

In[17]:= |

Out[18]= |

Check the solution:

In[19]:= |

Out[19]= |

Use an operator form of LinearAlgebraMod with operation and modulus both specified:

In[20]:= |

Out[21]= |

Use a matrix for the right-hand side:

In[22]:= |

Out[1]= |

Check that first column agrees with the previous solution:

In[23]:= |

Out[23]= |

Check that the result is correct:

In[24]:= |

Out[24]= |

Define a matrix of integers:

In[25]:= |

Out[26]= |

For integer matrices, operations supported by LinearAlgebraMod are equivalent to their built-in counterparts using the Modulus option:

In[27]:= |

Out[27]= |

Symbolic linear algebra can suffer from expression swell (the phenomenon wherein outputs and/or intermediate computations get much larger than inputs).

Define a random polynomial matrix generator:

In[28]:= |

Create a random 3×3 matrix of polynomials in two variables with up to seven terms having coefficients between 0 and 70, each of which can have a degree up to 4:

In[29]:= |

Solve the system:

In[30]:= |

Out[30]= |

Check the result:

In[31]:= |

Out[31]= |

Note the difference in size between input and result:

In[32]:= |

Out[32]= |

Create a 6×6 example:

In[33]:= |

This takes significantly longer:

In[34]:= |

Out[34]= |

The factor between output and input sizes has also grown:

In[35]:= |

Out[35]= |

Also note that using the built-in LinearSolve for the non-modular case is also on the slow side, though faster than LinearAlgebraMod:

In[36]:= |

Out[36]= |

It produces a similarly large result:

In[37]:= |

Out[37]= |

The determinant can be found somewhat faster:

In[38]:= |

Out[38]= |

In[39]:= |

Out[39]= |

- 7.0.1 – 05 December 2022
- 7.0.0 – 01 September 2021

This work is licensed under a Creative Commons Attribution 4.0 International License