Samuelson–Berkowitz algorithm

Template:Short description Template:Expand German In mathematics, the Samuelson–Berkowitz algorithm efficiently computes the characteristic polynomial of an $n\times 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)\times (n-1)$ principal submatrix.

Let $A_0$ be an $n\times n$ matrix partitioned so that

$A_0=\left[\begin{array}{cc}{a}_{1,1}& R\\ C& A_1\end{array}\right]$

The first principal submatrix of $A_0$ is the $(n-1)\times (n-1)$ matrix $A_1$. Associate with $A_0$ the $(n+1)\times n$ Toeplitz matrix $T_0$ defined by

$T_0=\left[\begin{array}{c}1\\ -a_{1,1}\end{array}\right]$

if $A_0$ is $1\times 1$,

$T_0=\left[\begin{array}{cc}1& 0\\ -a_{1,1}& 1\\ -RC& -a_{1,1}\end{array}\right]$

if $A_0$ is $2\times 2$, and in general

$T_0=\left[\begin{array}{ccccc}1& 0& 0& 0& \cdots \\ -a_{1,1}& 1& 0& 0& \cdots \\ -RC& -a_{1,1}& 1& 0& \cdots \\ -R{A}_{1}C& -RC& -a_{1,1}& 1& \cdots \\ -R{A}_1^{2}C& -R{A}_{1}C& -RC& -a_{1,1}& \cdots \\ ⋮& ⋮& ⋮& ⋮& \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 subdiagonal consists of $-R{A}_1^{k-2}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\times 1$ matrix $A_{n-1}$ is simply $T_{n-1}$. The Samuelson–Berkowitz algorithm then states that the vector $v$ defined by

$v=T_0{T}_1{T}_2\cdots 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

• Template:Cite journal
• Template:Cite journal
• Template:Cite tech report