J u m p t o c o n t e n t
M a i n m e n u
M a i n m e n u
N a v i g a t i o n
● M a i n p a g e
● C o n t e n t s
● C u r r e n t e v e n t s
● R a n d o m a r t i c l e
● A b o u t W i k i p e d i a
● C o n t a c t u s
● D o n a t e
C o n t r i b u t e
● H e l p
● L e a r n t o e d i t
● C o m m u n i t y p o r t a l
● R e c e n t c h a n g e s
● U p l o a d f i l e
S e a r c h
Search
A p p e a r a n c e
● C r e a t e a c c o u n t
● L o g i n
P e r s o n a l t o o l s
● C r e a t e a c c o u n t
● L o g i n
P a g e s f o r l o g g e d o u t e d i t o r s l e a r n m o r e
● C o n t r i b u t i o n s
● T a l k
( T o p )
1
S o l v i n g a T o e p l i t z s y s t e m
2
G e n e r a l p r o p e r t i e s
3
D i s c r e t e c o n v o l u t i o n
4
I n f i n i t e T o e p l i t z m a t r i x
5
S e e a l s o
6
N o t e s
7
R e f e r e n c e s
8
F u r t h e r r e a d i n g
T o g g l e t h e t a b l e o f c o n t e n t s
T o e p l i t z m a t r i x
2 7 l a n g u a g e s
● ا ل ع ر ب ي ة
● C a t a l à
● Č e š t i n a
● D e u t s c h
● E s p a ñ o l
● E s p e r a n t o
● E u s k a r a
● ف ا ر س ی
● F r a n ç a i s
● 한 국 어
● ह ि न ् द ी
● I t a l i a n o
● N e d e r l a n d s
● 日 本 語
● P o l s k i
● P o r t u g u ê s
● R o m â n ă
● Р у с с к и й
● S l o v e n č i n a
● S l o v e n š č i n a
● S v e n s k a
● த ம ி ழ ்
● ไ ท ย
● У к р а ї н с ь к а
● ا ر د و
● 粵 語
● 中 文
E d i t l i n k s
● A r t i c l e
● T a l k
E n g l i s h
● R e a d
● E d i t
● V i e w h i s t o r y
T o o l s
T o o l s
A c t i o n s
● R e a d
● E d i t
● V i e w h i s t o r y
G e n e r a l
● W h a t l i n k s h e r e
● R e l a t e d c h a n g e s
● U p l o a d f i l e
● S p e c i a l p a g e s
● P e r m a n e n t l i n k
● P a g e i n f o r m a t i o n
● C i t e t h i s p a g e
● G e t s h o r t e n e d U R L
● D o w n l o a d Q R c o d e
● W i k i d a t a i t e m
P r i n t / e x p o r t
● D o w n l o a d a s P D F
● P r i n t a b l e v e r s i o n
A p p e a r a n c e
F r o m W i k i p e d i a , t h e f r e e e n c y c l o p e d i a
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 [ edit ]
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 [ edit ]
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 [ edit ]
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 [ edit ]
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 [ edit ]
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
^ Krishna & Wang 1993
^ Monahan 2011 , §4.5—Toeplitz systems
^ Brent 1999
^ Bojanczyk et al. 1995
^ Mukherjee & Maiti 1988
^ Böttcher & Grudsky 2012
References [ edit ]
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 [ edit ]
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
R e t r i e v e d f r o m " https://en.wikipedia.org/w/index.php?title=Toeplitz_matrix&oldid=1208778200 "
C a t e g o r y :
● M a t r i c e s
H i d d e n c a t e g o r i e s :
● A r t i c l e s w i t h s h o r t d e s c r i p t i o n
● S h o r t d e s c r i p t i o n i s d i f f e r e n t f r o m W i k i d a t a
● P a g e s d i s p l a y i n g w i k i d a t a d e s c r i p t i o n s a s a f a l l b a c k v i a M o d u l e : A n n o t a t e d l i n k
● A r t i c l e s w i t h J 9 U i d e n t i f i e r s
● A r t i c l e s w i t h L C C N i d e n t i f i e r s
● T h i s p a g e w a s l a s t e d i t e d o n 1 8 F e b r u a r y 2 0 2 4 , a t 2 2 : 1 8 ( U T C ) .
● T e x t i s a v a i l a b l e u n d e r t h e C r e a t i v e C o m m o n s A t t r i b u t i o n - S h a r e A l i k e L i c e n s e 4 . 0 ;
a d d i t i o n a l t e r m s m a y a p p l y . B y u s i n g t h i s s i t e , y o u a g r e e t o t h e T e r m s o f U s e a n d P r i v a c y P o l i c y . W i k i p e d i a ® i s a r e g i s t e r e d t r a d e m a r k o f t h e W i k i m e d i a F o u n d a t i o n , I n c . , a n o n - p r o f i t o r g a n i z a t i o n .
● P r i v a c y p o l i c y
● A b o u t W i k i p e d i a
● D i s c l a i m e r s
● C o n t a c t W i k i p e d i a
● C o d e o f C o n d u c t
● D e v e l o p e r s
● S t a t i s t i c s
● C o o k i e s t a t e m e n t
● M o b i l e v i e w