In mathematics, the Samuelson–Berkowitz algorithm efficiently computes the

characteristic polynomial In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The chara ...

of an

n\times n

matrix whose entries may be elements of any unital

commutative ring In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not sp ...

. 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 In linear algebra, a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a matrix in which each descending diagonal from left to right is constant. For instance, the following matrix is a Toeplitz matrix: :\qquad\begin a & b ...

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
                    a_ & R \\ \hline
                    C & A_1
                    \end  \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

T_0

defined by :

T_0 = \left \begin
                    1 \\ 
                    -a_
                    \end  \right

A_0

1\times 1

, :

T_0 = \left \begin
                    1        & 0 \\ 
                    -a_ & 1 \\
                    -RC      & -a_
                    \end \right

A_0

2\times 2

, and in general :

T_0 = \left[ \begin
                    1        & 0        & 0        & 0        & \cdots\\ 
                    -a_ & 1        & 0        & 0        & \cdots\\
                    -RC      & -a_ & 1        & 0        & \cdots\\
                    -RA_1C   & -RC      & -a_ & 1        & \cdots\\
                    -RA_1^2C & -RA_1C   & -RC      & -a_ & \cdots\\
                    \vdots   & \vdots   & \vdots   & \vdots   & \ddots
                    \end  \right]

That is, all super diagonals of

T_0

consist of zeros, the main diagonal consists of ones, the first subdiagonal consists of

-a_

and the

k

th subdiagonal consists of

-RA_1^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_

is simply

T_

. The Samuelson–Berkowitz algorithm then states that the vector

v

defined by :

v=T_0 T_1 T_2\cdots T_

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

* * * {{DEFAULTSORT:Samuelson-Berkowitz algorithm Linear algebra Polynomials Numerical linear algebra