Editing Toeplitz matrix (section)

==Solving a Toeplitz system==
A matrix equation of the form

:<math>Ax = b</math>

is called a '''Toeplitz system''' if <math>A</math> is a Toeplitz matrix.  If <math>A</math> is an <math>n \times n</math> Toeplitz matrix, then the system has at most only 
<math>2n-1</math> unique values, rather than <math>n^2</math>. We might therefore expect that the solution of a Toeplitz system would be easier, and indeed that is the case.

Toeplitz systems can be solved by algorithms such as the [[Schur class#Schur algorithm|Schur algorithm]] or the [[Levinson recursion|Levinson algorithm]] in [[Big O notation#Family of Bachmann–Landau notations|<math>O(n^2)</math>]] time.<ref>{{harvnb|Press| Teukolsky| Vetterling| Flannery| 2007 | loc= [http://apps.nrbook.com/empanel/index.html?pg=96 §2.8.2&mdash;Toeplitz matrices]}}</ref><ref>{{harvnb|Hayes|1996|loc=Chapter 5.2.6}}</ref>  Variants of the latter have been shown to be weakly stable (i.e. they exhibit [[numerical stability]] for [[Condition number|well-conditioned]] [[system of linear equations|linear systems]]).<ref>{{harvnb|Krishna | Wang |1993}}</ref>  The algorithms can also be used to find the [[determinant]] of a Toeplitz matrix in [[Big O notation|<math>O(n^2)</math>]] time.<ref>{{harvnb|Monahan |2011 | loc= §4.5&mdash;Toeplitz systems}}</ref>

A Toeplitz matrix can also be decomposed (i.e. factored) in [[Big O notation|<math>O(n^2)</math> time]].<ref>{{harvnb|Brent |1999}}</ref>  The Bareiss algorithm <!--this is not ''the'' [[Bareiss algorithm]] --> for an [[LU decomposition]] is stable.<ref>{{harvnb|Bojanczyk|Brent|de Hoog|Sweet| 1995}}</ref>  An LU decomposition gives a quick method for solving a Toeplitz system, and also for computing the determinant.