A generalization of the inertia theorem for quadratic matrix polynomials

We show that the inertia of a quadratic matrix polynomial is determined in terms of the inertia of its coefficient matrices if the leading coefficient is Hermitian and nonsingular, the constant term is Hermitian, and the real part of the coefficient matrix of the first degree term is definite. In particular, we prove that the number of zero eigenvalues of such a matrix polynomial is the same as the number of zero eigenvalues of its constant term. We also give some new results for the case where the real part of the coefficient matrix of the first degree term is semidefinite.     

Spectral factorization of non-symmetric polynomial matrices

The topic of the paper is spectral factorization of rectangular and possibly non-full-rank polynomial matrices. To each polynomial matrix we associate a matrix pencil by direct assignment of the coefficients. The associated matrix pencil has its finite generalized eigenvalues equal to the zeros of the polynomial matrix. The matrix dimensions of the pencil we obtain by solving an integer linear programming (ILP) minimization problem. Then by extracting a deflating subspace of the pencil we come to the required spectral factorization. We apply the algorithm to most general-case of inner–outer factorization, regardless continuous or discrete time case, and to finding the greatest common divisor of polynomial matrices.     

Instability indices for matrix polynomials

There is a well-established instability index theory for linear and quadratic matrix polynomials for which the coefficient matrices are Hermitian and skew-Hermitian. This theory relates the number of negative directions for the matrix coefficients which are Hermitian to the total number of unstable eigenvalues for the polynomial. Herein we extend the theory to ?-even matrix polynomials of any finite degree. In particular, unlike previously known cases we show that the instability index depends upon the size of the matrices when the degree of the polynomial is greater than two. We also consider Hermitian matrix polynomials, and derive an index which counts the number of eigenvalues with nonpositive imaginary part. The results are refined if we consider the Hermitian matrix polynomial to be a perturbation of a ?-even polynomials; however, this refinement requires additional assumptions on the matrix coefficients.     

Greatest common divisor of generalized polynomials and polynomial matrices

The comrade matrix was introduced recently as the analogue of the companion matrix when a polynomial is expressed in terms of a basis set of orthogonal polynomials. It is now shown how previous results on determining the greatest common divisor of two or more polynomials can be extended to the case of generalized polynomials using the comrade form. Furthermore, a block comrade matrix is defined, and this is used to extend to the generalized case another previous result on the regular greatest common divisor of two polynomial matrices.     

利用矩阵的初等变换求方阵的特征值

高阶方阵的特征多项式以及特征值的求得,在计算上往往有一定的难度.本文首先从理论上分析了存在一个上三角矩阵或者下三角矩阵与一个方阵相似;接着,提出了相似变换的概念,分析了相似变换中初等矩阵的选择方法;然后指出了利用相似变换在求方阵的特征多项式以及特征值时的方法,并列举若干实例给予了说明.     

Spectral problem for polynomial matrix pencils. 2

For an arbitrary polynomial pencil of matrices A_i of dimensions m×n one presents an algorithm for the computation of the eigenvalues of the regular kernel of the pencil. The algorithm allows to construct a regular pencil having the same eigenvalues as the regular kernel of the initial pencil or (in the case of a dead end termination) allows to pass from the initial pencil to a pencil of smaller dimensions whose regular kernel has the same eigenvalues as the initial pencil. The problem is solved by reducing the obtained pencil to a linear one. For solving the problem in the case of a linear pencil one considers algorithms for pencils of full column rank as well as for completely singular pencils.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 111, pp. 109–116, 1981.     

Detecting hyperbolic and definite matrix polynomials

Hyperbolic or more generally definite matrix polynomials are important classes of Hermitian matrix polynomials. They allow for a definite linearization and can therefore be solved by a standard algorithm for Hermitian matrices. They have only real eigenvalues which can be characterized as minmax and maxmin values of Rayleigh functionals, but there is no easy way to test if a given polynomial is hyperbolic or definite or not. Taking advantage of the safeguarded iteration which converges globally and monotonically to extreme eigenvalues we obtain an efficient algorithm that identifies hyperbolic or definite polynomials and enables the transformation to an equivalent definite linear pencil. Numerical examples demonstrate the efficiency of the approach.     

To solving problems of algebra for two-parameter matrices. III

The paper continues the series of papers devoted to surveying and developing methods for solving algebraic problems for two-parameter polynomial and rational matrices of general form. It considers linearization methods, which allow one to reduce the problem of solving an equation F(λ, μ)x = 0 with a polynomial two-parameter matrix F(λ, μ) to solving an equation of the form D(λ, μ)y = 0, where D(λ, μ) = A(μ)-λB(μ) is a pencil of polynomial matrices. Consistent pencils and their application to solving spectral problems for the matrix F(λ, μ) are discussed. The notion of reducing subspace is generalized to the case of a pencil of polynomial matrices. An algorithm for transforming a general pencil of polynomial matrices to a quasitriangular pencil is suggested. For a pencil with multiple eigenvalues, algorithms for computing the Jordan chains of vectors are developed. Bibliography: 8 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 359, 2008, pp. 166–207.     

Skew-prime polynomial matrices: The polynomial-model approach

We examine the concept of skew-primeness of polynomial matrices in terms of the associated polynomial model. It is shown that skew-primeness can be characterized in terms of the property of decomposition of a vector space relative to an endomorphism. This basic result is then applied to the special case of nonsingular polynomial matrices. We investigate the nonuniqueness of skew-complements of a skew-prime pair. It is shown that the space of equivalence classes of skew-complements is in bijective correspondence with a finite-dimensional linear space. Finally, the equivalence of the solutions to the problem of output regulation with internal stability obtained via geometric methods and via polynomial matrix techniques is shown explicitly.     

Localization of eigenvalues of polynomial matrices

We consider the problem of localization of eigenvalues of polynomial matrices. We propose sufficient conditions for the spectrum of a regular matrix polynomial to belong to a broad class of domains bounded by algebraic curves. These conditions generalize the known method for the localization of the spectrum of polynomial matrices based on the solution of linear matrix inequalities. We also develop a method for the localization of eigenvalues of a parametric family of matrix polynomials in the form of a system of linear matrix inequalities.     

Algebraic Properties of Subdivision Operators with Matrix Mask and Their Applications

Subdivision operators play an important role in wavelet analysis. This paper studies the algebraic properties of subdivision operators with matrix mask, especially their action on polynomial sequences and on some of their invariant subspaces. As an application, we characterize, under a mild condition, the approximation order provided by refinable vectors in terms of the eigenvalues and eigenvectors of polynomial sequences of the associated subdivision operator. Moreover, some necessary conditions, in terms of nondegeneracy and simplicity of eigenvalues of a matrix related to the subdivision operator for the refinable vector to be smooth are given. The main results are new even in the scalar case     

Pseudozeros of polynomials and pseudospectra of companion matrices

Summary. It is well known that the zeros of a polynomial are equal to the eigenvalues of the associated companion matrix . In this paper we take a geometric view of the conditioning of these two problems and of the stability of algorithms for polynomial zerofinding. The is the set of zeros of all polynomials obtained by coefficientwise perturbations of of size ; this is a subset of the complex plane considered earlier by Mosier, and is bounded by a certain generalized lemniscate. The is another subset of defined as the set of eigenvalues of matrices with ; it is bounded by a level curve of the resolvent of $A$. We find that if $A$ is first balanced in the usual EISPACK sense, then and are usually quite close to one another. It follows that the Matlab ROOTS algorithm of balancing the companion matrix, then computing its eigenvalues, is a stable algorithm for polynomial zerofinding. Experimental comparisons with the Jenkins-Traub (IMSL) and Madsen-Reid (Harwell) Fortran codes confirm that these three algorithms have roughly similar stability properties. Received June 15, 1993     

Average case tractability of non-homogeneous tensor product problems with the absolute error criterion

We study average case tractability of non-homogeneous tensor product problems with the absolute error criterion. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. For general non-homogeneous tensor product problems, we obtain the matching necessary and sufficient conditions for strong polynomial tractability in terms of the one-dimensional eigenvalues. We give some examples to show that strong polynomial tractability is not equivalent to polynomial tractability, and polynomial tractability is not equivalent to quasi-polynomial tractability. But for non-homogeneous tensor product problems with decreasing eigenvalues, we prove that strong polynomial tractability is always equivalent to polynomial tractability, and strong polynomial tractability is even equivalent to quasi-polynomial tractability when the one-dimensional largest eigenvalues are less than one. In particular, we find an example that quasi-polynomial tractability with the absolute error criterion is not equivalent to that with the normalized error criterion even if all the one-dimensional largest eigenvalues are one. Finally we consider a special class of non-homogeneous tensor product problems with improved monotonicity condition of the eigenvalues.     

Sufficient embedding conditions for three-state discrete-time Markov chains with real eigenvalues

Within the set of discrete-time Markov chains, a Markov chain is embeddable in case its transition matrix has at least one root that is a stochastic matrix. The present paper examines the embedding problem for discrete-time Markov chains with three states and with real eigenvalues. Sufficient embedding conditions are proved for diagonalizable transition matrices as well as for non-diagonalizable transition matrices and for all possible configurations regarding the sign of the eigenvalues. The embedding conditions are formulated in terms of the projections and the spectral decomposition of the transition matrix.     

Matrices and spectra satisfying the Newton inequalities

An n-by-n real matrix is called a Newton matrix (and its eigenvalues a Newton spectrum) if the normalized coefficients of its characteristic polynomial satisfy the Newton inequalities.A number of basic observations are made about Newton matrices, including closure under inversion, and then it is shown that a Newton matrix with nonnegative coefficients remains Newton under right translations. Those matrices that become (and stay) Newton under translation are characterized. In particular, Newton spectra in low dimensions are characterized.     

Hermitian matrix polynomials with real eigenvalues of definite type. Part I: Classification

The spectral properties of Hermitian matrix polynomials with real eigenvalues have been extensively studied, through classes such as the definite or definitizable pencils, definite, hyperbolic, or quasihyperbolic matrix polynomials, and overdamped or gyroscopically stabilized quadratics. We give a unified treatment of these and related classes that uses the eigenvalue type (or sign characteristic) as a common thread. Equivalent conditions are given for each class in a consistent format. We show that these classes form a hierarchy, all of which are contained in the new class of quasidefinite matrix polynomials. As well as collecting and unifying existing results, we make several new contributions. We propose a new characterization of hyperbolicity in terms of the distribution of the eigenvalue types on the real line. By analyzing their effect on eigenvalue type, we show that homogeneous rotations allow results for matrix polynomials with nonsingular or definite leading coefficient to be translated into results with no such requirement on the leading coefficient, which is important for treating definite and quasidefinite polynomials. We also give a sufficient and necessary condition for a quasihyperbolic matrix polynomial to be strictly isospectral to a real diagonal quasihyperbolic matrix polynomial of the same degree, and show that this condition is always satisfied in the quadratic case and for any hyperbolic matrix polynomial, thereby identifying an important new class of diagonalizable matrix polynomials.     

Generalized qd algorithm for block band matrices

The generalized qd algorithm for block band matrices is an extension of the block qd algorithm applied to a block tridiagonal matrix. This algorithm is applied to a positive definite symmetric block band matrix. The result concerning the behavior of the eigenvalues of the first and the last diagonal block of the matrix containing the entries q ^(k) which was obtained in the tridiagonal case is still valid for positive definite symmetric block band matrices. The eigenvalues of the first block constitute strictly increasing sequences and those of the last block constitute strictly decreasing sequences. The theorem of convergence, given in Draux and Sadik (Appl Numer Math 60:1300?C1308, 2010), also remains valid in this more general case.     

Polynomial functions on upper triangular matrix algebras

There are two kinds of polynomial functions on matrix algebras over commutative rings: those induced by polynomials with coefficients in the algebra itself and those induced by polynomials with scalar coefficients. In the case of algebras of upper triangular matrices over a commutative ring, we characterize the former in terms of the latter (which are easier to handle because of substitution homomorphism). We conclude that the set of integer-valued polynomials with matrix coefficients on an algebra of upper triangular matrices is a ring, and that the set of null-polynomials with matrix coefficients on an algebra of upper triangular matrices is an ideal.     

Perturbation theory of selfadjoint matrices and sign characteristics under generic structured rank one perturbations

For selfadjoint matrices in an indefinite inner product, possible canonical forms are identified that arise when the matrix is subjected to a selfadjoint generic rank one perturbation. Genericity is understood in the sense of algebraic geometry. Special attention is paid to the perturbation behavior of the sign characteristic. Typically, under such a perturbation, for every given eigenvalue, the largest Jordan block of the eigenvalue is destroyed and (in case the eigenvalue is real) all other Jordan blocks keep their sign characteristic. The new eigenvalues, i.e. those eigenvalues of the perturbed matrix that are not eigenvalues of the original matrix, are typically simple, and in some cases information is provided about their sign characteristic (if the new eigenvalue is real). The main results are proved by using the well known canonical forms of selfadjoint matrices in an indefinite inner product, a version of the Brunovsky canonical form and on general results concerning rank one perturbations obtained.     

Characteristic polynomials of sample covariance matrices: The non-square case

We consider the sample covariance matrices of large data matrices which have i.i.d. complex matrix entries and which are non-square in the sense that the difference between the number of rows and the number of columns tends to infinity. We show that the second-order correlation function of the characteristic polynomial of the sample covariance matrix is asymptotically given by the sine kernel in the bulk of the spectrum and by the Airy kernel at the edge of the spectrum. Similar results are given for real sample covariance matrices.