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.     

On backward errors of structured polynomial eigenproblems solved by structure preserving linearizations

We derive explicit computable expressions of structured backward errors of approximate eigenelements of structured matrix polynomials including symmetric, skew-symmetric, Hermitian, skew-Hermitian, even and odd polynomials. We determine minimal structured perturbations for which approximate eigenelements are exact eigenelements of the perturbed polynomials. We also analyze structured pseudospectra of a structured matrix polynomial and establish a partial equality between unstructured and structured pseudospectra. Finally, we analyze the effect of structure preserving linearizations of structured matrix polynomials on the structured backward errors of approximate eigenelements and show that structure preserving linearizations which minimize structured condition numbers of eigenvalues also minimize the structured backward errors of approximate eigenelements.     

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.     

Pseudospectra of Matrix Polynomials that Are Expressed in Alternative Bases

Spectra and pseudospectra of matrix polynomials are of interest in geometric intersection problems, vibration problems, and analysis of dynamical systems. In this note we consider the effect of the choice of polynomial basis on the pseudospectrum and on the conditioning of the spectrum of regular matrix polynomials. In particular, we consider the direct use of the Lagrange basis on distinct interpolation nodes, and give a geometric characterization of “good” nodes. We also give some tools for computation of roots at infinity via a new, natural, reversal. The principal achievement of the paper is to connect pseudospectra to the well-established theory of Lebesgue functions and Lebesgue constants, by separating the influence of the scalar basis from the natural scale of the matrix polynomial, which allows many results from interpolation theory to be applied. This work was partially funded by the Natural Sciences and Engineering Research Council of Canada, and by the MITACS Network of Centres of Excellence.     

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.     

Local convergence analysis of iterative aggregation-disaggregation methods with polynomial correction

The paper introduces some new results on local convergence analysis of one class of iterative aggregation-disaggregation methods for computing a stationary probability distribution vector of an irreducible stochastic matrix. We focus on methods, where the basic iteration on the fine level corresponds to a multiplication by a polynomial of order one with nonnegative coefficients in the original matrix. We show that this process is locally convergent for matrices with positive diagonals or when the coefficients of the polynomial are positive. On the other hand there are examples for which the process may diverge in a local sense for higher degree polynomials even if it converges for a polynomial of a lower degree for the same matrix.     

Generalized even and odd totally positive matrices

A generalization of the definition of an oscillatory matrix based on the theory of cones is given in this paper. The positivity and simplicity of all the eigenvalues of a generalized oscillatory matrix are proved. Classes of generalized even and odd oscillatory matrices are introduced. Spectral properties of the obtained matrices are studied. Criteria of generalized even and odd oscillation are given. Examples of generalized even and odd oscillatory matrices are presented.     

Generalized Jacobi–Trudi determinants and evaluations of Schur multiple zeta values

We present new determinant expressions for regularized Schur multiple zeta values. These generalize the known Jacobi–Trudi formulas and can be used to quickly evaluate certain types of Schur multiple zeta values. Using these formulas we prove that every Schur multiple zeta value with alternating entries in 1 and 3 can be written as a polynomial in Riemann zeta values. Furthermore, we give conditions on the shape, which determine when such Schur multiple zetas are polynomials purely in odd or in even Riemann zeta values.     

A new type of Hermite matrix polynomial series

Conventional Hermite polynomials emerge in a great diversity of applications in mathematical physics, engineering, and related fields. However, in physical systems with higher degrees of freedom it will be of practical interest to extend the scalar Hermite functions to their matrix analogue. This work introduces various new generating functions for Hermite matrix polynomials and examines existence and convergence of their associated series expansion by using Mehler’s formula for the general matrix case. Moreover, we derive interesting new relations for even- and odd-power summation in the generating-function expansion containing Hermite matrix polynomials. Some new results for the scalar case are also presented.     

Hermite interpolation with trigonometric polynomials

Interpolation methods of Hermite type in translation invariant spaces of trigonometric polynomials for any position of interpolation points and any number of derivatives are constructed. For the case of an odd number of interpolation conditions-periodic trigonometric polynomials of minimum order are chosen as interpolation functions while for the case of an even number of interpolation conditions-antiperiodic trigonometric polynomials of minimum order are appropriate.     

Perturbations on the subdiagonals of Toeplitz matrices

Let L be an Hermitian linear functional defined on the linear space of Laurent polynomials. It is very well known that the Gram matrix of the associated bilinear functional in the linear space of polynomials is a Toeplitz matrix. In this contribution we analyze some linear spectral transforms of L such that the corresponding Toeplitz matrix is the result of the addition of a constant in a subdiagonal of the initial Toeplitz matrix. We focus our attention in the analysis of the quasi-definite character of the perturbed linear functional as well as in the explicit expressions of the new monic orthogonal polynomial sequence in terms of the first one.     

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.     

Matrix polynomials satisfying first order differential equations and three term recurrence relations

We describe families of matrix valued polynomials satisfying simultaneously a first order differential equation and a three term recurrence relation. Our goal is to address the classification of the matrix valued polynomials satisfying first order differential equations through the solutions of the so-called bispectral problem. At the heart of this lies the need to solve some complicated nonlinear equations with matrix coefficients called ad-conditions. The solutions of these equations are studied under a variety of sufficient conditions on its coefficients.     

Pseudospectra, critical points and multiple eigenvalues of matrix polynomials

We develop a general framework for perturbation analysis of matrix polynomials. More specifically, we show that the normed linear space L_m(C^n×n) of n-by-n matrix polynomials of degree at most m provides a natural framework for perturbation analysis of matrix polynomials in L_m(C^n×n). We present a family of natural norms on the space L_m(C^n×n) and show that the norms on the spaces C^m+1 and C^n×n play a crucial role in the perturbation analysis of matrix polynomials. We define pseudospectra of matrix polynomials in the general framework of the normed space L_m(C^n×n) and show that the pseudospectra of matrix polynomials well known in the literature follow as special cases. We analyze various properties of pseudospectra in the unified framework of the normed space L_m(C^n×n). We analyze critical points of backward errors of approximate eigenvalues of matrix polynomials and show that each critical point is a multiple eigenvalue of an appropriately perturbed polynomial. We show that common boundary points of components of pseudospectra of matrix polynomials are critical points. As a consequence, we show that a solution of Wilkinson’s problem for matrix polynomials can be read off from the pseudospectra of matrix polynomials.     

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.     

Bounds for resultants of univariate and bivariate polynomials

The paper considers bounds on the size of the resultant for univariate and bivariate polynomials. For univariate polynomials we also extend the traditional representation of the resultant by the zeros of the argument polynomials to formal resultants, defined as the determinants of the Sylvester matrix for a pair of polynomials whose actual degree may be lower than their formal degree due to vanishing leading coefficients. For bivariate polynomials, the resultant is a univariate polynomial resulting by the elimination of one of the variables, and our main result is a bound on the largest coefficient of this univariate polynomial. We bring a simple example that shows that our bound is attainable and that a previous sharper bound is not correct.     

On an equation with dihedral Galois group

An earlier result of the author is applied to the inverse Galois problem for the dihedral group of odd order. The solution is given in the form of a polynomial in one variable. A completeness theorem holds for this polynomial; this means that any solution is determined by such a polynomial. Under natural assumptions concerning the ground field, necessary and sufficient conditions of irreducibility of these polynomials are given and some properties of these polynomials are proved. The problem of classification of cubic irrationalities with respect to the Tchirngausen transformations is completely solved. Bibliography: 5 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 227, 1995, pp. 119–124.     

Oversampling and reconstruction functions with compact support

Assume that a sequence of samples of a filtered version of a function in a shift-invariant space is given. This paper deals with the existence of a sampling formula involving these samples and having reconstruction functions with compact support. This is done in the light of the generalized sampling theory by using the oversampling technique. A necessary and sufficient condition is given in terms of the Smith canonical form of a polynomial matrix. Finally, we prove that the aforesaid oversampled formulas provide nice approximation schemes with respect to the uniform norm.     

Commutative presemifields and semifields

Strong conditions are derived for when two commutative presemifields are isotopic. It is then shown that any commutative presemifield of odd order can be described by a planar Dembowski-Ostrom polynomial and conversely, any planar Dembowski-Ostrom polynomial describes a commutative presemifield of odd order. These results allow a classification of all planar functions which describe presemifields isotopic to a finite field and of all planar functions which describe presemifields isotopic to Albert's commutative twisted fields. A classification of all planar Dembowski-Ostrom polynomials over any finite field of order p³, p an odd prime, is therefore obtained. The general theory developed in the article is then used to show the class of planar polynomials X¹⁰+aX⁶−a²X² with a≠0 describes precisely two new commutative presemifields of order e³ for each odd e?5.     

A bivariate Markov inequality for Chebyshev polynomials of the second kind

This note presents a Markov-type inequality for polynomials in two variables where the Chebyshev polynomials of the second kind in either one of the variables are extremal. We assume a bound on a polynomial at the set of even or odd Chebyshev nodes with the boundary nodes omitted and obtain bounds on its even or odd order directional derivatives in a critical direction. Previously, the author has given a corresponding inequality for Chebyshev polynomials of the first kind and has obtained the extension of V.A. Markov’s theorem to real normed linear spaces as an easy corollary.To prove our inequality we construct Lagrange polynomials for the new class of nodes we consider and give a corresponding Christoffel–Darboux formula. It is enough to determine the sign of the directional derivatives of the Lagrange polynomials.