LinearAlgebra[Modular] - Maple Programming Help

Home : Support : Online Help : Mathematics : Linear Algebra : LinearAlgebra Package : Modular Subpackage : LinearAlgebra/Modular/BackwardSubstitute

LinearAlgebra[Modular]

 BackwardSubstitute
 apply in-place backward substitution from an upper triangular mod m Matrix to a mod m Matrix or Vector

 Calling Sequence BackwardSubstitute(m, A, B)

Parameters

 m - modulus A - mod m upper triangular Matrix B - mod m Matrix or Vector to which to apply backward substitution

Description

 • 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](..).

Examples

Construct and solve an upper triangular system.

 > $\mathrm{with}\left(\mathrm{LinearAlgebra}\left[\mathrm{Modular}\right]\right):$
 > $p≔97$
 ${p}{≔}{97}$ (1)
 > $A≔\mathrm{Mod}\left(p,\mathrm{Matrix}\left(4,4,\left(i,j\right)↦\mathbf{if}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}i\le j\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{then}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{rand}\left(\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{else}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}0\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{if}\right),\mathrm{integer}\left[\right]\right):$
 > $B≔\mathrm{Mod}\left(p,\mathrm{Matrix}\left(4,2,\left(i,j\right)↦\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]$ (2)
 > $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]$ (3)
 > $\mathrm{Multiply}\left(p,A,X\right)-B$
 $\left[\begin{array}{cc}{0}& {0}\\ {0}& {0}\\ {0}& {0}\\ {0}& {0}\end{array}\right]$ (4)

Upper triangular with floats.

 > $p≔97$
 ${p}{≔}{97}$ (5)
 > $A≔\mathrm{Mod}\left(p,\mathrm{Matrix}\left(4,4,\left(i,j\right)↦\mathbf{if}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}i\le j\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{then}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{rand}\left(\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{else}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}0\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{if}\right),\mathrm{float}\left[8\right]\right):$
 > $B≔\mathrm{Mod}\left(p,\mathrm{Vector}\left[\mathrm{column}\right]\left(4,i↦\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]$ (6)
 > $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]$ (7)
 > $\mathrm{Multiply}\left(p,A,X\right)-B$
 $\left[\begin{array}{c}{0.}\\ {0.}\\ {0.}\\ {0.}\end{array}\right]$ (8)