LinearAlgebra[Generic] - Maple Programming Help

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

LinearAlgebra[Generic]

 BerkowitzAlgorithm
 apply the Berkowitz algorithm to a square Matrix

 Calling Sequence BerkowitzAlgorithm[R](A)

Parameters

 R - a table or module, the domain of computation A - square Matrix of values in R

Description

 • Given an n x n Matrix A of values from a commutative ring R, BerkowitzAlgorithm[R](A) returns a Vector V of dimension n+1 of values in R with the coefficients of the characteristic polynomial of A.
 • The characteristic polynomial is the polynomial V[1]*x^n + V[2]*x^(n-1) + ... + V[n]*x + V[n+1].
 • The Berkowitz algorithm does O(n^4) multiplications and additions in R.
 • The (indexed) parameter R, which specifies the domain of computation, a commutative ring, must be a Maple table/module which has the following values/exports:
 R[0] : a constant for the zero of the ring R
 R[1] : a constant for the (multiplicative) identity of R
 R[+] : a procedure for adding elements of R (nary)
 R[-] : a procedure for negating and subtracting elements of R (unary and binary)
 R[*] : a procedure for multiplying elements of R (binary and commutative)
 R[=] : a boolean procedure for testing if two elements of R are equal

Examples

 > $\mathrm{with}\left(\mathrm{LinearAlgebra}[\mathrm{Generic}]\right):$
 > ${Z}_{\mathrm{0}},{Z}_{\mathrm{1}},{Z}_{\mathrm{+}},{Z}_{\mathrm{-}},{Z}_{\mathrm{*}},{Z}_{\mathrm{=}}≔0,1,\mathrm{+},\mathrm{-},\mathrm{*},\mathrm{=}:$
 > $A≔\mathrm{Matrix}\left(\left[\left[2,1,4\right],\left[3,2,1\right],\left[0,0,5\right]\right]\right)$
 ${A}{:=}\left[\begin{array}{rrr}{2}& {1}& {4}\\ {3}& {2}& {1}\\ {0}& {0}& {5}\end{array}\right]$ (1)
 > $C≔\mathrm{BerkowitzAlgorithm}[Z]\left(A\right)$
 ${C}{:=}\left[\begin{array}{r}{1}\\ {-}{9}\\ {21}\\ {-}{5}\end{array}\right]$ (2)
 > $⟨{x}^{3}|{x}^{2}|x|1⟩\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}.\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}C$
 ${{x}}^{{3}}{-}{9}{}{{x}}^{{2}}{+}{21}{}{x}{-}{5}$ (3)