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.     

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.     

On condition numbers of polynomial eigenvalue problems

In this paper, we investigate condition numbers of eigenvalue problems of matrix polynomials with nonsingular leading coefficients, generalizing classical results of matrix perturbation theory. We provide a relation between the condition numbers of eigenvalues and the pseudospectral growth rate. We obtain that if a simple eigenvalue of a matrix polynomial is ill-conditioned in some respects, then it is close to be multiple, and we construct an upper bound for this distance (measured in the euclidean norm). We also derive a new expression for the condition number of a simple eigenvalue, which does not involve eigenvectors. Moreover, an Elsner-like perturbation bound for matrix polynomials is presented.     

Fiedler companion linearizations for rectangular matrix polynomials

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.     

Matrix orthogonal polynomials whose derivatives are also orthogonal

In this paper we prove some characterizations of the matrix orthogonal polynomials whose derivatives are also orthogonal, which generalize other known ones in the scalar case. In particular, we prove that the corresponding orthogonality matrix functional is characterized by a Pearson-type equation with two matrix polynomials of degree not greater than 2 and 1. The proofs are given for a general sequence of matrix orthogonal polynomials, not necessarily associated with a hermitian functional. We give several examples of non-diagonalizable positive definite weight matrices satisfying a Pearson-type equation, which show that the previous results are non-trivial even in the positive definite case.A detailed analysis is made for the class of matrix functionals which satisfy a Pearson-type equation whose polynomial of degree not greater than 2 is scalar. We characterize the Pearson-type equations of this kind that yield a sequence of matrix orthogonal polynomials, and we prove that these matrix orthogonal polynomials satisfy a second order differential equation even in the non-hermitian case. Finally, we prove and improve a conjecture of Durán and Grünbaum concerning the triviality of this class in the positive definite case, while some examples show the non-triviality for hermitian functionals which are not positive definite.     

Zeros of Polynomials on Banach Spaces: The Real Story

Let E be a real Banach space. We show that either E admits a positive definite 2-homogeneous polynomial or every 2-homogeneous polynomial on E has an infinite dimensional subspace on which it is identically zero. Under addition assumptions, we show that such subspaces are non-separable. We examine analogous results for nuclear and absolutely (1,2)-summing 2-homogeneous polynomials and give necessary and sufficient conditions on a compact set K so that C(K) admits a positive definite 2-homogeneous polynomial or a positive definite nuclear 2-homogeneous polynomial.     

Theorems of the Alternative for Inequality Systems of Real Polynomials

In this paper, we establish theorems of the alternative for inequality systems of real polynomials. For the real quadratic inequality system, we present two new results on the matrix decomposition, by which we establish two theorems of the alternative for the inequality system of three quadratic polynomials under an assumption that at least one of the involved forms be negative semidefinite. We also extend a theorem of the alternative to the case with a regular cone. For the inequality system of higher degree real polynomials, defined by even order tensors, a theorem of the alternative for the inequality system of two higher degree polynomials is established under suitable assumptions. As a byproduct, we give an equivalence result between two statements involving two higher degree polynomials. Based on this result, we investigate the optimality condition of a class of polynomial optimization problems under suitable assumptions.     

Determinantal representations and Bézoutians

A major open question in convex algebraic geometry is whether all hyperbolicity cones are spectrahedral, i.e. the solution sets of linear matrix inequalities. We will use sum-of-squares decompositions of certain bilinear forms called Bézoutians to approach this problem. More precisely, we show that for every smooth hyperbolic polynomial h there is another hyperbolic polynomial q such that \(q \cdot h\) has a definite determinantal representation. Besides commutative algebra, the proof relies on results from real algebraic geometry.     

The condition number of real Vandermonde, Krylov and positive definite Hankel matrices

Summary. We show that the Euclidean condition number of any positive definite Hankel matrix of order may be bounded from below by with , and that this bound may be improved at most by a factor . Similar estimates are given for the class of real Vandermonde matrices, the class of row-scaled real Vandermonde matrices, and the class of Krylov matrices with Hermitian argument. Improved bounds are derived for the case where the abscissae or eigenvalues are included in a given real interval. Our findings confirm that all such matrices – including for instance the famous Hilbert matrix – are ill-conditioned already for “moderate” order. As application, we describe implications of our results for the numerical condition of various tasks in Numerical Analysis such as polynomial and rational i nterpolation at real nodes, determination of real roots of polynomials, computation of coefficients of orthogonal polynomials, or the iterative solution of linear systems of equations. Received December 1, 1997 / Revised version received February 25, 1999 / Published online 16 March 2000     

Inertia‐based spectrum slicing for symmetric quadratic eigenvalue problems

In the quadratic eigenvalue problem (QEP) with all coefficient matrices symmetric, there can be complex eigenvalues. However, some applications need to compute real eigenvalues only. We propose a Lanczos‐based method for computing all real eigenvalues contained in a given interval of large‐scale symmetric QEPs. The method uses matrix inertias of the quadratic polynomial evaluated at different shift values. In this way, for hyperbolic problems, it is possible to make sure that all eigenvalues in the interval have been computed. We also discuss the general nonhyperbolic case. Our implementation is memory‐efficient by representing the computed pseudo‐Lanczos basis in a compact tensor product representation. We show results of computational experiments with a parallel implementation in the SLEPc library.     

Structured eigenvalue condition numbers and linearizations for matrix polynomials

This work is concerned with eigenvalue problems for structured matrix polynomials, including complex symmetric, Hermitian, even, odd, palindromic, and anti-palindromic matrix polynomials. Most numerical approaches to solving such eigenvalue problems proceed by linearizing the matrix polynomial into a matrix pencil of larger size. Recently, linearizations have been classified for which the pencil reflects the structure of the original polynomial. A question of practical importance is whether this process of linearization significantly increases the eigenvalue sensitivity with respect to structured perturbations. For all structures under consideration, we show that this cannot happen if the matrix polynomial is well scaled: there is always a structured linearization for which the structured eigenvalue condition number does not differ much. This implies, for example, that a structure-preserving algorithm applied to the linearization fully benefits from a potentially low structured eigenvalue condition number of the original matrix polynomial.     

Relative asymptotics for orthogonal matrix polynomials

In this paper we study sequences of matrix polynomials that satisfy a non-symmetric recurrence relation. To study this kind of sequences we use a vector interpretation of the matrix orthogonality. In the context of these sequences of matrix polynomials we introduce the concept of the generalized matrix Nevai class and we give the ratio asymptotics between two consecutive polynomials belonging to this class. We study the generalized matrix Chebyshev polynomials and we deduce its explicit expression as well as we show some illustrative examples. The concept of a Dirac delta functional is introduced. We show how the vector model that includes a Dirac delta functional is a representation of a discrete Sobolev inner product. It also allows to reinterpret such perturbations in the usual matrix Nevai class. Finally, the relative asymptotics between a polynomial in the generalized matrix Nevai class and a polynomial that is orthogonal to a modification of the corresponding matrix measure by the addition of a Dirac delta functional is deduced.     

Spectral properties of matrix polynomials in the max algebra

We consider the spectral properties of matrix polynomials over the max algebra. In particular, we show how the Perron-Frobenius theorem for the max algebra extends to such polynomials and illustrate the relevance of this for multistep difference equations in the max algebra. We also present a number of inequalities for the largest max eigenvalue of a matrix polynomial.     

A note on biorthogonal ensembles

We study multiple orthogonal polynomials in the context of biorthogonal ensembles of random matrices. In these ensembles, the eigenvalue probability density function factorizes into a product of two determinants while the eigenvalue correlation functions can be written as a determinant of a kernel function. We show that the kernel is itself an average of a single ratio of characteristic polynomials. In the same vein, we prove that the type I multiple polynomials can be expressed as an average of the inverse of a characteristic polynomial. We finally introduce a new biorthogonal matrix ensemble, namely the chiral unitary perturbed by a source term, whose multiple polynomials are related to the modified Bessel function of the first kind.     

A fitting algorithm for real coefficient polynomial rooting

A new algorithm for computing all roots of polynomials with real coefficients is introduced. The principle behind the new algorithm is a fitting of the convolution of two subsequences onto a given polynomial coefficient sequence. This concept is used in the initial stage of the algorithm for a recursive slicing of a given polynomial into degree-2 subpolynomials from which initial root estimates are computed in closed form. This concept is further used in a post-fitting stage where the initial root estimates are refined to high numerical accuracy. A reduction of absolute root errors by a factor of 100 compared to the famous Companion matrix eigenvalue method based on the unsymmetric QR algorithm is not uncommon. Detailed computer experiments validate our claims.     

On some classes of polynomials with nonnegative coefficients and a given factor

For a given real polynomial f without positive roots we study polynomials g of lowest degree such that the product gf has positive (nonnegative, respectively) coefficients. We show that for quadratic f with negative linear coefficient every such g must have positive coefficients and exhibit an easy procedure for the determination of g. If f has only integer coefficients we show that g with integer coefficients can be found. Furthermore, for some classes of polynomials f we give upper (lower, respectively) bounds for the degrees of g.     

Trimmed linearizations for structured matrix polynomials

We discuss the eigenvalue problem for general and structured matrix polynomials which may be singular and may have eigenvalues at infinity. We derive condensed forms that allow (partial) deflation of the infinite eigenvalue and singular structure of the matrix polynomial. The remaining reduced order staircase form leads to new types of linearizations which determine the finite eigenvalues and corresponding eigenvectors. The new linearizations also simplify the construction of structure preserving linearizations.     

Backward errors for eigenvalues and eigenvectors of Hermitian,skew-Hermitian,H-even and H-odd matrix polynomials

We discuss the perturbation analysis for eigenvalues and eigenvectors of structured homogeneous matrix polynomials with Hermitian, skew-Hermitian, H-even and H-odd structure. We construct minimal structured perturbations (structured backward errors) such that an approximate eigenvalue and eigenvector pair (finite or infinite eigenvalues) is an exact eigenvalue eigenvector pair of an appropriately perturbed structured matrix polynomial. We present various comparisons with unstructured backward errors and previous backward errors constructed for the non-homogeneous case and show that our results generalize previous results.     

关于合成矩阵的正定性

利用标准形分别给出了复正定矩阵的合成矩阵为复正定矩阵和实正定矩阵的合成矩阵为实正定矩阵的充分必要条件,其结果简单而实用.     

Homogeneous polynomials and extensions of Hardy‐Hilbert's inequality

If L is a continuous symmetric n‐linear form on a real or complex Hilbert space and $\widehat{L}$ is the associated continuous n‐homogeneous polynomial, then $\Vert L\Vert =\big \Vert \widehat{L}\big \Vert$. We give a simple proof of this well‐known result, which works for both real and complex Hilbert spaces, by using a classical inequality due to S. Bernstein for trigonometric polynomials. As an application, an open problem for the optimal lower bound of the norm of a homogeneous polynomial, which is a product of linear forms, is related to the so‐called permanent function of an n × n positive definite Hermitian matrix. We have also derived generalizations of Hardy‐Hilbert's inequality.