LinearAlgebra[Modular] - Maple Programming Help

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

LinearAlgebra[Modular]

 IntegerCharacteristicPolynomial
 computation of the characteristic polynomial of an integer matrix using modular methods

 Calling Sequence IntegerCharacteristicPolynomial(A, lambda)

Parameters

 A - square matrix with integer entries lambda - variable to use for output characteristic polynomial

Description

 • The IntegerCharacteristicPolynomial function computes the characteristic polynomial for a square Matrix with integer entries. This is a programmer level function, and it does not perform argument checking. Thus, argument checking must be handled external to this function.
 Note: The IntegerCharacteristicPolynomial routine uses a probabilistic approach that achieves great gains for structured systems. Information on controlling the probabilistic behavior can be found in EnvProbabilistic.
 • This command is part of the LinearAlgebra[Modular] package, so it can be used in the form IntegerCharacteristicPolynomial(..) only after executing the command with(LinearAlgebra[Modular]).  However, it can always be used in the form LinearAlgebra[Modular][IntegerCharacteristicPolynomial](..).

Examples

 > $\mathrm{with}\left({\mathrm{LinearAlgebra}}_{\mathrm{Modular}}\right):$
 > $M≔\mathrm{Matrix}\left(\left[\left[2,1,3\right],\left[4,3,1\right],\left[-2,1,-3\right]\right]\right)$
 ${M}{≔}\left[\begin{array}{ccc}{2}& {1}& {3}\\ {4}& {3}& {1}\\ {-2}& {1}& {-3}\end{array}\right]$ (1)
 > $\mathrm{IntegerCharacteristicPolynomial}\left(M,x\right)$
 ${{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{-}{8}{}{x}{-}{20}$ (2)
 > $\mathrm{LinearAlgebra}:-\mathrm{CharacteristicPolynomial}\left(M,x\right)$
 ${{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{-}{8}{}{x}{-}{20}$ (3)

This function is provided as a high-efficiency function for computation of characteristic polynomials for larger matrices. For example:

 > $M≔\mathrm{LinearAlgebra}:-\mathrm{RandomMatrix}\left(50,50,\mathrm{density}=0.5,\mathrm{generator}=-99..99,\mathrm{outputoptions}=\left[\mathrm{datatype}=\mathrm{integer}\right]\right)$
  (4)
 > $\mathrm{tt}≔\mathrm{time}\left(\right):$
 > $\mathrm{p1}≔\mathrm{IntegerCharacteristicPolynomial}\left(M,x\right):$
 > $\mathrm{t1}≔\mathrm{time}\left(\right)-\mathrm{tt}$
 ${\mathrm{t1}}{≔}{0.016}$ (5)
 > $\mathrm{_EnvDisableModular}≔\mathrm{true}:$
 > $\mathrm{tt}≔\mathrm{time}\left(\right):$
 > $\mathrm{p2}≔\mathrm{LinearAlgebra}:-\mathrm{CharacteristicPolynomial}\left(M,x\right):$
 > $\mathrm{t2}≔\mathrm{time}\left(\right)-\mathrm{tt}$
 ${\mathrm{t2}}{≔}{0.530}$ (6)
 > $\mathrm{expand}\left(\mathrm{p1}-\mathrm{p2}\right)$
 ${0}$ (7)

Speed-up factor:

 > $\frac{\mathrm{t2}}{\mathrm{t1}}$
 ${33.12500000}$ (8)