Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Samuelson–Berkowitz algorithm
open-in-new
<h2 id="description-of-the-algorithm">Description of the algorithm</h2> <p>The Samuelson–Berkowitz algorithm applied to a matrix A {\displaystyle A} produces a vector whose entries are the coefficient of the characteristic polynomial of A {\displaystyle A} . It computes this coefficients vector recursively as the product of a <a href="/facts/Toeplitz_matrix/WAjSdlaW">Toeplitz matrix</a> and the coefficients vector an ( n − 1 ) × ( n − 1 ) {\displaystyle (n-1)\times (n-1)} <a href="/facts/Submatrix/qa8FI4ko">principal submatrix</a>. </p><p>Let A 0 {\displaystyle A_{0}} be an n × n {\displaystyle n\times n} matrix partitioned so that </p> A 0 = [ a 1 , 1 R C A 1 ] {\displaystyle A_{0}=\left[{\begin{array}{c|c}a_{1,1}&R\\\hline C&A_{1}\end{array}}\right]} <p>The <i>first principal submatrix</i> of A 0 {\displaystyle A_{0}} is the ( n − 1 ) × ( n − 1 ) {\displaystyle (n-1)\times (n-1)} matrix A 1 {\displaystyle A_{1}} . Associate with A 0 {\displaystyle A_{0}} the ( n + 1 ) × n {\displaystyle (n+1)\times n} <a href="/facts/Toeplitz_matrix/WAjSdlaW">Toeplitz matrix</a> T 0 {\displaystyle T_{0}} defined by </p> T 0 = [ 1 − a 1 , 1 ] {\displaystyle T_{0}=\left[{\begin{array}{c}1\\-a_{1,1}\end{array}}\right]} <p>if A 0 {\displaystyle A_{0}} is 1 × 1 {\displaystyle 1\times 1} , </p> T 0 = [ 1 0 − a 1 , 1 1 − R C − a 1 , 1 ] {\displaystyle T_{0}=\left[{\begin{array}{c c}1&0\\-a_{1,1}&1\\-RC&-a_{1,1}\end{array}}\right]} <p>if A 0 {\displaystyle A_{0}} is 2 × 2 {\displaystyle 2\times 2} , and in general </p> T 0 = [ 1 0 0 0 ⋯ − a 1 , 1 1 0 0 ⋯ − R C − a 1 , 1 1 0 ⋯ − R A 1 C − R C − a 1 , 1 1 ⋯ − R A 1 2 C − R A 1 C − R C − a 1 , 1 ⋯ ⋮ ⋮ ⋮ ⋮ ⋱ ] {\displaystyle 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_{1}C&-RC&-a_{1,1}&1&\cdots \\-RA_{1}^{2}C&-RA_{1}C&-RC&-a_{1,1}&\cdots \\\vdots &\vdots &\vdots &\vdots &\ddots \end{array}}\right]} <p>That is, all super diagonals of T 0 {\displaystyle T_{0}} consist of zeros, the main diagonal consists of ones, the first subdiagonal consists of − a 1 , 1 {\displaystyle -a_{1,1}} and the k {\displaystyle k} th subdiagonal consists of − R A 1 k − 2 C {\displaystyle -RA_{1}^{k-2}C} . </p><p>The algorithm is then applied recursively to A 1 {\displaystyle A_{1}} , producing the Toeplitz matrix T 1 {\displaystyle T_{1}} times the characteristic polynomial of A 2 {\displaystyle A_{2}} , etc. Finally, the characteristic polynomial of the 1 × 1 {\displaystyle 1\times 1} matrix A n − 1 {\displaystyle A_{n-1}} is simply T n − 1 {\displaystyle T_{n-1}} . The Samuelson–Berkowitz algorithm then states that the vector v {\displaystyle v} defined by </p> v = T 0 T 1 T 2 ⋯ T n − 1 {\displaystyle v=T_{0}T_{1}T_{2}\cdots T_{n-1}} <p>contains the coefficients of the characteristic polynomial of A 0 {\displaystyle A_{0}} . </p><p>Because each of the T i {\displaystyle T_{i}} may be computed independently, the algorithm is highly <a href="/facts/Parallel_algorithm/nUPzEF4C">parallelizable</a>. </p> <ul><li>Berkowitz, Stuart J. (30 March 1984). "On computing the determinant in small parallel time using a small number of processors". <i>Information Processing Letters</i>. 18 (3): 147–150. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0020-0190%2884%2990018-8">10.1016/0020-0190(84)90018-8</a>.</li> <li>Soltys, Michael; Cook, Stephen (December 2004). <a href="http://prof.msoltys.com/wp-content/uploads/2015/04/soltys-cook-apal.pdf">"The Proof Complexity of Linear Algebra"</a> (PDF). <i>Annals of Pure and Applied Logic</i>. 130 (1–3): 277–323. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.308.6521">10.1.1.308.6521</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.apal.2003.10.018">10.1016/j.apal.2003.10.018</a>.</li> <li>Kerber, Michael (May 2006). <a href="https://pure.mpg.de/pubman/faces/ViewItemOverviewPage.jsp?itemId=item_1819171"><i>Division-Free computation of sub-resultants using Bezout matrices</i></a> (PS) (Technical report). Saarbrucken: Max-Planck-Institut für Informatik. Tech. Report MPI-I-2006-1-006.</li></ul>