Search

Bundles of matrix pencils (under strict equivalence) are sets of pencils having the same Kronecker canonical form, up to the eigenvalues (namely, they are an infinite union of orbits under strict equivalence). The notion of bundle for matrix pencils was introduced in the 1990's, following the same notion for matrices under similarity, introduced by Arnold in 1971, and it has been extensively used since then. Despite the amount of literature devoted to describing the topology of bundles of matrix pencils, some relevant questions remain still open in this context. For example, the following two: (a) provide a characterization for the inclusion relation between the closures (in the standard topology) of bundles; and (b) are the bundles open in their closure? The main goal of this paper is providing an explicit answer to these two questions. In order to get this answer, we also review and/or formalize some notions and results already existing in the literature. We also prove that bundles of matrices under similarity, as well as bundles of matrix polynomials (defined as the set of m x n matrix polynomials of the same grade having the same spectral information, up to the eigenvalues) are open in their closure. This work has been supported by the Agencia Estatal de Investigación of Spain through grants PID2019-106362GB-I00 MCIN/ AEI/10.13039/501100011033/ and MTM2017-90682-REDT, and by the Madrid Government (Comunidad de Madrid-Spain) under the Multiannual Agreement with UC3M in the line of Excellence of University Professors (EPUC3M23), and in the context of the V PRICIT (Regional Programme of Research and Technological Innovation).

The generic change of the Weierstras canonical form of regular complex structured matrix pencils under generic structure-preserving additive low-rank perturbations is studied. Several different symmetry structures are considered, and it is shown that for most of the structures, the generic change in the eigenvalues is analogous to the case of generic perturbations that ignore the structure. However, for some odd/even and palindromic structures, there is a different behavior for the eigenvalues 0 and $$\infty $$ , respectively, $$+1$$ and $$-1$$ . The differences arise in those cases where the parity of the partial multiplicities in the perturbed matrix pencil provided by the generic behavior in the general structure-ignoring case is not in accordance with the restrictions imposed by the structure. The new results extend results for the rank-1 and rank-2 cases that were obtained in Batzke (Linear Algebra Appl 458:638–670, 2014, Oper Matrices 10:83–112, 2016) for the case of special structure-preserving perturbations. As the main tool, we use decompositions of matrix pencils with symmetry structure into sums of rank-1 matrix pencils, as those allow a parametrization of the set of matrix pencils with a given symmetry structure and a given rank.

In this paper, which is a follow-up to Borobia et al. (Mediterr J Math, 18:40, 2021), we provide a necessary and sufficient condition for the matrix equation $$X^\top AX=B$$ X ⊤ A X = B to be consistent when B is symmetric. The condition depends on the canonical form for congruence of the matrix A, and is proved to be necessary for all matrices A, and sufficient for most of them. This result improves the main one in the previous paper, since the condition is stronger than the one in that reference, and the sufficiency is guaranteed for a larger set of matrices (namely, those whose canonical form for congruence, CFC(A), includes skew-symmetric blocks).

The purpose of this Corrigendum is twofold. The main goal is to fix a gap in the proof of Theorem 5.3 in De Teran and Hernando (Rev R Acad Cienc Exactas Fis Nat Ser A Mat RACSAM 114(1):1–17, 2020). The second objective is to clarify part of the proof of Lemma 3.1 in the same reference.

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.

We provide necessary and sufficient conditions for the matrix equation $$X^\top A X=B$$ to be consistent when B is a symmetric matrix, for all matrices A with a few exceptions. The matrices A, B, and X (unknown) are matrices with complex entries. We first see that we can restrict ourselves to the case where A and B are given in canonical form for congruence and, then, we address the equation with A and B in such form. The characterization strongly depends on the canonical form for congruence of A. The problem we solve is equivalent to: given a complex bilinear form (represented by A) find the maximum dimension of a subspace such that the restriction of the bilinear form to this subspace is a symmetric non-degenerate bilinear form.

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

In this paper, we introduce a general class of quasi-sparse potential companion pencils for arbitrary square matrix polynomials over an arbitrary field, which extends the class introduced in [B. Eastman, I.-J. Kim, B. L. Shader, K.N. Vander Meulen, Companion matrix patterns. Linear Algebra Appl. 436 (2014) 255–272] for monic scalar polynomials. We provide a canonical form, up to permutation, for companion pencils in this class. We also relate these companion pencils with other relevant families of companion linearizations known so far. Finally, we determine the number of different sparse companion pencils in the class, up to permutation.

In this paper, we introduce a new notion of generalized companion pencils for scalar polynomials over an arbitrary field expressed in the monomial basis. Our definition is quite general and extends the notions of companion pencil in De Terán et al. (Linear Algebra Appl 459:264&-333, 2014), generalized companion matrix in Garnett et al. (Linear Algebra Appl 498:360&-365, 2016), and Ma&-Zhan companion matrices in Ma and Zhan (Linear Algebra Appl 438: 621&-625, 2013), as well as the class of quasi-sparse companion pencils introduced in De Terán and Hernando (INdAM Series, Springer, Berlin, pp 157&-179, 2019). We analyze some algebraic properties of generalized companion pencils. We determine their Smith canonical form and we prove that they are all nonderogatory. In the last part of the work we will pay attention to the sparsity of these constructions. In particular, by imposing some natural conditions on its entries, we determine the smallest number of nonzero entries of a generalized companion pencil This work has been partially supported by the Ministerio de Economía y Competitividad of Spain through Grants MTM2017-90682-REDT and MTM2015-65798-P.

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.

We present necessary and sufficient conditions for the existence of a unique solution of the generalized ⋆-Sylvester matrix equation A X B + C X ⋆ D = E , where A , B , C , D , E are square matrices of the same size with real or complex entries, and where ⋆ stands for either the transpose or the conjugate transpose. This generalizes several previous uniqueness results for specific equations like the ⋆-Sylvester or the ⋆-Stein equations.

We provide necessary and sufficient conditions for the generalized $\star$-Sylvester matrix equation, $AXB + CX^\star D = E$, to have exactly one solution for any right-hand side E. These conditions are given for arbitrary coefficient matrices $A, B, C, D$ (either square or rectangular) and generalize existing results for the same equation with square coefficients. We also review the known results regarding the existence and uniqueness of solution for generalized Sylvester and $\star$-Sylvester equations., This new version corrects some inaccuracies in corollaries 7 and 9

The sets of $n\times n$ $\top$-palindromic, $\top$-antipalindromic, $\top$-even, and $\top$-odd matrix pencils with rank at most $r< n$ are algebraic subsets of the set of $n\times n$ matrix pencils. In this paper, we determine their dimension and we prove that they are all irreducible. This is in contrast with the nonstructured case, since it is known that the set of $n\times n$ matrix pencils with rank at most $r< n$ is an algebraic set with $r+1$ irreducible components. We also show that these sets of structured pencils with bounded rank are the closure of the congruence orbit of a certain structured pencil given in canonical form. This allows us to determine the generic canonical form of a structured $n\times n$ matrix pencil with rank at most $r$, for any of the previous structures.

We provide an amended version of Corollaries 7 and 9 in [De Teran, Iannazzo, Poloni, Robol, "Solvability and uniqueness criteria for generalized Sylvester-type equations"]. These results characterize the unique solvability of the matrix equation AXB + CX*D = E (where the coefficients need not be square) in terms of an equivalent condition on the spectrum of certain matrix pencils of the same size as one of its coefficients. (C) 2017 Elsevier Inc. All rights reserved.

A canonical form for congruence of matrices was introduced by Turnbull and Aitken in 1932. More than 70 years later, in 2006, another canonical form for congruence has been introduced by Horn and Sergeichuk. The main purpose of this paper is to draw the attention on the pioneer work of Turnbull and Aitken and to compare both canonical forms. As an application, we also show how to recover the spectral structure of T-palindromic matrix pencils from the canonical form of matrices by Horn and Sergeichuk.

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).

We consider the uniqueness of solution (i.e., nonsingularity) of systems of r generalized Sylvester and ⋆‐Sylvester equations with n×n coefficients. After several reductions, we show that it is sufficient to analyze periodic systems having, at most, one generalized ⋆‐Sylvester equation. We provide characterizations for the nonsingularity in terms of spectral properties of either matrix pencils or formal matrix products, both constructed from the coefficients of the system. The proposed approach uses the periodic Schur decomposition and leads to a backward stable O(n3r) algorithm for computing the (unique) solution. Ministerio de Economía y Competitividad of Spain. Grant Numbers: MTM2015-68805-REDT, MTM2015- 65798-P; Istituto Nazionale di Alta Matematica “Francesco Severi”. Grant Number: GNCS Project 2016; Research project of the Università di Perugia Soluzione numerica di problemi di algebra lineare strutturata

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.

In this paper, we obtain formulas for the left and right eigenvectors and minimal bases of some families of Fiedler-like linearizations of square matrix polynomials. In particular, for the families of Fiedler pencils, generalized Fiedler pencils and Fiedler pencils with repetition. These formulas allow us to relate the eigenvectors and minimal bases of the linearizations with the ones of the polynomial. Since the eigenvectors appear in the standard formula of the condition number of eigenvalues of matrix polynomials, our results may be used to compare the condition numbers of eigenvalues of the linearizations within these families and the corresponding condition number of the polynomial eigenvalue problem. Publicado

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

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.

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.

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.

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

Given a singular n×n matrix function A(λ) , analytic in a neighborhood of an eigenvalue λ0 ∈ C , and perturbations, B(λ ,e) , such that B(λ ,0) ≡ 0 and analytic in λ and e near (λ0,0) , we provide sufficient conditions on these perturbations for the existence of eigenvalue expansions of the perturbed matrix A(λ) + B(λ ,e) near λ0 . We also describe the first order term of these expansions. This extends to the singular case some results by Langer and Najman. Mathematics subject classification (2010): 15A18, 47A56.

We develop first order eigenvalue expansions of one-parametric perturbations of square singular matrix polynomials. Although the eigenvalues of a singular matrix polynomial P(λ) are not continuous functions of the entries of the coefficients of the polynomial, we show that for most perturbations they are indeed continuous. Given an eigenvalue λ0 of P(λ) we prove that, for generic perturbations M(λ) of degree at most the degree of P(λ), the eigenvalues of P(λ)+ϵM(λ) admit covergent series expansions near λ0 and we describe the first order term of these expansions in terms of M(λ0) and certain particular bases of the left and right null spaces of P(λ0). In the important case of λ0 being a semisimple eigenvalue of P(λ) any bases of the left and right null spaces of P(λ0) can be used, and the first order term of the eigenvalue expansions takes a simple form. In this situation we also obtain the limit vector of the associated eigenvector expansions.

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.

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)$.

The proceeding at: Joint ALAMA-GAMM/ANLA 2014 Meeting, took place 2014, July 14-16, in Barcelona (Spain). We present necessary and su cient conditions for the existence of a matrix polynomial when its degree, its nite and in nite elementary divisors, and its left and right minimal indices are prescribed. These conditions hold for arbitrary in nite elds and are determined mainly by the \index sum theorem", which is a fundamental relationship between the rank, the degree, the sum of all partial multiplicities, and the sum of all minimal indices of any matrix polynomial. The proof developed for the existence of such polynomial is constructive and, therefore, solves a very general inverse problem for matrix polynomials with prescribed complete eigenstructure. This result allows us to x the problem of the existence of (l)-ifications of a given matrix polynomial, as well as to determine all their possible sizes and eigenstructures. This research was partially supported by the Ministerio de Economía y Competitividad of Spain through grant MTM-2012-32542 and by the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office. Publicado

The concept of linearization is fundamental for theory, applications, and spectral computations related to matrix polynomials. However, recent research on several important classes of structured matrix polynomials arising in applications has revealed that the strategy of using linearizations to develop structure-preserving numerical algorithms that compute the eigenvalues of structured matrix polynomials can be too restrictive, because some structured polynomials do not have any linearization with the same structure. This phenomenon strongly suggests that linearizations should sometimes be replaced by other low degree matrix polynomials in applied numerical computations. Motivated by this fact, we introduce equivalence relations that allow the possibility of matrix polynomials (with coefficients in an arbitrary field) to be equivalent, with the same spectral structure, but have different sizes and degrees. These equivalence relations are directly modeled on the notion of linearization, and consequently inherit the simplicity, applicability, and most relevant properties of linearizations; simultaneously, though, they are much more flexible in the possible degrees of equivalent polynomials. This flexibility allows us to define in a unified way the notions of quadratification and l-ification, to introduce the concept of companion form of arbitrary degree, and to provide concrete and simple examples of these notions that generalize in a natural and smooth way the classical first and second Frobenius companion forms. The properties of l-ifications are studied in depth; in this process a fundamental result on matrix polynomials, the “Index Sum Theorem”, is recovered and extended to arbitrary fields. Although this result is known in the systems theory literature for real matrix polynomials, it has remained unnoticed by many researchers. It establishes that the sum of the (finite and infinite) partial multiplicities, together with the (left and right) minimal indices of any matrix polynomial is equal to the rank times the degree of the polynomial. The “Index Sum Theorem” turns out to be a key tool for obtaining a number of significant results: on the possible sizes and degrees of l-ifications and companion forms, on the minimal index preservation properties of companion forms of arbitrary degree, as well as on obstructions to the existence of structured companion forms for structured matrix polynomials of even degree. This paper presents many new results, blended together with results already known in the literature but extended here to the most general setting of matrix polynomials of arbitrary sizes and degrees over arbitrary fields. Therefore we have written the paper in an expository and self-contained style that makes it accessible to a wide variety of readers.

The proceeding at: 6th Conference on Structured Numerical Linear and Multilinear Algebra: Analysis, Algorithms and Applications (SLA 2014), took place at 2014, Septembe 8-12, in Kalamata (Grece), Computing roots of scalar polynomials as the eigenvalues of Frobenius companion matrices using backward stable eigenvalue algorithms is a classical approach. The introduction of new families of companion matrices allows for the use of other matrices in the root-finding problem. In this paper, we analyze the backward stability of polynomial root-finding algorithms via Fiedler companion matrices. In other words, given a polynomial p(z), the question is to determine whether the whole set of computed eigenvalues of the companion matrix, obtained with a backward stable algorithm for the standard eigenvalue problem, are the set of roots of a nearby polynomial or not. We show that, if the coefficients of p(z) are bounded in absolute value by a moderate number, then algorithms for polynomial root-finding using Fiedler matrices are backward stable, and Fiedler matrices are as good as the Frobenius companion matrices. This allows us to use Fiedler companion matrices with favorable structures in the polynomial root-finding problem. However, when some of the coefficients of the polynomial are large, Fiedler companion matrices may produce larger backward errors than Frobenius companion matrices, although in this case neither Frobenius nor Fiedler matrices lead to backward stable computations. To prove this we obtain explicit expressions for the change, to first order, of the characteristic polynomial coefficients of Fielder matrices under small perturbations. We show that, for all Fiedler matrices except the Frobenius ones, this change involves quadratic terms in the coefficients of the characteristic polynomial of the original matrix, while for the Frobenius matrices it only involves linear terms. We present extensive numerical experiments that support these theoretical results. The effect of balancing these matrices is also investigated. This work has been supported by the Ministerio de Economía y Competitividad of Spain through grant MTM2012-32542 Publicado

Several matrix norms of the classical Frobenius companion matrices of a monic polynomial p(z) have been used in the literature to obtain simple lower and upper bounds on the absolute values of the roots lambda of p(z). Recently, M. Fiedler (2003) [9] has introduced a new family of companion matrices of p(z) that has received considerable attention and it is natural to investigate if matrix norms of Fiedler companion matrices may be used to obtain new and sharper lower and upper bounds on vertical bar lambda vertical bar. The development of such bounds requires first to know simple expressions for some relevant matrix norms of Fiedler matrices and we obtain them in the case of the 1- and infinity-matrix norms. With these expressions at hand, we will show that norms of Fiedler matrices produce many new bounds, but that none of them improves significatively the classical bounds obtained from the Frobenius companion matrices. However, we will prove that if the norms of the inverses of Fiedler matrices are used, then another family of new bounds on vertical bar lambda vertical bar is obtained and some of the bounds in this family improve significatively the bounds coming from the Frobenius companion matrices for certain polynomials. This work has been supported by the Ministerio de Economía y Competitividad of Spain through grant MTM2012-32542.

We analyze the relationship between the Jordan canonical form of products, in different orders, of k square matrices A1,.,Ak. Our results extend some classical results by H. Flanders. Motivated by a generalization of Fiedler matrices, we study permuted products of A1,.,Ak under the assumption that the graph of non-commutativity relations of A1,.,Ak is a forest. Under this condition, we show that the Jordan structure of all nonzero eigenvalues is the same for all permuted products. For the eigenvalue zero, we obtain an upper bound on the difference between the sizes of Jordan blocks for any two permuted products, and we show that this bound is attainable. For k=3 we show that, moreover, the bound is exhaustive. This research has been sSupported by the Ministerio de Economía y Competitividad of Spain through grants MTM-2009-09281 and MTM-2012-32542. Publicado

We give a complete solution of the matrix equation AX+BX=0, where A, B ∈ C^mxn are two given matrices, X ∈ C^mxn is an unknown matrix, and denotes the transpose or the conjugate transpose. We provide a closed formula for the dimension of the solution space of the equation in terms of the Kronecker canonical form of the matrix pencil A+B, and we also provide an expression for the solution X in terms of this canonical form, together with two invertible matrices leading A+B to the canonical form by strict equivalence. This work was partially supported by the Ministerio de Ciencia e Innovación of Spain through grant MTM-2009-09281 Publicado

We solve the matrix equation XA+AX� = 0, where A 2 Cn×n is an arbitrary given square matrix, and we compute the dimension of its solution space. This dimension coincides with the codimension of the tangent space of thecongruence orbit of A. Hence, we also obtain the (real) dimension ofcongruence orbits in C n×n . As an application, we determine the generic canonical structure forcongruence in C n×n and also the generic Kronecker canonical form ofpalindromic pencils A + �A � .

A standard way of dealing with a regular matrix polynomial P (λ) is to convert it into an equivalent matrix pencil - a process known as linearization. Two vector spaces of pencils L1(P ) and L2(P ) that generalize the first and second companion forms have recently been introduced by Mackey, Mackey, Mehl and Mehrmann. Almost all of these pencils are linearizations for P (λ )w hen P is regular. The goal of this work is to show that most of the pencils in L1(P )a ndL2(P )a re stil l linearizations when P (λ) is a singular square matrix polynomial, and that these linearizations can be used to obtain the complete eigenstructure of P (λ), comprised not only of the finite and infinite eigenvalues, but also for singular polynomials of the left and right minimal indices and minimal bases. We show explicitly how to recover the minimal indices and bases of the polynomial P (λ )f rom the minimalindices and bases of l in L1(P )a ndL2(P ). As a consequence of the recovery formulae for minimal indices, we prove that the vector space DL(P )= L1(P ) ∩ L2(P )w il l never contain any linearization for a square singular polynomial P (λ). Finally, the results are extended to other linearizations of singular polynomials defined in terms of more general polynomial bases.

A standard way of dealing with matrixpolynomial eigenvalue problems is to use linearizations. Byers, Mehrmann and Xu have recently defined and studied linearizations of dimen- sions smaller than the classical ones. In this paper, lower bounds are provided for the dimensions of linearizations and strong linearizations of a given m × n matrixpolynomial, and particular lineariza- tions are constructed for which these bounds are attained. It is also proven that strong linearizations of an n × n regular matrixpolynomial of degreemust have dimension n� × n� .