Definitizable hermitian matrix pencils

Summary An hermitian matrix pencilA – B withA nonsingular is called strongly definitizable ifAp(A ^–1 B) is positive definite for some polynomialp. We present three characterizations of strongly definitizable pencils, which generalize the classical results for definite pencils. They are, in particular, stably simultaneously diagonable. We also discuss this form of stability with respect to an open subset of the real line. Implications for some quadratic eigenvalue problems are included.Research supported in part by the National Sciences and Engineering Research Council of Canada.Dedicated to the memory of Alexander M. Ostrowski on the occasion of the 100th anniversary of his birth.     

On the perturbation of analytic matrix functions

In this paper behaviour of the spectrum of matrix-valued functions depending analytically on two parameters is studied. Generalizations of the Rellich theorem on analytic dependence of the spectrum and complete regular splitting of multiple eigenvalues are established.This work is partially supported by Natural Sciences and Engineering Research Council of Canada. R. H. also acknowledges appointment as a Post Doctoral Fellow of the Pacific Institute for Mathematical Sciences.     

Left and right factorizations of rational matrix functions

The right partial indices of the symbol are described in terms of realizations of factors of the left Wiener-Hopf canonical factorization of the same symbol. The dual results are also stated. Application to Wiener-Hopf equations is considered.     

Quasicomplete factorizations of rational matrix functions

It is shown that within the class ofn×n rational matrix functions which are analytic at infinity with valueW()=I _n, any rational matrix functionW is the productW=W ₁...W _p of rational matrix functionsW ₁,...,W _p of McMillan degree one. Furthermore, such a factorization can be established with a number of factors not exceeding 2(W)–1, where (W) denotes the McMillan degree ofW.     

Leading coefficients of the eigenvalues of perturbed analytic matrix functions

This note contains some supplements to our earlier notes [LN II], [LN III], where the Newton diagram was used in order to obtain in a straightforward way information about the perturbed eigenvalues of an analytic and analytically perturbed matrix function.     

Perturbation bounds for theLDL H andLU decompositions

LetA andA+A be Hermitian positive definite matrices. Suppose thatA=LDL ^H and (A+A)=(L+L)(D+D)(L+L)^H are theLDL ^H decompositons ofA andA+A, respectively. In this paper upper bounds on |D| _F and |L| _F are presented. Moreover, perturbation bounds are given for theLU decomposition of a complexn ×n matrix.     

Inversion of regular analytic matrix functions: Local Smith form and subspace duality

This paper analyzes the relation between the local rank-structure of a regular analytic matrix function and the one of its inverse function. The local rank factorization (lrf) of a matrix function is introduced, which characterizes extended canonical systems of root functions and the local Smith form. An interpretation of the local rank factorization in terms of Jordan chains and Jordan pairs is provided. Duality results are shown to hold between the subspaces associated with the lrf of the matrix function and the one of its reduced adjoint.     

An algorithm for computing Jordan chains and inverting analytic matrix functions

We present an efficient algorithm for obtaining a canonical system of Jordan chains for an n × n regular analytic matrix function A(λ) that is singular at the origin. For any analytic vector function b(λ), we show that each term in the Laurent expansion of A(λ)⁻¹b(λ) may be obtained from the previous terms by solving an (n + d) × (n+d) linear system, where d is the order of the zero of det A(λ) at λ = 0. The matrix representing this linear system contains A(0) as a principal submatrix, which can be useful if A(0) is sparse. The last several iterations can be eliminated if left Jordan chains are computed in addition to right Jordan chains. The performance of the algorithm in floating point and exact (rational) arithmetic is reported for several test cases. The method is shown to be forward stable in floating point arithmetic.     

Extreme rays for the large cone of hermitian generalized matrix functions

Given a <artwork name="GLMA31007ei1">-valued function f with domain <artwork name="GLMA31007ei2">, the symmetric group on {1,2,…, m}, we define the generalized matrix function [ f ](?), or d_f (?), in the usual way on the set of all m× m complex matrices. Letting <artwork name="GLMA31007ei3"> denote the set of all m× m positive semi-definite Hermitian matrices we consider the cone K _m whose elements are the Hermitian functions <artwork name="GLMA31007ei4"> such that [ f ]( A)≥0 for all <artwork name="GLMA31007ei5">. The extreme rays in K _m are fundamental to an understanding of the linear inequalities that result by restricting the generalized matrix functions [ f ](?) to the sets <artwork name="GLMA31007ei6">. In particular, the resolution of Lieb's permanent dominance conjecture, and certain similar conjectures such as the conjecture of Soules, will likely require identification and careful analysis of these rays. Grone, Merris, and Watkins have shown that the determinant function det(?), which is [ f ](?) if f is the signum function, is extreme in K _m for each m. We identify additional rays that are extreme for all m. In particular, we associate with each 2-term partition <artwork name="GLMA31007ei7"> of {1,2,…, m} an element <artwork name="GLMA31007ei8"> that is shown to be extreme in K _m for each m. If <artwork name="GLMA31007ei9"> is trivial, then <artwork name="GLMA31007ei10"> reduces to the determinant function; hence, our results are a natural extension of the result of Grone, Merris, and Watkins. Moreover <artwork name="GLMA31007ei11">, like det ( A), is expressible as a function of the eigenvalues of certain matrices related to A. Additional classes of extreme rays are also presented.     

On decomposing any matrix as a linear combination of three idempotents

In a recent article, we gave a full characterization of matrices that can be decomposed as linear combinations of two idempotents with prescribed coefficients. In this one, we use those results to improve on a recent theorem of Rabanovich: we establish that every square matrix is a linear combination of three idempotents (for an arbitrary coefficient field rather than just one of characteristic 0).     

Perturbation bounds for the Cholesky andQR factorizations

LetA, A+E be Hermitian positive definite matrices. Suppose thatA=LL ^H andA+E=(L+G)(L+G)^H are the Cholesky factorizations ofA andA+E, respectively. In this paper lower bounds and upper bounds on |G|/|L| in terms of |E|/|A| are given. Moreover, perturbation bounds are given for the QR factorization of a complexm ×n matrixA of rankn.This research was supported by the National Science Foundation of China and the Department of Mathematics of Linköping University in Sweden.     

Generalized hermitian operators

In this paper, the concept of generalized hermitian operators defined on a complex Hilbert space is introduced. It is shown that the spectrums and the Fredholm fields of generalized hermitian operators are both symmetric with respect to the real axis. Some other results on generalized hermitian operators are obtained.     

Computing the optimal commuting matrix pairs

A matrix can be modified by an additive perturbation so that it commutes with any given matrix. In this paper, we discuss several algorithms for computing the smallest perturbation in the Frobenius norm for a given matrix pair. The algorithms have applications in 2-D direction-of-arrival finding in array signal processing. The work of first author was supported in part by NSF grant CCR-9308399. The work of the second author was supported in part by China State Major Key Project for Basic Researches.     

Circular trichotomy of the spectrum of regular matrix pencils

We introduce a method for approximating the right and left deflating subspaces of a regular matrix pencil corresponding to the eigenvalues inside, on and outside the unit circle. The method extends the iteration used in the context of spectral dichotomy, where the assumption on the absence of eigenvalues on the unit circle is removed. It constructs two matrix sequences whose null spaces and the null space of their sum lead to approximations of the deflating subspaces corresponding to the eigenvalues of modulus less than or equal to 1, equal to 1 and larger than or equal to 1. An orthogonalization process is then used to extract the desired delating subspaces. The resulting algorithm is an inverse free, easy to implement, and sufficiently fast. The derived convergence estimates reveal the key parameters, which determine the rate of convergence. The method is tested on several numerical examples.     

The complexity of tropical matrix factorization

The tropical arithmetic operations on R are defined by a⊕b=min{a,b}$a\oplus b=\min \{a,b\}$ and a⊗b=a+b$a\otimes b=a+b$. Let A be a tropical matrix and k   a positive integer, the problem of Tropical Matrix Factorization (TMF) asks whether there exist tropical matrices B∈R^m×k$B\in {\mathbf{R}}^{m\times k}$ and C∈R^k×n$C\in {\mathbf{R}}^{k\times n}$ satisfying B⊗C=A$B\otimes C=A$. We show that the TMF problem is NP-hard for every k≥7$k\ge 7$ fixed in advance, thus resolving a problem proposed by Barvinok in 1993.     

Palindromic matrix polynomials, matrix functions and integral representations

We study the properties of palindromic quadratic matrix polynomials φ(z)=P+Qz+Pz², i.e., quadratic polynomials where the coefficients P and Q are square matrices, and where the constant and the leading coefficients are equal. We show that, for suitable choices of the matrix coefficients P and Q, it is possible to characterize by means of φ(z) well known matrix functions, namely the matrix square root, the matrix polar factor, the matrix sign and the geometric mean of two matrices. Finally we provide some integral representations of these matrix functions.     

Multiple LU factorizations of a singular matrix

A singular matrix A may have more than one LU factorizations. In this work the set of all LU factorizations of A is explicitly described when the lower triangular matrix L is nonsingular. To this purpose, a canonical form of A under left multiplication by unit lower triangular matrices is introduced. This canonical form allows us to characterize the matrices that have an LU factorization and to parametrize all possible LU factorizations. Formulae in terms of quotient of minors of A are presented for the entries of this canonical form.     

Equalities and inequalities for inertias of hermitian matrices with applications

The inertia of a Hermitian matrix is defined to be a triplet composed of the numbers of the positive, negative and zero eigenvalues of the matrix counted with multiplicities, respectively. In this paper, we show some basic formulas for inertias of 2×2 block Hermitian matrices. From these formulas, we derive various equalities and inequalities for inertias of sums, parallel sums, products of Hermitian matrices, submatrices in block Hermitian matrices, differences of outer inverses of Hermitian matrices. As applications, we derive the extremal inertias of the linear matrix expression A-BXB^∗ with respect to a variable Hermitian matrix X. In addition, we give some results on the extremal inertias of Hermitian solutions to the matrix equation AX=B, as well as the extremal inertias of a partial block Hermitian matrix.     

Number theory of matrix semigroups

Unlike factorization theory of commutative semigroups which are well-studied, very little literature exists describing factorization properties in noncommutative semigroups. Perhaps the most ubiquitous noncommutative semigroups are semigroups of square matrices and this article investigates the factorization properties within certain subsemigroups of M_n(Z), the semigroup of n×n matrices with integer entries. Certain important invariants are calculated to give a sense of how unique or non-unique factorization is in each of these semigroups.     

Generalized canonical factorization of matrix and operator functions with definite hermitian part

It is proved that rational matrix functions with definite hermitian part on the real line admit a generalized canonical factorization. The functions are allowed to have poles on the real line. A generalization of this result to a class of operator functions is obtained as well.Partially supported by an NSF grant