next up previous
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 conjugate-transpose. 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 well-defined 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.

Self-adjoint and Non-self-adjoint Eigenproblems:
We abuse notation to avoid confusion with the very similar but less general notions of Hermitian and non-Hermitian: We call an eigenproblem is self-adjoint 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 self-adjoint 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 self-adjoint, 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 skew-Hermitian matrix (i.e., ) by the constant makes it Hermitian, so its eigenproblem becomes self-adjoint. 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 up previous
Next: Mathematical Properties Up: Templates for Solution Previous: Templates for Solution

Jack Dongarra
Wed Jun 21 02:35:11 EDT 1995