The IntegerLinearSolve function constructs the rational solution(s) of a linear integer coefficient system in Matrix form. This is a programmer level function, it does not perform argument checking. Thus, argument checking must be handled external to this function.

It is possible to solve systems with an arbitrary number of augmented columns. If one augmented column is present, the output is a Vector with dimension rcol. If multiple augmented columns are present, the output is a Matrix where each column is of length rcol and represents the solution for the corresponding right-hand side vector in the augmented part of the input Matrix.

It is also possible to obtain solutions with free parameters. These free parameters represent the nullspace vectors of the input Matrix, and are output after the solution.  In this case, the output is a sequence.

Note: Regardless of the number of augmented columns, the trailing nullspace is described by Vectors with dimension rcol.

The default method is to solve the system modulo a machine-sized prime and construct rational solutions using p-adic lifting. For large linear systems or systems with large solutions this is the fastest method. The optional argument method='padic' forces the use of this method.

Alternatively, one can specify the optional argument method='chrem' and the system will be solved modulo multiple primes and the solution recovered using the Chinese remainder theorem. This method can be faster in some cases; however, it is a probabilistic approach. Information on controlling the probabilistic behavior can be found in _EnvProbabilistic.

This function is also available in LinearSolve as method='modular'.

This command is part of the LinearAlgebra[Modular] package, so it can be used in the form IntegerLinearSolve(..) only after executing the command with(LinearAlgebra[Modular]).  However, it can always be used in the form LinearAlgebra[Modular][IntegerLinearSolve](..).

$\mathrm{with}\left(\mathrm{LinearAlgebra}\left[\mathrm{Modular}\right]\right)\:$

$M≔\mathrm{Matrix}\left(\left[\left[2\,1\,3\,-1\right]\,\left[4\,3\,1\,3\right]\,\left[-2\,1\,-3\,5\right]\right]\right)$

$M≔\left[\begin{array}{cccc}2& 1& 3& \mathrm{-1}\\ 4& 3& 1& 3\\ \mathrm{-2}& 1& \mathrm{-3}& 5\end{array}\right]$

$X≔\mathrm{IntegerLinearSolve}\left(M\,3\right)$

$X≔\left[\begin{array}{c}-\frac{3}{5}\\ 2\\ -\frac{3}{5}\end{array}\right]$

$M\left[1..3,1..3\right]·X-M\left[1..3,4\right]$

$\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]$

$M≔\mathrm{Matrix}\left(\left[\left[2\,1\,3\,-1\,-2\,-5\right]\,\left[4\,3\,1\,3\,1\,3\right]\,\left[-2\,1\,-3\,5\,-3\,2\right]\right]\right)$

$M≔\left[\begin{array}{cccccc}2& 1& 3& \mathrm{-1}& \mathrm{-2}& \mathrm{-5}\\ 4& 3& 1& 3& 1& 3\\ \mathrm{-2}& 1& \mathrm{-3}& 5& \mathrm{-3}& 2\end{array}\right]$

$X≔\mathrm{IntegerLinearSolve}\left(M\,3\right)$

$X≔\left[\begin{array}{ccc}-\frac{3}{5}& \frac{5}{2}& \frac{13}{5}\\ 2& -\frac{5}{2}& -\frac{3}{2}\\ -\frac{3}{5}& -\frac{3}{2}& -\frac{29}{10}\end{array}\right]$

$M\left[1..3,1..3\right]·X-M\left[1..3,4..6\right]$

$\left[\begin{array}{ccc}0& 0& 0\\ 0& 0& 0\\ 0& 0& 0\end{array}\right]$

$M≔\mathrm{Matrix}\left(\left[\left[2\,1\,3\,-1\,-2\,-5\right]\,\left[4\,3\,1\,3\,1\,3\right]\,\left[2\,2\,-2\,4\,3\,8\right]\right]\right)$

$M≔\left[\begin{array}{cccccc}2& 1& 3& \mathrm{-1}& \mathrm{-2}& \mathrm{-5}\\ 4& 3& 1& 3& 1& 3\\ 2& 2& \mathrm{-2}& 4& 3& 8\end{array}\right]$

$X≔\left[\mathrm{IntegerLinearSolve}\left(M\,3\right)\right]$

$X≔\left[\left[\begin{array}{ccc}\mathrm{-3}& -\frac{7}{2}& \mathrm{-9}\\ 5& 5& 13\\ 0& 0& 0\end{array}\right]\,\left[\begin{array}{c}\mathrm{-4}\\ 5\\ 1\end{array}\right]\right]$

$M\left[1..3,1..3\right]·X\left[1\right]-M\left[1..3,4..6\right],M\left[1..3,1..3\right]·X\left[2\right]$

$\left[\begin{array}{ccc}0& 0& 0\\ 0& 0& 0\\ 0& 0& 0\end{array}\right],\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]$

$M≔\mathrm{Matrix}\left(\left[\left[-85\,-55\,-30\,-35\right]\,\left[97\,50\,47\,56\right]\,\left[49\,63\,-14\,-59\right]\,\left[45\,-8\,53\,92\right]\right]\right)$

$M≔\left[\begin{array}{cccc}\mathrm{-85}& \mathrm{-55}& \mathrm{-30}& \mathrm{-35}\\ 97& 50& 47& 56\\ 49& 63& \mathrm{-14}& \mathrm{-59}\\ 45& \mathrm{-8}& 53& 92\end{array}\right]$

$X≔\left[\mathrm{IntegerLinearSolve}\left(M\,4\right)\right]$

$X≔\left[\left[\begin{array}{c}\mathrm{-1}\\ 1\\ 1\\ 0\end{array}\right]\right]$

$M·X\left[1\right]$

$\left[\begin{array}{c}0\\ 0\\ 0\\ 0\end{array}\right]$

$M≔\mathrm{Matrix}\left(\left[\left[2\,1\,3\,-1\right]\,\left[4\,3\,1\,3\right]\,\left[2\,2\,-2\,5\right]\right]\right)$

$M≔\left[\begin{array}{cccc}2& 1& 3& \mathrm{-1}\\ 4& 3& 1& 3\\ 2& 2& \mathrm{-2}& 5\end{array}\right]$

$\mathrm{IntegerLinearSolve}\left(M\,3\right)$

Error, (in LinearAlgebra:-Modular:-IntegerLinearSolve) system is inconsistent