Given an n x n Matrix A of elements in F, a field, HessenbergAlgorithm[F](A) returns a Vector V of n+1 values from F encoding the characteristic polynomial of A as V[1] x^n + V[2] x^(n-1) + .... + V[n] x + V[n+1]

The algorithm converts a copy of A into upper Hessenberg form H using O(n^3) operations in F then expands the determinant of x I - H in a further O(n^3) operations in F. The algorithm requires that F be a field and should only be used if F is finite as there is severe expression swell in computing H.

The (indexed) parameter F, which specifies the domain of computation, a field, must be a Maple table/module which has the following values/exports:

F[`0`]: a constant for the zero of the ring F

F[`1`]: a constant for the (multiplicative) identity of F

F[`+`]: a procedure for adding elements of F (nary)

F[`-`]: a procedure for negating and subtracting elements of F (unary and binary)

F[`*`]: a procedure for multiplying two elements of F (commutative)

F[`/`]: a procedure for dividing two elements of F

F[`=`]: a boolean procedure for testing if two elements in F are equal

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

$Q\left[\mathrm{`0`}\right],Q\left[\mathrm{`1`}\right],Q\left[\mathrm{`+`}\right],Q\left[\mathrm{`-`}\right],Q\left[\mathrm{`*`}\right],Q\left[\mathrm{`/`}\right],Q\left[\mathrm{`=`}\right]≔0,1,\mathrm{`+`},\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}{ccc}2& 1& 4\\ 3& 2& 1\\ 0& 0& 5\end{array}\right]$

$C≔\mathrm{HessenbergAlgorithm}\left[Q\right]\left(A\right)$

$C≔\left[\begin{array}{c}1\\ \mathrm{-9}\\ 21\\ \mathrm{-5}\end{array}\right]$

$⟨x^3\left|x^2\right|x|1⟩·C$

$x^3-9x^2+21x-5$