Function Repository Resource:

# LinearAlgebraMod

Perform matrix operations over a finite field

Contributed by: Daniel Lichtblau
 ResourceFunction["LinearAlgebraMod"][op,mat,p] performs the operation op on matrix mat using prime modulus p. ResourceFunction["LinearAlgebraMod"][LinearSolve,mat,rhs,p] solves mat.x ==rhs for x, modulo p. ResourceFunction["LinearAlgebraMod"][CharacteristicPolynomial,mat,t,p] computes the characteristic polynomial for square matrix mat using t as the polynomial variable. ResourceFunction["LinearAlgebraMod"][op] represents an operator form that can be applied to matrix and modulus arguments. ResourceFunction["LinearAlgebraMod"][op,p] represents an operator form, with the operation and modulus both specified, that can be applied to a matrix.

## Details and Options

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.

## Examples

### Basic Examples (11)

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 73=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]=

### Scope (2)

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]=

### Properties and Relations (2)

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]=

### Possible Issues (2)

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]=

## Version History

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