To explain s and sep , we need to introduce the spectral projector P [56][72], and the separation of two matrices A and B, sep(A , B) [75][72].
We may assume the matrix A is in Schur form, because reducing it to this form does not change the values of s and sep. Consider a cluster of m > = 1 eigenvalues, counting multiplicities. Further assume the n-by-n matrix A is
where the eigenvalues of the m-by-n matrix
are exactly those in which we are
interested. In practice, if the eigenvalues on the diagonal of A
are in the wrong order, routine xTREXC
can be used to put the desired ones in the upper left corner
as shown.
We define the spectral projector, or simply projector P belonging
to the eigenvalues of as
where R satisfies the system of linear equations
Equation (4.3) is called a Sylvester equation . Given the Schur form (4.1), we solve equation (4.3) for R using the subroutine xTRSYL.
We can now define s for the eigenvalues of :
In practice we do not use this expression since 
is hard to
compute. Instead we use the more easily computed underestimate
which can underestimate the true value of s by no more than a factor
.
This underestimation makes our error bounds more conservative.
This approximation of s is called RCONDE in xGEEVX and xGEESX.
The separation 
of the matrices and
is defined as the smallest singular value of the linear
map in (4.3) which takes X to 
, i.e.,
This formulation lets us estimate
using the condition estimator
xLACON [52][51][48], which estimates the norm of
a linear operator 
given the ability to compute T and
quickly for arbitrary x.
In our case, multiplying an
arbitrary vector by T
means solving the Sylvester equation (4.3)
with an arbitrary right hand side using xTRSYL, and multiplying by
means solving the same equation with replaced by
and replaced by 
. Solving either equation
costs at most 
operations, or as few as 
if m << n.
Since the true value of sep is 
but we use ,
our estimate of sep may differ from the true value by as much as
. This approximation to sep is called
RCONDV by xGEEVX and xGEESX.
Another formulation which in principle permits an exact evaluation of
is
where 
is the Kronecker product of X and Y.
This method is
generally impractical, however, because the matrix whose smallest singular
value we need is m(n - m) dimensional, which can be as large as
. Thus we would require as much as 
extra workspace and
operations, much more than the estimation method of the last
paragraph.
The expression measures the ``separation'' of
the spectra
of and in the following sense. It is zero if and only if
and have a common eigenvalue, and small if there is a small
perturbation of either one that makes them have a common eigenvalue. If
and are both Hermitian matrices, then
is just the gap, or minimum distance between an eigenvalue of and an
eigenvalue of . On the other hand, if and are
non-Hermitian, may be much smaller than
this gap.
