Bounds on the Extreme Eigenvalues of Real Symmetric Toeplitz Matrices.
We derive upper and lower bounds on the smallest and largest eigenvalues, respectively, of real symmetric Toeplitz matrices. The bounds are first obtained for positive-definite matrices and then extended to the general real symmetric case. They are computed as the roots of rational and polynomial approximations to spectral, or secular, equations for the symmetric and antisymmetric parts of the spectrum; this leads to separate bounds on the even and odd eigenvalues. We also present numerical results.
Introduction
The study of eigenvalues of Toeplitz matrices continues to be of interest, due to the
occurrence of these matrices in a host of applications (see [4] for a good overview) including
linear prediction, a well-known problem in digital signal processing.
In this work we present improved bounds on the extreme eigenvalues of real symmetric
positive-definite Toeplitz matrices and describe their extension to matrices that are not
positive-definite. The computation of the smallest eigenvalue of such matrices was considered
in, e.g., [8], [16] and [19], whereas bounds were studied in [10], [14] and [22]. Among
the latter, the best bounds were obtained in [10]. Our approach is similar to the one used
in [8], [10], [19] and in [23], where it serves as a basis for computing other eigenvalues
as well. In this approach, the eigenvalues of the matrix are computed as the roots of
a one-dimensional rational function. The extreme eigenvalues can then be bounded by
computing bounds on the roots of the aforementioned equation, often called a spectral
equation, or secular equation (see [12]).
In [10] the bounds are obtained by using a Taylor series expansion for the secular
equation. We propose to improve this in two ways, first of all by considering "better"
secular equations (of a similar rational nature) and, secondly, by considering rational approximations
to the secular function, rather than a Taylor series, which is an inappropriate
On leave from Ben-Gurion University, Beer-Sheva, Israel.
approximation for a rational function. As an added advantage of our different equations,
we obtain separate bounds on the even and odd eigenvalues.
To put matters in perspective, we note that these "better" equations are hinted at in
[10] without being explixitly stated and they also appear in [9] in an equivalent form that
is less suitable for computation. No applications of these equations were considered in
either paper. In [16], an equation such as one of ours is derived in a different way which
does not take into account the spectral structure of the submatrices of the matrix, thereby
obscuring key properties of the equation. It is used there to compute the smallest even
eigenvalue and it too uses polynomial approximations.
The idea of a rational approximation for secular equations is not new. In a different
context, it was already used in, e.g., [5] and many other references, the most relevant to
this work being [19]. However, apparently because of the somewhat complicated nature of
their analysis, it seems that these rational approximations are rarely considered beyond
the first order. We consider a different approach that enables us to consider higher order
rational approximations, which we prove to be better than polynomial ones. To our knowl-
edge, the equations for the even and odd spectra have not been combined with rational
approximations to compute bounds and the resulting improvement is quite significant.
The paper is organized as follows. Section 1 contains definitions, a brief overview of
the properties of Toeplitz matrices and basic results for a class of rational functions. In
Section 2 we develop spectral equations and in Section 3 we consider the approximations
which lead, in Section 4, to the bounds on the extreme eigenvalues. Finally, we present
numerical results in Section 5. In Sections 2 and 3, we have included a summary of parts
of [21], to improve readability and to make the paper as self-contained as possible.
The identity matrix is denoted by I throughout this paper, without specifically indicating
its dimension, which is assumed to be clear from the context.
Preliminaries
A symmetric matrix T 2 IR (n;n) is said to be Toeplitz if its elements
for some vector Many early results about such matrices can be
found in, e.g., [3], [6] and [9].
Toeplitz matrices are persymmetric, i.e., they are symmetric about their southwest-
northeast diagonal. For such a matrix T , this is the same as requiring that JT T
where J is a matrix with ones on its southwest-northeast diagonal and zeros everywhere
else (the n \Theta n exchange matrix). It is easy to see that the inverse of a persymmetric
matrix is also persymmetric. A matrix that is both symmetric and persymmetric is called
doubly symmetric.
A symmetric vector v is defined as a vector satisfying and an antisymmetric
vector w as one that satisfies Jw = \Gammaw. If these vectors are eigenvectors, then their
associated eigenvalues are called even and odd, respectively. It was shown in [6] that,
given a real symmetric Toeplitz matrix T of order n, there exists an orthonormal basis
for composed of n \Gamma bn=2c symmetric and bn=2c antisymmetric eigenvectors of T ,
where bffc denotes the integral part of ff. In the case of simple eigenvalues, this is easy to
see from the fact that, if
Therefore u and Ju must be proportional, and therefore u must be an eigenvector of J ,
which means that either \Gammau. Finally, we note that for ff 2 IR, the matrix
\Gamma ffI) is symmetric and Toeplitz, whenever T is.
We now state two lemma's, the proofs of which can be found in [20]. They concern
the relation between a class of rational functions, which will be considered later, and their
approximations.
Lemma 2.1 Let g(-) be a strictly positive and twice continuously differentiable real func-
tion, defined on some interval K ae IR. With fl a nonzero integer, consider the real function
of -: a(b \Gamma -) fl , where the parameters a and b are such that it interpolates g up to first
order at a point - 2 K with
is positive (negative) for all - 2 K, then for all - such that a(b \Gamma -) fl - 0, the interpolant
lies below (above) the function g(-). 2
Lemma 2.2 The function
with m a positive and fl a nonzero integer and the ff j 's nonnegative, satisfies
for all - such that 8j :
3 Spectral equations
In this section we derive various spectral, or "secular", equations for the eigenvalues of a
real symmetric Toeplitz matrix. Several of these results are not new, even though some
were not explicitly stated elsewhere or appear in a form less suitable for computation.
Let us consider the following partition of a symmetric Toeplitz matrix
by the vector . Then the following well-known theorem (see, e.g., [8]) holds:
Theorem 3.1 The eigenvalues of T that are not shared with those eigenvalues of Q, whose
associated eigenspaces are not entirely contained in ftg ? , are given by the solutions of the
We define the function OE(-) by
Equation (1) is equivalent to
are the p eigenvalues of Q for which the associated eigenspace U
is not
entirely contained in the subspace ftg ? , i.e., for which U ! i
details). Denote the orthonormal vectors which form a basis for U
by fu (i)
is the dimension of U
. Then the scalars c 2
are given by c 2
. The rational
function in (1), or (3), has p simple poles, dividing the real axis into
each of which it is monotonely increasing from \Gamma1 to +1. The solutions f- j g p+1
of equation (3) therefore satisfy
i.e., the eigenvalues ! i strictly interlace the eigenvalues - j , which is known as Cauchy's
interlacing theorem. These results are well-known and we refer to, e.g., [8], [10] and [23].
A positive-definite matrix T will therefore certainly have an eigenvalue in the interval
An upper bound can then be found by approximating the function in (1) at
in such a way that the approximation always lies below that function, and by subsequently
computing the root of this approximation. This is the approach used in [10], where the
approximations are the Taylor polynomials. However, such polynomials are inadequate
for rational functions and we shall return to this matter after deriving additional spectral
equations.
It would appear that our previous partition of T is inappropriate, given the persym-
metry of Toeplitz matrices. We therefore consider the following, more natural, partition
for a matrix that is both symmetric and persymmetric:
G is an (n \Gamma 2) \Theta (n \Gamma 2) symmetric Toeplitz matrix, generated
by the vector This partition is also used in Theorem 4 of [10], but no use
was made of this partition in the computation or bounding of eigenvalues in any of the
aforementioned references. In what follows, we denote the even and odd eigenvalues of
T by - e
, and the even and odd eigenvalues of G by - i and - i , respectively. We
then have the following theorem, which yields two equations: one for even and one for odd
eigenvalues of T .
Theorem 3.2 The even eigenvalues of T that are not shared with those even eigenvalues
of G, whose associated eigenspaces are not entirely contained in f ~ t g ? , are the solutions of
whereas the odd eigenvalues of T that are not shared with those odd eigenvalues of G,
whose associated eigenspaces are not entirely contained in f ~ t g ? , are the solutions of
Proof. The proof is based on finding the conditions under which has a
nontrivial solution for x. These conditions take the form of a factorable equation, which
then leads directly to equations (4) and (5). For more details, we refer to [21]. 2
To gain a better understanding of equations (4) and (5), let us assume for a moment
that all eigenvalues of G are simple (the general case does not differ substantially) and
denote an orthonormal basis of IR n\Gamma2 , composed of orthonormal eigenvalues of G, by
are symmetric
eigenvector - even eigenvalue pairs and (w
eigenvalue pairs. With ~
means that
r
a
s
r
a
s
Once more exploiting the orthonormality of the eigenvectors yields
r
a 2
Analogously we obtain
s
Equations (4) and (5) now become
r
a 2
s
which shows that the rational functions in each of equations (4) and (5) are of the same
form as the function in (1). It is also clear that T will certainly have an even eigenvalue
on (0; - 1 ) and an odd one on (0; - 1 ). These equations were also hinted at in [10] without
however deriving or stating them in an explicit way. The meaning of Theorem 3.2 is
therefore that those even and odd eigenvalues of G, whose associated eigenspaces are not
completely contained in f ~ t g ? , interlace, respectively, the even and odd eigenvalues of T
that are not shared with those eigenvalues of G. This result was obtained in [9] in a
different way, along with equivalent forms of equations (6) and (7). However, the use of
determinants there makes them less suitable for applications.
Finally, because of the orthonormality of the eigenvectors, equations (4) and (5) can
be written in a more symmetric way, as shown in the following two equations, which at
the same time define the functions OE e (-) and OE
We note that equation (8) was also obtained in [16], where it was used to compute the
smallest eigenvalue which was known in advance to be even. However, the derivation of
the equation is quite different, concentrating exclusively on the smallest eigenvalue and
disregarding the spectral structure of the submatrices of T , which obscures important
properties of that equation.
To evaluate the functions OE(-), OE e (-) and OE o (-) and their derivatives, as we will need
to do later on, we need to compute expressions of the form s T S \Gammak s for a positive integer
k, where S is the real symmetric Toeplitz matrix defined by (s
In this work, we will use the Levinson-Durbin algorithm, abbreviated as
LDA. The original references for this algorithm are [11] and [18], but an excellent overview
of this and other Toeplitz-related algorithms can be found in [13]. Let us start with
In this case we have to solve \Gammas, where the minus sign in the right-hand side is by
convention. This system of linear equations is called the Yule-Walker (YW) system and
the LDA solves this problem recursively in 2n 2 flops, where we define one flop as in [13],
namely a multiplication/division or an addition/subtraction. Because of the persymmetry
of S, once the Yule-Walker equations are solved, the solution to
After solving the YW system, we have obtained
can then be evaluated as kS
2 in O(n) flops. To compute higher order derivatives, we
use a decomposition of S, supplied by the LDA itself in the process of solving the YW
system. Denoting by w (') the solution to the '-th dimensional YW subsystem, obtained
in the course of the LDA algorithm, this decomposition is given by U T
is a diagonal matrix and U is the upper triangular n \Theta n matrix, whose '-th column is
given by (Jw its diagonal elements are equal to one. This result is due
to [7]. We calculate s T S \Gamma3 s as follows:
s
This computation costs flops. To evaluate s T S \Gamma4 s, we compute first S \Gamma2 s as
once again, n 2 +O(n) flops, and then compute kS \Gamma2 sk 2
2 with
an additional O(n) flops. Roughly speaking, we can say that, for each increase of k by
one, we need to execute an additional n 2 flops.
Of course, there are other algorithms such as the fast Toeplitz solvers (see, e.g., [1]
and [2]), and these could be substituted for the LDA. However, this influences only the
complexity of computing our bounds and not the bounds themselves, which are the focus
of this work.
Approximations
As we mentioned before, our bounds will be obtained by the roots of approximations to
the secular equations. In the case of the smallest eigenvalue, those approximations will be
shown to be dominated by the spectral function, so that their root will provide an upper
bound on the smallest eigenvalue. Bounds for the largest eigenvalue will be based on the
bounds for the smallest eigenvalue of a different matrix. In the derivation of the bounds,
we will assume that the matrices are positive-definite, even though a slight modification
suffices to extend our results to general symmetric matrices. All this will be explained in
Section 4.
We shall now construct approximations to our spectral equations. These will be of
two types: rational and polynomial, each of which will be of three kinds: first, second and
third order.
Throughout this section we will consider approximations, obtained by interpolation at
function g of the form
2. Functions of this form occur in
all the equations considered in this paper. We note that g has simple poles at the fi j 's
and is a positive, monotonely increasing convex function (or on the interval
Our results are applicable for interpolation at a point -
different
from zero, simply by translating the origin to that point.
As mentioned before, we consider both rational and polynomial approximations of first,
second and third order and we will denote them, respectively, ae 1 , ae 2 , ae 3 for the rational
ones and - 1 , - 2 , - 3 for the polynomial ones. The polynomial approximations are nothing
but the Taylor polynomials of degree 1,2 and 3. We now define these approximations,
while cautioning that some of the parameters are defined "locally", i.e., the same letter
may have different meanings in different contexts, when no confusion is possible.
(1) First order rational. A function ae 1 (-) 4
ae 0
(0). The coefficients a and b are easily computed to be a
(0). It is not difficult to see that b is a weighted average of the fi j 's. We
therefore have that a ? 0 and and therefore that ae 1 is a positive, monotonely
increasing convex function on (\Gamma1; fi 1 ).
(2) Second order rational. A function ae 2 (-)
ae 0
(0). The coefficients a, b and c are then given by a =
(0)=g 002 (0) and (0). It is clear immediately that
similarly to what we had before, From Lemma 2.2 with
we have that a ? 0 as well. This same lemma also shows that the pole of ae 2 lies
closer to fi 1 than the pole of ae 1 . The approximation ae 2 is therefore positive, monotonely
increasing and convex on (\Gamma1; fi 1 ).
(3) Third order rational. A function ae 3 (-) a=(b\Gamma-)+c=(d\Gamma-) such that ae 3
ae 0
(0). For convenience, let us set
temporarily leave out the argument of g and its derivatives, i.e., g j g(0).
To compute the coefficients of ae 3 , we then have to solve the following system of equations
in a, c, v and w:
From Cramer's rule, we have
The first equation in (15) yields a equations in (15) then
give
By considering c instead of a, the analog of (15) yields
Equations (16) and (17) give, after some algebra:
This means that v and w are the solutions for x of the quadratic equation x
Lemma 2.2 with
vw ? 0, which in turn means that v; w ? 0. As a direct consequence from equations (16),
(17), (18) and (19), we then have that either w ! g 0 =g and v ? g 000 =3g 00 , or vice versa.
This is the same as saying that d ? g=g 0 and b ! 3g 00 =g 000 , or vice versa. In both cases,
using these inequalities in the expressions for a and c show that a; c ? 0. All the above
put together means that ae 3 is a positive, monotonely increasing convex function on the
interval (\Gamma1; minfb; d; fi 1 g). The minimum is, in fact, fi 1 , but this will be shown in the
next theorem. We note therefore, that the smallest pole of ae 3 lies between fi 1 and the pole
of ae 2 .
First-order polynomial. A function - 1 (-) 4
b- such that - 1
(0). The coefficients a and b are easily computed to be a = g(0) and
0 (0), which are all positive. The function - 1 is therefore a linear and increasing function
everywhere.
(5) Second-order polynomial. A function - 2 (-) 4
(0). The coefficients a, b and c are given by a
and and they are all positive. The function - 2 is therefore an increasing and
convex function for - 0.
Third-order polynomial. A function - 3 (-) 4
(0). The coefficients a, b, c and d are
000 (0)=6 and they are all positive. The function
- 3 is therefore an increasing and convex function for - 0.
Theorem 4.1 The following inequalities hold on the interval (0; fi 1
Proof. We first remark that some inequalities will be proved on the larger interval
us begin with inequalities (22). The function ae 1 (-) is a first order rational
approximation to g(-) at It is then immediate from Lemmas 2.1 and 2.2 with
g(-). The linear approximation - 1 (-) to g(-) at is also the
linear approximation to ae 1 (-) at that same point. Since ae 1 (-) is a convex function on
must lie below it on the same interval. This concludes the proof for
For we have that ae 2 (-) j a to second order.
This is the same as saying that b=(c \Gamma -) 2 approximates g 0 (-) up to first order. Lemmas
2.1 and 2.2 with yield that b=(c \Gamma -) 2 - g 0 (-), from which it then follows,
with
doe -
Integrating, we obtain b=(c Adding and subtracting a in the
left-hand side and using the function value interpolation condition concludes the proof for
2. We note that - 2 (-) interpolates both g(-) and ae 2 (-) at to second order.
This means that 2c-
(-) up to first order at
2 is convex on that interval. We then have that 2c-
2 (-) on that same
interval and we can integrate back to obtain the desired inequality for - 2 (0; fi 1 ).
For us first consider the difference
Using equations (16)-(19), it is not hard to show that b and d cannot be equal to fi 1 or
which we excluded. The function h(-) must therefore have m+1 roots.
roots, so that both b and d must lie inside the interval (fi 1
the number of roots to balance out (so that b and d can "destroy" existing roots of g on
that interval). This means that h cannot have other roots on the interval (0; fi 1 ) and must
therefore have the same sign throughout that interval. Since h(-) ! +1 as
1 , we
obtain that ae 3 (- g(-) on (0; fi 1 ). Turning now to - 3 (-), we have, similarly to the case
to third order at which is equivalent
to 2c
3 up to first order at
ae 00
3 (-) is convex on that same interval, which means that on that interval 2c+6d- ae 00
3 (-).
Integrating back twice, we obtain once again our inequality for - 2 (0; fi 1 ).
Let us now consider inequalities (23), starting with the inequality between ae 1 and ae 2 .
We first note that ae 1 approximates ae 2 up to first order. We also have
\Gamma2ae
a
Taking into account that a and b are positive and that c ? easily see that the
last term in the right-hand side of (25) is positive on (\Gamma1; fi 1 ), whereas the sum of the
first two terms is positive because of Lemma 2.2 with
then shows that ae 1 (- ae 2 (-) on (\Gamma1; fi 1 ).
For the inequality between ae 2 and ae 3 , it suffices to note that ae 2 approximates ae 3 up to
second order and that ae 3 is a function of the same form and with the same properties as
g. An argument analogous the one used to prove that ae 2 (- g(-) then also yields that
Inequalities (24) all follow by an analogous argument to the one used to prove the
inequalities between - i (-) after observing that - 1 is the first-order
approximation to - 2 , which itself is the second-order approximation to - 3 . 2
5 Bounds
We now finally derive our bounds on the extreme eigenvalues and we start by considering
the smallest eigenvalue. We first consider matrices that are positive-definite. Upper
bounds are then obtained by computing the roots of the various approximations at
to the secular equations OE(-), OE e (-) and OE o (-), which were defined in (2), (8) and (9). As
we have shown before, all these equations are of the form
where g(-) is of the form defined in (10) and ff 2 IR. Their approximations are obtained
by replacing g(-) with the various approximations that were described in the previous
section.
We first define the following:
where all quantities are as previously defined. Once again, all these functions are of the
same form as the function g, defined in (10).
The bounds obtained by replacing f(-) in OE(-) with ae 1 , ae 2 and ae 3 will be denoted r 1 ,
r 2 and r 3 , respectively. Those bounds obtained by replacing f(-) with - 1 , - 2 and - 3 will
be denoted respectively. As an example, this means that r 1 is the root of
the equation
which is obtained by solving a quadratic equation. To compute r 3 and p 3 , a cubic equation
needs to be solved, which can either be accomplished in closed form, or by an iterative
method such as Newton's method (at negligable cost, compared to the computation of
g(0)).
This general bound-naming procedure is now applied to OE e (-) and OE
the bounds on the smallest even eigenvalue are obtained by approximating f e (-) in OE e (-)
and they will be denoted by r e
3 for the rational approximations and p e
2 and p efor the polynomial approximations. For the odd eigenvalues, approximating f
yields the bounds r
3 and p
3 for the rational and polynomial approximations,
respectively. If one uses the LDA for the computation of the spectral equations and their
derivatives as was discussed in Section 3, then the computational cost for first, second and
third order bounds is 2n 2 +O(n), 3n 2 +O(n) and 4n 2 +O(n) flops, respectively.
One of the advantages of the rational approximations is that, contrary to polynomial
approximations, they always generate bounds that are guaranteed not to exceed the largest
pole of f , f e or f applies, as is obvious from their properties, regardless of
how badly behaved the matrix is. In addition to providing separate bounds on the even
and odd eigenvalues, the approximations to the functions OE e (-) and OE should be more
accurate than those for the function OE(-) since now only roughly half of the terms appear
in the function to be interpolated. There is also the additional benefit that both the
smallest and the largest roots are now farther removed from the nearest singularity in the
equation so that once again an improved approximation can be expected. All this is borne
out by our numerical experiments.
Better upper bounds can be obtained if a positive lower bound is known on the smallest
eigenvalue. The only difference in that case is that the approximations are performed at
that lower bound, rather than at As was mentioned before, all our results can be
aplied in this case to the same spectral equations, but with the origin translated to the
lower bound.
Before presenting numerical comparisons in the next section, we will first establish a
theoretical result. We denote the smallest even and odd eigenvalues of T by - e
min and -
min ,
respectively and its smallest eigenvalue by - min . We note that -
min g.
The theoretical comparisons between the various bounds are then given in the following
theorem:
Theorem 5.1 The upper bounds on the mallest eigenvalue of T satisfy:
Proof. The proof follows immediately from the properties of the approximations that
define the bounds, which were proved in Theorem 4.1. 2
This theorem shows that the bounds, obtained by rational approximations, are always
superior to those obtained by polynomial approximations, which should not be surprising,
as the functions they approximate are themselves rational. It also confirms the intuitive
result that, as the order of the approximations increases, then so does the accuracy of the
bounds. This also means that the bounds obtained in [10] (the best currently available),
which are all based on polynomial approximations and correspond to our
are inferior to those produced by rational approximations.
Let us now consider lower bounds on the largest eigenvalue. The largest eigenvalue of
T can be bounded from below, given an upper bound ffi on it. This can be accomplished by
translating the origin in the spectral equations to ffi, replacing the resulting new variable
by its opposite and multiplying the equation by \Gamma1, thus obtaining the exact same type
of spectral equation for the matrix ffiI \Gamma T , which is always positive definite. Computing
an upper bound on the smallest eigenvalue of this new matrix then leads to the desired
bound on the largest eigenvalue, since - min possible value
for ffi is the Frobenius norm of T , defined as (see [13]):
ijA
which for a Toeplitz matrix can be computed in O(n) flops. An exact analog of Theorem
5.1 holds for the maximal eigenvalues.
To conclude this section we briefly consider the fact that the same procedure for
obtaining bounds for real symmetric postive-definite matrices can be used for general real
symmetric matrices as well, provided that a lower bound on the smallest eigenvalue is
available. Any known lower bound can be used (see, e.g., [10] or [14]), or one could be
obtained by a process where a trial value is iteratively lowered until it falls below the
smallest eigenvalue. Calling such a trial value ffl, Sylvester's law of inertia can then be
applied to the decomposition of (T \Gamma fflI ), which was used in Section 3, to determine its
position relative to the smallest eigenvalue of T . Such a procedure is extensively described
and used in, e.g., [8], [15] and [23], and we refer to these papers for further details.
6 Numerical results
In this section we will test our methods on four classes of positive semi-definite matrices.
For each class and for each of the dimensions we have run 200 experiments
to examine the quality of the bounds on the smallest eigenvalue and 200 separate
experiments doing the same for the maximal eigenvalue. The tables report the average
values (with their standard deviations in parentheses) of the bound to eigenvalue ratio
for the smallest eigenvalue and eigenvalue to bound ratio for the largest eigenvalue. The
closer this ratio is to one, the better the bound. Each entry in the table has a left and
right part, separated by a slash. The left part pertains to the use of OE e and OE o (i.e., the
bound is obtained by taking the minimum of the bounds on the even and odd extreme
eigenvalues), whereas the right part represents the use of OE. The figures represent the
distribution of the ratios among the 200 experiments, with the total range of the ratios
divided into five "bins". The frequency associated with those bins is then graphed versus
their midpoints. We note that the x-axis is scaled differently for each figure to accomodate
the entire range of ratios. The solid line represents the bounds obtained by using OE e and
the dashed line represents the use of OE. The dimension is indicated by n. The
polynomial approximation-based bounds are denoted by "Taylor", followed by the order
of the approximation. Let us now list the four classes of matrices.
(1) CVL matrices. These are matrices defined in [8] (whence their name) as
where n is the dimension of T , - is such that T
These matrices are positive semi-definite of rank two. We generated random matrices of
this kind by taking the value of ' to be uniformly distributed on [0; 1].
(2) KMS matrices. These are the Kac-Murdock-Szeg-o matrices (see [17]), defined as
is the dimension of the matrix. These matrices
are positive definite and are characterized by the fact that their even and odd eigenvalues
lie extremely close together. Random matrices of this kind were generated by taking the
value of - to be uniformly distributed on [0; 1].
(3) UNF matrices. We define UNF matrices by first defining a random vector v of length
whose components are uniformly distributed on [\Gamma10; 10]. We then modify that vector
by adding to its first component 1.1 times the absolute value of the smallest eigenvalue of
the Toeplitz matrix generated by v. Finally, the vector v is normalized by dividing it by
its first component, provided that it is different from zero. The Toeplitz matrix generated
by this normalized vector is then called an UNF matrix. From their construction, these
matrices are positive semi-definite.
matrices. We define NRM matrices exactly like UNF matrices, the only
difference being that the random vector v now has its components normally distributed
with mean and standard deviation equal to 0 and 10, respectively. As in the uniform case,
these matrices are positive semi-definite.
Theoretically, some of the matrices generated in the experiments might be singular,
although we never encountered this situation in practice. A typical distribution of the
spectra (even on top, odd at the bottom) for these four classes of matrices is shown in

Figure

1.
CVL
KMS
UNF
NRM

Figure

1: Typical distribution of the even and odd spectra for the four classes test
matrices (n=200).
The experiments clearly show that exploiting the even and odd spectra yields better
bounds. The magnitude of the improvement diminishes the closer the even and odd
eigenvalues are lying together, as is obviously true for the KMS matrices. The superiority
of rational bounds is also clearly demonstrated, both in their smaller average ratios and
smaller standard deviations. They may yield a ratio of up to three times smaller than
polynomial ones and in many cases, lower-order rational bounds are better than higher-order
polynomial ones. This is especially true for larger matrix dimensions. These results
also confirm our previous remark that the bounds obtained in [10] are inferior to rational
approximation-based bounds.
Although we did not report results on bounds for the even and odd eigenvalues sep-
arately, we did verify that they are virtually identical to those obtained for the smallest
eigenvalue proper.
All experiments were run in MATLAB on a Pentium II 233MHz machine.
We conclude that computing separate, rational approximation-based, bounds on the
even and odd spectra leads to a significant improvement over existing bounds.
Figure

2: Distribution of bound/eigenvalue ratio for the minimal eigenvalue of CVL matrices
with dimension n=100,200,400.
Method Dimension
100 200 400

Table

1: Bound to eigenvalue ratio for the minimal eigenvalue of CVL matrices.
Taylor1.3 1.4 1.5 1.6 1.7 1.8 1.9 2 2.150
Taylor1.2 1.450
Taylor
Figure

3: Distribution of eigenvalue/bound ratio for the maximal eigenvalue of CVL matrices
with dimension n=100,200,400.
Method Dimension
100 200 400

Table

2: Eigenvalue to bound ratio for the maximal eigenvalue of CVL matrices.
1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 250Taylor1 1.1 1.2 1.3 1.4 1.5 1.650
1.1 1.2 1.3 1.4 1.5 1.6 1.750Taylor1 1.05 1.1 1.15 1.2 1.25 1.3 1.3520Rational1 1.05 1.1 1.15 1.2 1.25 1.3 1.35 1.4 1.45 1.550Taylor1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 220n=200
1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 250Taylor1 1.1 1.2 1.3 1.4 1.5 1.620Rational1 1.1 1.2 1.3 1.4 1.5 1.6 1.750Taylor1 1.05 1.1 1.15 1.2 1.25 1.3 1.3520Rational1 1.05 1.1 1.15 1.2 1.25 1.3 1.35 1.4 1.45 1.550Taylor1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 220n=400
Taylor1 1.1 1.2 1.3 1.4 1.5 1.620Rational1 1.1 1.2 1.3 1.4 1.5 1.6 1.750Taylor1 1.05 1.1 1.15 1.2 1.25 1.3 1.3520Rational1 1.05 1.1 1.15 1.2 1.25 1.3 1.35 1.4 1.45 1.550Taylor
Figure

4: Distribution of bound/eigenvalue ratio for the minimal eigenvalue of KMS matrices
with dimension n=100,200,400.
Method Dimension
100 200 400

Table

3: Bound to eigenvalue ratio for the minimal eigenvalue of KMS matrices.
Figure

5: Distribution of eigenvalue/bound ratio for the maximal eigenvalue of KMS
matrices with dimension n=100,200,400.
Method Dimension
100 200 400

Table

4: Eigenvalue to bound ratio for the maximal eigenvalue of KMS matrices.
Figure

Distribution of bound/eigenvalue ratio for the minimal eigenvalue of UNF matrices
with dimension n=100,200,400.
Method Dimension
100 200 400

Table

5: Bound to eigenvalue ratio for the minimal eigenvalue of UNF matrices.
2.2 2.4 2.6 2.8 350Taylor1 1.05 1.1 1.15 1.2 1.25 1.3 1.3550Rational1.4 1.6 1.8 2 2.2 2.4 2.6 2.8 350
Taylor1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.850
2.3 2.4 2.550
Taylor1.1 1.2 1.3 1.4 1.5 1.6 1.750
2.3 2.4 2.550
1.1 1.15 1.2 1.25 1.3 1.3550
2.3 2.4 2.550
2.3 2.4 2.550
Taylor1.2 1.25 1.3 1.35 1.4 1.45 1.5 1.55 1.6 1.65 1.750
2.3 2.4 2.550Taylor1.1 1.15 1.2 1.25 1.3 1.35 1.450
2.3 2.4 2.550Taylor
Figure

7: Distribution of eigenvalue/bound ratio for the maximal eigenvalue of UNF
matrices with dimension n=100,200,400.
Method Dimension
100 200 400

Table

Eigenvalue to bound ratio for the maximal eigenvalue of UNF matrices.
Taylor1 1.1 1.2 1.3 1.4 1.5 1.650Rational1 1.2 1.4 1.6 1.8 2 2.2 2.4 2.6 2.850
Rational 1
Taylor
Figure

8: Distribution of bound/eigenvalue ratio for the minimal eigenvalue of NRM
matrices with dimension n=100,200,400.
Method Dimension
100 200 400

Table

7: Bound to eigenvalue ratio for the minimal eigenvalue of NRM matrices.
Rational1.4 1.6 1.8 2 2.2 2.4 2.6 2.850Taylor1.1 1.2 1.3 1.4 1.5 1.6 1.750Rational1.4 1.6 1.8 2 2.2 2.4 2.650Taylor1 1.05 1.1 1.15 1.2 1.25 1.3 1.3550Rational1.2 1.4 1.6 1.8 2 2.2 2.4 2.650Taylor1.15 1.2 1.25 1.3 1.35 1.4 1.45 1.5 1.55 1.6 1.6550
2.3 2.420Taylor1.2 1.25 1.3 1.35 1.4 1.45 1.5 1.55 1.6 1.6520Rational1.5 1.6 1.7 1.8 1.9 2 2.1 2.2 2.3 2.420Taylor1.1 1.15 1.2 1.25 1.3 1.35 1.420Rational1.5 1.6 1.7 1.8 1.9 2 2.1 2.2 2.320Taylor
Figure

9: Distribution of eigenvalue/bound ratio for the maximal eigenvalue of NRM
matrices with dimension n=100,200,400.
Method Dimension
100 200 400

Table

8: Eigenvalue to bound ratio for the maximal eigenvalue of NRM matrices.



--R

The generalized Schur algorithm for the superfast solution of Toeplitz systems.
Numerical experience with a superfast Toeplitz solver.
Eigenvectors of certain matrices.
Stability of methods for solving Toeplitz systems of equations.

Eigenvalues and eigenvectors of symmetric centrosymmetric matrices.
The numerical stability of the Levinson-Durbin algortihm for Toeplitz systems of equations
Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix.
Spectral properties of finite Toeplitz matrices.
Bounds on the extreme eigenvalues of positive definite Toeplitz matrices.
The fitting of time series model.
Some modified matrix eigenvalue problems.
Matrix Computations.
Simple bounds on the extreme eigenvalues of Toeplitz matrices.
Toeplitz eigensystem solver.
Symmetric solutions and eigenvalue problems of Toeplitz systems.
On the eigenvalues of certain Hermitian forms.
The Wiener RMS (root mean square) error criterion in filter design and prediction.
The minimum eigenvalue of a symmetric positive-definite Toeplitz matrix and rational Hermitian interpolation
A unifying convergence analysis of second-order methods for secular equations
Spectral functions for real symmetric Toeplitz matrices.
A note on the eigenvalues of Hermitian matrices.
Numerical solution of the eigenvalue problem for Hermitian Toeplitz matrices.
--TR
toeplitz matrix;spectral equation;bounds;rational approximation;secular equation;eigenvalues