Editing Toeplitz matrix

{{Short description|Matrix with shifting rows}}
In [[linear algebra]], a '''Toeplitz matrix''' or '''diagonal-constant matrix''', named after [[Otto Toeplitz]], is a [[matrix (mathematics)|matrix]] in which each descending diagonal from left to right is constant. For instance, the following matrix is a Toeplitz matrix:

:<math>\qquad\begin{bmatrix}
a & b & c & d & e \\
f & a & b & c & d \\
g & f & a & b & c \\
h & g & f & a & b \\
i & h & g & f & a 
\end{bmatrix}.</math>

Any <math>n \times n</math> matrix <math>A</math> of the form

:<math>A = \begin{bmatrix}
  a_0 & a_{-1}   & a_{-2} & \cdots & \cdots & a_{-(n-1)} \\
  a_1 & a_0      & a_{-1} & \ddots &        & \vdots \\
  a_2 & a_1      & \ddots & \ddots & \ddots & \vdots \\ 
 \vdots & \ddots & \ddots & \ddots & a_{-1} & a_{-2} \\
 \vdots &        & \ddots & a_1    & a_0    & a_{-1} \\
a_{n-1} & \cdots & \cdots & a_2    & a_1    & a_0
\end{bmatrix}</math>

is a '''Toeplitz matrix'''. If the <math>i,j</math> element of <math>A</math> is denoted <math>A_{i,j}</math> then we have
:<math>A_{i,j} = A_{i+1,j+1} = a_{i-j}.</math>

A Toeplitz matrix is not necessarily [[Square matrix|square]].

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

==Properties==
* An <math>n\times n</math> Toeplitz matrix may be defined as a matrix <math>A</math> where <math>A_{i,j}=c_{i-j}</math>, for constants <math>c_{1-n},\ldots,c_{n-1}</math>. The [[set (mathematics)|set]] of <math>n\times n</math> Toeplitz matrices is a [[linear subspace|subspace]] of the [[vector space]] of <math>n\times n</math> matrices (under matrix addition and scalar multiplication).
* Two Toeplitz matrices may be added in <math>O(n)</math> time (by storing only one value of each diagonal) and [[matrix multiplication|multiplied]] in <math>O(n^2)</math> time.
* Toeplitz matrices are [[persymmetric matrix|persymmetric]]. [[Symmetric matrix|Symmetric]] Toeplitz matrices are both [[centrosymmetric matrix|centrosymmetric]] and [[bisymmetric matrix|bisymmetric]].
* Toeplitz matrices are also closely connected with [[Fourier series]], because the [[multiplication operator]] by a [[trigonometric polynomial]], [[compression (functional analysis)|compressed]] to a finite-dimensional space, can be represented by such a matrix. Similarly, one can represent linear convolution as multiplication by a Toeplitz matrix.
* Toeplitz matrices commute [[asymptotic analysis|asymptotically]]. This means they [[Diagonalizable matrix|diagonalize]] in the same [[basis (linear algebra)|basis]] when the row and column dimension tends to infinity.

* For symmetric Toeplitz matrices, there is the decomposition

::<math>\frac{1}{a_0} A = G G^\operatorname{T} - (G - I)(G - I)^\operatorname{T}</math>

:where <math>G</math> is the lower triangular part of <math>\frac{1}{a_0} A</math>.

* The [[inverse matrix|inverse]] of a [[nonsingular matrix|nonsingular]] symmetric Toeplitz matrix has the representation

::<math>A^{-1} = \frac{1}{\alpha_0} (B B^\operatorname{T} - C C^\operatorname{T})</math>

:where <math>B</math> and <math>C</math> are [[triangular matrix|lower triangular]] Toeplitz matrices and <math>C</math> is a strictly lower triangular matrix.<ref>{{harvnb|Mukherjee | Maiti |1988}}</ref>

== Discrete convolution ==
The [[convolution]] operation can be constructed as a matrix multiplication, where one of the inputs is converted into a Toeplitz matrix. For example, the convolution of <math> h </math> and <math> x </math> can be formulated as:

:<math>
        y = h \ast x =
            \begin{bmatrix}
                h_1 & 0 & \cdots & 0 & 0 \\
                h_2 & h_1 &      & \vdots & \vdots \\
                h_3 & h_2 & \cdots & 0 & 0 \\
                \vdots & h_3 & \cdots & h_1 & 0 \\
                h_{m-1} & \vdots & \ddots & h_2 & h_1 \\
                h_m & h_{m-1} &      & \vdots & h_2 \\
                0 & h_m & \ddots & h_{m-2} & \vdots \\
                0 & 0 & \cdots & h_{m-1} & h_{m-2} \\
                \vdots & \vdots &        & h_m & h_{m-1} \\
                0 & 0 & 0 & \cdots & h_m
            \end{bmatrix}
            \begin{bmatrix}
                x_1 \\
                x_2 \\
                x_3 \\
                \vdots \\
                x_n
            \end{bmatrix}
</math>

: <math> y^T =
            \begin{bmatrix}
                h_1 & h_2 & h_3 & \cdots & h_{m-1} & h_m
            \end{bmatrix}
            \begin{bmatrix}
                x_1 & x_2 & x_3 & \cdots & x_n & 0 & 0 & 0& \cdots & 0 \\
                0 & x_1 & x_2 & x_3 & \cdots & x_n & 0 & 0 & \cdots & 0 \\
                0 & 0 & x_1 & x_2 & x_3 & \ldots & x_n & 0  & \cdots & 0 \\
                \vdots &    & \vdots & \vdots & \vdots &    & \vdots & \vdots  & & \vdots \\
                0 & \cdots & 0 & 0 & x_1 & \cdots & x_{n-2} & x_{n-1} & x_n & 0 \\
                0 & \cdots & 0 & 0 & 0 & x_1 & \cdots & x_{n-2} & x_{n-1} & x_n
            \end{bmatrix}.
</math>

This approach can be extended to compute [[autocorrelation]], [[cross-correlation]], [[moving average]] etc.

==Infinite Toeplitz matrix==
{{Main|Toeplitz operator}}
A bi-infinite Toeplitz matrix (i.e. entries indexed by <math>\mathbb Z\times\mathbb Z</math>) <math>A</math> induces a [[linear operator]] on <math>\ell^2</math>.

:<math>
A=\begin{bmatrix}
       & \vdots & \vdots & \vdots & \vdots \\
\cdots & a_0 & a_{-1} & a_{-2} & a_{-3} & \cdots \\
\cdots & a_1 & a_0 &  a_{-1} & a_{-2} & \cdots   \\
\cdots & a_2 & a_1 & a_0 & a_{-1} & \cdots  \\
\cdots & a_3 & a_2 & a_1 & a_0 & \cdots \\
       & \vdots  & \vdots & \vdots & \vdots
\end{bmatrix}.
 
</math>

The induced operator is [[bounded operator|bounded]] if and only if the coefficients of the Toeplitz matrix <math>A</math> are the Fourier coefficients of some [[Essential range|essentially bounded]] function <math>f</math>.

In such cases, <math>f</math> is called the '''symbol''' of the Toeplitz matrix <math>A</math>, and the spectral norm of the Toeplitz matrix <math>A</math> coincides with the <math>L^\infty</math> norm of its symbol. The [[mathematical proof|proof]] can be found as Theorem 1.1 of Böttcher and Grudsky.<ref>{{harvnb|Böttcher|Grudsky|2012}}</ref>

==See also==

* [[Circulant matrix]], a square Toeplitz matrix with the additional property that <math>a_i=a_{i+n}</math>
* [[Hankel matrix]], an "upside down" (i.e., row-reversed) Toeplitz matrix
* {{annotated link|Szegő limit theorems}}
* {{annotated link|Toeplitz operator}}

==Notes==
{{Reflist}}

==References==
{{refbegin}}
*{{citation | last1 = Bojanczyk | first1 = A. W. | last2 = Brent | first2 = R. P. | last3 = de Hoog | first3 = F. R. | last4 = Sweet | first4 = D. R. | year = 1995 | title = On the stability of the Bareiss and related Toeplitz factorization algorithms | journal = [[SIAM Journal on Matrix Analysis and Applications]] | volume = 16 | pages = 40–57 | doi = 10.1137/S0895479891221563| arxiv = 1004.5510 | s2cid = 367586 }}
*{{citation|first1=Albrecht| last1= Böttcher| first2=Sergei M. | last2= Grudsky|title=Toeplitz Matrices, Asymptotic Linear Algebra, and Functional Analysis|url=https://books.google.com/books?id=Dmr0BwAAQBAJ&pg=PA1|year=2012|publisher=Birkhäuser|isbn=978-3-0348-8395-5}}
*{{citation | first= R. P. | last= Brent | author-link=Richard P. Brent | year= 1999 | contribution= Stability of fast algorithms for structured linear systems| title= Fast Reliable Algorithms for Matrices with Structure | editor1-first= T. | editor1-last= Kailath | editor2-first= A. H. | editor2-last=Sayed |  publisher= [[Society for Industrial and Applied Mathematics|SIAM]] | pages=103–116|doi=10.1137/1.9781611971354.ch4| hdl= 1885/40746 | s2cid= 13905858 | hdl-access= free }}
*{{citation|last1=Chan |first1=R. H.-F.| last2= Jin| first2= X.-Q. | year=2007 | title= An Introduction to Iterative Toeplitz Solvers | publisher= [[Society for Industrial and Applied Mathematics|SIAM]]|doi=10.1137/1.9780898718850|isbn=978-0-89871-636-8 }}
*{{citation | last1 = Chandrasekeran | first1 = S. | last2 = Gu | first2 = M. | last3 = Sun | first3 = X. | last4 = Xia | first4 = J. | last5 = Zhu | first5 = J. | year = 2007 | title = A superfast algorithm for Toeplitz systems of linear equations | journal = [[SIAM Journal on Matrix Analysis and Applications]] | volume = 29 | issue = 4| pages = 1247–66 | doi = 10.1137/040617200| citeseerx = 10.1.1.116.3297 }}
*{{citation | last1 = Chen | first1 = W. W. | last2 = Hurvich | first2 = C. M. | last3 = Lu | first3 = Y. | year = 2006 | title = On the correlation matrix of the discrete Fourier transform and the fast solution of large Toeplitz systems for long-memory time series | journal = [[Journal of the American Statistical Association]] | volume = 101 | issue = 474| pages = 812–822 | doi = 10.1198/016214505000001069| citeseerx = 10.1.1.574.4394 | s2cid = 55893963 }}
*{{citation | last=Hayes | first=Monson H.|title= Statistical digital signal processing and modeling | year = 1996 | publisher = Wiley | isbn = 0-471-59431-8}}
*{{citation | last1 = Krishna | first1 = H. | last2=Wang | first2= Y. | title = The Split Levinson Algorithm is weakly stable | journal = [[SIAM Journal on Numerical Analysis]] | volume = 30 | issue = 5 | pages = 1498–1508 | year = 1993 | url = http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SJNAAM000030000005001498000001&idtype=cvips&gifs=yes | doi = 10.1137/0730078| url-access = subscription }}
*{{citation| last=Monahan | first= J. F. | year=2011 | title=Numerical Methods of Statistics | publisher= [[Cambridge University Press]] |isbn=978-1-139-08211-2 |doi=10.1017/CBO9780511977176}}
*{{citation| last1=Mukherjee | first1= Bishwa Nath | first2= Sadhan Samar | last2= Maiti | year= 1988 | title=On some properties of positive definite Toeplitz matrices and their possible applications | journal= [[Linear Algebra and Its Applications]] | volume= 102 | pages= 211–240 | doi= 10.1016/0024-3795(88)90326-6 | url= https://core.ac.uk/download/pdf/82070573.pdf| doi-access= free }}
*{{citation|last1=Press | first1=W. H. | last2= Teukolsky | first2= S. A. | last3= Vetterling | first3= W. T. | last4= Flannery | first4= B. P. | year=2007 | title= Numerical Recipes: The Art of Scientific Computing | edition= 3rd | publisher= [[Cambridge University Press]] | isbn= 978-0-521-88068-8| title-link=Numerical Recipes }}
*{{citation | last = Stewart | first = M. | year = 2003 | title = A superfast Toeplitz solver with improved numerical stability | journal = [[SIAM Journal on Matrix Analysis and Applications]] | volume = 25 | issue = 3| pages = 669–693 | doi = 10.1137/S089547980241791X | s2cid = 15717371 }}
*{{citation | last1 = Yang | first1 = Zai | last2 = Xie | first2 = Lihua | last3 = Stoica | first3 = Petre | year = 2016 | title = Vandermonde decomposition of multilevel Toeplitz matrices with application to multidimensional super-resolution | journal = [[IEEE Transactions on Information Theory]] | volume = 62 | issue = 6 | pages = 3685–3701 | doi = 10.1109/TIT.2016.2553041 | arxiv = 1505.02510 | s2cid = 6291005 }}
{{refend}}

==Further reading==
{{refbegin}}
*{{citation | last = Bareiss | first = E. H. | year = 1969 | title = Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices | journal = [[Numerische Mathematik]] | volume = 13 | issue = 5| pages = 404–424 | doi = 10.1007/BF02163269 | s2cid = 121761517 }}
*{{citation | first1= O. | last1=  Goldreich | first2= A. | last2= Tal | author1-link= Oded Goldreich | title= Matrix rigidity of random Toeplitz matrices | journal= Computational Complexity | year= 2018 | volume= 27 | issue= 2 | pages= 305–350 | doi= 10.1007/s00037-016-0144-9 | s2cid= 253641700 }}
*{{citation |author-link=Gene H. Golub |last=Golub |first=G. H. |author2-link=Charles F. Van Loan |last2=van Loan |first2=C. F. |date=1996 |title=Matrix Computations |publisher=[[Johns Hopkins University Press]] |at=§4.7—Toeplitz and Related Systems |isbn=0-8018-5413-X |oclc=34515797 }}
*{{citation |last=Gray |first=R. M. |url=http://ee.stanford.edu/~gray/toeplitz.pdf |title=Toeplitz and Circulant Matrices: A Review |publisher=Now Publishers |doi=10.1561/0100000006}}
*{{citation | last1 =Noor | first1 = F. | last2= Morgera | first2= S. D. | year = 1992 | title = Construction of a Hermitian Toeplitz matrix from an arbitrary set of eigenvalues | journal = [[IEEE Transactions on Signal Processing]] | volume = 40 | issue=8 | pages= 2093–4 |  doi = 10.1109/78.149978 | bibcode= 1992ITSP...40.2093N }}
*{{citation | title=Structured Matrices and Polynomials: unified superfast algorithms | first=Victor Y. | last=Pan | author-link=Victor Pan | publisher=[[Birkhäuser]] | year=2001 | isbn=978-0817642402 }}
*{{citation| first1= Ke | last1= Ye |author2-link=Lek-Heng Lim | first2=Lek-Heng | last2= Lim | title= Every matrix is a product of Toeplitz matrices | journal= [[Foundations of Computational Mathematics#Publications|Foundations of Computational Mathematics]] | year= 2016 |  volume=16 | issue= 3 | pages= 577–598 | doi= 10.1007/s10208-015-9254-z | arxiv= 1307.5132 | s2cid= 254166943 }}
{{refend}}

{{Matrix classes}}
{{Authority control}}

[[Category:Matrices (mathematics)]]