HOME

TheInfoList



OR:

In
linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrices. ...
, a Toeplitz matrix or diagonal-constant matrix, named after
Otto Toeplitz Otto Toeplitz (1 August 1881 – 15 February 1940) was a German mathematician working in functional analysis., reprinted in Life and work Toeplitz was born to a Jewish family of mathematicians. Both his father and grandfather were ''Gymnasiu ...
, is a
matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
in which each descending diagonal from left to right is constant. For instance, the following matrix is a Toeplitz matrix: :\qquad\begin 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. Any ''n'' × ''n'' matrix ''A'' of the form :A = \begin a_0 & a_ & a_ & \cdots & \cdots & a_ \\ a_1 & a_0 & a_ & \ddots & & \vdots \\ a_2 & a_1 & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & a_ & a_ \\ \vdots & & \ddots & a_1 & a_0 & a_ \\ a_ & \cdots & \cdots & a_2 & a_1 & a_0 \end is a Toeplitz matrix. If the ''i'', ''j'' element of ''A'' is denoted ''A''''i'', ''j'' then we have :A_ = A_ = a_. A Toeplitz matrix is not necessarily
square In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90-degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length adj ...
.


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'' × ''n'' Toeplitz matrix, then the system has only 2''n'' − 1 degrees of freedom, rather than ''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 the Levinson algorithm in ''O''(''n''2) time. Variants of this algorithm have been shown to be weakly stable (i.e. they exhibit numerical stability for
well-conditioned In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument. This is used to measure how sensitive a function is to changes or errors in the input ...
linear systems). The algorithm can also be used to find the
determinant In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
of a Toeplitz matrix in ''O''(''n''2) time. A Toeplitz matrix can also be decomposed (i.e. factored) in ''O''(''n''2) time. The Bareiss algorithm for an
LU decomposition In numerical analysis and linear algebra, lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix (see matrix decomposition). The product sometimes includes a pe ...
is stable. 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.


General properties

* An ''n'' × ''n'' 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 Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
of ''n'' × ''n'' Toeplitz matrices is a subspace of the
vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
of ''n'' × ''n'' matrices (under matrix addition and scalar multiplication). * Two Toeplitz matrices may be added in ''O''(''n'') time (by storing only one value of each diagonal) and multiplied in ''O''(''n''2) time. * Toeplitz matrices are
persymmetric In mathematics, persymmetric matrix may refer to: # a square matrix which is symmetric with respect to the northeast-to-southwest diagonal; or # a square matrix such that the values on each line perpendicular to the main diagonal are the same for a ...
. Symmetric Toeplitz matrices are both
centrosymmetric In crystallography, a centrosymmetric point group contains an inversion center as one of its symmetry elements. In such a point group, for every point (x, y, z) in the unit cell there is an indistinguishable point (-x, -y, -z). Such point g ...
and bisymmetric. * Toeplitz matrices are also closely connected with
Fourier series A Fourier series () is a summation of harmonically related sinusoidal functions, also known as components or harmonics. The result of the summation is a periodic function whose functional form is determined by the choices of cycle length (or ''p ...
, because the
multiplication operator In operator theory, a multiplication operator is an operator defined on some vector space of functions and whose value at a function is given by multiplication by a fixed function . That is, T_f\varphi(x) = f(x) \varphi (x) \quad for all in th ...
by a
trigonometric polynomial In the mathematical subfields of numerical analysis and mathematical analysis, a trigonometric polynomial is a finite linear combination of functions sin(''nx'') and cos(''nx'') with ''n'' taking on the values of one or more natural numbers. The c ...
, 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 Commute, commutation or commutative may refer to: * Commuting, the process of travelling between a place of residence and a place of work Mathematics * Commutative property, a property of a mathematical operation whose result is insensitive to th ...
asymptotically In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates tends to infinity. In projective geometry and related contexts, ...
. This means they diagonalize in the same
basis Basis may refer to: Finance and accounting * Adjusted basis, the net cost of an asset after adjusting for various tax-related items *Basis point, 0.01%, often used in the context of interest rates * Basis trading, a trading strategy consisting ...
when the row and column dimension tends to infinity. * A positive semi-definite ''n'' × ''n'' Toeplitz matrix A of
rank Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as: Level or position in a hierarchical organization * Academic rank * Diplomatic rank * Hierarchy * ...
''r'' < ''n'' can be ''uniquely'' factored as ::A = \sum_^r d_k v(f_k) v(f_k)^\operatorname = VDV^\operatorname :where D = \mathrm(d_1, \ldots, d_r) is an ''r'' × ''r''
positive definite In mathematics, positive definiteness is a property of any object to which a bilinear form or a sesquilinear form may be naturally associated, which is positive-definite. See, in particular: * Positive-definite bilinear form * Positive-definite f ...
diagonal matrix In linear algebra, a diagonal matrix is a matrix in which the entries outside the main diagonal are all zero; the term usually refers to square matrices. Elements of the main diagonal can either be zero or nonzero. An example of a 2×2 diagonal ma ...
, V = (f_1), \ldots, v(f_r)/math> is an ''n'' × ''r''
Vandermonde matrix In linear algebra, a Vandermonde matrix, named after Alexandre-Théophile Vandermonde, is a matrix with the terms of a geometric progression in each row: an matrix :V=\begin 1 & x_1 & x_1^2 & \dots & x_1^\\ 1 & x_2 & x_2^2 & \dots & x_2^\\ 1 & x_3 ...
such that the columns are v(f) = , e^, \ldots, e^\operatorname. Here i^2 = -1 and f_k \in ,1/math> is normalized frequency, and V^\operatorname is the
Hermitian transpose In mathematics, the conjugate transpose, also known as the Hermitian transpose, of an m \times n complex matrix \boldsymbol is an n \times m matrix obtained by transposing \boldsymbol and applying complex conjugate on each entry (the complex co ...
of V. If the rank ''r'' = ''n'', then the Vandermonde decomposition is not unique. * For symmetric Toeplitz matrices, there is the decomposition ::\frac A = G G^\operatorname - (G - I)(G - I)^\operatorname :where G is the lower triangular part of \frac A. * The inverse of a nonsingular symmetric Toeplitz matrix has the representation ::A^ = \frac (B B^\operatorname - C C^\operatorname) :where B and C are lower triangular Toeplitz matrices and C is a strictly lower triangular matrix.


Discrete convolution

The
convolution In mathematics (in particular, functional analysis), convolution is a operation (mathematics), mathematical operation on two function (mathematics), functions ( and ) that produces a third function (f*g) that expresses how the shape of one is ...
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 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_ & \vdots & \ddots & h_2 & h_1 \\ h_m & h_ & & \vdots & h_2 \\ 0 & h_m & \ddots & h_ & \vdots \\ 0 & 0 & \cdots & h_ & h_ \\ \vdots & \vdots & & h_m & h_ \\ 0 & 0 & 0 & \cdots & h_m \end \begin x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_n \end : y^T = \begin h_1 & h_2 & h_3 & \cdots & h_ & h_m \end \begin 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_ & x_ & x_n & 0 \\ 0 & \cdots & 0 & 0 & 0 & x_1 & \cdots & x_ & x_ & x_n \end. This approach can be extended to compute
autocorrelation Autocorrelation, sometimes known as serial correlation in the discrete time case, is the correlation of a signal with a delayed copy of itself as a function of delay. Informally, it is the similarity between observations of a random variable ...
, cross-correlation,
moving average In statistics, a moving average (rolling average or running average) is a calculation to analyze data points by creating a series of averages of different subsets of the full data set. It is also called a moving mean (MM) or rolling mean and is ...
etc.


Infinite Toeplitz matrix

A bi-infinite Toeplitz matrix (i.e. entries indexed by \mathbb Z\times\mathbb Z) A induces a
linear operator In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a mapping V \to W between two vector spaces that pre ...
on \ell^2. : A=\begin & \vdots & \vdots & \vdots & \vdots \\ \cdots & a_0 & a_ & a_ & a_ & \cdots \\ \cdots & a_1 & a_0 & a_ & a_ & \cdots \\ \cdots & a_2 & a_1 & a_0 & a_ & \cdots \\ \cdots & a_3 & a_2 & a_1 & a_0 & \cdots \\ & \vdots & \vdots & \vdots & \vdots \end. The induced operator is bounded if and only if the coefficients of the Toeplitz matrix A are the Fourier coefficients of some
essentially bounded Essence ( la, essentia) is a polysemic term, used in philosophy and theology as a designation for the property or set of properties that make an entity or substance what it fundamentally is, and which it has by necessity, and without which it ...
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 of:


See also

*
Circulant matrix In linear algebra, a circulant matrix is a square matrix in which all row vectors are composed of the same elements and each row vector is rotated one element to the right relative to the preceding row vector. It is a particular kind of Toeplit ...
, a square Toeplitz matrix with the additional property that a_i=a_ *
Hankel matrix In linear algebra, a Hankel matrix (or catalecticant matrix), named after Hermann Hankel, is a square matrix in which each ascending skew-diagonal from left to right is constant, e.g.: \qquad\begin a & b & c & d & e \\ b & c & d & e & f \\ c & d & ...
, an "upside down" (i.e., row-reversed) Toeplitz matrix


Notes


References

* * * * * * * * * * * *


Further reading

* * * Golub G. H., van Loan C. F. (1996), ''Matrix Computations'' (
Johns Hopkins University Press The Johns Hopkins University Press (also referred to as JHU Press or JHUP) is the publishing division of Johns Hopkins University. It was founded in 1878 and is the oldest continuously running university press in the United States. The press publi ...
) §4.7—Toeplitz and Related Systems *Gray R. M.,
Toeplitz and Circulant Matrices: A Review
'
Now Publishers
* * * {{Authority control Matrices