The BackwardSubstitute function applies the backward substitution described by the upper triangular part of the square mod m Matrix A to the mod m Matrix or Vector B.

Note: It is assumed that A is in upper triangular form, or that only the upper triangular part is relevant, as the lower triangular part of A is ignored.

The mod m Matrix or Vector B must have the same number of rows as there are columns of A.

Application of backward substitution requires that m is a prime, but in some cases it can be computed when m is composite. In cases where it cannot be computed for m composite, a descriptive error message is returned.

The BackwardSubstitute function is most often used in combination with LUDecomposition, and is used in LUApply.

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

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

$p≔97$

$p≔97$

$A≔\mathrm{Mod}\left(p\,\mathrm{Matrix}\left(4\,4\,\left(i\,j\right)\mapsto \mathbf{if}i\le j\mathbf{then}\mathrm{rand}\left(\right)\mathbf{else}0\mathbf{end}\mathbf{if}\right)\,\mathrm{integer}\left[\right]\right)\:$

$B≔\mathrm{Mod}\left(p\,\mathrm{Matrix}\left(4\,2\,\left(i\,j\right)\mapsto \mathrm{rand}\left(\right)\right)\,\mathrm{integer}\left[\right]\right)\:$

$A,B$

$\left[\begin{array}{cccc}77& 96& 10& 86\\ 0& 58& 36& 80\\ 0& 0& 22& 44\\ 0& 0& 0& 39\end{array}\right],\left[\begin{array}{cc}60& 39\\ 43& 12\\ 55& 2\\ 24& 71\end{array}\right]$

$X≔\mathrm{Copy}\left(p\,B\right)\:$

$\mathrm{BackwardSubstitute}\left(p\,A\,X\right)\:$

$X$

$\left[\begin{array}{cc}94& 46\\ 88& 12\\ 5& 22\\ 23& 64\end{array}\right]$

$\mathrm{Multiply}\left(p\,A\,X\right)-B$

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

$p≔97$

$p≔97$

$A≔\mathrm{Mod}\left(p\,\mathrm{Matrix}\left(4\,4\,\left(i\,j\right)\mapsto \mathbf{if}i\le j\mathbf{then}\mathrm{rand}\left(\right)\mathbf{else}0\mathbf{end}\mathbf{if}\right)\,\mathrm{float}\left[8\right]\right)\:$

$B≔\mathrm{Mod}\left(p\,\mathrm{Vector}\left[\mathrm{column}\right]\left(4\,i\mapsto \mathrm{rand}\left(\right)\right)\,\mathrm{float}\left[8\right]\right)\:$

$A,B$

$\left[\begin{array}{cccc}45.& 29.& 21.& 48.\\ 0.& 7.& 33.& 57.\\ 0.& 0.& 65.& 16.\\ 0.& 0.& 0.& 93.\end{array}\right],\left[\begin{array}{c}96.\\ 71.\\ 44.\\ 70.\end{array}\right]$

$X≔\mathrm{Copy}\left(p\,B\right)\:$

$\mathrm{BackwardSubstitute}\left(p\,A\,X\right)\:$

$X$

$\left[\begin{array}{c}78.\\ 67.\\ 2.\\ 31.\end{array}\right]$

$\mathrm{Multiply}\left(p\,A\,X\right)-B$

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