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.

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

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

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

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.

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.

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.

We study generalizations of shortest programs as they pertain to Schaefer’s MIN ∗ problem. We identify sets of m -minimal and T -minimal indices and characterize their truth-table and Turing degrees. In particular, we show MIN m ⊕ 0 ″ ≡ T 0 ‴ , MIN T ( n ) ⊕ 0 ( n + 2 ) ≡ T 0 ( n + 4 ) , and that there exists a Kolmogorov numbering ψ satisfying both MIN ψ m ≡ tt 0 ‴ and MIN ψ T ( n ) ≡ T 0 ( n + 4 ) . This Kolmogorov numbering also achieves maximal truth-table degree for other sets of minimal indices. Finally, we show that the set of shortest descriptions, SD , is 2-c.e. but not co-2-c.e. Some open problems are left for the reader.

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

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.

We present two complementary condensed forms of linear control system with output x =A·x+B·u, x∈ R n , u∈ R m ,y=C·x, y∈ R r under transformation of the state coordinates. From them we derive two complementary condensed forms under output feedback. As an application of the condensed forms, we show that the output feedback control of the linear control systems generically reduces to a matrix completion problem, and we provide a partial solution of that problem, based on existing methods.