LinearAlgebra[Generic] - Maple Programming Help

Home : Support : Online Help : Mathematics : Linear Algebra : LinearAlgebra Package : Generic Subpackage : LinearAlgebra/Generic/GaussianElimination

LinearAlgebra[Generic]

 GaussianElimination
 perform Gaussian elimination on a Matrix
 ReducedRowEchelonForm
 compute the reduced row echelon form of a Matrix
 RREF
 compute the reduced row echelon form of a Matrix

 Calling Sequence GaussianElimination[F](A) GaussianElimination[F](A,r,d) ReducedRowEchelonForm[F](A) ReducedRowEchelonForm[F](A,r,d) ReducedRowEchelonForm[F](A,method=BareissAlgorithm) ReducedRowEchelonForm[F](A,method=GaussianElimination) RREF[F](A) RREF[F](A,r,d) RREF[F](A,method=BareissAlgorithm) RREF[F](A,method=GaussianElimination)

Parameters

 F - the domain of computation, a field A - rectangular Matrix over values in F r - name d - name

Description

 • GaussianElimination[F](A) makes a copy of the Matrix A and reduces it to row echelon form (upper triangular form) with leading ones.
 • ReducedRowEchelonForm[F](A) makes a copy of the Matrix A and reduces it to reduced row echelon form.
 • RREF is an abbreviation for ReducedRowEchelonForm
 • The (indexed) parameter F, which specifies the domain of computation, a field, must be a Maple table/module which has the following values/exports:
 F[0]: a constant for the zero of the ring F
 F[1]: a constant for the (multiplicative) identity of F
 F[+]: a procedure for adding elements of F (nary)
 F[-]: a procedure for negating and subtracting elements of F (unary and binary)
 F[*]: a procedure for multiplying two elements of F (commutative)
 F[/]: a procedure for dividing two elements of F
 F[=]: a boolean procedure for testing if two elements in F are equal
 • ReducedRowEchelonForm can use either Gaussian Elimination or the Bareiss algorithm to reduce the system to triangular form. If the Bareiss algorithm is used, the leading entries of each row are normalized to one and back substitution is performed, which avoids normalizing entries which are eliminated during back substitution.
 • The Bareiss algorithm requires the field to support exact division, i.e., it requires F to be an integral domain with the following operation:
 F[Divide]: a boolean procedure for dividing two elements of F where F[Divide](a,b,'q') outputs true if b | a and optionally assigns q the quotient such that a = b q.
 • If the method is not given and the operation F[Divide] is defined, then the Bareiss algorithm is used, otherwise Gaussian Elimination is used.

Examples

 > $\mathrm{with}\left(\mathrm{LinearAlgebra}[\mathrm{Generic}]\right):$
 > ${Q}_{\mathrm{0}},{Q}_{\mathrm{1}},{Q}_{\mathrm{+}},{Q}_{\mathrm{-}},{Q}_{\mathrm{*}},{Q}_{\mathrm{/}},{Q}_{\mathrm{=}}≔0,1,\mathrm{+},\mathrm{-},\mathrm{*},\mathrm{/},\mathrm{=}$
 ${{Q}}_{{0}}{,}{{Q}}_{{1}}{,}{{Q}}_{{\mathrm{+}}}{,}{{Q}}_{{\mathrm{-}}}{,}{{Q}}_{{\mathrm{*}}}{,}{{Q}}_{{\mathrm{/}}}{,}{{Q}}_{{\mathrm{=}}}{:=}{0}{,}{1}{,}{\mathrm{+}}{,}{\mathrm{-}}{,}{\mathrm{*}}{,}{\mathrm{/}}{,}{\mathrm{=}}$ (1)
 > $A≔\mathrm{Matrix}\left(\left[\left[1,2,3\right],\left[0,0,0\right],\left[3,2,1\right]\right]\right)$
 ${A}{:=}\left[\begin{array}{rrr}{1}& {2}& {3}\\ {0}& {0}& {0}\\ {3}& {2}& {1}\end{array}\right]$ (2)
 > $\mathrm{GaussianElimination}[Q]\left(A\right)$
 $\left[\begin{array}{rrr}{1}& {2}& {3}\\ {0}& {1}& {2}\\ {0}& {0}& {0}\end{array}\right]$ (3)
 > $\mathrm{ReducedRowEchelonForm}[Q]\left(A,'r','d'\right)$
 $\left[\begin{array}{rrr}{1}& {0}& {-}{1}\\ {0}& {1}& {2}\\ {0}& {0}& {0}\end{array}\right]$ (4)
 > $r$
 ${2}$ (5)
 > $d$
 ${0}$ (6)
 > $A≔\mathrm{Matrix}\left(\left[\left[1,2,1,0\right],\left[2,1,0,1\right]\right]\right)$
 ${A}{:=}\left[\begin{array}{rrrr}{1}& {2}& {1}& {0}\\ {2}& {1}& {0}& {1}\end{array}\right]$ (7)
 > $B≔\mathrm{GaussianElimination}[Q]\left(A\right)$
 ${B}{:=}\left[\begin{array}{cccc}{1}& {2}& {1}& {0}\\ {0}& {1}& \frac{{2}}{{3}}& {-}\frac{{1}}{{3}}\end{array}\right]$ (8)
 > $\mathrm{RREF}[Q]\left(B\right)$
 $\left[\begin{array}{cccc}{1}& {0}& {-}\frac{{1}}{{3}}& \frac{{2}}{{3}}\\ {0}& {1}& \frac{{2}}{{3}}& {-}\frac{{1}}{{3}}\end{array}\right]$ (9)