Search

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.

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

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.

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

We present a new O(n3) algorithm for computing all eigenvalues of certain sign regular matrices to high relative accuracy in floating point arithmetic. The accuracy and cost are unaffected by the conventional eigenvalue condition numbers.A matrix is called sign regular when the signs of its nonzero minors depend only of the order of the minors. The sign regular matrices we consider are the ones which are nonsingular and whose kth order nonzero minors are of sign (-1)k(k-1)/2 for all k. This class of matrices can also be characterized as “nonsingular totally nonnegative matrices with columns in reverse order”.We exploit a characterization of these particular sign regular matrices as products of nonnegative bidiagonals and the reverse identity. We arrange the computations in such a way that no subtractive cancellation is encountered, thus guaranteeing high relative forward accuracy.

Let $P(\lambda) = A_0 + \lambda A_1$ be a singular $m\times n$ matrix pencil without full rank whose Kronecker canonical form (KCF) is given. Let r be a positive integer such that $\rho \leq \min\{m,n\}- {\rm rank} (P)$ and $\rho \leq {\rm rank}(P)$. We study the change of the KCF of $P(\lambda)$ due to perturbation pencils $Q(\lambda)$ with ${\rm rank} (Q) = \rho$. We focus on the generic behavior of the KCF of $(P+Q)(\lambda)$, i.e., the behavior appearing for perturbations $Q(\lambda)$ in a dense open subset of the pencils with rank r. The most remarkable generic properties of the KCF of the perturbed pencil $(P+Q) (\lambda)$ are (i) if $\lambda_0$ is an eigenvalue of $P(\lambda)$, finite or infinite, then $\lambda_0$ is an eigenvalue of $(P+Q)(\lambda)$; (ii) if $\lambda_0$ is an eigenvalue of $P(\lambda)$, then the number of Jordan blocks associated with $\lambda_0$ in the KCF of $(P+Q) (\lambda)$ is equal to or greater than the number of Jordan blocks associated with $\lambda_0$ in the KCF of $P(\lambda)$; (iii) if $\lambda_0$ is an eigenvalue of $P(\lambda)$, then the dimensions of the Jordan blocks associated with $\lambda_0$ in $(P+Q) (\lambda)$ are equal to or greater than the dimensions of the Jordan blocks associated with $\lambda_0$ in $P (\lambda)$; (iv) the row (column) minimal indices of $(P+Q) (\lambda)$ are equal to or greater than the largest row (column) minimal indices of $P(\lambda)$. Moreover, if the sum of the row (column) minimal indices of the perturbations $Q(\lambda)$ is known, apart from their rank, then the whole set of the row (column) minimal indices of $(P+Q) (\lambda)$ is generically obtained, and in the case $\rho < \min\{m,n\}- {\rm rank} (P)$ the whole KCF of $(P+Q) (\lambda)$ is generically determined.

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

New results on the patterns of linearly independent rows and columns among the blocks of a symplectic matrix are presented. These results are combined with the block structure of the inverse of a symplectic matrix, together with some properties of Schur complements, to give a new and elementary proof that the determinant of any symplectic matrix is +1. The new proof is valid for any field. Information on the zero patterns compatible with the symplectic structure is also presented.

A singular matrix A may have more than one LU factorizations. In this work the set of all LU factorizations of A is explicitly described when the lower triangular matrix L is nonsingular. To this purpose, a canonical form of A under left multiplication by unit lower triangular matrices is introduced. This canonical form allows us to characterize the matrices that have an LU factorization and to parametrize all possible LU factorizations. Formulae in terms of quotient of minors of A are presented for the entries of this canonical form.

We present new $O(n^3)$ algorithms that compute eigenvalues and eigenvectors to high relative accuracy in floating point arithmetic for the following types of matrices: symmetric Cauchy, symmetric diagonally scaled Cauchy, symmetric Vandermonde, and symmetric totally nonnegative matrices when they are given as products of nonnegative bidiagonal factors. The algorithms are divided into two stages: the first stage computes a symmetric rank revealing decomposition of the matrix to high relative accuracy, and the second stage applies previously existing algorithms to this decomposition to get the eigenvalues and eigenvectors. Rank revealing decompositions are also interesting in other problems, such as the numerical determination of the rank and the approximation of a matrix by a matrix with smaller rank.

Component- and normwise perturbation bounds for the block LU factorization and block LDL$^*$ factorization of Hermitian matrices are presented. We also obtain, as a consequence, perturbation bounds for the usual pointwise LU, LDL$^*$, and Cholesky factorizations. Some of these latter bounds are already known, but others improve previous results. All the bounds presented are easily proved by using series expansions. Given a square matrix $A=L U$ having the LU factorization, and a perturbation $E$, the LU factors of the matrix $A+E= \widetilde{L} \widetilde{U}$ are written as two convergent series of matrices: $\widetilde{L} = \sum_{k=0}^{\infty} L_k$ and $\widetilde{U} = \sum_{k=0}^{\infty} U_k$, where $L_k = O(\|E\|^k)$, $U_k = O(\|E\|^k)$, and $L_0 = L$, $U_0 = U$. We present expressions for the matrices $L_k$ and $U_k$ in terms of $L$, $U$, and $E$. The domain and the rate of convergence of these series are studied. Simple bounds on the remainders of any order of these series are found, which significantly improve the bounds on the second-order terms existing in the literature. This is useful when first-order perturbation analysis is used.

In this paper the accuracy of LU factorization of tridiagonal matrices without pivoting is considered. Two types of componentwise condition numbers for the L and U factors of tridiadonal matrices are presented and compared. One type is a condition number with respect to small relative perturbations of each entry of the matrix. The other type is a condition number with respect to small componentwise perturbations of the kind appearing in the backward error analysis of the usual algorithm for the LU factorization. We show that both condition numbers are of similar magnitude. This means that the algorithm is componentwise forward stable, i.e., the forward errors are of similar magnitude to those produced by a componentwise backward stable method. Moreover the presented condition numbers can be computed in O(n) flops, which allows to estimate with low cost the forward errors.

Let A be a matrix and $\lambda_0$ be one of its eigenvalues having g elementary Jordan blocks in the Jordan canonical form of A. We show that for most matrices B satisfying ${\rm rank}\,(B)\leq g$, the Jordan blocks of A+B with eigenvalue $\lambda_0$ are just the $g-{\rm rank}\,(B)$ smallest Jordan blocks of A with eigenvalue $\lambda_0$. The set of matrices for which this behavior does not happen is explicitly characterized through a scalar determinantal equation involving B and some of the $\lambda_0$-eigenvectors of A. Thus, except for a set of zero Lebesgue measure, a low rank perturbation A+B of A destroys for each of its eigenvalues exactly the rank,(B) largest Jordan blocks of A, while the rest remain unchanged.

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.

This work introduces a new perturbation bound for the L factor of the LDU factorization of (row) diagonally dominant matrices computed via the column diagonal dominance pivoting strategy. This strategy yields L and U factors which are always well-conditioned and, so, the LDU factorization is guaranteed to be a rank-revealing decomposition. The new bound together with those for the D and U factors in [F. M. Dopico and P. Koev, Numer. Math., 119 (2011), pp. 337– 371] establish that if diagonally dominant matrices are parameterized via their diagonally dominant parts and off-diagonal entries, then tiny relative componentwise perturbations of these parameters produce tiny relative normwise variations of L and U and tiny relative entrywise variations of D when column diagonal dominance pivoting is used. These results will allow us to prove in a follow-up work that such perturbations also lead to strong perturbation bounds for many other problems involving diagonally dominant matrices. Research supported in part by Ministerio de Economía y Competitividad of Spain under grant MTM2012-32542. Publicado

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

Let A ( λ ) be a complex regular matrix polynomial of degree l with g elementary divisors corresponding to the finite eigenvalue λ 0 . We show that for most complex matrix polynomials B ( λ ) with degree at most l satisfying rank B ( λ 0 ) g the perturbed polynomial ( A + B ) ( λ ) has exactly g - rank B ( λ 0 ) elementary divisors corresponding to λ 0 , and we determine their degrees. If rank B ( λ 0 ) + rank ( B ( λ ) - B ( λ 0 ) ) does not exceed the number of λ 0 -elementary divisors of A ( λ ) with degree greater than 1, then the λ 0 -elementary divisors of ( A + B ) ( λ ) are the g - rank B ( λ 0 ) - rank ( B ( λ ) - B ( λ 0 ) ) elementary divisors of A ( λ ) corresponding to λ 0 with smallest degree, together with rank ( B ( λ ) - B ( λ 0 ) ) linear λ 0 -elementary divisors. Otherwise, the degree of all the λ 0 -elementary divisors of ( A + B ) ( λ ) is one. This behavior happens for any matrix polynomial B ( λ ) except those in a proper algebraic submanifold in the set of matrix polynomials of degree at most l . If A ( λ ) has an infinite eigenvalue, the corresponding result follows from considering the zero eigenvalue of the perturbed dual polynomial.

The K -Orthogonal group of an n -by- n matrix K is defined as the set of nonsingular n -by- n matrices A satisfying A T KA = K , where the superscript T denotes transposition. These form a group under matrix multiplication. It is well-known that if K is skew-symmetric and nonsingular the determinant of every element of the K -Orthogonal group is +1, i.e., the determinant of any symplectic matrix is +1. We present necessary and sufficient conditions on a real or complex matrix K so that all elements of the K -Orthogonal group have determinant +1. These necessary and sufficient conditions can be simply stated in terms of the symmetric and skew-symmetric parts of K , denoted by K s and K w respectively, as follows: the determinant of every element in the K -Orthogonal group is +1 if and only if the matrix pencil K w - λ K s is regular and the matrix ( K w - λ 0 K s ) - 1 K w has no Jordan blocks associated to the zero eigenvalue with odd dimension, where λ 0 is any number such that det ( K w - λ 0 K s ) ≠ 0 .

In this paper, the matrix equation AX + X⋆B = C is considered, where the matrices A and B have sizes m × n and n × m, respectively, the size of the unknown X is n × m, and the operator (·) ⋆ denotes either the transpose or the conjugate transpose of a matrix. In the first part of the paper, necessary and sufficient conditions for the existence and uniqueness of solutions are reviewed. These conditions were obtained previously by Wimmer (H.K. Wimmer. Roth's theorems for matrix equations with symmetry constraints. Linear Algebra Appl., 199:357- 362, 1994.), by Byers and Kressner (R. Byers and D. Kressner. Structured condition numbers for invariant subspaces. SIAM J. Matrix Anal. Appl., 28:326-347, 2006.), and by Kressner, Schroder and Watkins (D. Kressner, C. Schroder, and D.S. Watkins. Implicit QR algorithms for palindromic and even eigenvalue problems. Numer. Algorithms, 51:209-238, 2009.). This review generalizes to fields of characteristic different from two the existence condition that Wimmer originally proved for the complex field. In the second part, an algorithm is developed, in the real or complex square case m = n, to solve the equation in O(n3) flops when the solution is unique. This algorithm is based on the generalized Schur decomposition of the matrix pencil A λB ⋆ . The equation AX + X ⋆ B = C is connected with palindromic eigenvalue problems and, as a consequence, the square complex case has attracted recently the attention of several authors.