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

# Online Help

###### All Products    Maple    MapleSim

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}[\mathrm{Modular}]\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.5em}{0.0ex}}i\le j\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{then}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{rand}\left(\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{else}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}0\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{end if}\right),{\mathrm{integer}}_{[]}\right):$
 > $B:=\mathrm{Mod}\left(p,\mathrm{Matrix}\left(4,2,\left(i,j\right)→\mathrm{rand}\left(\right)\right),{\mathrm{integer}}_{[]}\right):$
 > $A,B$
 $\left[\begin{array}{rrrr}{77}& {96}& {10}& {86}\\ {0}& {58}& {36}& {80}\\ {0}& {0}& {22}& {44}\\ {0}& {0}& {0}& {39}\end{array}\right]{,}\left[\begin{array}{rr}{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}{rr}{94}& {46}\\ {88}& {12}\\ {5}& {22}\\ {23}& {64}\end{array}\right]$ (3)
 > $\mathrm{Multiply}\left(p,A,X\right)-B$
 $\left[\begin{array}{rr}{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.5em}{0.0ex}}i\le j\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{then}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{rand}\left(\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{else}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}0\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{end if}\right),{\mathrm{float}}_{8}\right):$
 > $B:=\mathrm{Mod}\left(p,{\mathrm{Vector}}_{\mathrm{column}}\left(4,i→\mathrm{rand}\left(\right)\right),{\mathrm{float}}_{8}\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)

## Was this information helpful?

 Please add your Comment (Optional) E-mail Address (Optional) What is ? This question helps us to combat spam