Samuelson–Berkowitz algorithm

Short description: Method for matrix characteristic polynomials

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 n×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)×(n−1) principal submatrix.

Let A0 be an n×n matrix partitioned so that

A0=[a1,1RCA1]

The first principal submatrix of A0 is the (n−1)×(n−1) matrix A1. Associate with A0 the (n+1)×n Toeplitz matrix T0 defined by

T0=[1−a1,1]

if A0 is 1×1,

T0=[10−a1,11−RC−a1,1]

if A0 is 2×2, and in general

T0=[1000⋯−a1,1100⋯−RC−a1,110⋯−RA1C−RC−a1,11⋯−RA12C−RA1C−RC−a1,1⋯⋮⋮⋮⋮⋱]

That is, all super diagonals of T0 consist of zeros, the main diagonal consists of ones, the first subdiagonal consists of −a1,1 and the kth subdiagonal consists of −RA1k−2C.

The algorithm is then applied recursively to A1, producing the Toeplitz matrix T1 times the characteristic polynomial of A2, etc. Finally, the characteristic polynomial of the 1×1 matrix An−1 is simply Tn−1. The Samuelson–Berkowitz algorithm then states that the vector v defined by

v=T0T1T2⋯Tn−1

contains the coefficients of the characteristic polynomial of A0.

Because each of the Ti may be computed independently, the algorithm is highly parallelizable.

## References

* 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

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Samuelson–Berkowitz_algorithm&oldid=3990857"