To this end,
we note that tasks such as counting the
number of eigenvalues of that are smaller than a given real
number
or are in a given interval
do not require computing
the eigenvalues and so can be performed much more cheaply.
The key tool is the matrix inertia.
The inertia of
is the triplet of integers
,
where
is the number of negative eigenvalues of
,
is the number of zero eigenvalues of
, and
is the number of positive eigenvalues of
.
Sylvester's law of inertia
states that the inertia of a matrix is invariant
under congruence; that is, for all nonsingular matrices
,
, and
have the same inertia. See, for examples,
[198, p. 403] or [114, p. 202].
Suppose that the shifted matrix has
the LDL
factorization
It is easy to see that
is
the number of eigenvalues in the interval
,
assuming that
and
the two shifted matrices
and
are nonsingular. Thus, the cost of counting the
number of eigenvalues of
in a given interval
is equivalent to the cost of two LDL
factorizations of
and
, respectively.
This is much cheaper than finding all eigenvalues in
.
We refer to §10.3 for the software availability
of the LDL
factorization.
In practice, the counting technique is frequently used as
a verification tool for the so-called
trust interval of a numerical method for
finding all eigenvalues in a given interval
.