The computation of Kronecker's canonical form of a singular pencil

We develop stable algorithms for the computation of the Kronecker structure of an arbitrary pencil. This problem can be viewed as a generalization of the well-known eigenvalue problem of pencils of the type λI?A. We first show that the elementary divisors (λ ? α)ⁱ of a regular pencil λB?A can be retrieved with a deflation algorithm acting on the expansion (λ ? α)B ? (A ? αB). This method is a straightforward generalization of Kublanovskaya's algorithm for the determination of the Jordan structure of a constant matrix. We also show how to use this method to determine the structure of the infinite elementary divisors of λB?A. In the case of singular pencils, the occurrence of Kronecker indices—containing the singularity of the pencil—somewhat complicates the problem. Yet our algorithm retrieves these indices with no additional effort, when determining the elementary divisors of the pencil. The present ideas can also be used to separate from an arbitrary pencil a smaller regular pencil containing only the finite elementary divisors of the original one. This is shown to be an effective tool when used together with the QZ algorithm.     

On the Computation of Particular Eigenvectors of Hamiltonian Matrix Pencils

We discuss a structure-preserving algorithm for the accurate solution of generalized eigenvalue problems for skew-Hamiltonian/Hamiltonian matrix pencils λN − ℋ. By embedding the matrix pencil λ𝒩 − ℋ into a skew-Hamiltonian/Hamiltonian matrix pencil of double size it is possible to avoid the problem of non-existence of a structured Schur form. For these embedded matrix pencils we can compute a particular condensed form to accurately compute the simple, finite, purely imaginary eigenvalues of λ𝒩 − ℋ. In this paper we describe a new method to compute also the corresponding eigenvectors by using the information contained in the condensed form of the embedded matrix pencils and associated transformation matrices. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Operator pencils on the algebra of densities

We continue to study equivariant pencil liftings and differential operators on the algebra of densities. We emphasize the role played by the geometry of the extended manifold where the algebra of densities is a special class of functions. Firstly we consider basic examples. We give a projective line of diff(M)-equivariant pencil liftings for first order operators and describe the canonical second order self-adjoint lifting. Secondly we study pencil liftings equivariant with respect to volume preserving transformations. This helps to understand the role of self-adjointness for the canonical pencils. Then we introduce the Duval-Lecomte-Ovsienko (DLO) pencil lifting which is derived from the full symbol calculus of projective quantisation. We use the DLO pencil lifting to describe all regular proj-equivariant pencil liftings. In particular, the comparison of these pencils with the canonical pencil for second order operators leads to objects related to the Schwarzian.     

Uniqueness of the “nonsingular core” for Hermitian and other matrix pencils

Every pencil of hermitian matrices is conjunctive with a pencil of the form L ⊕ M, where L (the "minimal-indices" part) has no elementary divisors and M (the "nonsingular core") is a nonsingular pencil. Here it is shown that the conjunctivity type ofM is determined by that of L ⊕ M. The same method of proof applies to many other types of pencils, e.g. to congruence of pencils based on (1) a pair of symmetric matrices, (2) a pair of alternating matrices, or (3) a symmetric and an alternating matrix.     

A deflation method for regular matrix pencils

A generalization of the concept of eigenvalue is introduced for a matrix pencil and it is called eigenpencil; an eigenpencil is a pencil itself and it contains part of the spectral information of the matrix pencil. A Wielandt type deflation procedure for regular matrix pencils is developed, using eigenpencils and supposing that they can have both finite and infinite eigenvalues. A numerical example illustrates the proposed method.     

Spectral properties of λ-matrices

One investigates the spectral problem for polynomial -matrices of the general form (regular and singular). One establishes a relation between the elements of the complete spectral structure of the -matrix (i.e., its elementary divisors, its Jordan chains of vectors, its minimal indices and polynomial solutions) and of the matrices which occur in its transformation to the Smith canonical form. One establishes a correspondence between the complete spectral structures of a -matrix and of three linear accompanying matrix pencils. One notes the possibility of reducing the solution of the spectral problem for a -matrix to the solution of a similar problem for its accompanying pencil. One gives a factorization of a -matrix which allows to represent it by any of its considered accompanying pencils or by its Kronecker canonical form.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 111, pp. 180–194, 1981.     

Matrix pencils: Theory,applications, and numerical methods

This paper surveys nearly all of the publications that have appeared in the last twenty years on the theory of and numerical methods for linear pencils. The survey is divided into the following sections: theory of canonical forms for symmetric and Hermitian pencils and the associated problem of simultaneous reduction of pairs of quadratic forms to canonical form; results on perturbation of characteristic values and deflating subspaces; numerical methods. The survey is self-contained in the sense that it includes the necessary information from the elementary theory of pencils and the theory of perturbations for the common algebraic problem Ax=x.Translated from Itogi Nauki i Tekhniki, Seriya Matematicheskii Analiz, Vol. 29, pp. 3–106, 1991.     

Spectral problem for polynomial matrix pencils. 2

For an arbitrary polynomial pencil of matrices A_i of dimensions m×n one presents an algorithm for the computation of the eigenvalues of the regular kernel of the pencil. The algorithm allows to construct a regular pencil having the same eigenvalues as the regular kernel of the initial pencil or (in the case of a dead end termination) allows to pass from the initial pencil to a pencil of smaller dimensions whose regular kernel has the same eigenvalues as the initial pencil. The problem is solved by reducing the obtained pencil to a linear one. For solving the problem in the case of a linear pencil one considers algorithms for pencils of full column rank as well as for completely singular pencils.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 111, pp. 109–116, 1981.     

Extracting partial canonical structure for large scale eigenvalue problems

We present methods for computing a nearby partial Jordan-Schur form of a given matrix and a nearby partial Weierstrass-Schur form of a matrix pencil. The focus is on the use and the interplay of the algorithmic building blocks – the implicitly restarted Arnoldi method with prescribed restarts for computing an invariant subspace associated with the dominant eigenvalue, the clustering method for grouping computed eigenvalues into numerically multiple eigenvalues and the staircase algorithm for computing the structure revealing form of the projected problem. For matrix pencils, we present generalizations of these methods. We introduce a new and more accurate clustering heuristic for both matrices and matrix pencils. Particular emphasis is placed on reliability of the partial Jordan-Schur and Weierstrass-Schur methods with respect to the choice of deflation parameters connecting the steps of the algorithm such that the errors are controlled. Finally, successful results from computational experiments conducted on problems with known canonical structure and varying ill-conditioning are presented. This revised version was published online in June 2006 with corrections to the Cover Date.     

矩阵的初等标准形与线性方程组

指出矩阵的初等标准形理论是线性方程组问题的理论基础     

ON THE GENERALIZED RESOLVENT OF LINEAR PENCILS IN BANACH SPACES

Utilizing the stability characterizations of generalized inverses of linear operator, we investigate the existence of generalized resolvent of linear pencils in Banach spaces. Some practical criterions for the existence of generalized resolvents of the linear pencil λ→ T λ S are provided and an explicit expression of the generalized resolvent is also given. As applications, the characterization for the Moore-Penrose inverse of the linear pencil to be its generalized resolvent and the existence of the generalized resolvents of linear pencils of finite rank operators, Fredholm operators and semi-Fredholm operators are also considered. The results obtained in this paper extend and improve many results in this area.     

Orthogonal Projections and the Perturbation of the Eigenvalues of Singular Pencils

In this paper we obtain a Hoffman-Wielandt type theorem and a Bauer-Fike type theorem for singular pencils of matrics. These results delineate the relations between the perturbation of the eigenvalues of a singular diagonalizable pencil $A-λB$ and the variation of the orthogonal projection onto the column space $\mathcal{R} \Bigg( \begin{matrix} A^H \\ B^H \end{matrix} \Bigg)$.     

Perturbation of eigenvalues of matrix pencils and the optimal assignment problem

We extend the perturbation theory of Vi?ik, Ljusternik and Lidski?? to the case of eigenvalues of matrix pencils. This extension allows us to solve certain degenerate cases of this theory. We show that the first order asymptotics of the eigenvalues of a perturbed matrix pencil can be computed generically by methods of min-plus algebra and optimal assignment algorithms. We illustrate this result by discussing a singular perturbation problem considered by Najman. To cite this article: M. Akian et al., C. R. Acad. Sci. Paris, Ser. I 339 (2004).     

Condition numbers and backward perturbation bound for linear matrix equations

This paper deals with the normwise perturbation theory for linear (Hermitian) matrix equations. The definition of condition number for the linear (Hermitian) matrix equations is presented. The lower and upper bounds for the condition number are derived. The estimation for the optimal backward perturbation bound for the Hermitian matrix equations is obtained. Copyright © 2010 John Wiley & Sons, Ltd.     

An iterative method for solving the stable subspace of a matrix pencil and its application

This work is to propose an iterative method of choice to compute a stable subspace of a regular matrix pencil. This approach is to define a sequence of matrix pencils via particular left null spaces. We show that this iteration preserves a semigroup property depending only on the initial matrix pencil. Via this recursion relationship, we propose an accelerated iterative method to compute the stable subspace and use it to provide a theoretical result to solve the principal square root of a given matrix, both nonsingular and singular. We show that this method can not only find out the matrix square root, but also construct an iterative approach which converges to the square root with any desired order.     

Eigenvalue problem for a regular linear pencil of matrices close to singular ones

The solution is examined of the eigenvalue problem (1) for a regular linear pencil of matrices A and B of which at least one is close to being singular. Two groups of algorithms are proposed for solving (1). Both groups of algorithms work in the situation when the eigenvalues of the original pencil can be separated into groups of eigenvalues large and small in absolute value. The algorithms reveal this situation. The algorithms of the first group permit the passage from the original pencil to a pencil strictly equivalent to it, which in form is close to a quasitriangular pencil (or coincides with a quasitriangular one in case at least one of the pencil's matrices is singular). The eigenvalues of the diagonal blocks of the pencil constructed yield approximations to the eigenvalues of problem (1). If the approximations obtained are refined by the Newton method, using the normalized decomposition of auxiliary constructed matrices, then both the eigenvalues of (1) as well as all the linearly independent eigenvectors corresponding to them can be found. The algorithms of the second group permit the passage from the original pencil to a strictly equivalent pencil representable as a sum of two singular pencils whose null spaces are mutually perpendicular; next, with the aid of an iteration process based on the use of perturbation theory, these algorithms permit the finding of the eigenvalues of pencil (1), small (large) in absolute value, and the eigenvectors corresponding to them. Ill-conditioned regular pencils close to singular ones also are examined. For them an algorithm is suggested which permits the ill conditioning to be revealed and permits approximations to the stable (to perturbations in the original data) eigenvalues of the pencil to be obtained.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 90, pp. 63–82, 1979.     

Bounds for the Distance Between Nearby Jordan and Kronecker Structures in a Closure Hierarchy

Computing the fine-canonical-structure elements of matrices and matrix pencils are ill-posed problems. Therefore, besides knowing the canonical structure of a matrix or a matrix pencil, it is equally important to know what are the nearby canonical structures that explain the behavior under small perturbations. Qualitative strata information is provided by our StratiGraph tool. Here, we present lower and upper bounds for the distance between Jordan and Kronecker structures in a closure hierarchy of an orbit or bundle stratification. This quantitative information is of importance in applications, e.g., distance to more degenerate systems (uncontrollability). Our upper bounds are based on staircase regularizing perturbations. The lower bounds are of EckartYoung type and are derived from a matrix representation of the tangent space of the orbit of a matrix or a matrix pencil. Computational results illustrate the use of the bounds. Bibliography: 42 titles.     

Lur’e equations and even matrix pencils

In this work, we consider the so-called Lur’e matrix equations that arise e.g. in model reduction and linear-quadratic infinite time horizon optimal control. We characterize the set of solutions in terms of deflating subspaces of even matrix pencils. In particular, it is shown that there exist solutions which are extremal in terms of definiteness. It is shown how these special solutions can be constructed via deflating subspaces of even matrix pencils.