Samuelson–Berkowitz algorithm

In mathematics, the Samuelson–Berkowitz algorithm efficiently computes the characteristic polynomial of an $n\times n$ matrix who entries may be elements of any unital commutative ring without zero divisors.

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 as a recursive product of Toeplitz matrices based on the principal submatrices of $A$

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

A_{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)\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}{c c}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}{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 $T_{0}$ consist of zeros, the main diagonal consists of $1$ s, the first subdiagonal consists of $-a_{1,1}$ and the $k$ th subdiagonal consists of $-RA_{1}^{k-2}C$ .

The Toeplitz matrix $T_{1}$ is the Toeplitz matrix associated with the first principal submatrix $A_{1}$ , and so on. 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}$ .

References

^[1] ^[2] ^[3]

↑ Cook, Stephen and Soltys, Michael. The Proof Complexity of Linear Algebra. 1993
↑ S.J. Berkowitz, On computing the determinant in small parallel time using a small number of processors, ACM, Information Processing Letters 18, 1984, pp. 147–150
↑ M. Keber, Division-Free computation of sub-resultants using Bezout matrices, Tech. Report MPI-I-2006-1-006, Saarbrucken, 2006

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.