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.     

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.     

Invariant polynomials of sums of matrices

Some recent results on invariant polynomials of sums of two matrices are examined.     

On 0-1 matrices and small excluded submatrices

We say that a 0-1 matrix A avoids another 0-1 matrix (pattern) P if no matrix P^′ obtained from P by increasing some of the entries is a submatrix of A. Following the lead of (SIAM J. Discrete Math. 4 (1991) 17-27; J. Combin. Theory Ser. A 55 (1990) 316-320; Discrete Math. 103 (1992) 233-251) and other papers we investigate n by n 0-1 matrices avoiding a pattern P and the maximal number ex(n,P) of 1 entries they can have. Finishing the work of [8] we find the order of magnitude of ex(n,P) for all patterns P with four 1 entries. We also investigate certain collections of excluded patterns. These sets often yield interesting extremal functions different from the functions obtained from any one of the patterns considered.     

Representation of group elements as subsequence sums

Let G be a finite (additive written) abelian group of order n. Let w₁,…,w_n be integers coprime to n such that w₁+w₂+?+w_n≡0 (mod n). Let I be a set of cardinality 2n-1 and let ξ={x_i:i∈I} be a sequence of elements of G. Suppose that for every subgroup H of G and every a∈G, ξ contains at most terms in a+H.Then, for every y∈G, there is a subsequence {y₁,…,y_n} of ξ such that y=w₁y₁+?+w_ny_n.Our result implies some known generalizations of the Erd?s-Ginzburg-Ziv Theorem.     

Positive semi-definite matrices as sums of squares

If K is a field and char K ≠ 2, then an element α?K is a sum of squares in K if and only if α ? 0 for every ordering of K. This is the famous theorem of Artin and Landau. It has been generalized to symmetric matrices over K by D. Gondard and P. Ribenboim. They have also shown that Artin's theorem on positive definite rational functions has a suitable extension to positive definite matrix functions. In this paper we attain two goals. First, we show that similar theorems are valid for Hermitian matrices instead of symmetric ones. Second, we simplify D. Gondard and P. Ribenboim's proof of their second theorem and strengthen it.     

Jacobi matrices for sums of weight functions

Orthogonal polynomials are conveniently represented by the tridiagonal Jacobi matrix of coefficients of the recurrence relation which they satisfy. LetJ ₁ andJ ₂ be finite Jacobi matrices for the weight functionsw ₁ andw ₂, resp. Is it possible to determine a Jacobi matrix \(\tilde J\) , corresponding to the weight functions \(\tilde w\) =w ₁+w ₂ using onlyJ ₁ andJ ₂ and if so, what can be said about its dimension? Thus, it is important to clarify the connection between a finite Jacobi matrix and its corresponding weight function(s). This leads to the need for stable numerical processes that evaluate such matrices. Three newO(n ²) methods are derived that “merge” Jacobi matrices directly without using any information about the corresponding weight functions. The first can be implemented using any of the updating techniques developed earlier by the authors. The second new method, based on rotations, is the most stable. The third new method is closely related to the modified Chebyshev algorithm and, although it is the most economical of the three, suffers from instability for certain kinds of data. The concepts and the methods are illustrated by small numerical examples, the algorithms are outlined and the results of numerical tests are reported.     

Diagonals and numerical ranges of direct sums of matrices

For any n-by-n matrix A  , we consider the maximum number k=k(A)$k=k(A)$ for which there is a k-by-k compression of A   with all its diagonal entries in the boundary ∂W(A)$\partial W(A)$ of the numerical range W(A)$W(A)$ of A. If A   is a normal or a quadratic matrix, then the exact value of k(A)$k(A)$ can be computed. For a matrix A   of the form B⊕C$B\oplus C$, we show that k(A)=2$k(A)=2$ if and only if the numerical range of one summand, say, B is contained in the interior of the numerical range of the other summand C   and k(C)=2$k(C)=2$. For an irreducible matrix A  , we can determine exactly when the value of k(A)$k(A)$ equals the size of A  . These are then applied to determine k(A)$k(A)$ for a reducible matrix A   of size 4 in terms of the shape of W(A)$W(A)$.     

Maximum and minimum diagonal sums of doubly stochastic matrices

Let Ω_n denote the convex polyhedron of all n×n doubly stochastic (d.s.) matrices. The purpose of this paper is to investigate some of the numerical properties of the maximum and the minimum diagonal sums of the matrices in Ω_n. A few conjectures that naturally arise will be mentioned.     

Error-free matrix symmetrizers and equivalent symmetric matrices

A symmetrizer of the matrix A is a symmetric solution X that satisfies the matrix equation XA=AX. An exact matrix symmetrizer is computed by obtaining a general algorithm and superimposing a modified multiple modulus residue arithmetic on this algorithm. A procedure based on computing a symmetrizer to obtain a symmetric matrix, called here an equivalent symmetric matrix, whose eigenvalues are the same as those of a given real nonsymmetric matrix is presented.Supported by CSIR.     

On eigenvalues and equivalent transformation of trigonometric matrices

This paper discusses some issues related to trigonometric matrices arising from the design of finite impulse response (FIR) digital filters. A conjecture on the eigenvalues of a trigonometric matrix is posed with a partial proof given. A new result is also presented on the related equivalent transformation of this trigonometric matrix into a diagonal matrix.     

Subdirect sums of weakly chained diagonally dominant matrices

Some sufficient conditions ensuring that the subdirect sum of two weakly chained diagonally dominant matrices is in this class, are given. In particular, it is shown that the subdirect sum of overlapping principal submatrices of a weakly chained diagonally dominant matrix is also a weakly chained diagonally dominant matrix.     

On the sensitivity of generators for the QR factorization of quasiseparable matrices with total nonpositivity

In this paper, we provide a relatively robust representation for the QR factorization of quasiseparable matrices with total nonpositivity. This representation allows us to develop a structure-preserving perturbation analysis. Consequently, stronger perturbation bounds are obtained to show that its generators determine the factors Q and R to high relative accuracy, independent of any conventional condition number. This means that it is possible to accurately compute the QR factorization by operating on these generators.     

Sum rules for Jacobi matrices and divergent Lieb-Thirring sums

Let E_j be the eigenvalues outside [-2,2] of a Jacobi matrix with a_n-1∈?² and b_n→0, and μ^′ the density of the a.c. part of the spectral measure for the vector δ₁. We show that if b_n∉?⁴, b_n+1-b_n∈?², then

     

Direct sums and direct products of canonical pencils of matrices

A theorem of Kulikov characterizes the K[x]-modules which are direct sums of finite-dimensional (as a K-vector space) indecomposable modules, where K[x] is the polynomial ring over the field K. In this paper an analogous characterization is given for modules over the ring R, arising from pairs of linear transformations between a pair of complex vector spaces, (V, W). R is a certain subring of the ring of 3 × 3 complex matrices. The equivalence between the category of right R-modules and the category of systems enables one to work entirely in the category of systems. (A pair of complex vector spaces is a system if and only if there is a $\text{C}$-bilinear map from $\text{C}{}^2\text{× V}$ to W). R-modules that are direct sums of finite-dimensional indecomposable subsystems are called pure-projective. The above characterization of pure-projective R-modules is used to prove that an R-module M is projective if and only if Ext(M, R) = 0. Direct products of finite-dimensional indecomposable R-modules are also studied, and a theorem pinpoints those that are pure-projective. An example of an R-module M that is not pure-projective, but with the property that every finite subset of M is contained in a pure-projective direct summand of M, is given. A by-product of this example is a class of matrices that generalizes the Vandermonde matrices.