Samuelson–Berkowitz algorithm explained

In mathematics, the Samuelson–Berkowitz algorithm efficiently computes the characteristic polynomial of an

n x n 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.

Description of the algorithm

The Samuelson–Berkowitz algorithm applied to a matrix

A produces a vector whose entries are the coefficient of the characteristic polynomial of A . It computes this coefficients vector recursively as the product of a Toeplitz matrix and the coefficients vector an (n -1 ) x (n -1 ) principal submatrix.

Let

A _{0} be an n x n matrix partitioned so thatA _{0} = \left[ \begin{array}{c|c} a _{1,1} & R \ \hline C & A _{1} \end{array} \right]

The first principal submatrix of

A _{0} is the (n -1 ) x (n -1 ) matrix A _{1} . Associate with A _{0} the (n +1 ) x n Toeplitz matrix T _{0} defined byT _{0} = \left[ \begin{array}{c} 1 \ - a _{1,1} \end{array} \right] if A _{0} is 1 x 1 ,T _{0} = \left[ \begin{array}{c c} 1 & 0 \ - a _{1,1} & 1 \\ - RC & - a _{1,1} \end{array} \right] if A _{0} is 2 x 2 ,and in generalT _{0} = \left[ \begin{array}{c c c c c} 1 & 0 & 0 & 0 & … \ - a _{1,1} & 1 & 0 & 0 & … \\ - RC & - a _{1,1} & 1 & 0 & … \\ - RA _{1C} & - RC & - a _{1,1} & 1 & … \\ - RA ^{2 C} _{1} & - RA _{1C} & - RC & - a _{1,1} & … \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{array} \right]

That is, all super diagonals of

T _{0} consist of zeros, the main diagonal consists of ones, the first subdiagonal consists of - a _{1,1} and the k th subdiagonalconsists of - RA ^{k -2} _{1} C .

The algorithm is then applied recursively to

A _{1} , producing the Toeplitz matrix T _{1} times the characteristic polynomial of A _{2} , etc. Finally, the characteristic polynomial of the 1 x 1 matrix A _{n-1} is simply T _{n-1} . The Samuelson–Berkowitz algorithm then states that the vector v defined byv = T _{0} T _{1} T _{2 …} T _{n-1} contains the coefficients of the characteristic polynomial of A _{0} .

Because each of the

T _{i} may be computed independently, the algorithm is highly parallelizable.

References

• Stuart J. . Berkowitz . On computing the determinant in small parallel time using a small number of processors . Information Processing Letters . 18 . 3 . 30 March 1984 . 147–150 . 10.1016/0020-0190(84)90018-8.
• Cook . Stephen . Soltys . Michael . The Proof Complexity of Linear Algebra . Annals of Pure and Applied Logic . 130 . 1–3 . December 2004 . 277–323 . 10.1016/j.apal.2003.10.018 . 10.1.1.308.6521 .
• Michael . Kerber . Division-Free computation of sub-resultants using Bezout matrices . Tech. Report MPI-I-2006-1-006 . Max-Planck-Institut für Informatik . Saarbrucken . May 2006 . PS.