Search

Given a possibly singular matrix polynomial P (z) , we study how the eigenvalues, eigenvectors, root polynomials, minimal indices, and minimal bases of the pencils in the vector space DL (P) introduced in Mackey, Mackey, Mehl, and Mehrmann [SIAM J. Matrix Anal. Appl. 28(4), 971-1004, 2006] are related to those of P (z). If P (z) is regular, it is known that those pencils in DL (P) satisfying the generic assumptions in the so-called eigenvalue exclusion theorem are strong linearizations for P (z). This property and the block-symmetric structure of the pencils in DL (P) have made these linearizations among the most influential for the theoretical and numerical treatment of structured regular matrix polynomials. However, it is also known that, if P (z) is singular, then none of the pencils in DL (P) is a linearization for P (z). In this paper, we prove that despite this fact a generalization of the eigenvalue exclusion theorem holds for any singular matrix polynomial P (z) and that such a generalization allows us to recover all the relevant quantities of P (z) from any pencil in DL (P) satisfying the eigenvalue exclusion hypothesis. Our proof of this general theorem relies heavily on the representation of the pencils in DL (P) via Bézoutians by Nakatsukasa, Noferini and Townsend [SIAM J. Matrix Anal. Appl. 38(1), 181-209, 2015]. [ABSTRACT FROM AUTHOR]

Let L = (L 1 , L 2) be a list consisting of structural data for a matrix polynomial; here L 1 is a sublist consisting of powers of irreducible (monic) scalar polynomials over the field R , and L 2 is a sublist of nonnegative integers. For an arbitrary such L , we give easy-to-check necessary and sufficient conditions for L to be the list of elementary divisors and minimal indices of some real T-palindromic quadratic matrix polynomial. For a list L satisfying these conditions, we show how to explicitly build a real T-palindromic quadratic matrix polynomial having L as its structural data; that is, we provide a T-palindromic quadratic realization of L over R . A significant feature of our construction differentiates it from related work in the literature; the realizations constructed here are direct sums of blocks with low bandwidth, that transparently display the spectral and singular structural data in the original list L . [ABSTRACT FROM AUTHOR]

Structured rational matrices such as symmetric, skew-symmetric, Hamiltonian, skew-Hamiltonian, Hermitian, and para-Hermitian rational matrices arise in many applications. Linearizations of rational matrices have been introduced recently for computing poles, eigenvalues, eigenvectors, minimal bases and minimal indices of rational matrices. For structured rational matrices, it is desirable to construct structure-preserving linearizations so as to preserve the symmetry in the eigenvalues and poles of the rational matrices. With a view to constructing structure-preserving linearizations of structured rational matrices, we propose a family of Fiedler-like pencils and show that the family of Fiedler-like pencils is a rich source of structure-preserving strong linearizations of structured rational matrices. We construct symmetric, skew-symmetric, Hamiltonian, skew-Hamiltonian, Hermitian, skew-Hermitian, para-Hermitian and para-skew-Hermitian strong linearizations of a rational matrix G (λ) when G (λ) has the same structure. We also describe recovery of eigenvectors, minimal bases and minimal indices of G (λ) from those of the linearizations of G (λ) and show that the recovery is operation-free. [ABSTRACT FROM AUTHOR]

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 pioneering results obtained by Verghese, Van Dooren and Kailath in 1979-1980, which were the first proving results of this type. 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. [ABSTRACT FROM AUTHOR]

This paper studies generic and perturbation properties inside the linear space of m × (m + n) polynomial matrices whose rows have degrees bounded by a given list d 1 , ... , d m of natural numbers, which in the particular case d 1 = ⋯ = d m = d is just the set of m × (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 [29] only for polynomial matrices with degree at most d. Surprisingly, most of the properties proved in [29] , 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 , ... , d m , and with right minimal indices differing at most by one and having a sum equal to ∑ 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. [ABSTRACT FROM AUTHOR]

Abstract Linearization is a widely used method for solving polynomial eigenproblems in which a matrix polynomial is transformed to a matrix pencil of larger size. Fiedler pencils, generalized Fiedler pencils, Fiedler pencils with repetition (FPRs) and generalized Fiedler pencils with repetition (GFPRs) are well known classes of strong linearizations of matrix polynomials. The class GFPRs is also a rich source of structure-preserving strong linearizations of structured matrix polynomials. The recovery of eigenvectors, minimal bases and minimal indices of matrix polynomials from those of the linearizations is an important task. It is well known that eigenvectors and minimal bases of matrix polynomials can be easily recovered from those of the Fiedler and generalized Fiedler pencils. By contrast, barring a small subclass of FPRs, the recovery of eigenvectors and minimal bases of matrix polynomials from those of the FPRs and GFPRs is still an open problem. The purpose of this paper is to fill this gap. We consider the class of GFPRs, which subsumes the class of FPRs, and describe the recovery of eigenvectors, minimal bases and minimal indices of matrix polynomials from those of the GFPRs and show that the recovery is operation-free. [ABSTRACT FROM AUTHOR]

Abstract Let L = (L 1 , L 2) be a list consisting of a sublist L 1 of powers of irreducible (monic) scalar polynomials over an algebraically closed field F , and a sublist L 2 of nonnegative integers. For an arbitrary such list L , we give easily verifiable necessary and sufficient conditions for L to be the list of elementary divisors and minimal indices of some T-palindromic quadratic matrix polynomial with entries in the field F. For L satisfying these conditions, we show how to explicitly construct a T -palindromic quadratic matrix polynomial having L as its structural data; that is, we provide a T-palindromic quadratic realization of L. 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öbius transformation, we show how all of our results can be easily extended to quadratic matrix polynomials with T -even structure. [ABSTRACT FROM AUTHOR]

The structural data of any rational matrix R(λ), i.e., the structural indices of its poles and zeros together with the minimal indices of its left and right nullspaces, 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 L of prescribed structural data does there exist some rational matrix R(λ) that realizes exactly the list L? We show that Van Dooren's condition is the only constraint on rational realizability; that is, a list L is the structural data of some rational matrix R(λ) if and only if L satisfies the rational index sum condition. [ABSTRACT FROM AUTHOR]

Abstract Let G (λ) be an n × n rational matrix. By considering a minimal realization of G (λ) , Fiedler-like pencils (such as Fiedler pencils, generalized Fiedler pencils and Fiedler pencils with repetition) of G (λ) have been proposed recently which are shown to be linearizations of G (λ). We show that the Fiedler-like pencils allow operation-free recovery of eigenvectors and minimal bases of G (λ) , that is, eigenvectors and minimal bases of G (λ) can be recovered from those of the Fiedler-like pencils of G (λ) without performing any arithmetic operations. Further, we show that the minimal indices of G (λ) can be easily recovered from those of the Fiedler-like pencils of G (λ). We also show that a Fiedler pencil with repetition of G (λ) can be constructed directly from that of a matrix polynomial. [ABSTRACT FROM AUTHOR]

Abstract 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 ℓ -ification of a matrix polynomial, which is a matrix polynomial of degree at most ℓ 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 ℓ -ifications of matrix polynomials of size m × n and grade d when ℓ < d , and ℓ 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 ℓ -ifications can be constructed from the coefficients of a given matrix polynomial P (λ). We also show that these ℓ -ifications satisfy many desirable properties for numerical applications: they are strong ℓ -ifications regardless of whether P (λ) is regular or singular, the minimal indices of the ℓ -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 ℓ -ifications. In the special case where ℓ 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 ℓ -ifications. [ABSTRACT FROM AUTHOR]

The need to solve polynomial eigenvalue problems for matrix polynomials expressed in nonmonomial bases has become very important. Among the most important bases in numerical applications are the Chebyshev polynomials of the first and second kind. In this work, we introduce a new approach for constructing strong linearizations for matrix polynomials expressed in Chebyshev bases, generalizing the classical colleague pencil, and expanding the arena in which to look for linearizations of matrix polynomials expressed in Chebyshev bases. We show that any of these linearizations is a strong linearization regardless of whether the matrix polynomial is regular or singular. In addition, we show how to recover eigenvectors, minimal indices, and minimal bases of the polynomial from those of any of the new linearizations. As an example, we also construct strong linearizations for matrix polynomials of odd degree that are symmetric (resp., Hermitian) whenever the matrix polynomials are symmetric (resp., Hermitian). [ABSTRACT FROM AUTHOR]

Fiedler pencils are a family of strong linearizations for polynomials expressed in the monomial basis, that include the classical Frobenius companion pencils as special cases. We generalize the definition of a Fiedler pencil from monomials to a larger class of orthogonal polynomial bases. In particular, we derive Fiedler-comrade pencils for two bases that are extremely important in practical applications: the Chebyshev polynomials of the first and second kind. The new approach allows one to construct linearizations having limited bandwidth: a Chebyshev analogue of the pentadiagonal Fiedler pencils in the monomial basis. Moreover, our theory allows for linearizations of square matrix polynomials expressed in the Chebyshev basis (and in other bases), regardless of whether the matrix polynomial is regular or singular, and for recovery formulas for eigenvectors, and minimal indices and bases. [ABSTRACT FROM AUTHOR]

We provide an algorithm for constructing strong ℓ -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 ℓ -ification of P ( λ ) is a matrix polynomial of degree ℓ 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 ℓ -ifications introduced so far in the literature have been limited to the case where ℓ 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 ℓ -ifications for wider choices of the degree ℓ , namely, when ℓ divides one of nd or md (and d ≥ ℓ ). In the case where ℓ divides nd (respectively, md ), the strong ℓ -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 ℓ -ification are the ones of P ( λ ) increased by d − ℓ (each). Moreover, in the particular case ℓ divides d , the new method provides a companion ℓ -ification that resembles very much the companion ℓ -ifications already known in the literature. [ABSTRACT FROM AUTHOR]

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 Z 1 ( λ ) k × n and Z 2 ( λ ) m × n , respectively, then Z 1 and Z 2 are 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 Z 1 and Z 2 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. [ABSTRACT FROM AUTHOR]

We discuss Möbius transformations for general matrix polynomials over arbitrary fields, analyzing their influence on regularity, rank, determinant, constructs such as compound matrices, and on structural features including sparsity and symmetry. Results on the preservation of spectral information contained in elementary divisors, partial multiplicity sequences, invariant pairs, and minimal indices are presented. The effect on canonical forms such as Smith forms and local Smith forms, on relationships of strict equivalence and spectral equivalence, and on the property of being a linearization or quadratification are investigated. We show that many important transformations are special instances of Möbius transformations, and analyze a Möbius connection between alternating and palindromic matrix polynomials. Finally, the use of Möbius transformations in solving polynomial inverse eigenproblems is illustrated. [ABSTRACT FROM AUTHOR]

We present necessary and sufficient conditions for the existence of a matrix polynomial when its degree, its finite and infinite elementary divisors, and its left and right minimal indices are prescribed. These conditions hold for arbitrary infinite fields 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 fix the problem of the existence of l-ifications of a given matrix polynomial, as well as to determine all their possible sizes and eigenstructures. [ABSTRACT FROM AUTHOR]

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 ℓ -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 ℓ -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 ℓ -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. [ABSTRACT FROM AUTHOR]

A Lie algebra is called complete if its centre is zero and all its derivations are inner. A nilpotent Lie algebra is called completable if it is the maximal nilpotent ideal of a complete solvable Lie algebra. A two-step nilpotent Lie algebrais said to be of type, if dimand dim. In this paper, based on the classification result of M. Gauger, we classify two step completable complex nilpotent Lie algebras of type. [ABSTRACT FROM PUBLISHER]

Abstract: This is a reconstruction in article-like form of a talk given at the “Minisymposium in Honor of Miroslav Fiedler” at the 17th ILAS Conference, held at TU Braunschweig, Germany, on Thursday 25 August 2011. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: The standard way to solve polynomial eigenvalue problems is to convert the matrix polynomial into a matrix pencil that preserves its spectral information — a process known as linearization. When is palindromic, the eigenvalues, elementary divisors, and minimal indices of 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 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 which are palindromic whenever 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. [Copyright &y& Elsevier]

Abstract: This paper studies the Turing degrees of various properties defined for universal numberings, that is, for numberings which list all partial-recursive functions. In particular properties relating to the domain of the corresponding functions are investigated like the set DEQ of all pairs of indices of functions with the same domain, the set DMIN of all minimal indices of sets and DMIN⁎ of all indices which are minimal with respect to equality of the domain modulo finitely many differences. A partial solution to a question of Schaefer is obtained by showing that for every universal numbering with the Kolmogorov property, the set DMIN⁎ is Turing equivalent to the double jump of the halting problem. Furthermore, it is shown that the join of DEQ and the halting problem is Turing equivalent to the jump of the halting problem and that there are numberings for which DEQ itself has 1-generic Turing degree. [Copyright &y& Elsevier]

A standard way to solve polynomial eigenvalue problems P(kλ)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 definition of linearization does not imply the existence of simple relationships between the eigenvectors, minimal indices, and minimal bases of P(λ) and those of the linearization. So, given a class of linearizations, to provide easy recovery procedures for eigenvectors, minimal indices, and minimal bases of P(λ) from those of the linearizations is essential for the usefulness of this class. In this paper we develop such recovery procedures for generalized Fiedler linearizations and pay special attention to structure-preserving linearizations inside this class. [ABSTRACT FROM AUTHOR]

A standard way of dealing with a matrix polynomial P(λ) 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(λ) 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(λ) 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. [ABSTRACT FROM AUTHOR]

Abstract: We study generalizations of shortest programs as they pertain to Schaefer’s problem. We identify sets of -minimal and -minimal indices and characterize their truth-table and Turing degrees. In particular, we show , , and that there exists a Kolmogorov numbering satisfying both and . This Kolmogorov numbering also achieves maximal truth-table degree for other sets of minimal indices. Finally, we show that the set of shortest descriptions, , is 2-c.e. but not co-2-c.e. Some open problems are left for the reader. [Copyright &y& Elsevier]

The main purpose of this work is to determine the forward and backward solution space of a nonregular discrete time AR-representation i.e. A(σ)ξ(k)=0, in a finite time horizon where A(σ) is a polynomial matrix and σ is the forward shift operator. The construction of the behavior is based on the structural invariants of the polynomial matrix that describes the AR-representation i.e. the finite and infinite elementary divisors and the right and left minimal indices of A(σ). [Copyright &y& Elsevier]