Samuelson–Berkowitz algorithm

In mathematics, the Samuelson–Berkowitz algorithm efficiently computes the characteristic polynomial of an ${\displaystyle n\times n}${\displaystyle 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.

The Samuelson–Berkowitz algorithm applied to a matrix ${\displaystyle A}${\displaystyle A} produces a vector whose entries are the coefficient of the characteristic polynomial of ${\displaystyle A}${\displaystyle A}. It computes this coefficients vector recursively as the product of a Toeplitz matrix and the coefficients vector an ${\displaystyle (n-1)\times (n-1)}${\displaystyle (n-1)\times (n-1)} principal submatrix.

Let ${\displaystyle A_{0}}${\displaystyle A_{0}} be an ${\displaystyle n\times n}${\displaystyle n\times n} matrix partitioned so that

${\displaystyle A_{0}=\left[{\begin{array}{c|c}a_{1,1}&R\\\hline C&A_{1}\end{array}}\right]}${\displaystyle A_{0}=\left[{\begin{array}{c|c}a_{1,1}&R\\\hline C&A_{1}\end{array}}\right]}

The first principal submatrix of ${\displaystyle A_{0}}${\displaystyle A_{0}} is the ${\displaystyle (n-1)\times (n-1)}${\displaystyle (n-1)\times (n-1)} matrix ${\displaystyle A_{1}}${\displaystyle A_{1}}. Associate with ${\displaystyle A_{0}}${\displaystyle A_{0}} the ${\displaystyle (n+1)\times n}${\displaystyle (n+1)\times n} Toeplitz matrix ${\displaystyle T_{0}}${\displaystyle T_{0}} defined by

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

if ${\displaystyle A_{0}}${\displaystyle A_{0}} is ${\displaystyle 1\times 1}${\displaystyle 1\times 1},

${\displaystyle T_{0}=\left[{\begin{array}{c c}1&0\\-a_{1,1}&1\\-RC&-a_{1,1}\end{array}}\right]}${\displaystyle T_{0}=\left[{\begin{array}{c c}1&0\\-a_{1,1}&1\\-RC&-a_{1,1}\end{array}}\right]}

if ${\displaystyle A_{0}}${\displaystyle A_{0}} is ${\displaystyle 2\times 2}${\displaystyle 2\times 2}, and in general

${\displaystyle T_{0}=\left[{\begin{array}{c c c c c}1&0&0&0&\cdots \\-a_{1,1}&1&0&0&\cdots \\-RC&-a_{1,1}&1&0&\cdots \\-RA_{1}C&-RC&-a_{1,1}&1&\cdots \\-RA_{1}^{2}C&-RA_{1}C&-RC&-a_{1,1}&\cdots \\\vdots &\vdots &\vdots &\vdots &\ddots \end{array}}\right]}${\displaystyle T_{0}=\left[{\begin{array}{c c c c c}1&0&0&0&\cdots \\-a_{1,1}&1&0&0&\cdots \\-RC&-a_{1,1}&1&0&\cdots \\-RA_{1}C&-RC&-a_{1,1}&1&\cdots \\-RA_{1}^{2}C&-RA_{1}C&-RC&-a_{1,1}&\cdots \\\vdots &\vdots &\vdots &\vdots &\ddots \end{array}}\right]}

That is, all super diagonals of ${\displaystyle T_{0}}${\displaystyle T_{0}} consist of zeros, the main diagonal consists of ones, the first subdiagonal consists of ${\displaystyle -a_{1,1}}${\displaystyle -a_{1,1}} and the ${\displaystyle k}${\displaystyle k}th subdiagonal consists of ${\displaystyle -RA_{1}^{k-2}C}${\displaystyle -RA_{1}^{k-2}C}.

The algorithm is then applied recursively to ${\displaystyle A_{1}}${\displaystyle A_{1}}, producing the Toeplitz matrix ${\displaystyle T_{1}}${\displaystyle T_{1}} times the characteristic polynomial of ${\displaystyle A_{2}}${\displaystyle A_{2}}, etc. Finally, the characteristic polynomial of the ${\displaystyle 1\times 1}${\displaystyle 1\times 1} matrix ${\displaystyle A_{n-1}}${\displaystyle A_{n-1}} is simply ${\displaystyle T_{n-1}}${\displaystyle T_{n-1}}. The Samuelson–Berkowitz algorithm then states that the vector ${\displaystyle v}${\displaystyle v} defined by

${\displaystyle v=T_{0}T_{1}T_{2}\cdots T_{n-1}}${\displaystyle v=T_{0}T_{1}T_{2}\cdots T_{n-1}}

contains the coefficients of the characteristic polynomial of ${\displaystyle A_{0}}${\displaystyle A_{0}}.

Because each of the ${\displaystyle T_{i}}${\displaystyle T_{i}} may be computed independently, the algorithm is highly parallelizable.

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

• Linear algebra
• Polynomials
• Numerical linear algebra

• Articles with short description
• Short description is different from Wikidata
• Articles needing translation from German Wikipedia