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:
:
Any ''n'' × ''n'' matrix ''A'' of the form
:
is a Toeplitz matrix. If the ''i'', ''j'' element of ''A'' is denoted ''A''
''i'', ''j'' then we have
:
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
:
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
Degrees of freedom (often abbreviated df or DOF) refers to the number of independent variables or parameters of a thermodynamic system. In various scientific fields, the word "freedom" is used to describe the limits to which physical movement or ...
, 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
In the mathematical subfield of numerical analysis, numerical stability is a generally desirable property of numerical algorithms. The precise definition of stability depends on the context. One is numerical linear algebra and the other is algorit ...
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 groups ...
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
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
* H ...
''r'' < ''n'' can be ''uniquely'' factored as
::
:where
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 ...
,