Given an n x n Matrix A of values from a commutative ring R, BerkowitzAlgorithm[R](A) returns a Vector V of dimension n+1 of values in R with 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].

The Berkowitz algorithm does O(n^4) multiplications and additions in R.

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

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

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

$C≔\mathrm{BerkowitzAlgorithm}\left[Z\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$