Samuelson–Berkowitz algorithm

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.

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}{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_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] 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 -RA_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==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374516742 under CC BY-SA 4.0; modifications have been made.