Bdtyk

In linear algebra, a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a matrix in which each descending diagonal from left to right is constant. For instance, the following matrix is a Toeplitz matrix:

[abcdefabcdgfabchgfabihgfa].{displaystyle {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&aend{bmatrix}}.}

Any n×n matrix A of the form

A=[a0a−1a−2……a−(n−1)a1a0a−1⋱⋮a2a1⋱⋱⋱⋮⋮⋱⋱⋱a−1a−2⋮⋱a1a0a−1an−1……a2a1a0]{displaystyle A={begin{bmatrix}a_{0}&a_{-1}&a_{-2}&ldots &ldots &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}&ldots &ldots &a_{2}&a_{1}&a_{0}end{bmatrix}}}

is a Toeplitz matrix. If the i,j element of A is denoted A_i,j, then we have

Ai,j=Ai+1,j+1=ai−j. {displaystyle A_{i,j}=A_{i+1,j+1}=a_{i-j}. }

A Toeplitz matrix is not necessarily square.

Solving a Toeplitz system

A matrix equation of the form

Ax=b {displaystyle Ax=b }

is called a Toeplitz system if A is a Toeplitz matrix. If A is an n×n{displaystyle ntimes n} Toeplitz matrix, then the system has only 2n−1 degrees of freedom, rather than n². 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 the Levinson algorithm in Θ(n²) time.^[1] Variants of this algorithm have been shown to be weakly stable (i.e. they exhibit numerical stability for well-conditioned linear systems).^[2] The algorithm can also be used to find the determinant of a Toeplitz matrix in O(n²) time.^[3]

A Toeplitz matrix can also be decomposed (i.e. factored) in O(n²) time.^[4] The Bareiss algorithm for an LU decomposition is stable.^[5] An LU decomposition gives a quick method for solving a Toeplitz system, and also for computing the determinant.

Algorithms that are asymptotically faster than those of Bareiss and Levinson have been described in the literature, but their accuracy cannot be relied upon.^[6][7][8][9]

General properties

A Toeplitz matrix may be defined as a matrix A where A_i,j = c_i−j, for constants c_1−n … c_n−1. The set of n×n Toeplitz matrices is a subspace of the vector space of n×n matrices under matrix addition and scalar multiplication.

Two Toeplitz matrices may be added in O(n) time and multiplied in O(n²) time.

Toeplitz matrices are persymmetric. Symmetric Toeplitz matrices are both centrosymmetric and bisymmetric.

Toeplitz matrices are also closely connected with Fourier series, because the multiplication operator by a trigonometric polynomial, 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 asymptotically. This means they diagonalize in the same basis when the row and column dimension tends to infinity.

A nonsingular Toeplitz matrix A{displaystyle A} can be factored as

A=VDU{displaystyle A=VDU}

where D{displaystyle D} is a diagonal matrix, and V{displaystyle V} and U{displaystyle U} are Vandermonde matrices: (V)ij=γj1−i{displaystyle (V)_{ij}=gamma _{j}^{1-i}}, (U)ij=γij−1{displaystyle (U)_{ij}=gamma _{i}^{j-1}}. γ1,γ2,...,γn{displaystyle gamma _{1},gamma _{2},...,gamma _{n}} are nonzero numbers.

For symmetric Toeplitz matrices, there is the decomposition

1a0A=GGT−(G−I)(G−I)T{displaystyle {frac {1}{a_{0}}}A=GG^{operatorname {T} }-(G-I)(G-I)^{operatorname {T} }}

where G{displaystyle G} is the lower triangular part of 1a0A{displaystyle {frac {1}{a_{0}}}A}.

The inverse of a nonsingular symmetric Toeplitz matrix has the representation

A−1=1α0(BBT−CCT){displaystyle A^{-1}={frac {1}{alpha _{0}}}(BB^{operatorname {T} }-CC^{operatorname {T} })}

where B{displaystyle B} and C{displaystyle C} are lower triangular Toeplitz matrices and C{displaystyle C} is a strictly lower triangular matrix.^[10]

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 h{displaystyle h} and x{displaystyle x} can be formulated as:

y=h∗x=[h10…00h2h1…⋮⋮h3h2…00⋮h3…h10hm−1⋮…h2h1hmhm−1⋮⋮h20hm…hm−2⋮00…hm−1hm−2⋮⋮⋮hmhm−1000…hm][x1x2x3⋮xn]{displaystyle y=hast x={begin{bmatrix}h_{1}&0&ldots &0&0\h_{2}&h_{1}&ldots &vdots &vdots \h_{3}&h_{2}&ldots &0&0\vdots &h_{3}&ldots &h_{1}&0\h_{m-1}&vdots &ldots &h_{2}&h_{1}\h_{m}&h_{m-1}&vdots &vdots &h_{2}\0&h_{m}&ldots &h_{m-2}&vdots \0&0&ldots &h_{m-1}&h_{m-2}\vdots &vdots &vdots &h_{m}&h_{m-1}\0&0&0&ldots &h_{m}end{bmatrix}}{begin{bmatrix}x_{1}\x_{2}\x_{3}\vdots \x_{n}end{bmatrix}}}

yT=[h1h2h3…hm−1hm][x1x2x3…xn000…00x1x2x3…xn00…000x1x2x3…xn0…0⋮⋮⋮⋮⋮…⋮⋮…00…00x1…xn−2xn−1xn⋮0…000x1…xn−2xn−1xn].{displaystyle y^{T}={begin{bmatrix}h_{1}&h_{2}&h_{3}&ldots &h_{m-1}&h_{m}end{bmatrix}}{begin{bmatrix}x_{1}&x_{2}&x_{3}&ldots &x_{n}&0&0&0&ldots &0\0&x_{1}&x_{2}&x_{3}&ldots &x_{n}&0&0&ldots &0\0&0&x_{1}&x_{2}&x_{3}&ldots &x_{n}&0&ldots &0\vdots &vdots &vdots &vdots &vdots &ldots &vdots &vdots &ldots &0\0&ldots &0&0&x_{1}&ldots &x_{n-2}&x_{n-1}&x_{n}&vdots \0&ldots &0&0&0&x_{1}&ldots &x_{n-2}&x_{n-1}&x_{n}end{bmatrix}}.}

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

Infinite Toeplitz matrix

A bi-infinite Toeplitz matrix (i.e. entries indexed by Z×Z{displaystyle mathbb {Z} times mathbb {Z} }) A{displaystyle A} induces a linear operator on ℓ2{displaystyle ell ^{2}}.

A=[…………………a0a−1a−2a−3……a1a0a−1a−2……a2a1a0a−1……a3a2a1a0…………………].{displaystyle A={begin{bmatrix}ldots &ldots &ldots &ldots &ldots &ldots \ldots &a_{0}&a_{-1}&a_{-2}&a_{-3}&ldots \ldots &a_{1}&a_{0}&a_{-1}&a_{-2}&ldots \ldots &a_{2}&a_{1}&a_{0}&a_{-1}&ldots \ldots &a_{3}&a_{2}&a_{1}&a_{0}&ldots \ldots &ldots &ldots &ldots &ldots &ldots \end{bmatrix}}.}

The induced operator is bounded if and only if the coefficients of the Toeplitz matrix A{displaystyle A} are the Fourier coefficients of some essentially bounded function f{displaystyle f}.

In such cases, f{displaystyle f} is called the symbol of the Toeplitz matrix A{displaystyle A}, and the spectral norm of the Toeplitz matrix A{displaystyle A} coincides with the L∞{displaystyle L^{infty }} norm of its symbol. The proof is easy to establish and can be found as Theorem 1.1 in the google book link:
^[11]

See also

• 
  Circulant matrix, a Toeplitz matrix with the additional property that ai=ai+n{displaystyle a_{i}=a_{i+n}}
  


• 
  Hankel matrix, a Toeplitz matrix "upside down"

Notes

References

• 
  Bojanczyk, A. W.; Brent, R. P.; de Hoog, F. R.; Sweet, D. R. (1995), "On the stability of the Bareiss and related Toeplitz factorization algorithms", SIAM Journal on Matrix Analysis and Applications, 16: 40–57, arXiv:1004.5510, doi:10.1137/S0895479891221563.mw-parser-output cite.citation{font-style:inherit}.mw-parser-output .citation q{quotes:"""""""'""'"}.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-maint{display:none;color:#33aa33;margin-left:0.3em}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}
  


• 
  Böttcher, Albrecht; Grudsky, Sergei M. (2012), Toeplitz Matrices, Asymptotic Linear Algebra, and Functional Analysis, Birkhäuser, ISBN 978-3-0348-8395-5
  


• 
  Brent, R. P. (1999), "Stability of fast algorithms for structured linear systems", in Kailath, T.; Sayed, A. H., Fast Reliable Algorithms for Matrices with Structure, SIAM, pp. 103–116
  


• 
  Chan, R. H.-F.; Jin, X.-Q. (2007), An Introduction to Iterative Toeplitz Solvers, SIAM
  


• 
  Chandrasekeran, S.; Gu, M.; Sun, X.; Xia, J.; Zhu, J. (2007), "A superfast algorithm for Toeplitz systems of linear equations", SIAM Journal on Matrix Analysis and Applications, 29 (4): 1247–1266, CiteSeerX 10.1.1.116.3297, doi:10.1137/040617200
  


• 
  Chen, W. W.; Hurvich, C. M.; Lu, Y. (2006), "On the correlation matrix of the discrete Fourier transform and the fast solution of large Toeplitz systems for long-memory time series", Journal of the American Statistical Association, 101 (474): 812–822, CiteSeerX 10.1.1.574.4394, doi:10.1198/016214505000001069
  


• 
  Krishna, H.; Wang, Y. (1993), "The Split Levinson Algorithm is weakly stable", SIAM Journal on Numerical Analysis, 30 (5): 1498–1508, doi:10.1137/0730078
  


• 
  Monahan, J. F. (2011), Numerical Methods of Statistics, Cambridge University Press
  


• 
  Mukherjee, Bishwa Nath; Maiti, Sadhan Samar (1988), "On some properties of positive definite Toeplitz matrices and their possible applications" (PDF), Linear Algebra and Its Applications, 102: 211–240, doi:10.1016/0024-3795(88)90326-6
  


• 
  Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007), Numerical Recipes: The Art of Scientific Computing (Third ed.), Cambridge University Press, ISBN 978-0-521-88068-8
  


• 
  Stewart, M. (2003), "A superfast Toeplitz solver with improved numerical stability", SIAM Journal on Matrix Analysis and Applications, 25 (3): 669–693, doi:10.1137/S089547980241791X
  

Further reading

• 
  Bareiss, E. H. (1969), "Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices", Numerische Mathematik, 13 (5): 404–424, doi:10.1007/BF02163269
  


• 
  Golub G. H., van Loan C. F. (1996), Matrix Computations (Johns Hopkins University Press) §4.7—Toeplitz and Related Systems.


• Gray R. M., Toeplitz and Circulant Matrices: A Review (Now Publishers)


• 
  Noor, F.; Morgera, S. D. (1992), "Construction of a Hermitian Toeplitz matrix from an arbitrary set of eigenvalues", IEEE Transactions on Signal Processing, 40 (8): 2093–2094, Bibcode:1992ITSP...40.2093N, doi:10.1109/78.149978
  


• 
  Pan, Victor Y. (2001), Structured Matrices and Polynomials: unified superfast algorithms, Birkhäuser, ISBN 978-0817642402
  


• 
  Ye, Ke; Lim, Lek-Heng (2016), "Every matrix is a product of Toeplitz matrices", Foundations of Computational Mathematics, 16 (3): 577–598, arXiv:1307.5132, doi:10.1007/s10208-015-9254-z