Notation
Next: Mathematical Properties
Up: Templates for Solution
Previous: Templates for Solution
 Matrix Pencil:

We will talk mostly about eigenproblems of the form .
is also called a matrix pencil.
is an indeterminate in this latter expression,
and indicates that there are two matrices which define the eigenproblem.
and need not be square.
 Eigenvalues and Eigenvectors:

For almost all fixed scalar values of , the
rank of the matrix will be constant. The discrete set of values
of
for which the rank of is lower than this constant are
the eigenvalues. Let be the discrete set of
eigenvalues. Some may be infinite, in which case we really consider
with eigenvalue .
Nonzero vectors and such that
are called a right eigenvector and a left eigenvector,
respectively, where
is the transpose of and is its conjugatetranspose.
The word eigenvector alone will mean right eigenvector.
Since there are many kinds of eigenproblems, and associated algorithms, we
propose some simple top level categories to help classify them.
The ultimate decision tree presented to the reader will begin with easier
concepts and questions about the eigenproblem in an attempt to classify it,
and proceed to harder questions. For the purposes of this overview, we will
use rather more advanced categories in order to be brief but precise.
For background, see [12][25][23].
 Regular and Singular Pencils:

is regular if
and are square and
is not identically zero for all ; otherwise it
is singular.
Regular pencils have welldefined sets of eigenvalues
which change continuously as functions of and ;
this is a minimal requirement to be able to compute the
eigenvalues accurately, in the absence of other
constraints on and . Singular pencils have eigenvalues
which can change discontinuously as functions of
and ; extra information about and ,
as well as special algorithms which use this information,
are necessary in order to compute meaningful eigenvalues.
Regular and singular pencils have correspondingly different
canonical forms representing their spectral
decompositions. The Jordan Canonical Form of a single
matrix is the best known; the Kronecker Canonical Form
of a singular pencil is the most general. More will be
discussed in section 4.3
below.
 Selfadjoint and Nonselfadjoint Eigenproblems:

We abuse notation to avoid confusion with the very
similar but less general notions of Hermitian and nonHermitian:
We call an eigenproblem is selfadjoint if
1) and are both Hermitian, and
2) there is a nonsingular such that and
are real and diagonal.
Thus the finite eigenvalues are real, all elementary divisors
are linear, and the only possible singular blocks in the
Kronecker Canonical Form represent a common null space of
and . The primary source of selfadjoint eigenproblems is
eigenvalue problems in which is known to be positive definite;
in this case is called a definite pencil.
These properties lead to generally simpler and more
accurate algorithms. We classify the singular value decomposition (SVD)
and its generalizations as selfadjoint, because of the relationship
between the SVD of and the eigendecomposition of the Hermitian
matrix .
It is sometimes possible to change the classification of an eigenproblem
by simple transformations. For example, multiplying a skewHermitian
matrix (i.e., )
by the constant makes it Hermitian, so its
eigenproblem becomes selfadjoint. Such simple transformations are very
useful in finding the best algorithm for a problem.
Many other definition and notation will be introduced in section
4.3.
Next: Mathematical Properties
Up: Templates for Solution
Previous: Templates for Solution
Jack Dongarra
Wed Jun 21 02:35:11 EDT 1995