![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
In this paper, we investigate some properties of Toeplitz matrices with respect to different matrix products. We also give some results regarding circulant matrices, skew-circulant matrices and approximation by Toeplitz matrices over the field of complex numbers.
Keywords:
Public Interest Statement
Toeplitz matrices arise in a variety of problems in applied mathematics and engineering such as queuing theory, signal processing, time series analysis, integral equations, etc. Despite the fact that Toeplitz matrices have been around for a long time, there are still a number of open problems regarding Toeplitz matrices and Toeplitz operators. One of them is counting the number of involutory and nilpotent Toeplitz matrices over a finite field. In this paper, we provide some solutions to the problem only in very specific cases. We also give several optimal approximation results for Toeplitz, circulant and skew-circulant matrices over the field of complex numbers. Furthermore, we give a characterization for pairs of Toeplitz matrices over a commutative ring whose product with respect to the usual multiplication or the Kronecker product is Toeplitz.
1. Introduction
Toeplitz matrices are important both in theory and application. For example, it is known that a large class of matrices are similar to Toeplitz matrices (Heinig, Citation2001; Mackey, Mackey, & Petrovic, Citation1999). Moreover, it is shown that every matrix is a product of Toeplitz matrices (Lim & Ye, Citation2013).
The notation of this paper is as follows. An Toeplitz matrix T is denoted by
, for
; which implies all the entries along each of the
diagonals are the same. A circulant matrix C is a Toeplitz matrix where each row is obtained by applying the permutation (1 2 ... n) to the previous row. A skew-circulant matrix S differs from a circulant matrix C only by a change in the sign in the subdiagonal entries, i.e.
when
and
when
. A matrix T is involutory if
, and is called nilpotent of degree k if
, but
.
This paper is organized as follows. In Section 2, we characterize those Toeplitz matrices over a commutative ring (of any characteristic) having the property that their product is a Toeplitz matrix. We consider also Kronecker products of Toeplitz matrices. Fuethermore, we give some combinatorial results over the finite prime field .
In Section 3, we count the number of involutory and degree two nilpotent Toeplitz matrices in for particular values of n or p.
In Section 4, Toeplitz matrices over the field of complex numbers are studied. We show that for any matrix, there exists a closest Topelitz matrix (with respect to the Frobenius norm) that approximates it. We describe the equivalence classes of Toeplitz matrices and give several results regarding circulant and skew-circulant matrices.
2. Product of Toeplitz matrices over a commutative ring
We consider three different binary operations, the usual matrix multiplication, Kronecker product and Schur product, denoted by AB, and
, respectively. With the exception of Schur product, the set of Toeplitz matrices is neither closed under the usual matrix multiplication nor under the Kronecker product. We characterize those pairs of Toeplitz matrices whose product with respect to the usual multiplication or the Kronecker product is Toeplitz again. The following theorem gives a characterization in terms of the usual matrix multiplication:
Theorem 2.1
If and
are two
Toeplitz matrices over a commutative ring, then AB is a Toeplitz matrix if and only if the following system of equations, of
equations with
variables, holds:
Proof
If we set , by the product formula we have:
By definition, C is a Toeplitz matrix if and only if . Therefore, C is Toeplitz if and only if
where
.
It is clear that the inverse of an arbitrary nonsingular Toeplitz matrix is not necessarily Toeplitz. However, the following proposition shows how stability under inversion, with respect to being Toeplitz, is related to stability under multiplication. For an arbitrary matrix A over a commutative ring, we can compute the coefficients of the characteristic polynomial
in many different ways, including the eigenvalues of the matrix, or the entries of the matrix (Brooks, Citation2006). In particular, we wish to use the following formula to compute the coefficients:
where is the
exterior power of A. Furthermore, if the characteristic of the commutative ring is zero then it is known (Winitzki, Citation2010, 3.9) that
where
Proposition 2.2
For an invertible Toeplitz matrix
over a commutative ring, if every
, for
, is Toeplitz, then
is a Toeplitz matrix. Furthermore, if the Toeplitz matrix is considered over a ring of characteristic zero, we have
where
and the symbol
disappears.
Proof
By the Cayley–Hamilton Theorem, , where each coefficient
of the characteristic polynomial could be explicitly computed as the sum of all principal minors of A of size m. Furthermore, if the matrix is considered over a commutative ring of characteristic zero, then we have
. The trace of a Toeplitz matrix is simply n times its diagonal entry, but the diagonal entry of a the m-th power of A, denoted by
here, can be calculated recursively.
Remark 2.3
If an upper (lower) triangular Toeplitz matrix is invertible, then its inverse is Toeplitz, because the product of two upper (lower) triangular Toeplitz matrices is again an upper (lower) triangular Toeplitz matrix. Since an upper (lower) unitriangular matrix is always invertible and its inverse is an upper (lower) unitriangular matrix, the inverse of any upper (lower) unitriangular Toeplitz matrix is also an upper (lower) unitriangular Toeplitz matrix.
Theorem 2.4
Let be an
Toeplitz matrix and
be an
Toeplitz matrix over a commutative ring. The
matrix
is Toeplitz if and only if the following system of equations, of
equations with
variables, holds:
where and
.
Proof
With regard to the Kronecker multiplication of two matrices, consists of
blocks of Toeplitz matrices, and it is Toeplitz if and only if each of the
diagonals has the same entries, i.e. if and only if for each diagonal, which is formed by concatenation of diagonals of the adjacent blocks, the entries agree with each other.
Clearly, for the top right corner block in , there is no concatenation, and therefore, the top
diagonals always satisfy the property, and the same fact holds for the bottom
diagonals of
. Furthermore, the main diagonal of
is just the concatenation of n copies of the main diagonal of B, multiplied by
, i.e. it is simply
. We also notice that for the diagonals of
that are the result of concatenation of the main diagonals of some internal blocks, we have no extra conditions and each of them always has the same entry since A and B are both Toeplitz.
Regarding the remaining diagonals, however, we certainly have concatenation of different diagonals of adjacent blocks, which should agree. A simple computation shows that the above equations are coming from those concatenations. Thus, out of the diagonals of
, always
of them satisfy the property, from which
comes from the fact that holds for the main diagonals, and
from the diagonals, coming from the single blocks on the top-right and bottom-left corners.
Let be a finite field with q elements and let
Define the following set
where is the
-dimensional projective space over
. Since the equations of Theorem 2.1 are homogeneous,
is a projective variety and an upper bound of its cardinality can be given by the Lang–Weil estimate (Ghorpade & Lachaud, Citation2002; Lang & Weil, Citation1954). Similarly, we can define an affine variety
As an example, one can check that and
.
3. Involutory and nilpotent Toeplitz matrices over the finite field ![](//:0)
Let and
, respectively, denote the number of involutory Toeplitz matrices and nilpotent Toeplitz matrices of degree two in
. In the following theorem, we calculate
for specific values of p or n. Clearly, for a Toeplitz matrix A in
, A is involutory if and only if
is idempotent. In this case, since
is again a Toeplitz matrix in
, for
,
also gives us the number of idempotent Toeplitz matrices in
. Moreover, for
, a Toeplitz matrix A is a nontrivial involutory matrix if and only if the Toeplitz matrix
is nilpotent of degree two. Therefore,
is also the number of degree two nilpotent Toeplitz matrices when n is odd.
Theorem 3.1
The following hold:
(i) | If n is odd then | ||||
(ii) |
| ||||
(iii) |
|
Proof
(i) | Let | ||||
(ii) | Since trace | ||||
(iii) | For |
We note that cannot be zero because if
, then
because of the equation
and the first equation in the above gives a contradiction. Furthermore, it follows from the above equations and invertibility of
that if
, then
,
, and if
, then
,
. Hence, we have two solutions in this case, namely
,
and
,
. Therefore, the remaining case is when
and
are both invertible which means that by knowing the values of
,
and
, we can uniquely determine the values of
and
from the equations. Thus, it suffices to count the solutions of the equation
. Since the equation
has
solutions in
, where p is odd and greater than 3, there are
solutions in total.
For , the matrix equation
, in
, where p is odd, gives the following equations in
:
The above equations indicate that if , then either
, and
or
,
,
and
. Since each of the equations
and
has
solutions in
, there are
solutions when
. If
, then there are two cases to consider: (1) If either
or
is zero, then it follows from the above equations that all variables except
must be zero. Therefore, this case leads to the equation
which has two solutions. (2) If neither
nor
is zero, then the above equations can be simplified as follows:
The equations and
lead to equations
and
each of which has
solutions. Therefore, if
, then there are
solutions, and if
, then there are
solutions. Hence, there are
solutions in total.
Conjecture 3.2
If n is even then or equivalently
.
Theorem 3.3
The following hold:
(i) |
| ||||
(ii) |
|
Proof
(i) | The matrix equation | ||||
(ii) | The matrix equation |
Remark 3.4
For matrices in , it is known that the number of invertible, involutory (Hodges, Citation1958) and nilpotent (Fine & Herstein, Citation1958) matrices are as follows:
Therefore, the probabilities of being invertible, involutory and nilpotent are ,
and
, respectively. Since the number of invertible Toeplitz matrices is
(Kaltofen & Lobo, Citation1996, Theorem 4), the probability that a Toeplitz matrix is invertible is
which is independent of n. By Theorem 3.1, the probability that a Toeplitz matrix in
, where n is odd, is involutory is
.
Theorem 3.5
Let :
and T is Toeplitz
where
is the Schur product and J is the matrix with all entries equal to 1. The cardinality of the set G(n, p, m) is
.
Proof
The entries of T must satisfy the equation (mod p). Therefore, we are counting elements of
that their order divides m and their order also divides
, i.e. their order divides
. Hence,
where is Euler’s totient function. Since there are
distinct elements, there are
different matrices T with the aforementioned properties.
4. Toeplitz matrices over the complex field ![](//:0)
In this section, we consider Toeplitz matrices over the complex field . We define a metric that measures how far a matrix is from being Toeplitz. We can associate a Toeplitz matrix
to any matrix A as follows:
For example, the associated Toeplitz matrix to , is
and we observe that
where
is the operator norm. If A is a Toeplitz matrix, then
is zero.
Theorem 4.1
If is the associated Toeplitz matrix of A such that
where
, then
(i) |
| ||||
(ii) | if A is self-adjoint then |
Proof
(i) | We have the following inequalities: | ||||
(ii) |
|
We now consider involutory Toeplitz matrices over the complex field . The following simple Proposition shows that if there exists one such matrix, there exist uncountably many.
Proposition 4.2
If
is an involutory Toeplitz matrix over , and v is a nonzero complex scalar, then
is also an involutory Toeplitz matrix.
Proof
The two matrices are related by a similarity transformation by a diagonal matrix. See for example, Proposition 3.1 in Kucerovsky and Sarraf (Citation2014).
In view of the above result, it would appear inevitable that we should consider some equivalence relation or some restriction on the class of involutory Toeplitz matrices considered. We give two such results:
Theorem 4.3
There are n+1 equivalence classes of involutory Toeplitz matrices in , where the equivalence relation is similarity. Furthermore, every equivalence class contains at least one (involutory) Hermitian circulant matrix.
Proof
Let T be an involutory Toeplitz matrix. Since the polynomial annihilates T, it follows that the minimal polynomial of T divides p. But because p has distinct roots over
, it follows that the minimal polynomial of T has distinct roots over
, and thus that T is diagonalizable. Thus, T is equivalent under similarity to a diagonal matrix
. Let F denote the usual Vandermonde matrix representation of the finite Fourier transform (over
). Then,
is equivalent to T, is a Hermitian matrix and is a circulant (Driessel, Citation2011). Clearly, thus, the number of equivalence classes is given by the number of possible involutory diagonal matrices in
, after equivalence, which is n + 1. Two diagonal matrices are in the same class after equivalence if and only if the elements of the diagonals are permutations of one another.
Note: the above proof will work in more general fields: we just need sufficiently many roots of unity and the existence of 1 / n.
We can also look at restricting the class of Toeplitz matrices considered:
Theorem 4.4
In , the involutory symmetric Toeplitz matrices are all either symmetric real circulants or are symmetric real skew-circulants. If n is even and greater than 2, there are a total of
such matrices. If n is odd and greater than 1, there is a total of
such matrices.
Proof
We observe that if a symmetric real matrix satisfies , it is in fact an orthogonal matrix. Orthogonal and symmetric real Toeplitz matrices are either circulants or skew-circulants (Böttcher, Citation2008, [section 3]). From Theorem 4.1 and Theorem 4.2 in Böttcher (Citation2008), if n is odd and greater than 1, there is a total of
such matrices, and if n is even and greater than 2, there are a total of
such matrices.
Theorem 4.5
Consider the Frobenius norm on the complex n-by-n matrices,
. Given an arbitrary
, there exist a unique complex Toeplitz matrix minimizing
over all Toeplitz matrices T. This unique minimizing matrix is the Toeplitz matrix given in each diagonal by the average of the elements of the corresponding diagonal of A. The same statement holds in the real case.
Proof
Under this norm, is a complex Hilbert space, with the complex Toeplitz matrices forming a subspace
. Let
denote the Toeplitz matrices that have zero in all diagonals except one, and in that
diagonal, has elements equal to 1. At the level of Hilbert spaces, this is a finite orthogonal set spanning the subspace
. Thus, we can explicitly construct the projection from
onto
in the form:
It is well known that orthogonal projection onto a closed subspace, in Hilbert space, minimizes the norm. In this case, the subspace is closed as a consequence of its finite-dimensionality. It is clear that P(A) is given in each diagonal by the average of the elements of the corresponding diagonal of A. In the real case, exactly the same proof works, but with real Hilbert spaces instead of complex Hilbert spaces.
It seems interesting to consider generalizations of the above Theorem to the C*-norm on . However, projection onto linear subspaces of C*-algebras has poor properties in general. It is not even true that the operation of projection onto a subspace will not increase the norm distance between elements (Silverman, Citation1969). The situation improves when we consider projection onto subalgebras. Tomiyama (Tomiyama) showed that each projection of norm one of a C*-algebra onto a C*-subalgebra is a conditional expectation, and Takesaki (Citation1972) showed that in a finite von Neumann algebra, there exist faithful conditional expectations onto von Neumann subalgebras. We will make use of this result, and will explicitly construct faithful conditional expectations onto the circulant algebra and the skew-circulant algebra. We will show these expectations are basically unique.
For information on circulants and skew-circulants, see Driessel, Citation2011. The circulants of a given order form an abelian subalgebra of , as do the skew-circulants. The circulants can be simultaneously diagonalized by (a scalar multiple of) the DFT matrix
where
is a primitive (complex) root of unity. The skew-circulants can be simultaneously diagonalized by
where
is a suitable diagonal unitary matrix, see Proposition 31 in Driessel (Citation2011). We will write
, where W is a skew-circulant and
is a diagonal matrix, or
, for a circulant C.
Theorem 4.6
A faithful, trace-preserving, idempotent, conditional expectation of operator norm 1 of onto the circulants is given by
where D takes all elements that are not on the main diagonal to zero, and preserves the elements of the main diagonal and F is the discrete Fourier transform matrix.
Proof
Since the map is a unitary transformation diagonalizing the circulants, we must show that the map D is a faithful, idempotent, trace-preserving, conditional expectation of norm 1 of
onto the subalgebra of diagonal matrices. To show that D is a conditional expectation, we verify that the defining property
holds, where d is a diagonal matrix, and m is in
. It is apparent that
preserves the trace. Since the diagonal elements of a positive definite matrix are real and nonnegative, it follows that D maps a positive definite matrix to a positive definite (diagonal) matrix. If D were not faithful, there would be some nonzero positive definite matrix that maps to zero under D. But a positive definite matrix with principal diagonal zero is in fact the zero matrix (Horn & Johnson, Citation1990, p. 398). Conditional expectations are completely positive maps, and a completely positive map of unital algebras has norm one if and only if it takes the unit to the unit. Evidently, the map D is unital, and thus has norm 1. It is clear that D is idempotent.
Corollary 4.7
There is only one idempotent linear mapping of onto the circulant subalgebra in
. It is given by the map in the above Theorem.
Proof
By Theorem 1 in Tomiyama (Citation1957), by given idempotent linear mapping L is a conditional expectation of a finite-dimensional von Neumann algebra onto a finite-dimensional von Neumann algebra. By finite-dimensionality, the mapping is necessarily normal. By Proposition 1.2 in Tomiyama (Citation1972), the mapping L is necessarily faithful. By Theorem 6.2.2 (and Theorem 6.2.3) in Arveson (Citation1967), the mapping L is unique. It therefore follows that any two maps satisfying the hypotheses of the Corollary are in fact the same map, and clearly, the map provided by Theorem 4.6 satisfies the hypotheses.
From the uniqueness, we have the following further Corollary:
Corollary 4.8
The map of Theorem 4.6 minimizes the error in (operator) norm among all idempotent projections of onto the circulant subalgebra in
.
Replacing circulants by skew-circulants in the proofs of the last three results, we obtain analoguous results for skew-circulants. We summarize as follows:
Theorem 4.9
A faithful, trace-preserving, idempotent, conditional expectation of operator norm 1 of onto the skew-circulants is given by
where D takes all elements that are not on the main diagonal to zero, and preserves the elements of the main diagonal. This map minimizes the error in (operator) norm among all idempotent projections of onto the skew-circulant subalgebra in
. H is the matrix provided by Driessel (Citation2011, [Proposition 31]).
Since every Toeplitz matrix can be uniquely decomposed as the sum of a circulant and a skew-circulant, we have the following Remark:
Remark 4.10
For each matrix m, the sum of the maps from Theorems 4.6 and 4.9, , gives a Toeplitz matrix.
We next consider how the usual product and Schur product interact with circulant property. The finite Fourier transform over the complex numbers can be described most briefly as the unitary transformation that is (up to a scalar multiple) represented by the N-by-N matrix with
. The complex number
is a principal
root of unity. This definition can be made in a finite field. If
is a principal
root of unity in a finite field, it follows that
and
for
, and these are the main properties used in establishing the well-known properties of the (complex) finite Fourier transform with respect to convolution. In order to be able to invert the generalized finite Fourier transform, it is necessary that N be not divisible by the characteristic of the field. See Chapter 11 of Elliott and Rao (Citation1982) for more information. If these conditions are met, then the generalized finite Fourier transform takes the convolution operation defined by multiplication by a circulant matrix to multiplication by a diagonal matrix, see section 11.2 and 11.3 of Elliott and Rao (Citation1982). Thus, we are able to diagonalize circulant matrices, even over a finite field. The diagonal matrix obtained will be referred to as the eigenvalue matrix of the circulant, and denoted
where A is the given circulant. Let us say that a circular convolution of two sequences is the first row of the matrix product of the circulants having the given sequences as their first row. Thus, if
, then the sequence
is the circular convolution of
and
.
Proposition 4.11
Let A and B be two circulants, over a finite field with characteristic relatively prime to the matrix dimension N of the circulant matrix. The eigenvalues of AB and can be determined in terms of the eigenvalues of A and B. The eigenvalues of AB are given by
, and the eigenvalues of
are given by
where C is the circulant matrix whose eigenvalue sequence is the circular convolution of the eigenvalue sequences of A and B.
Proof
Since the generalized Fourier transform is a unitary transformation, W, it is clear that . Thus, the eigenvalues of AB are the elementwise product of the eigenvalues of A and B. The main issue is the behaviour of the Schur product.
To reduce notation, let us consider first the case where both A and B have the property that all the eigenvalues except one are zero, and that eigenvalue is 1. Then, is an outer product of a row of W and a column of
. Since
and
, we thus have that
where k is the index of the nonzero eigenvalue of A. Similarly,
where
is the index of the nonzero eigenvalue of B. Taking the Schur product, we have
. We can thus write
where C is the circulant matrix with all eigenvalues zero except for a 1 in the
place. Since
, the values of the exponent in
may be taken as being modulo N. Thus, we see that the eigenvalues of
are given by
, where the eigenvalue sequence of the circulant matrix C are given by the circular convolution of the eigenvalue sequence of A and the eigenvalue sequence of B. The case of general circulants A and B follows by taking linear combinations.
The above result can be rephrased as follows: if we diagonalize a circulant using the generalized discrete Fourier transform, and then put the eigenvalue sequence into the first row of a circulant matrix, then up to a scalar multiple, Schur products are transformed into matrix products. This transformation is invertible.
Correction
This article was originally published with errors, which have now been corrected in the online version. Please see Correction (http://dx.doi.org/10.1080/25742558.2018.1520444)
Additional information
Funding
Notes on contributors
Dan Kucerovsky
Dan Kucerovsky is a full professor in the Department of Mathematics and Statistics at the University of New Brunswick in Canada. He studied in Oxford and in Paris. He is a former director of the Centre for Noncommutative Geometry and Topology. He has over 50 published papers in several areas of mathematics and statistics.
Kaveh Mousavand
Kaveh Mousavand is a graduate student in the Department of Mathematics at Université du Québec á Montréal (UQAM) in Canada. His research interests are representation theory of finite dimensional algebras and combinatorial algebra.
![](/cms/asset/96036fa4-7004-4102-b313-2f5245a39577/oama_a_1154705_ilm0394.gif)
Aydin Sarraf
Aydin Sarraf received his PhD in Mathematics from University of New Brunswick in Canada. His research interests in mathematics include operator theory, C-algebras and K-theory, and in computer science include computer vision, computational fluid dynamics and computational finance.
References
- Arveson, W. B. (1967). Analyticity in operator algebras. American Journal of Mathematics , 89 , 578–642.
- B{\"o}ttcher, A. (2008). Orthogonal symmetric Toeplitz matrices. Complex Analysis and Operator Theory , 2 , 285–298.
- Brooks, B. P. (2006). The coefficients of the characteristic polynomial in terms of the eigenvalues and the elements of an n × n matrix. Applied Mathematics Letters , 19 , 511–515.
- Bronstein, M. M. , & Glashoff, K. (2013). Almost-commuting matrices are almost jointly diagonalizable , arXiv:1305.2135.
- Driessel, K. R. (2011). A relation between some special centro-skew, near-Toeplitz, tridiagonal matrices and circulant matrices . arXiv:1102.1953v2.
- Elliott, D. F. , & Rao, K. R. (1982). Fast transforms, algorithms, analyses, applications . New York, NY: Academic Press.
- Fine, N. J. , & Herstein, I. N. (1958). The probability that a matrix be nilpotent. Illinois Journal of Mathematics , 2 , 499–504.
- Ghorpade, S. R. , & Lachaud, G. (2002). Number of solutions of equations over finite fields and a conjecture of Lang and Weil. Number theory and discrete mathematics (pp. 269–291). Basel: Springer.
- Heinig, G. (2001). Not every matrix is similar to a Toeplitz matrix. Linear Algebra and its Applications , 332 , 519–531.
- Hodges, J. H. (1958). The matrix equation X 2− I=0 over a finite field. The American Mathematical Monthly , 65 , 518–520.
- Horn, R. A. , & Johnson, C. R. (1990). Matrix analysis . Cambridge: Cambridge University Press.
- Kaltofen, E. , & Lobo, A. (1996). On rank properties of Toeplitz matrices over finite fields. In ISSAC ’96 Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation (pp. 241–249).New York, NY: ACM.
- Kucerovsky, D. , & Sarraf, A. (2014). Schur multipliers and matrix products. Houston Journal of Mathematics , 40 , 837–850.
- Lang, S. , & Weil, A. (1954). Number of points of varieties in finite fields. American Journal of Mathematics , 76 , 819–827.
- Lim, L. H. , & Ye, K. (2013). Every matrix is a product of Toeplitz matrices . arXiv:1307.5132.
- Mackey, D. S. , Mackey, N. , & Petrovic, S. (1999). Is every matrix similar to a Toeplitz matrix? Linear Algebra and its Applications , 297 , 87–105.
- Silverman, E. (1969). A weak projection of C onto a Euclidean subspace. Transactions of the AMS , 136 , 381–390.
- Takesaki, M. (1972). Conditional expectations in von Neumann algebras. Journal of Functional Analysis , 9 , 306–321.
- Tomiyama, J. (1957). On the projection of norm one in W*-algebras. Proceedings of the Japan Academy , 33 , 608–612.
- Tomiyama, J. (1972). On some types of maximal Abelian subalgebras. Journal of Functional Analysis , 10 , 373–386.
- Winitzki, S. (2010). Linear algebra via exterior products . San Bernardino: Lulu.