---
title: Samuelson–Berkowitz algorithm
slug: samuelson-berkowitz-algorithm
qid: 
snapshot: enwiki-001374516742
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1374516742
tags: [22937263, 23060232, 23118434, 23603337, 26709309, 26709316]
---

# Samuelson–Berkowitz algorithm

> [!note] Provenance
> Snapshot `enwiki-001374516742` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1374516742> · Licensed CC BY-SA 4.0

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==