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.

Tue Nov 29 14:03:33 EST 1994