Samuelson–Berkowitz algorithm

You can help expand this article with text translated from the corresponding article in Deutsch. (July 2020) Click [show] for important translation instructions. View a machine-translated version of the Deutsch article. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wikipedia. Do not translate text that appears unreliable or low-quality. If possible, verify the text with references provided in the foreign-language article. You must provide copyright attribution in the edit summary accompanying your translation by providing an interlanguage link to the source of your translation. A model attribution edit summary is Content in this edit is translated from the existing Deutsch Wikipedia article at [[:de:Algorithmus von Samuelson-Berkowitz]]; see its history for attribution. You may also add the template {{Translated|de|Algorithmus von Samuelson-Berkowitz}} to the talk page. For more guidance, see Wikipedia:Translation.

In mathematics, the Samuelson–Berkowitz algorithm efficiently computes the characteristic polynomial of an ${\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}$ produces a vector whose entries are the coefficient of the characteristic polynomial of ${\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)}$ principal submatrix.

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

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

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

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

if ${\displaystyle A_0}$ is ${\displaystyle 1\times 1}$,

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

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

${\displaystyle 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 ${\displaystyle T_0}$ consist of zeros, the main diagonal consists of ones, the first subdiagonal consists of ${\displaystyle -a_{1,1}}$ and the ${\displaystyle k}$th subdiagonal consists of ${\displaystyle -R{A}_1^{k-2}C}$.

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

${\displaystyle v=T_0{T}_1{T}_2\cdots T_{n-1}}$

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

Because each of the ${\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". Annals of Pure and Applied Logic 130 (1–3): 277–323. doi:10.1016/j.apal.2003.10.018. http://prof.msoltys.com/wp-content/uploads/2015/04/soltys-cook-apal.pdf. 
• 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.

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Samuelson–Berkowitz algorithm. Read more