In mathematics, the Samuelson–Berkowitz algorithm efficiently computes the characteristic polynomial of an
matrix whose entries may be elements of any unital commutative ring.
Unlike the Faddeev–LeVerrier algorithm, it performs no divisions, so may be applied to a wider range of algebraic structures.
The Samuelson–Berkowitz algorithm applied to a matrix
produces a vector whose entries are the coefficient of the characteristic polynomial of
It computes this coefficients vector recursively as the product of a Toeplitz matrix and the coefficients vector an
principal submatrix.
matrix partitioned so that The first principal submatrix of
Toeplitz matrix
, and in general That is, all super diagonals of
consist of zeros, the main diagonal consists of ones, the first subdiagonal consists of
th subdiagonal consists of
The algorithm is then applied recursively to
, producing the Toeplitz matrix
times the characteristic polynomial of
Finally, the characteristic polynomial of the
The Samuelson–Berkowitz algorithm then states that the vector
defined by contains the coefficients of the characteristic polynomial of
may be computed independently, the algorithm is highly parallelizable.