The ForwardSubstitute function applies the forward substitution described by the lower 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 lower triangular form, or that only the lower triangular part is relevant and the upper triangular part of A is completely ignored.

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

Application of forward substitution requires that m is prime, but in some cases it can be computed if m is composite. If it cannot be computed for m composite, an error message is returned.

The diagflag parameter is a boolean that indicates if the diagonal of the lower triangular Matrix is considered to be the identity (true), or used in the forward substitution (false). This option is most useful when applying forward substitution from a compact LU decomposition (see LUDecomposition), where the diagonal of the lower triangular factor is the identity, and is not explicitly stored.

The ForwardSubstitute function is used as one of the steps in the LUApply function.

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

$\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}j\le i\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& 0& 0& 0\\ 96& 10& 0& 0\\ 86& 58& 36& 0\\ 80& 22& 44& 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{ForwardSubstitute}\left(p\,A\,X\,\mathrm{false}\right)\:$

$X$

$\left[\begin{array}{cc}94& 32\\ 4& 82\\ 75& 34\\ 94& 58\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\&comma;\mathrm{Matrix}\left(4\&comma;4\&comma;\left(i\&comma;j\right)\mapsto \mathbf{if}j<i\mathbf{then}\mathrm{rand}\left(\right)\mathbf{else}0\mathbf{end}\mathbf{if}\right)\&comma;\mathrm{float}\left[8\right]\right)\&colon;$

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

$A,B$

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

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

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

$X$

$\left[\begin{array}{c}57.\\ 22.\\ 35.\\ 25.\end{array}\right]$

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

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