View source for Toeplitz matrix

{{Short description|Matrix with equal values along diagonals}}
In [[Linear algebra|linear algebra]], a '''Toeplitz matrix''' or '''diagonal-constant matrix''', named after [[Biography:Otto Toeplitz|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|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|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.

==General 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|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|multiplication operator]] by a [[Trigonometric polynomial|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 of a 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|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|autocorrelation]], [[Cross-correlation|cross-correlation]], [[Moving average|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]] is easy to establish and can be found as Theorem 1.1 of.<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}}

==Notes==
{{Reflist}}

==References==
*{{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 |  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= 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= 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–1266 | 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 = [[Organization:Journal of the American Statistical Association|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 = John Wiley & Son | 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= {{wipe|Cambridge University Press}} }}
*{{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= Third | publisher= {{wipe|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 }}

==Further reading==
*{{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 |  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 }}
*[[Biography:Gene H. Golub|Golub G. H.]], [[Biography:Charles F. Van Loan|van Loan C. F.]] (1996), ''Matrix Computations'' (Johns Hopkins University Press) §4.7&mdash;Toeplitz and Related Systems
*Gray R. M., ''[http://ee.stanford.edu/~gray/toeplitz.pdf Toeplitz and Circulant Matrices: A Review]'' ([http://www.nowpublishers.com 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 = [[Engineering:IEEE Transactions on Signal Processing|IEEE Transactions on Signal Processing]] | volume = 40 | issue=8 | pages= 2093–2094 |  doi = 10.1109/78.149978 | bibcode= 1992ITSP...40.2093N }}
*{{citation | title=Structured Matrices and Polynomials: unified superfast algorithms | first=Victor Y. | last=Pan |  publisher=Birkhäuser | year=2001 | isbn=978-0817642402 }}
*{{citation| first1= Ke | last1= Ye | first2=Lek-Heng | last2= Lim | title= Every matrix is a product of Toeplitz matrices | journal= 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 }}

{{Matrix classes}}

[[Category:Matrices]]

{{Sourceattribution|Toeplitz matrix}}