The LUDecomposition function computes an in-place PLU decomposition of a square mod m Matrix A placing the permutation information in pvec. Optionally, the determinant can also be computed.

Computation of an LU decomposition requires that m is a prime, but in some cases it can be computed when m is composite. If it cannot be computed for m composite, an error message returns.

The pvec parameter must be a Vector of type integer[4]/integer[8], integer, or anything, having at least $n-1$ entries, where the Matrix A is $nxn$.

If the determinant of the Matrix being decomposed is required, specify det as a name. Otherwise, specify as the value 0. On output, the name specified for det is assigned the value of the determinant.

Note: If the determinant is not required, set det to zero to avoid unnecessary calculations.

Since the computation is performed in-place, the LU decomposition is stored in compact form. On successful completion, the upper triangular Matrix is stored in the upper triangular part of A, and the lower triangular Matrix is stored in the lower triangular part of A, replacing diagonal entries with 1.

The permutation is also stored in a compact form in pvec. This vector can be interpreted as an ordered list of instructions on how to apply a permutation, where the first entry describes the row exchange required for the first row, the second describes the row exchange required for the second row, etcetera.

For example, for a $4x4$ Matrix the permutation vector must have 3 elements. If these are [1, 4, 4], this corresponds to the following exchanges in the given order: $1<=>1$, $2<=>4$, $3<=>4$.

Unlike a permutation Matrix, this format does not result in a unique representation for a permutation. For example, for a $4x4$ Matrix, the identity permutation is given by [1,2,3], [3,2,1], [2,1,3], etcetera. Use of this format makes application of the permutation (or its inverse) to a Matrix or Vector quite simple. If the permutation Matrix is required, it can be obtained through application of the Permute function on an identity Matrix.

After obtaining the LU decomposition and permutation vector, it can be applied to the right-hand side of the original system (a mod m Matrix or Vector) to obtain the solution using the LUApply function, or explicitly by using Permute, ForwardSubstitute, and then BackwardSubstitute.

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

$\mathrm{with}\left(\mathrm{LinearAlgebra}\left[\mathrm{Modular}\right]\right)\&colon;$

$p≔97$

$p≔97$

$A≔\mathrm{Mod}\left(p\&comma;\mathrm{Matrix}\left(5\&comma;5\&comma;\left(i\&comma;j\right)\mapsto \mathrm{rand}\left(\right)\right)\&comma;\mathrm{integer}\left[\right]\right)\&colon;$

$A$

$\left[\begin{array}{ccccc}77& 96& 10& 86& 58\\ 36& 80& 22& 44& 39\\ 60& 39& 43& 12& 55\\ 2& 24& 71& 45& 29\\ 21& 48& 7& 33& 57\end{array}\right]$

$\mathrm{A2}≔\mathrm{Copy}\left(p\&comma;A\right)\&colon;$

$\mathrm{pv}≔\mathrm{Vector}\left(4\right)\&colon;$

$\mathrm{LUDecomposition}\left(p\&comma;\mathrm{A2}\&comma;\mathrm{pv}\&comma;'\det '\right)\&colon;$

$\mathrm{A2},\mathrm{pv},\det$

$\left[\begin{array}{ccccc}77& 96& 10& 86& 58\\ 37& 20& 40& 63& 27\\ 94& 60& 1& 79& 64\\ 29& 56& 63& 7& 78\\ 62& 54& 40& 10& 5\end{array}\right],\left[\begin{array}{c}1\\ 2\\ 3\\ 4\end{array}\right],65$

$\mathrm{modp}\left(\mathrm{LinearAlgebra}:-\mathrm{Determinant}\left(\mathrm{Matrix}\left(5\&comma;5\&comma;\left(i\&comma;j\right)\mapsto A\left[i,j\right]\right)\right)\&comma;p\right)$

$65$

$B≔\mathrm{Mod}\left(p\&comma;\mathrm{Matrix}\left(5\&comma;2\&comma;\left(i\&comma;j\right)\mapsto \mathrm{rand}\left(\right)\right)\&comma;\mathrm{integer}\left[\right]\right)$

$B≔\left[\begin{array}{cc}65& 16\\ 93& 96\\ 71& 44\\ 70& 58\\ 25& 29\end{array}\right]$

$X≔\mathrm{Copy}\left(p\&comma;B\right)\&colon;$

$\mathrm{LUApply}\left(p\&comma;\mathrm{A2}\&comma;\mathrm{pv}\&comma;X\right)\&colon;$

$X$

$\left[\begin{array}{cc}11& 37\\ 12& 20\\ 57& 11\\ 83& 68\\ 1& 11\end{array}\right]$

$\mathrm{Multiply}\left(p\&comma;A\&comma;X\right),B$

$\left[\begin{array}{cc}65& 16\\ 93& 96\\ 71& 44\\ 70& 58\\ 25& 29\end{array}\right],\left[\begin{array}{cc}65& 16\\ 93& 96\\ 71& 44\\ 70& 58\\ 25& 29\end{array}\right]$

$p≔13\&colon;$

$A≔\mathrm{Mod}\left(13\&comma;\left[\left[0\&comma;0\&comma;12\right]\&comma;\left[12\&comma;0\&comma;3\right]\&comma;\left[1\&comma;1\&comma;1\right]\right]\&comma;\mathrm{float}\left[8\right]\right)$

$A≔\left[\begin{array}{ccc}0.& 0.& 12.\\ 12.& 0.& 3.\\ 1.& 1.& 1.\end{array}\right]$

$\mathrm{A2}≔\mathrm{Copy}\left(p\&comma;A\right)\&colon;$

$\mathrm{pv}≔\mathrm{Vector}\left(2\right)\&colon;$

$\mathrm{LUDecomposition}\left(p\&comma;\mathrm{A2}\&comma;\mathrm{pv}\&comma;0\right)\&colon;$

$\mathrm{A2},\mathrm{pv}$

$\left[\begin{array}{ccc}12.& 0.& 3.\\ 12.& 1.& 4.\\ 0.& 0.& 12.\end{array}\right],\left[\begin{array}{c}2\\ 3\end{array}\right]$

$B≔\mathrm{Mod}\left(p\&comma;\mathrm{Vector}\left(3\&comma;i\mapsto \mathrm{rand}\left(\right)\right)\&comma;\mathrm{float}\left[8\right]\right)$

$B≔\left[\begin{array}{c}5.\\ 3.\\ 5.\end{array}\right]$

$X≔\mathrm{Copy}\left(p\&comma;B\right)\&colon;$

$\mathrm{Permute}\left(p\&comma;\mathrm{pv}\&comma;X\&comma;\mathrm{true}\&comma;\mathrm{false}\right)\&colon;$

$\mathrm{ForwardSubstitute}\left(p\&comma;\mathrm{A2}\&comma;X\&comma;\mathrm{true}\right)\&colon;$

$\mathrm{BackwardSubstitute}\left(p\&comma;\mathrm{A2}\&comma;X\right)\&colon;$

$X$

$\left[\begin{array}{c}8.\\ 2.\\ 8.\end{array}\right]$

$\mathrm{Multiply}\left(p\&comma;A\&comma;X\right),B$

$\left[\begin{array}{c}5.\\ 3.\\ 5.\end{array}\right],\left[\begin{array}{c}5.\\ 3.\\ 5.\end{array}\right]$