LinearAlgebra[Generic] - Maple Programming Help

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

LinearAlgebra[Generic]

 CharacteristicPolynomial
 compute the characteristic polynomial of a square Matrix

 Calling Sequence CharacteristicPolynomial[R](A) CharacteristicPolynomial[R](A,x) CharacteristicPolynomial[R](A,output=factored) CharacteristicPolynomial[R](A,output=expanded) CharacteristicPolynomial[R](A,method=Berkowitz) CharacteristicPolynomial[R](A,method=Hessenberg)

Parameters

 R - the domain of computation x - name of the variable A - square Matrix of values in R

Description

 • 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
 • A must be a square (n x n) Matrix of values from R.
 • The optional parameter x must be a name.
 • CharacteristicPolynomial[R](A) returns a Vector V of dimension n+1 of values in R containing 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].
 • CharacteristicPolynomial[R](A,x) returns the characteristic polynomial as a Maple expression in the variable x. This option should only be used if the data type for R is compatible with Maple's * operator. For example, if the elements of R are represented by Vectors, or Arrays, then this option should not be used because Vector([1,2,3])*x is simplified to Vector([x,2*x,3*x]).
 • The optional argument output=... specifies the form of the output. In the case output=expanded, the characteristic polynomial is returned as one Vector encoding the characteristic polynomial in expanded form. In the case output=factored, the characteristic polynomial is returned as a sequence of the form m, [v1, v2, ...] where m is a non-negative integer, and v1, v2, ... are Vectors of elements of R representing (not necessarily irreducible) factors of the characteristic polynomial. The integer m represents the factor x^m. The implementation looks for diagonal blocks and computes the characteristic polynomial of each block separately.
 • The optional argument method=... specifies the algorithm to be used. The option method=Berkowitz directs the code to use the Berkowitz algorithm, which uses O(n^4) arithmetic operations in R. The option method=Hessenberg directs the code to use the Hessenberg algorithm, which uses O(n^3) arithmetic operations in R but requires R to be a field, i.e., the following operation must be defined:
 R[/]: a procedure for dividing two elements of R
 If method=... is not given, and the operation R[/] is defined, then the Hessenberg algorithm is used, otherwise the Berkowitz algorithm is used.

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{CharacteristicPolynomial}[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)
 > $C≔\mathrm{CharacteristicPolynomial}[Z]\left(A,x\right)$
 ${C}{:=}{{x}}^{{3}}{-}{9}{}{{x}}^{{2}}{+}{21}{}{x}{-}{5}$ (4)
 > $n,C≔\mathrm{CharacteristicPolynomial}[Z]\left(A,\mathrm{output}=\mathrm{factored}\right)$
 ${n}{,}{C}{:=}{0}{,}\left[\left[\begin{array}{r}{1}\\ {-}{5}\end{array}\right]{,}\left[\begin{array}{r}{1}\\ {-}{4}\\ {1}\end{array}\right]\right]$ (5)
 > ${x}^{n}\left(x+{{C}_{1}}_{2}\right)\left({x}^{2}+{{C}_{2}}_{2}x+{{C}_{2}}_{3}\right)$
 $\left({x}{-}{5}\right){}\left({{x}}^{{2}}{-}{4}{}{x}{+}{1}\right)$ (6)
 > $\mathrm{CharacteristicPolynomial}[Z]\left(A,x,\mathrm{output}=\mathrm{factored}\right)$
 $\left({x}{-}{5}\right){}\left({{x}}^{{2}}{-}{4}{}{x}{+}{1}\right)$ (7)
 > ${Q}_{\mathrm{0}},{Q}_{\mathrm{1}},{Q}_{\mathrm{+}},{Q}_{\mathrm{-}},{Q}_{\mathrm{*}},{Q}_{\mathrm{/}},{Q}_{\mathrm{=}}≔0,1,\mathrm{+},\mathrm{-},\mathrm{*},\mathrm{/},\mathrm{=}:$
 > $A≔\mathrm{Matrix}\left(\left[\left[2,-7,-3,4\right],\left[1,-3,-4,5\right],\left[0,0,5,-7\right],\left[0,0,0,0\right]\right]\right)$
 ${A}{:=}\left[\begin{array}{rrrr}{2}& {-}{7}& {-}{3}& {4}\\ {1}& {-}{3}& {-}{4}& {5}\\ {0}& {0}& {5}& {-}{7}\\ {0}& {0}& {0}& {0}\end{array}\right]$ (8)
 > $n,C≔\mathrm{CharacteristicPolynomial}[Q]\left(A,\mathrm{output}=\mathrm{factored}\right)$
 ${n}{,}{C}{:=}{1}{,}\left[\left[\begin{array}{r}{1}\\ {-}{5}\end{array}\right]{,}\left[\begin{array}{r}{1}\\ {1}\\ {1}\end{array}\right]\right]$ (9)
 > ${x}^{n}\left(x+{{C}_{1}}_{2}\right)\left({x}^{2}+{{C}_{2}}_{2}x+{{C}_{2}}_{3}\right)$
 ${x}{}\left({x}{-}{5}\right){}\left({{x}}^{{2}}{+}{x}{+}{1}\right)$ (10)
 > $C≔\mathrm{CharacteristicPolynomial}[Q]\left(A\right)$
 ${C}{:=}\left[\begin{array}{r}{1}\\ {-}{4}\\ {-}{4}\\ {-}{5}\\ {0}\end{array}\right]$ (11)
 > $⟨{x}^{4}|{x}^{3}|{x}^{2}|x|1⟩\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}.\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}C$
 ${{x}}^{{4}}{-}{4}{}{{x}}^{{3}}{-}{4}{}{{x}}^{{2}}{-}{5}{}{x}$ (12)