REPRINT OF: A quasiseparable approach to five-diagonal CMV and Fiedler matrices

Recent work in the characterization of structured matrices in terms of characteristic polynomials of principal submatrices is furthered in this paper. Some classical classes of matrices with quasiseparable structure include tridiagonal (related to real orthogonal polynomials) and banded matrices, unitary Hessenberg matrices (related to Szegö polynomials), and semiseparable matrices, as well as others. Hence working with the class of quasiseparable matrices provides new results which generalize and unify classical results.Previous work has focused on characterizing (H,1)-quasiseparable matrices, matrices with order-one quasiseparable structure that are also upper Hessenberg. In this paper, the authors introduce the concept of a twist transformation, and use such transformations to explain the relationship between (H,1)-quasiseparable matrices and the subclass of (1,1)-quasiseparable matrices (without the upper Hessenberg restriction) which are related to the same systems of polynomials. These results generalize the discoveries of Cantero, Fiedler, Kimura, Moral and Velázquez of five-diagonal matrices related to Horner and Szegö polynomials in the context of quasiseparable matrices.     

Green’s matrices

Our goal is to identify and understand matrices A that share essential properties of the unitary Hessenberg matrices M that are fundamental for Szegö’s orthogonal polynomials. Those properties include: (i) Recurrence relations connect characteristic polynomials {r_k(x)} of principal minors of A. (ii) A is determined by generators (parameters generalizing reflection coefficients of unitary Hessenberg theory). (iii) Polynomials {r_k(x)} correspond not only to A but also to a certain “CMV-like” five-diagonal matrix. (iv) The five-diagonal matrix factors into a product BC of block diagonal matrices with 2 × 2 blocks. (v) Submatrices above and below the main diagonal of A have rank 1. (vi) A is a multiplication operator in the appropriate basis of Laurent polynomials. (vii) Eigenvectors of A can be expressed in terms of those polynomials.Conditions (v) connects our analysis to the study of quasi-separable matrices. But the factorization requirement (iv) narrows it to the subclass of “Green’s matrices” that share Properties (i)-(vii).The key tool is “twist transformations” that provide 2ⁿ matrices all sharing characteristic polynomials of principal minors with A. One such twist transformation connects unitary Hessenberg to CMV. Another twist transformation explains findings of Fiedler who noticed that companion matrices give examples outside the unitary Hessenberg framework. We mention briefly the further example of a Daubechies wavelet matrix. Infinite matrices are included.     

On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms

In this paper we design a fast new algorithm for reducing an N × N quasiseparable matrix to upper Hessenberg form via a sequence of N − 2 unitary transformations. The new reduction is especially useful when it is followed by the QR algorithm to obtain a complete set of eigenvalues of the original matrix. In particular, it is shown that in a number of cases some recently devised fast adaptations of the QR method for quasiseparable matrices can benefit from using the proposed reduction as a preprocessing step, yielding lower cost and a simplification of implementation.     

Limits for Szegö polynomials in frequency analysis

We characterize limits for orthogonal Szegö polynomials of fixed degree k, with respect to certain measures on the unit circle which are weakly convergent to a sum of m<k point masses. Such measures arise, for example, as a convolution of point masses with an approximate identity. It is readily seen that the underlying measures in two recently-proposed methods for estimating the m frequencies, θj, of a discrete-time trigonometric signal using Szegö polynomials are of this form. We prove existence of Szegö polynomial limits associated with a general class of weakly convergent measures, and prove that for convolution of point masses with the Poisson kernel, which underlies one of the recently-proposed methods, the limit has as a factor the Szegö polynomial with respect to a related measure, which we specify. Since m of the zeros approach the eiθj, this result uniquely characterizes the limit. A similar result is obtained for measures consisting of point masses with additive absolutely continuous part.     

Matrices with prescribed Ritz values

On the way to establishing a commutative analog to the Gelfand-Kirillov theorem in Lie theory, Kostant and Wallach produced a decomposition of M(n) which we will describe in the language of linear algebra. The “Ritz values” of a matrix are the eigenvalues of its leading principal submatrices of order m=1,2,…,n. There is a unique unit upper Hessenberg matrix H with those eigenvalues. For real symmetric matrices with interlacing Ritz values, we extend their analysis to allow eigenvalues at successive levels to be equal. We also decide whether given Ritz values can come from a tridiagonal matrix.     

The eigenvalue distribution of products of Toeplitz matrices - Clustering and attraction

We use a recent result concerning the eigenvalues of a generic (non-Hermitian) complex perturbation of a bounded Hermitian sequence of matrices to prove that the asymptotic spectrum of the product of Toeplitz sequences, whose symbols have a real-valued essentially bounded product h, is described by the function h in the “Szegö way”. Then, using Mergelyan’s theorem, we extend the result to the more general case where h belongs to the Tilli class. The same technique gives us the analogous result for sequences belonging to the algebra generated by Toeplitz sequences, if the symbols associated with the sequences are bounded and the global symbol h belongs to the Tilli class. A generalization to the case of multilevel matrix-valued symbols and a study of the case of Laurent polynomials not necessarily belonging to the Tilli class are also given.     

A note on the theorems of M.G. Krein and L.A. Sakhnovich on continuous analogs of orthogonal polynomials on the circle

Continuous analogs of orthogonal polynomials on the circle are solutions of a canonical system of differential equations, introduced and studied by Krein and recently generalized to matrix systems by Sakhnovich. We prove that the continuous analogs of the adjoint polynomials converge in the upper half-plane in the case of L² coefficients, but in general the limit can be defined only up to a constant multiple even when the coefficients are in L^p for any p>2, the spectral measure is absolutely continuous and the Szegö-Kolmogorov-Krein condition is satisfied. Thus, we point out that Krein's and Sakhnovich's papers contain an inaccuracy, which does not undermine known implications from these results.     

Symmetric matrices related to the Mertens function

In this paper, we explore a family of congruences over N^∗ from which one builds a sequence of symmetric matrices related to the Mertens function. From the results of numerical experiments, we formulate a conjecture about the growth of the quadratic norm of these matrices, which implies the Riemann hypothesis. This suggests that matrix analysis methods may come to play a more important role in this classical and difficult problem.     

Matrices related to the Bell polynomials

In this paper, we study the matrices related to the partial exponential Bell polynomials and those related to the Bell polynomials with respect to Ω. As a result, the factorizations of these matrices are obtained, which give unified approaches to the factorizations of many lower triangular matrices. Moreover, some combinatorial identities are also derived from the corresponding matrix representations.     

Polynomial perturbations of bilinear functionals and Hessenberg matrices

This paper deals with symmetric and non-symmetric polynomial perturbations of symmetric quasi-definite bilinear functionals. We establish a relation between the Hessenberg matrices associated with the initial and the perturbed functionals using LU and QR factorizations. Moreover we give an explicit algebraic relation between the sequences of orthogonal polynomials associated with both functionals.     

On the critical ideals of graphs

We introduce some determinantal ideals of the generalized Laplacian matrix associated to a digraph G, that we call critical ideals of G. Critical ideals generalize the critical group and the characteristic polynomials of the adjacency and Laplacian matrices of a digraph. The main results of this article are the determination of some minimal generator sets and the reduced Gröbner basis for the critical ideals of the complete graphs, the cycles and the paths. Also, we establish a bound between the number of trivial critical ideals and the stability and clique numbers of a graph.     

Polynomials over ordered fields

In this paper we determine which polynomials over ordered fields have multiples with nonnegative coefficients and also which polynomials can be written as quotients of two polynomials with nonnegative coefficients. This problem is related to a result given by Pólya in [G.H. Hardy, J.E. Littlewood, G. Pólya, Inequalities, Cambridge University Press, Cambridge, England, 1952] (as a companion of Artin’s theorem) that asserts that if F(X₁,…,X_n)∈R[X₁,…,X_n] is a form (i.e., a homogeneous polynomial) s.t.  with ∑x_j>0, then F=G/H, where G,H are forms with all coefficients positive (i.e., every monomial of degree degG or degH appears in G or H, resp., with a coefficient that is strictly positive). In Pólya’s proof H is chosen to be H=(X₁+?+X_n)^m for some m.At the end we give some applications, including a generalization of Pólya’s result to arbitrary ordered fields.     

Functions of a matrix and Krylov matrices

For a given nonderogatory matrix A, formulas are given for functions of A in terms of Krylov matrices of A. Relations between the coefficients of a polynomial of A and the generating vector of a Krylov matrix of A are provided. With the formulas, linear transformations between Krylov matrices and functions of A are introduced, and associated algebraic properties are derived. Hessenberg reduction forms are revisited equipped with appropriate inner products and related properties and matrix factorizations are given.     

A Strong Szegö-Widom Limit Theorem for operators with almost periodic diagonal

The classical Strong Szegö-Widom Limit Theorem describes the asymptotic behavior of the determinants of the finite sections PnT(a)Pn of Toeplitz operators, i.e., of operators which have constant entries along each diagonal. We generalize these results to operators which have almost periodic sequences as their diagonals.     

Orthogonal polynomials and measures on the unit circle. The Geronimus transformations

In this paper we analyze a perturbation of a nontrivial positive measure supported on the unit circle. This perturbation is the inverse of the Christoffel transformation and is called the Geronimus transformation. We study the corresponding sequences of monic orthogonal polynomials as well as the connection between the associated Hessenberg matrices. Finally, we show an example of this kind of transformation.     

A Matrix-Polynomial Structure in a Finite-Dimensional Vector Space

The classical interpretation of a matrix is the representation of an operator in a fixed coordinate system. Another interpretation of a symmetric matrix is the representation of a quadratic form. In this article we propose a new concept by considering the following three objects simultaneously: (i) a strongly nonsingular matrix, (ii) nonfactorable low and upper Hessenberg matrices, and (iii) two systems of special polynomials.     

Symmetric polynomials, Pascal matrices, and Stirling matrices

We consider lower-triangular matrices consisting of symmetric polynomials, and we show how to factorize and invert them. Since binomial coefficients and Stirling numbers can be represented in terms of symmetric polynomials, these results contain factorizations and inverses of Pascal and Stirling matrices as special cases. This work generalizes that of several other authors on Pascal and Stirling matrices.     

The computation of orthogonal rational functions and their interpolating properties

We shall consider nested spacesl _n ,n = 0, 1, 21... of rational functions withn prescribed poles outside the unit disk of the complex plane. We study orthogonal basis functions of these spaces for a general positive measure on the unit circle. In the special case where all poles are placed at infinity,l _n = _n , the polynomials of degree at mostn. Thus the present paper is a study of orthogonal rational functions, which generalize the orthogonal Szegö polynomials. In this paper we shall concentrate on the functions of the second kind which are natural generalizations of the corresponding polynomials.The work of the first author is partially supported by a research grant from the Belgian National Fund for Scientific Research     

Matrix measures on the unit circle, moment spaces, orthogonal polynomials and the Geronimus relations

We study the moment space corresponding to matrix measures on the unit circle. Moment points are characterized by non-negative definiteness of block Toeplitz matrices. This characterization is used to derive an explicit representation of orthogonal polynomials with respect to matrix measures on the unit circle and to present a geometric definition of canonical moments. It is demonstrated that these geometrically defined quantities coincide with the Verblunsky coefficients, which appear in the Szegö recursions for the matrix orthogonal polynomials. Finally, we provide an alternative proof of the Geronimus relations which is based on a simple relation between canonical moments of matrix measures on the interval [−1, 1] and the Verblunsky coefficients corresponding to matrix measures on the unit circle.     

On the closed representation for the inverses of Hessenberg matrices

The general representation for the elements of the inverse of any Hessenberg matrix of finite order is here extended to the reduced case with a new proof. Those entries are given with proper Hessenbergians from the original matrix. It justifies both the use of linear recurrences of unbounded order for such computations on matrices of intermediate order, and some elementary properties of the inverse. These results are applied on the resolvent matrix associated to a finite Hessenberg matrix in standard form. Two examples on the unit disk are given.