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.     

An algorithm for best approximate solutions ofAx=b with a smooth strictly convex norm

Summary In this paper, overdetermined systems ofm linear equations inn unknowns are considered. With ^m equipped with a smooth strictly convex norm, ·, an iterative algorithm for finding the best approximate solution of the linear system which minimizes the ·-error is given. The convergence of the algorithm is established and numerical results are presented for the case when · is anl _p norm, 1<p<.Portions of this paper are taken from the author's Ph.D. thesis at Michigan State University     

On eigenvalues of perturbed quadratic matrix polynomials

Among other results, it is shown that ifC andK are arbitrary complexn×n matrices and if det( ₀ ² I₀ C+K)=0 for some ₀0 (resp. ₀=0), then the Newton diagram of the polynomialt(, ) = det(² I+(1+)C+K expanded in (–₀) and , has at least a point on or below the linex+y=b (resp. has no expanded in (–₀) and , has at least a point on or below the of 0 as an eigenvalue of ₀ ² I+₀ C+K. These are extensions of similar results deu to H. Langer, B. Najman, and K. Veseli proved for diagonable matricesC, and shed light on the eigenvalues of the perturbed quadratic matrix polynomials. Our proofs are independent and seem to be simpler     

A perturbation bound for the generalized polar decomposition

LetA be anm×n complex matrix. A decompositionA=QH is termed ageneralized polar decomposition ofA ifQ is anm×n subunitary matrix (sometimes also called a partial isometry) andH a positive semidefinite Hermitian matrix. It was proved that a nonzero matrixA ^m×n has a unique generalized polar decompositionA=QH with the property (Q ^H )=(H), whereQ ^H denotes the conjugate transpose ofQ and (H) the column space ofH. The main result of this note is a perturbation bound forQ whenA is perturbed.     

A lower bound on strictly non-blocking networks

We prove that a strictly non-blockingn-connector of depthk must have(n ^1+1/(k–1)) edges.     

Normal and seminormal eigenvalues of matrix functions

LetP() be ann×n analytic matrix function andW(P) be its numerical range. In this paper classical results on the normality of matrix eigenvalues on W(P) are generalized to the context of such matrix functions. Special attention is paid to corners of W(P) and to the special case of matrix polynomialsP().     

Normal forms in matrix spaces

For the groupGL(m, C)xGL(n, C) acting on the space ofmxn matrices over C, we introduce a class of subgroups which we call admissible. We suggest an algorithm to reduce an arbitrary matrix to a normal form with respect to an action of any admissible group. This algorithm covers various classification problems, including the wild problem of bringing a pair of matrices to normal form by simultaneous similarity. The classical left, right, two-sided and similarity transformations turns out to be admissible. However, the stabilizers of known normal forms (Smith's, Jordan's), generally speaking, are not admissible, and this obstructs inductive steps of our algorithm. This is the reason that we introduce modified normal forms for classical actions.Partially supported by Israel Science Foundation     

On polynomial EkP matrices

In this paper the relation betweenEP--matrices andE ^k P--matrices over an arbitrary filedF is studied. Further, conditions for the product ofE ^k P--matrices to be anE ^k P--matrix and for the reverse order law to hold for the polynomial Moore-Penrose inverse of the product ofE ^k P--matrices are determined     

The limit of the spectral radius of block Toeplitz matrices with nonnegative entries

A bi-infinite sequence ...,t _–2,t _–1,t ₀,t ₁,t ₂,... of nonnegativep×p matrices defines a sequence of block Toeplitz matricesT _n =(t _ik ),n=1,2,...,, wheret _ik =t _k–i ,i,k=1,...,n. Under certain irreducibility assumptions, we show that the limit of the spectral radius ofT _n , asn tends to infinity, is given by inf{()[0,]}, where () is the spectral radius of _jz t _j ^j .Supported by SFB 343 Diskrete Strukturen in der Mathematik, Universität Bielefeld     

Reconstruction of a rational nonsquare matrix function from local data

In many problems the local zero-pole structure (i.e. locations of zeros and poles together with their orders) of a scalar rational functionw is a key piece of structure. Knowledge of the order of the pole or zero of the rational functionw at the point is equivalent to knowledge of the -module (where is the space of rational functions analytic at ). For the more intricate case of a rationalp×m matrix functionW, we consider the structure of the module as the appropriate analogue of zero-pole structure (location of zeros and poles together with directional information), where is the set of column vectors of heightm with entries equal to rational functions which are analytic at . Modules of the form in turn can be explicitly parametrized in terms of a collection of matrices (C ,A ,B ,B , ) together with a certain row-reduced(p–m)×m matrix polynomialP(z) (which is independent of ) which satisfy certain normalization and consistency conditions. We therefore define the collection (C ,A ,Z ,B , ,P(z)) to be the local spectral data set of the rational matrix functionW at . We discuss the direct problem of how to compute the local spectral data explicitly from a realizationW(z)=D+C(z–A) ^–1 B forW and solve the inverse problem of classifying which collections (C ,A ,Z ,B , ,P(z)) satisfying the local consistency and normalization conditions arise as the local spectral data sets of some rational matrix functionW. Earlier work in the literature handles the case whereW is square with nonzero determinant.     

Two counterexamples related to the Kreiss matrix theorem

The modern version of the Kreiss matrix theorem states that A ⁿ esK (for alln0) ifA is ans ×s matrix satisfying a resolvent condition with respect to the unit disk with constantK. In this paper we show for any fixedK + 1 that the upper boundesK is sharp in the sense that a linear dependence on the dimensions is the best possible. An analogous result is obtained for the continuous version of the Kreiss matrix theorem, which states that exp(tA) esK (for allt0) ifA is ans ×s matrix satisfying a resolvent condition with respect to the left half plane with constantK.The research has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences (K.N.A.W.) and was carried out at the Department of Mathematics and Computer Science, University of Leiden, The Netherlands.     

Hierarchical decomposition of symmetric discrete systems by matroid and group theories

An algebraic method is proposed for the hierarchical decomposition of large-scale group-symmetric discrete systems into partially ordered subsystems. It aims at extracting substructures and hierarchy for such systems as electrical networks and truss structures.The mathematical problem considered is: given a parametrized family of group invariant structured matricesA, we are to find two constant (=parameter-independent) nonsingular matricesS _r andS _c such thatS _r ^-1 AS _c takes a (common) block-triangular form.The proposed method combines two different decomposition principles developed independently in matroid theory and in group representation theory. The one is the decomposition principle for submodular functions, which has led to the Dulmage—Mendelsohn (DM-) decomposition and further to the combinatorial canonical form (CCF) of layered mixed (LM-) matrices. The other is the full reducibility of group representations, which yields the block-diagonal decomposition of group invariant matrices. The optimality of the proposed method is also discussed.     

Finite digraphs with given regular automorphism groups

With five exceptions, every finite regular permutation group occurs as the automorphism group of a digraph.One of the corollaries: given a finite groupG of ordern, there is a commutative semigroupS of order 2n+2 such that AutSG. The problem whether a latticeL of order Cn with AutLG exists (for some constantC), remains open.     

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.     

J-pseudo-spectral andJ-inner-pseudo-outer factorizations for matrix polynomials

For a comonic polynomialL() and a selfadjoint invertible matrixJ the following two factorization problems are considered: firstly, we parametrize all comonic polynomialsR() such that . Secondly, if it exists, we give theJ-innerpseudo-outer factorizationL()=()R(), where () isJ-inner andR() is a comonic pseudo-outer polynomial. We shall also consider these problems with additional restrictions on the pole structure and/or zero structure ofR(). The analysis of these problems is based on the solution of a general inverse spectral problem for rational matrix functions, which consists of finding the set of rational matrix functions for which two given pairs are extensions of their pole and zero pair, respectively.The work of this author was supported by the USA-Israel Binational Science Foundation (BSF) Grant no. 9400271.     

Bernstein functions, complete hyperexpansivity and subnormality—I

Special classes of functions on the classical semigroupN of non-negative integers, as defined using the classical backward and forward difference operators, get associated in a natural way with special classes of bounded linear operators on Hilbert spaces. In particular, the class of completely monotone functions, which is a subclass of the class of positive definite functions ofN, gets associated with subnormal operators, and the class of completely alternating functions, which is a subclass of the class of negative definite functions onN, with completely hyper-expansive operators. The interplay between the theories of completely monotone and completely alternating functions has previously been exploited to unravel some interesting connections between subnormals and completely hyperexpansive operators. For example, it is known that a completely hyperexpansive weighted shift with the weight sequence {_n}(n0) (of positive reals) gives rise to a subnormal weighted shift whose weight sequence is {1/_n}(n0). The present paper discovers some new connections between the two classes of operators by building upon some well-known results in the literature that relate positive and negative definite functions on cartesian products of arbitrary sets using Bernstein functions. In particular, it is observed that the weight sequence of a completely hyperexpansive weighted shift with the weight sequence {_n}(n0) (of positive reals) gives rise to a subnormal weighted shift whose weight sequence is {_n+1/_n}(n0). It is also established that the weight sequence of any completely hyperexpansive weighted shift is a Hausdorff moment sequence. Further, the connection of Bernstein functions with Stieltjes functions and generalizations thereof is exploited to link certain classes of subnormal weighted shifts to completely hyperexpansive ones.     

Improved lower bounds on the length of Davenport-Schinzel sequences

We derive lower bounds on the maximal length _s(n) of (n, s) Davenport Schinzel sequences. These bounds have the form _2s=1(n)=(n^s(n)), where(n) is the extremely slowly growing functional inverse of the Ackermann function. These bounds extend the nonlinear lower bound ₃ (n)=(n(n)) due to Hart and Sharir [5], and are obtained by an inductive construction based upon the construction given in [5].Work on this paper has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.     

Para-orthogonal Laurent polynomials and associated sequences of rational functions

On the space, , of Laurent polynomials (L-polynomials) we consider a linear functional which is positive definite on (0, ) and is defined in terms of a given bisequence, { _k } _– . Two sequences of orthogonal L-polynomials, {Q _n (z) ₀ and , are constructed which span in the order {1,z ^–1,z,z ^–2,z ²,...} and {1,z,z ^–1,z ²,z ^–2,...} respectively. Associated sequences of L-polynomials {P _n (z) ₀ , and are introduced and we define rational functions , wherew is a fixed positive number. The partial fraction decomposition and integral representation of,M _n (z, w) are given and correspondence of {M _n (z, w)} is discussed. We get additional solutions to the strong Stieltjes moment problem from subsequences of {M _n (z, w)}. In particular when { _k } _– is a log-normal bisequence, {M _2n (z, w)} and {M _2n+1 (z, w)} yield such solutions.Research supported in part by the National Science Foundation under Grant DMS-9103141.     

On spectral variations under bounded real matrix perturbations

Summary In this paper we investigate the set of eigenvalues of a perturbed matrix {ie509-1} whereA is given and ^{n × n}, ||< is arbitrary. We determine a lower bound for thisspectral value set which is exact for normal matricesA with well separated eigenvalues. We also investigate the behaviour of the spectral value set under similarity transformations. The results are then applied tostability radii which measure the distance of a matrixA from the set of matrices having at least one eigenvalue in a given closed instability domain _b.     

Generalized Eulerian numbers and the topology of the Hessenberg variety of a matrix

Let Agl(n, C) and let p be a positive integer. The Hessenberg variety of degree p for A is the subvariety Hess(p, A) of the complete flag manifold consisting of those flags S ₁ S _n–1 in ⁿ which satisfy the condition AS _i S _i+p ,for all i. We show that if A has distinct eigenvalues, then Hess(p, A) is smooth and connected. The odd Betti numbers of Hess(p, A) vanish, while the even Betti numbers are given by a natural generalization of the Eulerian numbers. In the case where the eigenvalues of A have distinct moduli, |₁|<<|₁|, these results are applied to determine the dimension and topology of the submanifold of U(n) consisting of those unitary matrices P for which A ₀=P ^-1 AP is in Hessenberg form and for which the diagonal entries of the QR-iteration initialized at A ₀ converge to a given permutation of ₁,_n.Research partially supported by the National Science Foundation under Grant ECS-8696108.