Search

A well known method to solve the Polynomial Eigenvalue Problem (PEP) is via linearization. That is, transforming the PEP into a generalized linear eigenvalue problem with the same spectral information and solving such linear problem with some of the eigenvalue algorithms available in the literature. Linearizations of matrix polynomials are usually defined using unimodular transformations. In this paper we establish a connection between the standard definition of linearization for matrix polynomials introduced by Gohberg, Lancaster and Rodman and the notion of polynomial system matrix introduced by Rosenbrock. This connection gives new techniques to show that a matrix pencil is a linearization of the corresponding matrix polynomial arising in a PEP.

A complete theory of the relationship between the minimal bases and indices of rational matrices and those of their strong linearizations is presented. Such theory is based on establishing first the relationships between the minimal bases and indices of rational matrices and those of their polynomial system matrices under the classical minimality condition and certain additional conditions of properness. This is related to pioneer results obtained by Verghese, Van Dooren and Kailath in 1979-80, which were the first proving results of this type under different nonequivalent conditions. It is shown that the definitions of linearizations and strong linearizations do not guarantee any relationship between the minimal bases and indices of the linearizations and the rational matrices in general. In contrast, simple relationships are obtained for the family of strong block minimal bases linearizations, which can be used to compute minimal bases and indices of any rational matrix, including rectangular ones, via algorithms for pencils. These results extend the corresponding ones for other families of linearizations available in recent literature for square rational matrices.

This paper presents a definition for local linearizations of rational matrices and studies their properties. This definition allows us to introduce matrix pencils associated to a rational matrix that preserve its structure of zeros and poles in subsets of any algebraically closed field and also at infinity. Moreover, such definition includes, as particular cases, other definitions that have been used previously in the literature. In this way, this new theory of local linearizations captures and explains rigorously the properties of all the different pencils that have been used from the 1970's until 2019 for computing zeros, poles and eigenvalues of rational matrices. Particular attention is paid to those pencils that have appeared recently in the numerical solution of nonlinear eigenvalue problems through rational approximation., 49 pages

This paper studies generic and perturbation properties inside the linear space of $m\times (m+n)$ polynomial matrices whose rows have degrees bounded by a given list $d_1, \ldots, d_m$ of natural numbers, which in the particular case $d_1 = \cdots = d_m = d$ is just the set of $m\times (m+n)$ polynomial matrices with degree at most $d$. Thus, the results in this paper extend to a much more general setting the results recently obtained in [Van Dooren & Dopico, Linear Algebra Appl. (2017), http://dx.doi.org/10.1016/j.laa.2017.05.011] only for polynomial matrices with degree at most $d$. Surprisingly, most of the properties proved in [Van Dooren & Dopico, Linear Algebra Appl. (2017)], as well as their proofs, remain to a large extent unchanged in this general setting of row degrees bounded by a list that can be arbitrarily inhomogeneous provided the well-known Sylvester matrices of polynomial matrices are replaced by the new trimmed Sylvester matrices introduced in this paper. The following results are presented, among many others, in this work: (1) generically the polynomial matrices in the considered set are minimal bases with their row degrees exactly equal to $d_1, \ldots , d_m$, and with right minimal indices differing at most by one and having a sum equal to $\sum_{i=1}^{m} d_i$, and (2), under perturbations, these generic minimal bases are robust and their dual minimal bases can be chosen to vary smoothly., arXiv admin note: text overlap with arXiv:1612.03793

Let $\cL = (\cL_1,\cL_2)$ be a list consisting of a sublist $\cL_1$ of powers of irreducible (monic) scalar polynomials over an algebraically closed field $\FF$, and a sublist $\cL_2$ of nonnegative integers. For an arbitrary such list $\cL$, we give easily verifiable necessary and sufficient conditions for $\cL$ to be the list of elementary divisors and minimal indices of some $T$-palindromic quadratic matrix polynomial with entries in the field $\FF$. For $\cL$ satisfying these conditions, we show how to explicitly construct a $T$-palindromic quadratic matrix polynomial having $\cL$ as its structural data; that is, we provide a $T$-palindromic quadratic realization of $\cL$. Our construction of $T$-palindromic realizations is accomplished by taking a direct sum of low bandwidth $T$-palindromic blocks, closely resembling the Kronecker canonical form of matrix pencils. An immediate consequence of our in-depth study of the structure of $T$-palindromic quadratic polynomials is that all even grade $T$-palindromic matrix polynomials have a $T$-palindromic strong quadratification. Finally, using a particular M\"{o}bius transformation, we show how all of our results can be easily extended to quadratic matrix polynomials with $T$-even structure.

The structural data of any rational matrix R(\lambda ), i.e., the structural indices of its poles and zeros together with the minimal indices of its left and right nonespaces, is known to satisfy a simple condition involving certain sums of these indices. This fundamental constraint was first proved by Van Dooren in 1978; here we refer to this result as the rational index sum theorem. An analogous result for polynomial matrices has been independently discovered (and rediscovered) several times in the past three decades. In this paper we clarify the connection between these two seemingly different index sum theorems, describe a little bit of the history of their development, and discuss their curious apparent unawareness of each other. Finally, we use the connection between these results to solve a fundamental inverse problem for rational matrices---for which lists \scrL of prescribed structural data does there exist some rational matrix R(\lambda ) that realizes exactly the list \scrL ? We show that Van Dooren's condition is the only constraint on rational realizability; that is, a list \scrL is the structural data of some rational matrix R(\lambda ) if and only if \scrL satisfies the rational index sum condition.

We show that the set of $n \times n$ complex symmetric matrix pencils of rank at most $r$ is the union of the closures of $\lfloor r/2\rfloor +1$ sets of matrix pencils with some, explicitly described, complete eigenstructures. As a consequence, these are the generic complete eigenstructures of $n \times n$ complex symmetric matrix pencils of rank at most $r$. We also show that these closures correspond to the irreducible components of the set of $n\times n$ symmetric matrix pencils with rank at most $r$ when considered as an algebraic set., 15 pages

We develop a complete and rigorous theory of root polynomials of arbitrary matrix polynomials, i.e., either regular or singular, and study how these vector polynomials are related to the spectral properties of matrix polynomials. We pay particular attention to the so-called maximal sets of root polynomials and prove that they carry complete information about the eigenvalues (finite or infinite) of matrix polynomials and that they are related to the matrices that transform any matrix polynomial into its Smith form. In addition, we describe clearly, for the first time in the literature, the extremality properties of such maximal sets and identify some of them whose vectors have minimal grade. Once the main theoretical properties of root polynomials have been established, the interaction of root polynomials with three problems that have attracted considerable attention in the literature is analyzed. More precisely, we study the change of root polynomials under rational transformations, or reparametrizations, of matrix polynomials, the recovery of the root polynomials of a matrix polynomial from those of its most important linearizations, and the relationship between the root polynomials of two dual pencils. We emphasize that for the case of regular matrix polynomials all the results in this paper can be translated into the language of Jordan chains, as a consequence of the well known relationship between root polynomials and Jordan chains. Therefore, a number of open problems are also solved for Jordan chains of regular matrix polynomials. We also briefly discuss how root polynomials can be used to define eigenvectors and eigenspaces for singular matrix polynomials. Supported by “Ministerio de Economía, Industria y Competitividad of Spain” and “Fondo Europeo de Desarrollo Regional (FEDER) of EU” through grants MTM2015-65798-P and MTM2017-90682-REDT

The standard way of solving the polynomial eigenvalue problem associated with a matrix polynomial is to embed the matrix coefficients of the polynomial into a matrix pencil, transforming the problem into an equivalent generalized eigenvalue problem. Such pencils are known as linearizations. Many of the families of linearizations for matrix polynomials available in the literature are extensions of the so-called family of Fiedler pencils. These families are known as generalized Fiedler pencils, Fiedler pencils with repetition, and generalized Fiedler pencils with repetition—or Fiedler-like pencils for simplicity. The goal of this work is to unify the Fiedler-like pencils approach with the more recent one based on strong block minimal bases pencils introduced in F.M. Dopico et al. (2017) [17] . To this end, we introduce a family of pencils that we have named extended block Kronecker pencils, whose members are, under some generic nonsingularity conditions, strong block minimal bases pencils, and show that, with the exception of the non-proper generalized Fiedler pencils, all Fiedler-like pencils belong to this family modulo permutations. As a consequence of this result, we obtain a much simpler theory for Fiedler-like pencils than the one available so far. Moreover, we expect this simplification to allow for further developments in the theory of Fiedler-like pencils such as global or local backward error analyses and eigenvalue conditioning analyses of polynomial eigenvalue problems solved via Fiedler-like linearizations.

We introduce a new family of strong linearizations of matrix polynomials---which we call "block Kronecker pencils"---and perform a backward stability analysis of complete polynomial eigenproblems. These problems are solved by applying any backward stable algorithm to a block Kronecker pencil, such as the staircase algorithm for singular pencils or the QZ algorithm for regular pencils. This stability analysis allows us to identify those block Kronecker pencils that yield a computed complete eigenstructure which is exactly that of a slightly perturbed matrix polynomial. The global backward error analysis in this work presents for the first time the following key properties: it is a rigurous analysis valid for finite perturbations (i.e., it is not a first order analysis), it provides precise bounds, it is valid simultaneously for a large class of linearizations, and it establishes a framework that may be generalized to other classes of linearizations. These features are related to the fact that block Kronecker pencils are a particular case of the new family of "strong block minimal bases pencils", which are robust under certain perturbations and, so, include certain perturbations of block Kronecker pencils. We hope that this robustness property will allow us to extend the results in this paper to other contexts., this article supersedes MIMS Eprint 2016.34

Polynomial minimal bases of rational vector subspaces are a classical concept that plays an important role in control theory, linear systems theory, and coding theory. It is a common practice to arrange the vectors of any minimal basis as the rows of a polynomial matrix and to call such matrix simply a minimal basis. Very recently, minimal bases, as well as the closely related pairs of dual minimal bases, have been applied to a number of problems that include the solution of general inverse eigenstructure problems for polynomial matrices, the development of new classes of linearizations and l-ifications of polynomial matrices, and backward error analyses of complete polynomial eigenstructure problems solved via a wide class of strong linearizations. These new applications have revealed that although the algebraic properties of minimal bases are rather well understood, their robustness and the behavior of the corresponding dual minimal bases under perturbations have not yet been explored in the literature, as far as we know. Therefore, the main purpose of this paper is to study in detail when a minimal basis M ( λ ) is robust under perturbations, i.e., when all the polynomial matrices in a neighborhood of M ( λ ) are minimal bases, and, in this case, how perturbations of M ( λ ) change its dual minimal bases. In order to study such problems, a new characterization of whether or not a polynomial matrix is a minimal basis in terms of a finite number of rank conditions is introduced and, based on it, we prove that polynomial matrices are generically minimal bases with very specific properties. In addition, some applications of the results of this paper are discussed.

We show that the set of $m \times m$ complex skew-symmetric matrix polynomials of odd grade $d$, i.e., of degree at most $d$, and (normal) rank at most $2r$ is the closure of the single set of matrix polynomials with the certain, explicitly described, complete eigenstructure. This complete eigenstructure corresponds to the most generic $m \times m$ complex skew-symmetric matrix polynomials of odd grade $d$ and rank at most $2r$. In particular, this result includes the case of skew-symmetric matrix pencils ($d=1$)., 21 pages

We determine the generic complete eigenstructures for $n \times n$ complex symmetric matrix polynomials of odd grade $d$ and rank at most $r$. More precisely, we show that the set of $n \times n$ complex symmetric matrix polynomials of odd grade $d$, i.e., of degree at most $d$, and rank at most $r$ is the union of the closures of the $\lfloor rd/2\rfloor+1$ sets of symmetric matrix polynomials having certain, explicitly described, complete eigenstructures. Then, we prove that these sets are open in the set of $n \times n$ complex symmetric matrix polynomials of odd grade $d$ and rank at most $r$. In order to prove the previous results, we need to derive necessary and sufficient conditions for the existence of symmetric matrix polynomials with prescribed grade, rank, and complete eigenstructure, in the case where all their elementary divisors are different from each other and of degree $1$. An important remark on the results of this paper is that the generic eigenstructures identified in this work are completely different from the ones identified in previous works for unstructured and skew-symmetric matrix polynomials with bounded rank and fixed grade larger than one, because the symmetric ones include eigenvalues while the others not. This difference requires to use new techniques.

M��bius transformations have been used in numerical algorithms for computing eigenvalues and invariant subspaces of structured generalized and polynomial eigenvalue problems (PEPs). These transformations convert problems with certain structures arising in applications into problems with other structures and whose eigenvalues and invariant subspaces are easily related to the ones of the original problem. Thus, an algorithm that is efficient and stable for some particular structure can be used for solving efficiently another type of structured problem via an adequate M��bius transformation. A key question in this context is whether these transformations may change significantly the conditioning of the problem and the backward errors of the computed solutions, since, in that case, their use may lead to unreliable results. We present the first general study on the effect of M��bius transformations on the eigenvalue condition numbers and backward errors of approximate eigenpairs of PEPs. By using the homogeneous formulation of PEPs, we are able to obtain two clear and simple results. First, we show that, if the matrix inducing the M��bius transformation is well conditioned, then such transformation approximately preserves the eigenvalue condition numbers and backward errors when they are defined with respect to perturbations of the matrix polynomial which are small relative to the norm of the polynomial. However, if the perturbations in each coefficient of the matrix polynomial are small relative to the norm of that coefficient, then the corresponding eigenvalue condition numbers and backward errors are preserved approximately by the M��bius transformations induced by well-conditioned matrices only if a penalty factor, depending on those coefficients, is moderate. It is important to note that these simple results are no longer true if a non-homogeneous formulation is used., 33 pages, 3 figures

In this work, we propose a new method, termed as R-CORK, for the numerical solution of large-scale rational eigenvalue problems, which is based on a linearization and on a compact decomposition of the rational Krylov subspaces corresponding to this linearization. R-CORK is an extension of the compact rational Krylov method (CORK) introduced very recently by Van Beeumen et al. to solve a family of non-linear eigenvalue problems that can be expressed and linearized in certain particular ways and which include arbitrary polynomial eigenvalue problems, but not arbitrary rational eigenvalue problems. The R-CORK method exploits the structure of the linearized problem by representing the Krylov vectors in a compact form in order to reduce the cost of storage, resulting in a method with two levels of orthogonalization. The first level of orthogonalization works with vectors of the same size that the original problem, and the second level works with vectors of size much smaller than the original problem. Since vectors of the size of the linearization are never stored or orthogonalized, R-CORK is more efficient from the point of views of memory and orthogonalization than the classical rational Krylov method applied directly to the linearization. Taking into account that the R-CORK method is based on a classical rational Krylov method, to implement implicit restarting is also possible and we show how to do it in a memory efficient way. Finally, some numerical examples are included in order to show that the R-CORK method performs satisfactorily in practice.

The standard way of solving a polynomial eigenvalue problem associated with a matrix polynomial starts by embedding the matrix coefficients of the polynomial into a matrix pencil, known as a strong linearization. This process transforms the problem into an equivalent generalized eigenvalue problem. However, there are some situations in which is more convenient to replace linearizations by other low degree matrix polynomials. This has motivated the idea of a strong l-ification of a matrix polynomial, which is a matrix polynomial of degree at most l having the same finite and infinite elementary divisors, and the same numbers of left and right minimal indices as the original matrix polynomial. We present in this work a novel method for constructing strong l-ifications of matrix polynomials of size m × n and grade d when l d , and l divides nd or md. This method is based on a family called “strong block minimal bases matrix polynomials”, and relies heavily on properties of dual minimal bases. We show how strong block minimal bases l-ifications can be constructed from the coefficients of a given matrix polynomial P ( λ ) . We also show that these l-ifications satisfy many desirable properties for numerical applications: they are strong l-ifications regardless of whether P ( λ ) is regular or singular, the minimal indices of the l-ifications are related to those of P ( λ ) via constant uniform shifts, and eigenvectors and minimal bases of P ( λ ) can be recovered from those of any of the strong block minimal bases l-ifications. In the special case where l divides d, we introduce a subfamily of strong block minimal bases matrix polynomials named “block Kronecker matrix polynomials”, which is shown to be a fruitful source of companion l-ifications.

Over any field F every square matrix A can be factored into the product of two symmetric matrices as A = S1 . S2 with S_i = S_i^T ∈ F^(n,n) and either factor can be chosen nonsingular, as was discovered by Frobenius in 1910. Frobenius’ symmetric matrix factorization has been lying almost dormant for a century. The first successful method for computing matrix symmetrizers, i.e., symmetric matrices S such that SA is symmetric, was inspired by an iterative linear systems algorithm of Huang and Nong (2010) in 2013 [29, 30]. The resulting iterative algorithm has solved this computational problem over R and C, but at high computational cost. This paper develops and tests another linear equations solver, as well as eigen- and principal vector or Schur Normal Form based algorithms for solving the matrix symmetrizer problem numerically. Four new eigendata based algorithms use, respectively, SVD based principal vector chain constructions, Gram-Schmidt orthogonalization techniques, the Arnoldi method, or the Schur Normal Form of A in their formulations. They are helped by Datta’s 1973 method that symmetrizes unreduced Hessenberg matrices directly. The eigendata based methods work well and quickly for generic matrices A and create well conditioned matrix symmetrizers through eigenvector dyad accumulation. But all of the eigen based methods have differing deficiencies with matrices A that have ill-conditioned or complicated eigen structures with nontrivial Jordan normal forms. Our symmetrizer studies for matrices with ill-conditioned eigensystems lead to two open problems of matrix optimization. This research was partially supported by the Ministerio de Economía y Competitividad of Spain through the research grant MTM2012-32542. Publicado

The standard way of solving numerically a polynomial eigenvalue problem (PEP) is to use a linearization and solve the corresponding generalized eigenvalue problem (GEP). In addition, if the PEP possesses one of the structures arising very often in applications, then the use of a linearization that preserves such structure combined with a structured algorithm for the GEP presents considerable numerical advantages. Block-symmetric linearizations have proven to be very useful for constructing structured linearizations of structured matrix polynomials. In this scenario, we analyze the eigenvalue condition numbers and backward errors of approximated eigenpairs of a block symmetric linearization that was introduced by Fiedler (Linear Algebra Appl 372:325–331, 2003) for scalar polynomials and generalized to matrix polynomials by Antoniou and Vologiannidis (Electron J Linear Algebra 11:78–87, 2004). This analysis reveals that such linearization has much better numerical properties than any other block-symmetric linearization analyzed so far in the literature, including those in the well known vector space $$\mathbb {DL}(P)$$ of block-symmetric linearizations. The main drawback of the analyzed linearization is that it can be constructed only for matrix polynomials of odd degree, but we believe that it will be possible to extend its use to even degree polynomials via some strategies in the near future.

In this paper, we consider the different eigenvalue condition numbers for matrix polynomials used in the literature and we compare them. One of these condition numbers is a generalization of the Wilkinson condition number for the standard eigenvalue problem. This number has the disadvantage of only being defined for finite eigenvalues. In order to give a unified approach to all the eigenvalues of a matrix polynomial, both finite and infinite, two (homogeneous) condition numbers have been defined in the literature. In their definition, very different approaches are used. One of the main goals of this note is to show that, when the matrix polynomial has a moderate degree, both homogeneous numbers are essentially the same and one of them provides a geometric interpretation of the other. We also show how the homogeneous condition numbers compare with the "Wilkinson-like" eigenvalue condition number and how they extend this condition number to zero and infinite eigenvalues., 19 pages, 1 figure

We construct a new family of strong linearizations of rational matrices considering the polynomial part of them expressed in a basis that satisfies a three term recurrence relation. For this purpose, we combine the theory developed by Amparan et al., MIMS EPrint 2016.51, and the new linearizations of polynomial matrices introduced by Fa{\ss}bender and Saltenberger, Linear Algebra Appl., 525 (2017). In addition, we present a detailed study of how to recover eigenvectors of a rational matrix from those of its linearizations in this family. We complete the paper by discussing how to extend the results when the polynomial part is expressed in other bases, and by presenting strong linearizations that preserve the structure of symmetric or Hermitian rational matrices. A conclusion of this work is that the combination of the results in this paper with those in Amparan et al., MIMS EPrint 2016.51, allows us to use essentially all the strong linearizations of polynomial matrices developed in the last fifteen years to construct strong linearizations of any rational matrix by expressing such matrix in terms of its polynomial and strictly proper parts., Comment: 40 pages, no figures

This paper defines for the first time strong linearizations of arbitrary rational matrices, studies in depth properties and diferent characterizations of such linear matrix pencils, and develops infinitely many examples of strong linearizations that can be explicitly and easily constructed from a minimal state-space realization of the strictly proper part of the considered rational matrix and the coefficients of the polynomial part. As a consequence, the results in this paper establish a rigorous foundation for the numerical computation of the complete structure of zeros and poles, both finite and at infinity, of any rational matrix by applying any well known backward stable algorithm for generalized eigenvalue problems to any of the strong linearizations explicitly constructed in this work. Since the results of this paper require to use several concepts that are not standard in matrix computations, a considerable effort has been done to make the paper as self-contained as possible.

The set POL d , r m × n of m × n complex matrix polynomials of grade d and (normal) rank at most r in a complex ( d + 1 ) m n dimensional space is studied. For r = 1 , … , min ⁡ { m , n } − 1 , we show that POL d , r m × n is the union of the closures of the r d + 1 sets of matrix polynomials with rank r, degree exactly d, and explicitly described complete eigenstructures. In addition, for the full-rank rectangular polynomials, i.e. r = min ⁡ { m , n } and m ≠ n , we show that POL d , r m × n coincides with the closure of a single set of the polynomials with rank r, degree exactly d, and the described complete eigenstructure. These complete eigenstructures correspond to generic m × n matrix polynomials of grade d and rank at most r.

Given a matrix polynomial P ( λ ) = ∑ i = 0 k λ i A i of degree k , where A i are n × n matrices with entries in a field F , the development of linearizations of P ( λ ) that preserve whatever structure P ( λ ) might posses has been a very active area of research in the last decade. Most of the structure-preserving linearizations of P ( λ ) discovered so far are based on certain modifications of block-symmetric linearizations. The block-symmetric linearizations of P ( λ ) available in the literature fall essentially into two classes: linearizations based on the so-called Fiedler pencils with repetition, which form a finite family, and a vector space of dimension k of block-symmetric pencils, called DL ( P ) , such that most of its pencils are linearizations. One drawback of the pencils in DL ( P ) is that none of them is a linearization when P ( λ ) is singular. In this paper we introduce new vector spaces of block-symmetric pencils, most of which are strong linearizations of P ( λ ) . The dimensions of these spaces are O ( n 2 ) , which, for n ≥ k , are much larger than the dimension of DL ( P ) . When k is odd, many of these vector spaces contain linearizations also when P ( λ ) is singular. The coefficients of the block-symmetric pencils in these new spaces can be easily constructed as k × k block-matrices whose n × n blocks are of the form 0, ± α I n , ± α A i , or arbitrary n × n matrices, where α is an arbitrary nonzero scalar.

The set of m x n singular matrix pencils with normal rank at most r is an algebraic set with r + 1 irreducible components. These components are the closure of the orbits (under strict equivalence) of r 1 matrix pencils which are in Kronecker canonical form. In this paper, we provide a new explicit description of each of these irreducible components which is a parametrization of each component. Therefore one can explicitly construct any pencil in each of these components. The new description of each of these irreducible components consists of the sum of r rank-1 matrix pencils, namely, a column polynomial vector of degree at most 1 times a row polynomial vector of degree at most 1, where we impose one of these two vectors to have degree zero. The number of row vectors with zero degree determines each irreducible component. (C) 2017 Elsevier Inc. All rights reserved.

The aim of the present paper is to analyze the behavior of Fiedler companion matrices in the polynomial root-finding problem from the point of view of conditioning of eigenvalues. More precisely, we compare: (a) the condition number of a given root of a monic polynomial p(z) with the condition number of as an eigenvalue of any Fiedler matrix of p(z), (b) the condition number of as an eigenvalue of an arbitrary Fiedler matrix with the condition number of as an eigenvalue of the classical Frobenius companion matrices, and (c) the pseudozero sets of p(z) and the pseudospectra of any Fiedler matrix of p(z). We prove that, if the coefficients of the polynomial p(z) are not too large and not all close to zero, then the conditioning of any root of p(z) is similar to the conditioning of as an eigenvalue of any Fiedler matrix of p(z). On the contrary, when p(z) has some large coefficients, or they are all close to zero, the conditioning of as an eigenvalue of any Fiedler matrix can be arbitrarily much larger than its conditioning as a root of p(z) and, moreover, when p(z) has some large coefficients there can be two different Fiedler matrices such that the ratio between the condition numbers of as an eigenvalue of these two matrices can be arbitrarily large. Finally, we relate asymptotically the pseudozero sets of p(z) with the pseudospectra of any given Fiedler matrix of p(z), and the pseudospectra of any two Fiedler matrices of p(z). This work was partially supported by the Ministerio de Economía y Competitividad of Spain through Grants MTM-2012-32542, MTM2015-68805-REDT and MTM2015-65798-P, and by the Engineering and Physical Sciences Research Council Grant EP/I005293 (Javier Pérez).

The development of strong linearizations preserving whatever structure a matrix polynomial might possess has been a very active area of research in the last years, since such linearizations are the starting point of numerical algorithms for computing eigenvalues of structured matrix polynomials with the properties imposed by the considered structure. In this context, Hermitian matrix polynomials are one of the most important classes of matrix polynomials arising in applications and their real eigenvalues are of great interest. The sign characteristic is a set of signs attached to these real eigenvalues which is crucial for determining the behavior of systems described by Hermitian matrix polynomials and, therefore, it is desirable to develop linearizations that preserve the sign characteristic of these polynomials, but, at present, only one such linearization is known. In this paper, we present a complete characterization of all the Hermitian strong linearizations that preserve the sign characteristic of a given Hermitian matrix polynomial and identify several families of such linearizations that can be constructed very easily from the coefficients of the polynomial.

In this paper, strong relative perturbation bounds are developed for a number of linear algebra problems involving diagonally dominant matrices. The key point is to parameterize diagonally dominant matrices using their off-diagonal entries and diagonally dominant parts and to consider small relative componentwise perturbations of these parameters. This allows us to obtain new relative perturbation bounds for the inverse, the solution to linear systems, the symmetric indefinite eigenvalue problem, the singular value problem, and the nonsymmetric eigenvalue problem. These bounds are much stronger than traditional perturbation results, since they are independent of either the standard condition number or the magnitude of eigenvalues/singular values. Together with previously derived perturbation bounds for the LDU factorization and the symmetric positive definite eigenvalue problem, this paper presents a complete and detailed account of relative structured perturbation theory for diagonally dominant matrices. This research was partially supported by the Ministerio de Economía y Competitividad of Spain under grant MTM2012-32542. Publicado

Low-rank structured matrices have attracted much attention in the last decades, since they arise in many applications and all share the fundamental property that can be represented by O(n)$\mathcal {O}(n)$ parameters, where n×n is the size of the matrix. This property has allowed the development of fast algorithms for solving numerically many problems involving low-rank structured matrices by performing operations on the parameters describing the matrices, instead of directly on the matrix entries. Among these problems, the solution of linear systems of equations is probably the most basic and relevant one. Therefore, it is important to measure, via structured computable condition numbers, the relative sensitivity of the solutions of linear systems with low-rank structured coefficient matrices with respect to relative perturbations of the parameters representing such matrices, since this sensitivity determines the maximum accuracy attainable by fast algorithms and allows us to decide which set of parameters is the most convenient from the point of view of accuracy. To develop and analyze such condition numbers is the main goal of this paper. To this purpose, a general expression is obtained for the condition number of the solution of a linear system of equations whose coefficient matrix is any differentiable function of a vector of parameters with respect to perturbations of such parameters. Since there are many different classes of low-rank structured matrices and many different types of parameters describing them, it is not possible to cover all of them in a single work. Therefore, the general expression of the condition number is particularized to the important case of {1,1}-quasiseparable matrices and to the quasiseparable and the Givens-vector representations, in order to obtain explicit expressions of the corresponding two condition numbers that can be estimated in O(n) operations. In addition, detailed theoretical and numerical comparisons of these two condition numbers between themselves, and with respect to unstructured condition numbers, are provided, which show that there are situations in which the unstructured condition number is much larger than the structured ones, but that the opposite never happens. The approach presented in this manuscript can be generalized to other classes of low-rank structured matrices and parameterizations.

The Fiedler matrices of a monic polynomial p(z) of degree n are n × n matrices with characteristic polynomial equal to p(z) and whose nonzero entries are either 1 or minus the coefficients of p(z). Fiedler matrices include as particular cases the classical Frobenius companion forms of p(z). Frobenius companion matrices appear frequently in the literature on control and signal processing, but it is well known that they posses many properties that are undesirable numerically, which limit their use in applications. In particular, as n increases, Frobenius companion matrices are often nearly singular, i.e., their condition numbers for inversion are very large. Therefore, it is natural to investigate whether other Fiedler matrices are better conditioned than the Frobenius companion matrices or not. In this paper, we present explicit expressions for the condition numbers for inversion of all Fiedler matrices with respect the Frobenius norm, i.e., ‖ A ‖ F = ∑ ij | a ij | 2 . This allows us to get a very simple criterion for ordering all Fiedler matrices according to increasing condition numbers and to provide lower and upper bounds on the ratio of the condition numbers of any pair of Fiedler matrices. These results establish that if | p ( 0 ) | ⩽ 1 , then the Frobenius companion matrices have the largest condition number among all Fiedler matrices of p(z), and that if | p ( 0 ) | > 1 , then the Frobenius companion matrices have the smallest condition number. We also provide families of polynomials where the ratio of the condition numbers of pairs of Fiedler matrices can be arbitrarily large and prove that this can only happen when both Fiedler matrices are very ill-conditioned. We finally study some properties of the singular values of Fiedler matrices and determine how many of the singular values of a Fiedler matrix are equal to one.

We describe how to find the general solution of the matrix equation AX + X ★ B = 0 , where A ∈ C m × n and B ∈ C n × m are arbitrary matrices, X ∈ C n × m is the unknown, and X ★ denotes either the transpose or the conjugate transpose of X . We first show that the solution can be obtained in terms of the Kronecker canonical form of the matrix pencil A + λ B ★ and the two nonsingular matrices which transform this pencil into its Kronecker canonical form. We also give a complete description of the solution provided that these two matrices and the Kronecker canonical form of A + λ B ★ are known. As a consequence, we determine the dimension of the solution space of the equation in terms of the sizes of the blocks appearing in the Kronecker canonical form of A + λ B ★ . The general solution of the homogeneous equation AX + X ★ B = 0 is essential to finding the general solution of AX + X ★ B = C , which is related to palindromic eigenvalue problems that have attracted considerable attention recently.

Least squares problems min(x) parallel to b - Ax parallel to(2) where the matrix A is an element of C-mXn (m >= n) has some particular structure arise frequently in applications. Polynomial data fitting is a well-known instance of problems that yield highly structured matrices, but many other examples exist. Very often, structured matrices have huge condition numbers kappa(2)(A) = parallel to A parallel to(2) parallel to A(dagger)parallel to(2) (A(dagger) is the Moore-Penrose pseudoinverse of A) and therefore standard algorithms fail to compute accurate minimum 2-norm solutions of least squares problems. In this work, we introduce a framework that allows us to compute minimum 2-norm solutions of many classes of structured least squares problems accurately, i.e., with errors parallel to(x) over cap (0) - x(0)parallel to(2)/parallel to x(0)parallel to(2) = O(u), where u is the unit roundoff, independently of the magnitude of kappa(2)(A) for most vectors b. The cost of these accurate computations is O(n(2)m) flops, i.e., roughly the same cost as standard algorithms for least squares problems. The approach in this work relies in computing first an accurate rank-revealing decomposition of A, an idea that has been widely used in recent decades to compute, for structured ill-conditioned matrices, singular value decompositions, eigenvalues, and eigenvectors in the Hermitian case and solutions of linear systems with high relative accuracy. In order to prove that accurate solutions are computed, a new multiplicative perturbation theory of the least squares problem is needed. The results presented in this paper are valid for both full rank and rank deficient problems and also in the case of underdetermined linear systems (m < n). Among other types of matrices, the new method applies to rectangular Cauchy, Vandermonde, and graded matrices, and detailed numerical tests for Cauchy matrices are presented. This work was supported by the Ministerio de Economía y Competitividad of Spain through grants MTM-2009-09281, MTM-2012-32542 (Ceballos, Dopico, and Molera) and MTM2010-18057 (Castro-González). Publicado

We start by introducing a new class of structured matrix polynomials, namely, the class of M-A-structured matrix polynomials, to provide a common framework for many classes of structured matrix polynomials that are important in applications: the classes of (skew-)symmetric, (anti-) palindromic, and alternating matrix polynomials. Then, we introduce the families of M-A-structured strong block minimal bases pencils and of M-A-structured block Kronecker pencils, which are particular examples of block minimal bases pencils recently introduced by Dopico, Lawrence, Perez and Van Dooren, and show that any M-A-structured odd-degree matrix polynomial can be strongly linearized via an M-A-structured block Kronecker pencil. Finally, for the classes of (skew-)symmetric, (anti-)palindromic, and alternating odd-degree matrix polynomials, the M-A-structured framework allows us to perform a global and structured backward stability analysis of complete structured polynomial eigenproblems, regular or singular, solved by applying to a M-A-structured block Kronecker pencil a structurally backward stable algorithm that computes its complete eigenstructure, like the palindromic-QR algorithm or the structured versions of the staircase algorithm. This analysis allows us to identify those M-A-structured block Kronecker pencils that yield a computed complete eigenstructure which is the exact one of a slightly perturbed structured matrix polynomial. These pencils include (modulo permutations) the well-known block-tridiagonal and block-anti-tridiagonal structure-preserving linearizations. Our analysis incorporates structure to the recent (unstructured) backward error analysis performed for block Kronecker linearizations by Dopico, Lawrence, Perez and Van Dooren, and share with it its key features, namely, it is a rigorous analysis valid for finite perturbations, i.e., it is not a first order analysis, it provides precise bounds, and it is valid simultaneously for a large class of structure-pre

We describe the generic change of the partial multiplicities at a given eigenvalue $\lambda_0$ of a regular matrix pencil $A_0+\lambda A_1$ under perturbations with low normal rank. More precisely, if the pencil $A_0+\lambda A_1$ has exactly $g$ nonzero partial multiplicities at $\lambda_0$, then for most perturbations $B_0+\lambda B_1$ with normal rank $r

A little known property of a pair of eigenvectors (column and row) of a real tridiagonal matrix is presented. With its help we can define necessary and sufficient conditions for the unique real tridiagonal matrix for which an approximate pair of complex eigenvectors is exact. Similarly, we can designate the unique real tridiagonal matrix for which two approximate real eigenvectors, with different real eigenvalues, are also exact. We close with an illustration that these unique “backward error” matrices are sensitive to small rounding errors in certain partial sums which play a key role in determining the matrices., Ministerio de Economía y Competitividad of Spain through research grant MTM2012-32542, info:eu-repo/semantics/publishedVersion

We provide an algorithm for constructing strong l-ifications of a given matrix polynomial P ( λ ) of degree d and size m × n using only the coefficients of the polynomial and the solution of linear systems of equations. A strong l-ification of P ( λ ) is a matrix polynomial of degree l having the same finite and infinite elementary divisors, and the same numbers of left and right minimal indices as the original matrix polynomial P ( λ ) . All explicit constructions of strong l-ifications introduced so far in the literature have been limited to the case where l divides d, though recent results on the inverse eigenstructure problem for matrix polynomials show that more general constructions are possible. Based on recent developments on dual polynomial minimal bases, we present a general construction of strong l-ifications for wider choices of the degree l, namely, when l divides one of nd or md (and d ≥ l ). In the case where l divides nd (respectively, md), the strong l-ifications we construct allow us to easily recover the minimal indices of P ( λ ) . In particular, we show that they preserve the left (resp., right) minimal indices of P ( λ ) , and the right (resp., left) minimal indices of the l-ification are the ones of P ( λ ) increased by d − l (each). Moreover, in the particular case l divides d, the new method provides a companion l-ification that resembles very much the companion l-ifications already known in the literature.

Bounds for the variation of the Moore–Penrose inverse of general matrices under multiplicative perturbations are presented. Their advantages with respect to classical bounds under additive perturbations and with respect to other bounds under multiplicative perturbations available in the literature are carefully studied and established. Closely connected to these developments a complete multiplicative perturbation theory for least squares problems, valid for perturbations of any size, is also presented, improving in this way recent multiplicative perturbation bounds which are valid only to first order in the size of the perturbations. The results in this paper are mainly based on exact expressions of the perturbed Moore–Penrose inverse in terms of the unperturbed one, the perturbation matrices, and certain orthogonal projectors. Such feature makes the new results amenable to be generalized in the future to linear operators in infinite dimensional spaces.

Minimal bases of rational vector spaces are a well-known and important tool in systems theory. If minimal bases for two subspaces of rational n-space are displayed as the rows of polynomial matrices Z1(λ)_(k x n) and Z2(λ)_(m x n), respectively, then z_1and z_2are said to be dual minimal bases if the subspaces have complementary dimension, i.e., k+m=n, and Z_1 (λ) Z_2^T (λ)=0. In other words, each z_j (λ) provides a minimal basis for the nullspace of the other. It has long been known that for any dual minimal bases z_1 (λ) and z_2 (λ), the row degree sums of Z1 and Z2 are the same. In this paper we show that this is the only constraint on the row degrees, thus characterizing the possible row degrees of dual minimal bases. The proof is constructive, making extensive use of a new class of sparse, structured polynomial matrices that we have baptized zigzag matrices. Another application of these polynomial zigzag matrices is the constructive solution of the following inverse problem for minimal indices { given a list of left and right minimal indices and a desired degree d, does there exist a completely singular matrix polynomial (i.e., a matrix polynomial with no elementary divisors whatsoever) of degree d having exactly the prescribed minimal indices? We show that such a matrix polynomial exists if and only if d divides the sum of the minimal indices. The constructed realization is simple, and explicitly displays the desired minimal indices in a fashion analogous to the classical Kronecker canonical form of singular pencils. Supported by National Science Foundation grant DMS-1016224, and by Ministerio de Economía y Competitividad of Spain through grant MTM2012-32542. Publicado

The development of new classes of linearizations of square matrix polynomials that generalize the classical first and second Frobenius companion forms has attracted much attention in the last decade. Research in this area has two main goals: finding linearizations that retain whatever structure the original polynomial might possess, and improving properties that are essential for accurate numerical computation, such as eigenvalue condition numbers and backward errors. However, all recent progress on linearizations has been restricted to square matrix polynomials. Since rectangular polynomials arise in many applications, it is natural to investigate if the new classes of linearizations can be extended to rectangular polynomials. In this paper, the family of Fiedler linearizations is extended from square to rectangular matrix polynomials, and it is shown that minimal indices and bases of polynomials can be recovered from those of any linearization in this class via the same simple procedures developed previously for square polynomials. Fiedler linearizations are one of the most important classes of linearizations introduced in recent years, but their generalization to rectangular polynomials is nontrivial, and requires a completely different approach to the one used in the square case. To the best of our knowledge, this is the first class of new linearizations that has been generalized to rectangular polynomials.

Linear systems of equations Ax = b, where the matrix A has some particular structure, arise frequently in applications. Very often structured matrices have huge condition numbers κ(A) = ‖A−1‖‖A‖ and, therefore, standard algorithms fail to compute accurate solutions of Ax = b. We say in this paper that a computed solution x is accurate if ‖x− x‖/‖x‖ = O(u), being u the unit roundoff. In this work, we introduce a framework that allows to solve accurately many classes of structured linear systems, independently of the condition number of A and efficiently, that is, with cost O(n3). For most of these classes no algorithms are known that are both accurate and efficient. The approach in this work relies on computing first an accurate rank-revealing decomposition of A, an idea that has been widely used in the last decades to compute singular value and eigenvalue decompositions of structured matrices with high relative accuracy. In particular, we illustrate the new method solving accurately Cauchy and Vandermonde linear systems with any distribution of nodes, i.e., without requiring A to be totally positive, for most right-hand sides b.

The standard way to solve polynomial eigenvalue problems P ( λ ) x = 0 is to convert the matrix polynomial P ( λ ) into a matrix pencil that preserves its spectral information - a process known as linearization. When P ( λ ) is palindromic, the eigenvalues, elementary divisors, and minimal indices of P ( λ ) have certain symmetries that can be lost when using the classical first and second Frobenius companion linearizations for numerical computations, since these linearizations do not preserve the palindromic structure. Recently new families of pencils have been introduced with the goal of finding linearizations that retain whatever structure the original P ( λ ) might possess, with particular attention to the preservation of palindromic structure. However, no general construction of palindromic linearizations valid for all palindromic polynomials has as yet been achieved. In this paper we present a family of linearizations for odd degree polynomials P ( λ ) which are palindromic whenever P ( λ ) is, and which are valid for all palindromic polynomials of odd degree. We illustrate our construction with several examples. In addition, we establish a simple way to recover the minimal indices of the polynomial from those of the linearizations in the new family.

We present a structured perturbation theory for the LDU factorization of (row) diagonally dominant matrices and we use this theory to prove that a recent algorithm of Ye (Math Comp 77(264):2195–2230, 2008) computes the L, D and U factors of these matrices with relative errors less than 14n 3 u, where u is the unit roundoff and n × n is the size of the matrix. The relative errors for D are componentwise and for L and U are normwise with respect the “max norm” $${\|A\|_M = \max_{ij} |a_{ij}|}$$. These error bounds guarantee that for any diagonally dominant matrix A we can compute accurately its singular value decomposition and the solution of the linear system Ax = b for most vectors b, independently of the magnitude of the traditional condition number of A and in O(n 3) flops.

A standard way to solve polynomial eigenvalue problems P(λ)x=0 is to convert the matrix polynomial P(λ) into a matrix pencil that preserves its elementary divisors and, therefore, its eigenvalues. This process is known as linearization and is not unique, since there are infinitely many linearizations with widely varying properties associated with P(λ). This freedom has motivated the recent development and analysis of new classes of linearizations that generalize the classical first and second Frobenius companion forms, with the goals of finding linearizations that retain whatever structures that P(λ) might possess and/or of improving numerical properties, as conditioning or backward errors, with respect the companion forms. In this context, an important new class of linearizations is what we name generalized Fiedler linearizations, introduced in 2004 by Antoniou and Vologiannidis as an extension of certain linearizations introduced previously by Fiedler for scalar polynomials. On the other hand, the mere ...

We describe how to find the general solution of the matrix equation XA + AX T = 0, with A ∈ C n×n , which allows us to determine the dimension of its solution space. This result has immediate applications in the theory of congruence orbits of matrices in C n×n , because the set {XA + AX T : X ∈ C n×n } is the tangent space at A to the congruence orbit of A. Hence, the codimension of this orbit is precisely the dimension of the solution space of XA + AX T = 0. As a consequence, we also determine the generic canonical structure of matrices under the action of congruence. All these results can be directly extended to palindromic pencils A + λA T . AMS subject classication. 15A24, 15A21

A standard way of dealing with a matrix polynomial $P(\lambda)$ is to convert it into an equivalent matrix pencil—a process known as linearization. For any regular matrix polynomial, a new family of linearizations generalizing the classical first and second Frobenius companion forms has recently been introduced by Antoniou and Vologiannidis, extending some linearizations previously defined by Fiedler for scalar polynomials. We prove that these pencils are linearizations even when $P(\lambda)$ is a singular square matrix polynomial, and show explicitly how to recover the left and right minimal indices and minimal bases of the polynomial $P(\lambda)$ from the minimal indices and bases of these linearizations. In addition, we provide a simple way to recover the eigenvectors of a regular polynomial from those of any of these linearizations, without any computational cost. The existence of an eigenvector recovery procedure is essential for a linearization to be relevant for applications.

We prove that the Jacobi algorithm applied implicitly on a decomposition A = XDX T of the symmetric matrix A, where D is diagonal, and X is well conditioned, computes all eigenvalues of A to high relative accuracy. The relative error in every eigenvalue is bounded by $${O(\epsilon \kappa (X))}$$, where $${\epsilon}$$is the machine precision and $${\kappa(X)\equiv\|X\|_2\cdot\|X^{-1}\|_2}$$is the spectral condition number of X. The eigenvectors are also computed accurately in the appropriate sense. We believe that this is the first algorithm to compute accurate eigenvalues of symmetric (indefinite) matrices that respects and preserves the symmetry of the problem and uses only orthogonal transformations.

The group of symplectic matrices is explicitly parametrized, and this description is applied to solve two types of problems. First, we describe several sets of structured symplectic matrices, i.e., sets of symplectic matrices that simultaneously have another structure. We consider unitary symplectic matrices, positive definite symplectic matrices, entrywise positive symplectic matrices, totally nonnegative symplectic matrices, and symplectic M-matrices. The special properties of the LU factorization of a symplectic matrix play a key role in the parametrization of these sets. The second class of problems we deal with is to describe those matrices that can be certain significant submatrices of a symplectic matrix, and to parametrize the symplectic matrices with a given matrix occurring as a submatrix in a given position. The results included in this work provide concrete tools for constructing symplectic matrices with special structures or particular submatrices that may be used, for instance, to create examples for testing numerical algorithms.

Let H ( λ ) = A 0 + λ A 1 be a square singular matrix pencil, and let λ 0 ∈ C be an eventually multiple eigenvalue of H ( λ ) . It is known that arbitrarily small perturbations of H ( λ ) can move the eigenvalues of H ( λ ) anywhere in the complex plane, i.e., the eigenvalues are discontinuous functions of the entries of A 0 and A 1 . Therefore, it is not possible to develop an eigenvalue perturbation theory for arbitrary perturbations of H ( λ ) . However, if the perturbations are restricted to lie in an appropriate set then the eigenvalues change continuously. We prove that this set of perturbations is generic, i.e., it contains almost all pencils, and present sufficient conditions for a pencil to be in this set. In addition, for perturbations in this set, explicit first order perturbation expansions of λ 0 are obtained in terms of the perturbation pencil and bases of the left and right null spaces of H ( λ 0 ) , both for simple and multiple eigenvalues. Infinite eigenvalues are also considered. Finally, information on the eigenvectors of the generically regular perturbed pencil is presented. We obtain, as corollaries, results for regular pencils that are also new.

The set of $m\times n$ complex matrix pencils with rank (normal rank) at most $r$ defines a subset of pencils in a complex $2 m n$ dimensional space. For $r = 1,\dots,\min\{m,n\}-1$, we show that this subset is a closed set, which is the union of $r+1$ irreducible components. Each of these irreducible components is the closure of a certain orbit of strictly equivalent pencils with rank $r$. The Kronecker canonical forms of these orbits are explicitly described, and their dimensions are counted. These are the Kronecker canonical forms of generic pencils of rank at most $r$. If $m\ne n$, then each irreducible component has a codimension distinct from the others, and the least of these codimensions is the codimension of the set of matrix pencils with rank at most $r$. This is $(n-r)(2m-r)$ if $m \geq n$ and $(m-r)(2n-r)$ otherwise.

Let $A_0 + \lambda A_1$ be a regular matrix pencil, and let $\lambda_0$ be one of its finite eigenvalues having $g$ elementary Jordan blocks in the Weierstrass canonical form. We show that for most matrices $B_0$ and $B_1$ with ${\rm rank} (B_0 + \lambda_0 B_1)< g$ there are $g - {\rm rank} (B_0 + \lambda_0 B_1)$ Jordan blocks corresponding to the eigenvalue $\lambda_0$ in the Weierstrass form of the perturbed pencil $A_0+B_0 + \lambda (A_1+B_1)$. If ${\rm rank} (B_0 + \lambda_0 B_1)+ {\rm rank} (B_1)$ does not exceed the number of $\lambda_0$-Jordan blocks in $A_0 + \lambda A_1$ of dimension greater than one, then the $\lambda_0$-Jordan blocks of the perturbed pencil are the $g- {\rm rank} (B_0 + \lambda_0 B_1)-{\rm rank} (B_1)$ smallest $\lambda_0$-Jordan blocks of $A_0 + \lambda A_1$, together with ${\rm rank} (B_1)$ blocks of dimension one. Otherwise, all $g- {\rm rank} (B_0 + \lambda_0 B_1)$ $\lambda_0$-Jordan blocks of the perturbed pencil are of dimension one. This happens for any pair of matrices $B_0$ and $B_1$ except those in a proper algebraic submanifold in the set of matrix pairs. If $A_0 + \lambda A_1$ has an infinite eigenvalue, then the corresponding result follows from considering the zero eigenvalue of the dual pencils $A_1 + \lambda A_0$ and $A_1 + B_1 + \lambda (A_0 + B_0)$.