The CharacteristicPolynomial function computes the characteristic polynomial of a matrix mod m. Note that the matrix A need not have entries in the positive range $0..m-1$, as the routine needs to make a copy of the matrix for the computation, and does so using Mod. Upon successful completion, the characteristic polynomial of A mod m in lambda is returned.

A number of different algorithms and implementations are in use, each with significantly different efficiency, so it is important to describe these here.

If m is a prime number with fewer than 100 digits (the digit limitation is present only to guarantee that the primality check is not too expensive) then the Hessenberg algorithm is used. This is a reduction-like routine, in which the matrix is 'reduced' to Hessenberg form, and the characteristic polynomial is computed from this form.

Furthermore, if the prime is sufficiently small so that the Modular package can work with a hardware datatype (either integer[] or float[8]), then an efficient external routine is used for the computation, making it quite fast.

In the event that the modulus m is not prime, or greater than 100 digits in length, the Berkowitz algorithm is used. Unlike the Hessenberg implementation, the Berkowitz implementation uses no external code, so it is noticeably slower for comparable problems, as demonstrated in the examples.

This command is part of the LinearAlgebra[Modular] package, so it can be used in the form CharacteristicPolynomial(..) only after executing the command with(LinearAlgebra[Modular]).  However, it can always be used in the form LinearAlgebra[Modular][CharacteristicPolynomial](..).

$\mathrm{with}\left(\mathrm{LinearAlgebra}\left[\mathrm{Modular}\right]\right)\:$

$A≔\mathrm{Matrix}\left(30\,30\,\left(i\,j\right)\mapsto \mathrm{rand}\left(\right)\right)$

$\mathrm{t0}≔\mathrm{time}\left(\right)\:$

$\mathrm{p0}≔\mathrm{LinearAlgebra}:-\mathrm{CharacteristicPolynomial}\left(A\,x\right)\:$

$\mathrm{t0}≔\mathrm{time}\left(\right)-\mathrm{t0}$

$\mathrm{t0}≔0.031$

$\mathrm{m1}≔\mathrm{ithprime}\left(4600\right)$

$\mathrm{m1}≔44201$

$\mathrm{tH}≔\mathrm{time}\left(\right)\:$

$\mathrm{p1}≔\mathrm{CharacteristicPolynomial}\left(\mathrm{m1}\,A\,x\right)$

$\mathrm{p1}≔x^{30}+2002x^{29}+26760x^{28}+39582x^{27}+40328x^{26}+17238x^{25}+38348x^{24}+11836x^{23}+15733x^{22}+29600x^{21}+29719x^{20}+9058x^{19}+29063x^{18}+33642x^{17}+28407x^{16}+27842x^{15}+14164x^{14}+18577x^{13}+28084x^{12}+2630x^{11}+19981x^{10}+32617x^9+29073x^8+7564x^7+6983x^6+4578x^5+22718x^4+10812x^3+41753x^2+36640x+43117$

$\mathrm{tH}≔\mathrm{time}\left(\right)-\mathrm{tH}$

$\mathrm{tH}≔0.010$

$\mathrm{modp}\left(\mathrm{Expand}\left(\mathrm{p0}-\mathrm{p1}\right)\,\mathrm{m1}\right)$

$0$

$\mathrm{m2}≔\mathrm{m1}-1$

$\mathrm{m2}≔44200$

$\mathrm{tB}≔\mathrm{time}\left(\right)\:$

$\mathrm{p2}≔\mathrm{CharacteristicPolynomial}\left(\mathrm{m2}\,A\,x\right)$

$\mathrm{p2}≔x^{30}+37365x^{29}+4931x^{28}+43039x^{27}+35328x^{26}+26584x^{25}+23190x^{24}+27442x^{23}+41208x^{22}+38734x^{21}+19681x^{20}+7132x^{19}+14062x^{18}+31571x^{17}+43180x^{16}+6873x^{15}+2753x^{14}+18263x^{13}+9875x^{12}+13378x^{11}+29095x^{10}+20935x^9+2151x^8+1739x^7+6988x^6+26015x^5+15981x^4+38044x^3+4421x^2+12865x+30584$

$\mathrm{tB}≔\mathrm{time}\left(\right)-\mathrm{tB}$

$\mathrm{tB}≔0.091$

$\mathrm{modp}\left(\mathrm{Expand}\left(\mathrm{p0}-\mathrm{p2}\right)\,\mathrm{m2}\right)$

$0$

$\frac{\mathrm{tB}}{\mathrm{tH}}$

$9.100000000$