Lagrangian invariant subspaces for symplectic matrices play an important role in the numerical solution of discrete time, robust and optimal control problems. The sensitivity (perturbation) analysis of these subspaces, however, is a difficult problem, in particular, when the eigenvalues are on or close to some critical regions in the complex plane, such as the unit circle.
We present a detailed perturbation analysis for several different cases of real and complex symplectic matrices. We analyze stability and conditional stability
as well as the index of stability for these subspaces.
Canonical forms for matrix triples $(A,G,\hat G)$, where
$A$ is arbitrary rectangular and $G$, $\hat G$ are either real symmetric
or skew symmetric, or complex Hermitian or skew Hermitian, are derived.
These forms generalize classical product Schur forms as well as
singular value decompositions.
An new proof for the complex case is given, where there is no need to
distinguish whether $G$ and $\hat G$ are Hermitian or skew Hermitian.
This proof is independent from the results in Bolschakov/Reichstein 1995, where
a similar canonical form has been obtained for the complex case,
and it allows generalization to the real case. Here,
the three cases, i.e., that
$G$ and $\hat G$ are both symmetric, both skew symmetric or one each,
are treated separately.
For selfadjoint matrices in an indefinite inner product, possible canonical forms are identified that arise when the matrix is subjected to a selfadjoint generic rank one perturbation. Genericity is understood in
the sense of algebraic geometry. Special attention is paid to the perturbation
behavior of the sign characteristic. Typically, under such a perturbation,
for every given eigenvalue, the largest Jordan block of the eigenvalue is
destroyed and (in case the eigenvalue is real) all other Jordan blocks
keep their sign characteristic. The new eigenvalues, i.e., those eigenvalues of
the perturbed matrix that are not eigenvalues of the original matrix,
are typically simple, and in some cases information is provided about their sign
characteristic (if the new eigenvalue is real). The main results are proved by using
the well known canonical forms of selfadjoint matrices in an indefinite inner product, a version of the Brunovsky
canonical form and on general results concerning rank one perturbations.
Many applications give rise to matrix polynomials whose coefficients have
a kind of reversal symmetry, a structure we call palindromic.
Several properties of scalar palindromic polynomials are derived,
and together with properties of compound matrices, used to
establish the Smith form of regular and singular T-palindromic matrix polynomials,
over arbitrary fields.
The invariant polynomials are shown to
inherit palindromicity,
and their structure is described in detail.
Jordan structures of palindromic matrix polynomials are characterized,
and necessary conditions for the
existence of structured linearizations established.
In the odd degree case, a constructive procedure for building
palindromic linearizations shows that the necessary conditions are sufficient as well.
The Smith form for *-palindromic polynomials is also analyzed. Finally, results for palindromic matrix polynomials over fields of
characteristic two are presented.
Alternating matrix polynomials, that is, polynomials whose coefficients
alternate between symmetric and skew-symmetric matrices,
generalize the notions of even and odd scalar polynomials.
We investigate the Smith forms of alternating matrix polynomials,
showing that each invariant factor is an even or odd scalar polynomial.
Necessary and sufficient conditions
are derived for a given Smith form to be that of an alternating matrix polynomial.
These conditions allow a characterization of the possible Jordan structures
of alternating matrix polynomials,
and also lead to necessary and sufficient conditions
for the existence of structure-preserving strong linearizations.
Most of the results are applicable to singular as well
as regular matrix polynomials.
We study the perturbation theory of structured matrices under
structured rank one perturbations, and then focus on several classes of complex
matrices. Generic Jordan structures of perturbed matrices are identified.
It is shown that the perturbation
behavior of the Jordan structures
is substantially different from the corresponding theory for unstructured generic
rank one perturbations.
New perturbation results for the behavior of eigenvalues and Jordan forms of real and complex matrices
under generic rank one perturbations are discussed. Several results that are available in the complex
case are proved as well for the real case and the assumptions on the genericity are weakened.
Rank one perturbations that lead to maximal algebraic multiplicities of the ``new" eigenvalues are also
discussed.
We characterize the Smith form of skew-symmetric matrix polynomials
over an arbitrary field $\F$,
showing that all elementary divisors occur with even multiplicity.
Restricting the class of equivalence transformations to unimodular congruences,
a Smith-like skew-symmetric canonical form
for skew-symmetric matrix polynomials is also obtained.
These results are used to analyze the eigenvalue and elementary divisor structure
of matrices expressible as products of two skew-symmetric matrices,
as well as the existence of structured linearizations
for skew-symmetric matrix polynomials.
By contrast with other classes of structured matrix polynomials
(e.g., alternating or palindromic polynomials),
every regular skew-symmetric matrix polynomial
is shown to have a structured strong linearization.
While there are singular skew-symmetric polynomials of even degree
for which a structured linearization is impossible,
for each odd degree we develop a skew-symmetric companion form
that uniformly provides a structured linearization
for every regular and singular skew-symmetric polynomial
of that degree.
Finally, the results are applied to the construction of minimal
symmetric factorizations of skew-symmetric rational matrices.
Canonical forms are developed for several sets of complex matrices that are normal
with respect to an indefinite inner product induced by a nonsingular Hermitian,
symmetric, or skew-symmetric matrix. The most general result covers the case of
polynomially normal matrices, i.e., matrices whose adjoint with respect to the indefinite
inner product is a polynomial of the original matrix. From this result, canonical
forms for matrices that are selfadjoint, skewadjoint, or unitary with respect to the
given indefinite inner product are derived.
Real polynomially normal matrices are studied, i.e., matrices whose adjoint with
respect to the indefinite inner product is a polynomial in the matrix. The set of these matrices is
a subset of indefinite inner product normal matrices that contains all selfadjoint, skew-adjoint, and
unitary matrices, but that is small enough such that all elements can be completely classified. The
essential decomposition of a real polynomially normal matrix is introduced. This is a decomposition
into three parts, one part having real spectrum only and two parts that can be described by two
complex matrices that are polynomially normal with respect to a sesquilinear and bilinear form,
respectively. In the paper, the essential decomposition is used as a tool in order to derive a sufficient
condition for existence of invariant semidefinite subspaces and to obtain canonical forms for real
polynomially normal matrices. In particular, canonical forms for real matrices that are selfadjoint,
skewadjoint, or unitary with respect to an indefinite inner product are recovered.
The classical approach to investigating polynomial eigenvalue problems is linearization, where the
polynomial is converted into a larger matrix pencil with the same eigenvalues. For any polynomial there are infinitely
many linearizations with widely varying properties, but in practice the companion forms are typically used. However,
these companion forms are not always entirely satisfactory, and linearizations with special properties may sometimes
be required.
In this paper we develop a systematic approach to generating large classes of linearizations for matrix polynomials.
Given a polynomial P, we show how to simply construct two vector spaces of pencils that generalize the companion
forms of P, and prove that almost all of these pencils are linearizations for P. Eigenvectors of these pencils are
shown to be closely related to those of P. A distinguished subspace is then isolated, and the special properties of
these pencils are investigated. These spaces of pencils provide a convenient arena in which to look for structured
linearizations of structured polynomials, as well as to try to optimize the conditioning of linearizations, issues to be
addressed in further work.
Palindromic polynomial eigenvalue problems and related classes of structured eigenvalue problems are
considered. These structures generalize the concepts of symplectic and Hamiltonian matrices to matrix polynomials.
We discuss several applications where these matrix polynomials arise, and show how linearizations can be derived that
re
ect the structure of all these structured matrix polynomials and therefore preserve symmetries in the spectrum.
Numerical methods for palindromic eigenvalue problems: Computing the anti-triangular Schur form
(2007)
We present structure-preserving numerical methods
for complex palindromic polynomial eigenvalue problems
via corresponding palindromic linearizations.
A key ingredient is the development of an appropriate condensed form ---
the anti-triangular Schur form.
Ill-conditioned problems which have eigenvalues near the unit circle,
in particular near +/-1, are discussed.
We show how a combination of unstructured methods
followed by a structured refinement can be used
to solve such problems very accurately.
The asymptotic convergence behavior of cyclic versions of the nonsymmetric Jacobi algorithm for the
computation of the Schur form of a general complex matrix is investigated.
Similar to the symmetric case, the nonsymmetric Jacobi algorithm proceeds by applying a
sequence of rotations that annihilate a pivot element in the strict lower triangular
part of the matrix until convergence to the Schur form of the matrix is
achieved.
In this paper, it is shown that the cyclic nonsymmetric Jacobi method converges
locally and asymptotically quadratically under mild hypotheses if special ordering
schemes are chosen, namely ordering schemes that lead to so-called northeast directed sweeps.
The theory is illustrated by the help of numerical experiments. In particular, it is shown that
there are ordering schemes that lead to asymptotic quadratic convergence for the cyclic symmetric
Jacobi method, but only to asymptotic linear convergence for the cyclic nonsymmetric
Jacobi method. Finally, a generalization of the nonsymmetric Jacobi method
to the computation of the Hamiltonian Schur form for Hamiltonian matrices is introduced
and investigated.
The classical singular value decomposition for a matrix $A\in\Cmn$ is a
canonical form for $A$ that also displays the eigenvalues
of the Hermitian matrices $AA^\ast$ and $A^\ast A$. In this paper, we develop
a corresponding decomposition for $A$ that provides the Jordan canonical forms
for the complex symmetric matrices $AA^T$ and $A^TA$. More generally, we consider
the matrix triple $(A,G_1,G_2)$, where $G_1\in\CC{m}, G_2\in\CC{n}$
are invertible and either complex symmetric and complex skew-symmetric, and we
provide a canonical form under transformations of the form
$(A,G_1,G_2)\mapsto(X^T A Y, X^T G_1X, Y^T G_2Y)$, where $X,Y$ are nonsingular.
We study the perturbation theory of structured matrices under structured
rank one perturbations, with emphasis on matrices that are unitary, orthogonal, or symplectic
with respect to an indefinite inner product. The rank one perturbations are not necessarily of
arbitrary small size (in the sense of norm).
In the case of sesquilinear forms, results on selfadjoint matrices can be applied to
unitary matrices by using the Cayley transformation, but
in the case of real or complex symmetric or skew-symmetric bilinear forms
additional considerations are necessary. For complex symplectic matrices, it turns out that
generically (with respect to the perturbations) the behavior of the Jordan form of the
perturbed matrix follows the pattern established earlier for unstructured matrices and their unstructured perturbations, provided the specific properties of the Jordan
form of complex symplectic matrices are accounted for. For instance,
the number of Jordan blocks of fixed odd size corresponding to the eigenvalue $1$ or $-1$ have to be even.
For complex orthogonal matrices, it is shown that the behavior of
the Jordan structures corresponding to the original eigenvalues that are not moved by
perturbations follows again the pattern established earlier for unstructured matrices,
taking into account the specifics of Jordan forms of complex orthogonal
matrices.
The proofs are based on general results developed in the paper concerning Jordan forms of
structured matrices (which include in particular the classes of orthogonal and symplectic matrices)
under structured rank one perturbations. These results are presented and proved in the framework of
real as well as of complex matrices.
Structured eigenvalue backward errors of matrix pencils and polynomials with palindromic structures
(2014)
We derive formulas for the backward error of an approximate eigenvalue of a *-palindromic
matrix polynomial with respect to *-palindromic perturbations. Such formulas are also obtained
for complex T-palindromic pencils and quadratic
polynomials. When the T-palindromic polynomial is real, then we derive the backward error
of a real number considered as an approximate eigenvalue of the matrix polynomial with
respect to real T-palindromic perturbations.
In all cases the corresponding minimal structure preserving perturbations are obtained as well.
The results are illustrated by numerical experiments. These show that there is
significant difference between the backward errors with respect to structure
preserving and arbitrary perturbations in many cases.
An eigenvalue perturbation theory under rank-one perturbations is developed for classes
of real matrices that are symmetric with respect to a non-degenerate bilinear form,
or Hamiltonian with respect to a non-degenerate skew-symmetric form.
In contrast to the case of complex matrices, the sign characteristic is a crucial feature
of matrices in these classes. The behavior of the sign characteristic under generic
rank-one perturbations is analyzed in each of these two classes of matrices.
Partial results are presented, but some questions remain open. Applications
include boundedness and robust boundedness for solutions of structured systems
of linear differential equations with respect to general perturbations as well
as with respect to structured rank perturbations of the coefficients.
We derive a formula for the backward error of a complex number $\lambda$ when considered as an approximate eigenvalue
of a Hermitian matrix pencil or polynomial with respect to Hermitian perturbations. The same are also obtained for approximate
eigenvalues of matrix pencils and polynomials with related structures like skew-Hermitian, $*$-even and $*$-odd.
Numerical experiments suggest that in many cases there is a significant difference between the backward
errors with respect to perturbations that preserve structure and those with respect to arbitrary perturbations.
This paper deals with the effect of generic but structured low rank perturbations on the Jordan structure and sign
characteristic of matrices that have structure in an indefinite inner product space.
The paper is a follow-up of earlier papers in which the effect of rank one perturbations
was considered. Several results that are in contrast to the case of unstructured low rank
perturbations of general matrices are presented here.