imported>David Eppstein: more specific short description

2025-05-28T04:59:38Z

more specific short description

New page

{{Short description|Method for matrix characteristic polynomials}}
{{Expand German|Algorithmus von Samuelson-Berkowitz|date=July 2020}}
In mathematics, the '''Samuelson–Berkowitz algorithm''' efficiently computes the [[characteristic polynomial]] of an <math>n\times n</math> 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 <math>A</math> produces a vector whose entries are the coefficient of the characteristic polynomial of <math>A</math>. It computes this coefficients vector recursively as the product of a [[Toeplitz matrix]] and the coefficients vector an <math>(n-1)\times(n-1)</math> [[Submatrix#Submatrix|principal submatrix]].

Let <math>A_0</math> be an <math>n\times n</math> matrix partitioned so that

:<math> A_0 = \left[ \begin{array}{c|c}
a_{1,1} & R \\ \hline
C & A_1
\end{array} \right] </math>

The ''first principal submatrix'' of <math>A_0</math> is the <math>(n-1)\times(n-1)</math> matrix <math>A_1</math>. Associate with <math>A_0</math> the <math>(n+1)\times n</math> [[Toeplitz matrix]] <math>T_0</math>
defined by

:<math> T_0 = \left[ \begin{array}{c}
1 \\
-a_{1,1}
\end{array} \right] </math>
if <math>A_0</math> is <math>1\times 1</math>,

:<math> T_0 = \left[ \begin{array}{c c}
1 & 0 \\
-a_{1,1} & 1 \\
-RC & -a_{1,1}
\end{array} \right] </math>
if <math>A_0</math> is <math>2\times 2</math>,
and in general

:<math> 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_1C & -RC & -a_{1,1} & 1 & \cdots\\
-RA_1^2C & -RA_1C & -RC & -a_{1,1} & \cdots\\
\vdots & \vdots & \vdots & \vdots & \ddots
\end{array} \right] </math>

That is, all super diagonals of <math>T_0</math> consist of zeros, the main diagonal consists of ones, the first subdiagonal consists of <math>-a_{1,1}</math> and the <math>k</math>th subdiagonal
consists of <math>-RA_1^{k-2}C</math>.

The algorithm is then applied recursively to <math>A_1</math>, producing the Toeplitz matrix <math>T_1</math> times the characteristic polynomial of <math>A_2</math>, etc. Finally, the characteristic polynomial of the <math>1\times 1</math> matrix <math>A_{n-1}</math> is simply <math>T_{n-1}</math>. The Samuelson–Berkowitz algorithm then states that the vector <math>v</math> defined by
:<math> v=T_0 T_1 T_2\cdots T_{n-1} </math>
contains the coefficients of the characteristic polynomial of <math>A_0</math>.

Because each of the <math>T_i</math> may be computed independently, the algorithm is highly [[Parallel algorithm|parallelizable]].

==References==
* {{cite journal |first=Stuart J. |last=Berkowitz |title=On computing the determinant in small parallel time using a small number of processors |journal=Information Processing Letters |volume=18 |issue=3 |date=30 March 1984 |pages=147–150 |doi=10.1016/0020-0190(84)90018-8}}
* {{cite journal |last2=Cook |first2=Stephen |last1=Soltys |first1=Michael |title=The Proof Complexity of Linear Algebra |journal=Annals of Pure and Applied Logic |volume=130 |issue=1–3 |date=December 2004 |pages=277–323 |doi=10.1016/j.apal.2003.10.018 |citeseerx=10.1.1.308.6521 |url=http://prof.msoltys.com/wp-content/uploads/2015/04/soltys-cook-apal.pdf}}
*{{cite tech report |first=Michael |last=Kerber |title=Division-Free computation of sub-resultants using Bezout matrices |id=Tech. Report MPI-I-2006-1-006 |publisher=Max-Planck-Institut für Informatik |location=Saarbrucken |date=May 2006 |url=https://pure.mpg.de/pubman/faces/ViewItemOverviewPage.jsp?itemId=item_1819171 |format=PS}}

{{DEFAULTSORT:Samuelson-Berkowitz algorithm}}
[[Category:Linear algebra]]
[[Category:Polynomials]]
[[Category:Numerical linear algebra]]

Samuelson–Berkowitz algorithm - Revision history

imported>David Eppstein: more specific short description