#jsDisabledContent { display:none; } My Account | Register | Help

Toeplitz matrix

Article Id: WHEBN0000151569
Reproduction Date:

 Title: Toeplitz matrix Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

Toeplitz matrix

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:

\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}.

Any n×n matrix A of the form

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 Ai,j, then we have

A_{i,j} = A_{i+1,j+1} = a_{i-j}.\

Contents

• Solving a Toeplitz system 1
• General properties 2
• Discrete convolution 3
• Infinite Toeplitz Matrix 4
• Notes 6
• References 7

Solving a Toeplitz system

A matrix equation of the form

Ax=b\

is called a Toeplitz system if A is a Toeplitz matrix. If A is an n\times n Toeplitz matrix, then the system has only 2n−1 degrees of freedom, rather than n2. 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 Θ(n2) 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(n2) time.[3]

A Toeplitz matrix can also be decomposed (i.e. factored) in O(n2) 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 (in finite arithmetic, i.e., given a tolerance \epsilon the exact solution is obtained within the tolerance \epsilon) than those of Bareiss and Levinson have been described in the literature.[6][7][8][9]

General properties

A Toeplitz matrix may be defined as a matrix A where Ai,j = ci−j, for constants c1−ncn−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(n2) 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.

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 and x can be formulated as:

y = h \ast 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}
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 \mathbb Z\times\mathbb Z, see below) A induces a linear operator on \ell^2.

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 is the Fourier coefficients of some essentially bounded function f.

In such cases, f is called the symbol of the Toeplitz matrix A, and the spectral norm of the Toeplitz matrix A coincides with the 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: [10]

Notes

1. ^ Press et al. 2007, §2.8.2—Toeplitz matrices
2. ^ Krishna & Wang 1993
3. ^ Monahan 2011, §4.5—Toeplitz systems
4. ^ Brent 1999
5. ^ Bojanczyk et al. 1995
6. ^ Stewart 2003
7. ^ Chen et al. 2006
8. ^ Chan & Jin 2007
9. ^ Chandrasekeran et al. 2007
10. ^ Albrecht Böttcher & Sergei M. Grudsky 2012

References

• Bareiss, E.H. (1969), "Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices",
• Bojanczyk, A.W.; Brent, R.P.; Hoog, F.R. De; Sweet, D.R. (1995), "On the stability of the Bareiss and related Toeplitz factorization algorithms",
• Brent R.P. (1999), "Stability of fast algorithms for structured linear systems", Fast Reliable Algorithms for Matrices with Structure (editors—T. Kailath, A.H. Sayed), ch.4 (SIAM).
• Chan, R. H.-F.; Jin, X.-Q. (2007), An Introduction to Iterative Toeplitz Solvers, .
• Chandrasekeran, S.; Gu, M.; Sun, X.; Xia, J.; Zhu, J. (2007), "A superfast algorithm for Toeplitz systems of linear equations",
• 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",
• 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).
• Krishna, H.; Wang, Y. (1993), "The Split Levinson Algorithm is weakly stable", .
• Monahan, J.F. (2011), Numerical Methods of Statistics, .
• Press, W.H.; Teukolsky, S.A.; Vetterling, W.T.; Flannery, B.P. (2007), .
• Stewart, M (2003), "A superfast Toeplitz solver with improved numerical stability",
• Albrecht Böttcher; Sergei M. Grudsky (2012), Toeplitz Matrices, Asymptotic Linear Algebra, and Functional Analysis, Birkhäuser, pp. 1–,
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.

Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.