Matrix with shifting rows
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:
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
.
{\displaystyle \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}}.}
Any
n
×
n
{\displaystyle n\times n}
matrix
A
{\displaystyle A}
of the form
A
=
a
0
a
−
1
a
−
2
⋯
⋯
a
−
(
n
−
1
)
a
1
a
0
a
−
1
⋱
⋮
a
2
a
1
⋱
⋱
⋱
⋮
⋮
⋱
⋱
⋱
a
−
1
a
−
2
⋮
⋱
a
1
a
0
a
−
1
a
n
−
1
⋯
⋯
a
2
a
1
a
0
{\displaystyle 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}}}
is a Toeplitz matrix . If the
i
,
j
{\displaystyle i,j}
element of
A
{\displaystyle A}
is denoted
A
i
,
j
{\displaystyle A_{i,j}}
then we have
A
i
,
j
=
A
i
+
1
,
j
+
1
=
a
i
−
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
A
x
=
b
{\displaystyle Ax=b}
is called a Toeplitz system if
A
{\displaystyle A}
is a Toeplitz matrix. If
A
{\displaystyle A}
is an
n
×
n
{\displaystyle n\times n}
Toeplitz matrix, then the system has at most only
2
n
−
1
{\displaystyle 2n-1}
unique values, rather than
n
2
{\displaystyle n^{2}}
. 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 algorithm or the
Levinson algorithm in
O
(
n
2
)
{\displaystyle O(n^{2})}
time.
[1]
[2] Variants of the latter have been shown to be weakly stable (i.e. they exhibit
numerical stability for
well-conditioned
linear systems ).
[3] The algorithms can also be used to find the
determinant of a Toeplitz matrix in
O
(
n
2
)
{\displaystyle O(n^{2})}
time.
[4]
A Toeplitz matrix can also be decomposed (i.e. factored) in
O
(
n
2
)
{\displaystyle O(n^{2})}
time .
[5] The Bareiss algorithm for an
LU decomposition is stable.
[6] An LU decomposition gives a quick method for solving a Toeplitz system, and also for computing the determinant.
General properties
An
n
×
n
{\displaystyle n\times n}
Toeplitz matrix may be defined as a matrix
A
{\displaystyle A}
where
A
i
,
j
=
c
i
−
j
{\displaystyle A_{i,j}=c_{i-j}}
, for constants
c
1
−
n
,
…
,
c
n
−
1
{\displaystyle c_{1-n},\ldots ,c_{n-1}}
. The
set of
n
×
n
{\displaystyle n\times n}
Toeplitz matrices is a
subspace of the
vector space of
n
×
n
{\displaystyle n\times n}
matrices (under matrix addition and scalar multiplication).
Two Toeplitz matrices may be added in
O
(
n
)
{\displaystyle O(n)}
time (by storing only one value of each diagonal) and
multiplied in
O
(
n
2
)
{\displaystyle O(n^{2})}
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.
For symmetric Toeplitz matrices, there is the decomposition
1
a
0
A
=
G
G
T
−
(
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
1
a
0
A
{\displaystyle {\frac {1}{a_{0}}}A}
.
A
−
1
=
1
α
0
(
B
B
T
−
C
C
T
)
{\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.
[7]
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
=
h
1
0
⋯
0
0
h
2
h
1
⋮
⋮
h
3
h
2
⋯
0
0
⋮
h
3
⋯
h
1
0
h
m
−
1
⋮
⋱
h
2
h
1
h
m
h
m
−
1
⋮
h
2
0
h
m
⋱
h
m
−
2
⋮
0
0
⋯
h
m
−
1
h
m
−
2
⋮
⋮
h
m
h
m
−
1
0
0
0
⋯
h
m
x
1
x
2
x
3
⋮
x
n
{\displaystyle 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}}}
y
T
=
h
1
h
2
h
3
⋯
h
m
−
1
h
m
x
1
x
2
x
3
⋯
x
n
0
0
0
⋯
0
0
x
1
x
2
x
3
⋯
x
n
0
0
⋯
0
0
0
x
1
x
2
x
3
…
x
n
0
⋯
0
⋮
⋮
⋮
⋮
⋮
⋮
⋮
0
⋯
0
0
x
1
⋯
x
n
−
2
x
n
−
1
x
n
0
0
⋯
0
0
0
x
1
⋯
x
n
−
2
x
n
−
1
x
n
.
{\displaystyle 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}}.}
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
=
⋮
⋮
⋮
⋮
⋯
a
0
a
−
1
a
−
2
a
−
3
⋯
⋯
a
1
a
0
a
−
1
a
−
2
⋯
⋯
a
2
a
1
a
0
a
−
1
⋯
⋯
a
3
a
2
a
1
a
0
⋯
⋮
⋮
⋮
⋮
.
{\displaystyle 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}}.}
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 of.
[8]
See also
Circulant matrix , a square Toeplitz matrix with the additional property that
a
i
=
a
i
+
n
{\displaystyle a_{i}=a_{i+n}}
Hankel matrix , an "upside down" (i.e., row-reversed) Toeplitz matrix
Szegő limit theorems – Determinant of large Toeplitz matrices
Toeplitz operator – compression of a multiplication operator on the circle to the Hardy spacePages displaying wikidata descriptions as a fallback
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 ,
S2CID
367586
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. (eds.), Fast Reliable Algorithms for Matrices with Structure ,
SIAM , pp. 103–116,
doi :
10.1137/1.9781611971354.ch4 ,
hdl :
1885/40746 ,
S2CID
13905858
Chan, R. H.-F.; Jin, X.-Q. (2007), An Introduction to Iterative Toeplitz Solvers ,
SIAM ,
doi :
10.1137/1.9780898718850 ,
ISBN
978-0-89871-636-8
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 ,
S2CID
55893963
Hayes, Monson H. (1996), Statistical digital signal processing and modeling , John Wiley & Son,
ISBN
0-471-59431-8
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 ,
S2CID
15717371
Yang, Zai; Xie, Lihua; Stoica, Petre (2016), "Vandermonde decomposition of multilevel Toeplitz matrices with application to multidimensional super-resolution",
IEEE Transactions on Information Theory , 62 (6): 3685–3701,
arXiv :
1505.02510 ,
doi :
10.1109/TIT.2016.2553041 ,
S2CID
6291005
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 ,
S2CID
121761517
Goldreich, O. ; Tal, A. (2018), "Matrix rigidity of random Toeplitz matrices", Computational Complexity , 27 (2): 305–350,
doi :
10.1007/s00037-016-0144-9 ,
S2CID
253641700
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 )
doi :
10.1561/0100000006
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 ,
S2CID
254166943