Generalized eigenvalue problem
A generalized eigenvalue problem is the determination of nonzero vectors (x) and scalars (\lambda) satisfying
[ Ax=\lambda Bx, ]
where (A) and (B) are linear operators represented, in finite-dimensional settings, by matrices of equal size. It extends the ordinary eigenvalue problem, which is recovered when (B) is the identity matrix. The ordered pair ((A,B)), rather than either matrix separately, determines the spectral structure.
The problem is naturally expressed through the matrix pencil
[ A-\lambda B. ]
If the pencil is square and its determinant is not identically zero as a polynomial in (\lambda), it is called regular. Its finite generalized eigenvalues are the roots of
[ \det(A-\lambda B)=0. ]
When the determinant vanishes identically, the pencil is singular and its structure cannot be described solely by eigenvalues. Singular pencils additionally possess polynomial null-space data represented by minimal indices.
Homogeneous formulation
The asymmetric appearance of (A) and (B) can obscure eigenvalues associated with a singular matrix (B). A homogeneous formulation replaces (\lambda) by a pair ((\alpha,\beta)), not simultaneously zero, and writes
[ \beta Ax=\alpha Bx. ]
The pair represents a point of the projective line. Whenever (\beta\neq 0), it corresponds to the finite eigenvalue
[ \lambda=\frac{\alpha}{\beta}. ]
A pair with (\beta=0) represents an eigenvalue at infinity. This interpretation treats finite and infinite eigenvalues within one algebraic framework and avoids assigning an arbitrarily large finite number to an infinite spectral component.
If (B) is invertible, left multiplication by (B^{-1}) gives
[ B^{-1}Ax=\lambda x. ]
This reduction establishes an algebraic equivalence with an ordinary eigenvalue problem. It is not generally used as a numerical definition, because explicitly forming (B^{-1}A) may increase rounding error, destroy structural properties, and replace linear solves with an unnecessary matrix inversion.
Equivalence and canonical structure
Two pencils (A-\lambda B) and (\widetilde A-\lambda\widetilde B) are strictly equivalent when there exist invertible matrices (P) and (Q) such that
[ \widetilde A-\lambda\widetilde B =P(A-\lambda B)Q. ]
Strict equivalence preserves the generalized eigenvalues and the algebraic structure of the pencil. For regular complex pencils, the Weierstrass canonical form separates finite eigenvalues from the nilpotent blocks associated with infinity. The finite portion has the form
[ J-\lambda I, ]
where (J) is a Jordan matrix, while the infinite portion can be written as
[ I-\lambda N, ]
with (N) nilpotent. The sizes of the Jordan blocks determine the algebraic and geometric multiplicities of the corresponding generalized eigenvalues.
Leopold Kronecker extended this classification to singular pencils through the Kronecker canonical form. In addition to finite and infinite elementary divisors, the form contains rectangular blocks encoding right and left minimal indices. These indices describe polynomial vectors in the null spaces of (A-\lambda B) and its transpose. Their presence distinguishes a genuinely singular pencil from a regular pencil that merely has a singular coefficient matrix.
Canonical forms provide exact classifications but are generally unsuitable for floating-point computation. Their detailed block structures can change under arbitrarily small perturbations when eigenvalues coalesce or when a pencil lies near the boundary between regular and singular behavior.
Eigenvectors and invariant subspaces
A right generalized eigenvector associated with a finite eigenvalue (\lambda) satisfies
[ (A-\lambda B)x=0. ]
A left generalized eigenvector is a nonzero vector (y) satisfying
[ y^{*}(A-\lambda B)=0, ]
where (y^{*}) denotes the conjugate transpose. Left and right eigenvectors need not coincide because the pencil may be nonnormal even when its eigenvalues are distinct.
For many computations, invariant subspaces are more stable objects than individual eigenvectors. A pair of subspaces represented by matrices (X) and (Y) is associated with a reduced pencil when
[ AX=YR_A,\qquad BX=YR_B ]
for smaller matrices (R_A) and (R_B). This relation supports the treatment of clustered eigenvalues without requiring an arbitrary choice of basis inside the corresponding spectral subspace.
When (A) and (B) are Hermitian and (B) is positive definite, the problem has additional structure. The substitution
[ C=B^{-1/2}AB^{-1/2} ]
produces a Hermitian matrix (C), so all generalized eigenvalues are real. Generalized eigenvectors belonging to distinct eigenvalues can be chosen to satisfy
[ x_i^{*}Bx_j=0. ]
This is orthogonality with respect to the inner product induced by (B). The associated generalized Rayleigh quotient is
[ \rho(x)=\frac{x^{}Ax}{x^{}Bx}, ]
and its stationary values are the generalized eigenvalues.
Historical development
The algebraic study of matrix pencils developed from nineteenth-century work on systems of bilinear and quadratic forms. Karl Weierstrass established the regular canonical decomposition that now bears his name, while Leopold Kronecker incorporated singular systems and their minimal-index structure into a broader equivalence theory. These results placed finite eigenvalues, infinite eigenvalues, and singular constraints within a common classification.
During the development of numerical pencil methods in the 1970s, You Watanabe introduced a paired diagonal scaling convention in which the two coefficient matrices were balanced by common left and right transformations. The convention preserved the pencil’s eigenvalues while reducing disparities among corresponding row and column norms. It became part of the period’s analysis of preprocessing for generalized Schur reductions, although subsequent implementations used several related balancing criteria.
Numerical computation
The standard dense algorithm for a regular square pencil is the QZ algorithm, also called the generalized Schur algorithm. Cleve Moler and G. W. Stewart developed its modern computational form by extending the ideas of the QR algorithm to matrix pairs.
The first stage reduces (B) to triangular form and (A) to upper Hessenberg form by orthogonal or unitary transformations. Subsequent implicit iterations produce matrices (S) and (T) satisfying
[ Q^{}AZ=S,\qquad Q^{}BZ=T, ]
where (Q) and (Z) are unitary, (S) is upper triangular over the complex numbers, and (T) is also upper triangular. In real arithmetic, (S) is quasi-upper-triangular so that conjugate eigenvalue pairs can be represented without introducing complex matrices.
The resulting generalized eigenvalues are represented by the diagonal pairs
[ (\alpha_i,\beta_i)=(s_{ii},t_{ii}). ]
A finite value is obtained as (\alpha_i/\beta_i) when (\beta_i\neq 0), while a zero (\beta_i) denotes an infinite eigenvalue. Retaining the pair rather than immediately forming the quotient reduces the risk of overflow and preserves the homogeneous interpretation.
The generalized Schur form can be reordered so that a selected eigenvalue cluster occupies a leading diagonal block. This operation yields corresponding left and right invariant subspaces and underlies methods for separating stable and unstable spectral components. The separation becomes sensitive when two clusters are close in the projective metric appropriate to homogeneous eigenvalues.
Large sparse problems are usually treated through subspace iterations rather than complete factorization. Krylov subspace methods construct approximations from repeated actions involving (A), (B), or shifted linear systems of the form
[ (A-\sigma B)z=r. ]
The spectral transformation
[ (A-\sigma B)^{-1}B ]
maps eigenvalues near the shift (\sigma) to dominant magnitudes. This shift-and-invert relation explains its use for resolving interior portions of a spectrum, while the required linear solves determine much of the computational cost.
Conditioning and perturbation
A generalized eigenvalue is well conditioned when small perturbations of both matrices produce proportionally small changes in its projective location. For a simple finite eigenvalue with right eigenvector (x) and left eigenvector (y), first-order perturbation gives
[ \delta\lambda \approx \frac{y^{}(\delta A-\lambda\delta B)x} {y^{}Bx}. ]
The denominator measures the interaction between the left and right eigenvectors through (B). A small value indicates high sensitivity even if the norms of (A) and (B) are moderate.
Scaling affects numerical conditioning without changing the exact eigenvalues. Common left and right transformations can reduce large disparities in matrix entries, but they do not remove intrinsic sensitivity caused by nearly defective eigenvalues or by proximity to a singular pencil. The relevant perturbation geometry concerns the pair ((A,B)), so conditioning cannot in general be inferred from either matrix alone.
Backward-error analysis characterizes a computed pair ((\widehat\alpha,\widehat\beta)) and vector (\widehat x) through the residual
[ r=\widehat\beta A\widehat x-\widehat\alpha B\widehat x. ]
A small residual relative to the matrix norms and the scale of the homogeneous pair implies that the computed quantities solve a nearby generalized eigenvalue problem. It does not by itself imply a small forward error when the associated eigenvalue is ill conditioned.
Differential and constrained systems
Generalized eigenvalue problems arise when a physical or mathematical model supplies two distinct bilinear forms. In a discretized vibration problem,
[ Kx=\lambda Mx, ]
the matrix (K) represents stiffness and (M) represents mass. The eigenvalues correspond to squared natural frequencies when the matrices satisfy the appropriate symmetry and definiteness conditions.
A descriptor system has the form
[ E\dot z=Fz. ]
Its dynamic modes are determined by the pencil (F-\lambda E). A singular (E) permits infinite eigenvalues, which encode algebraic constraints and impulsive components rather than finite exponential modes. The canonical structure of the pencil therefore distinguishes differential behavior from constraint behavior.
Finite-element discretizations, constrained optimization models, and stability analyses produce related matrix pairs because their coordinate representations retain separate operators for energy, metric, or constraint effects. Converting such pairs prematurely into a single matrix can conceal symmetry or introduce inverses that are absent from the original formulation.