IntegerCharacteristicPolynomial - Maple Help

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}\left[\mathrm{Modular}\right]\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)$
 ${M}{≔}\begin{array}{c}\left[\begin{array}{ccccccccccc}{39}& {-64}& {0}& {0}& {0}& {19}& {-16}& {0}& {50}& {-3}& {\dots }\\ {-87}& {48}& {0}& {35}& {-20}& {-75}& {0}& {0}& {0}& {0}& {\dots }\\ {-48}& {0}& {-46}& {-1}& {0}& {0}& {81}& {-1}& {-5}& {0}& {\dots }\\ {0}& {0}& {56}& {-24}& {0}& {81}& {-78}& {26}& {0}& {-74}& {\dots }\\ {-62}& {7}& {73}& {2}& {13}& {0}& {41}& {-4}& {-21}& {90}& {\dots }\\ {-63}& {67}& {0}& {0}& {0}& {0}& {0}& {12}& {-86}& {0}& {\dots }\\ {0}& {0}& {94}& {-98}& {0}& {0}& {5}& {-60}& {0}& {58}& {\dots }\\ {-97}& {18}& {0}& {0}& {30}& {-57}& {0}& {82}& {43}& {0}& {\dots }\\ {0}& {0}& {-71}& {70}& {0}& {-54}& {0}& {0}& {-20}& {0}& {\dots }\\ {-57}& {45}& {-10}& {0}& {0}& {-46}& {-80}& {-95}& {0}& {0}& {\dots }\\ {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {}\end{array}\right]\\ \hfill {\text{50 × 50 Matrix}}\end{array}$ (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.036}$ (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}}{≔}{1.327}$ (6)
 > $\mathrm{expand}\left(\mathrm{p1}-\mathrm{p2}\right)$
 ${0}$ (7)

Speed-up factor:

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