The representation and perturbation of theW-weighted Drazin inverse

LetA andE bem x n matrices andW an n xm matrix, and letA _d,W denote the W-weighted Drazin inverse ofA. In this paper, a new representation of the W-weighted Drazin inverse ofA is given. Some new properties for the W-weighted Drazin inverseA _d,W and B_d,W are investigated, whereB =A+E. In addition, the Banach-type perturbation theorem for the W-weighted Drazin inverse ofA andB are established, and the perturbation bounds for ∥B_d,W∥ and ∥B_{d, W}, -A_d,W∥/∥A_d,W∥ are also presented. WhenA andB are square matrices andW is identity matrix, some known results in the literature related to the Drazin inverse and the group inverse are directly reduced by the results in this paper as special cases.     

Relative perturbation results for eigenvalues and eigenvectors of diagonalisable matrices

Let and be a perturbed eigenpair of a diagonalisable matrixA. The problem is to bound the error in and . We present one absolute perturbation bound and two relative perturbation bounds. The absolute perturbation bound is an extension of Davis and Kahan's sin θ Theorem from Hermitian to diagonalisable matrices. The two relative perturbation bounds assume that and are an exact eigenpair of a perturbed matrixD ₁ AD ₂ , whereD ₁ andD ₂ are non-singular, butD ₁ AD ₂ is not necessarily diagonalisable. We derive a bound on the relative error in and a sin θ theorem based on a relative eigenvalue separation. The perturbation bounds contain both the deviation ofD ₁ andD ₂ from similarity and the deviation ofD ₂ from identity. This work was partially supported by NSF grant CCR-9400921.     

On the immersion of digraphs in cubes

We consider some problems concerning generalizations of embeddings of acyclic digraphs inton-dimensional dicubes. In particular, we define an injectioni from a digraphD into then-dimensional dicubeQ _n to be animmersion if for any two elementsa andb inD there is a directed path inD froma tob iff there is a directed path inQ _n fromi(a) toi(b). We further define the immersion to bestrong iff there is a way of choosing these paths so that paths inQ _n corresponding to arcs inD have disjoint interiors, and we introduce a natural notion of “minimality” on the set of arcs of a digraph in terms of its paths. Our main theorem then becomes:Every (minimal) n-element acyclic digraph can be (strongly) immersed in Q _n. We also present examples ofn-element digraphs which cannot be immersed inQ _n?1 and examples of 9n-element non-minimal digraphs which cannot be strongly immersed inQ10n _?1. We conclude with some applications.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

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.     

Spectral criteria for complementary triangular forms

In this paper we consider the following problem: Given two matricesA,Z∈? ^n×n , does there exist an invertiblen×n-matrixS such thatS ^?1 AS is an upper triangular matrix andS ^?1 ZS is a lower triangular matrix, and if so, what can be said about the order in which the eigenvalues ofA andZ appear on the diagonals of these triangular matrices? For special choices ofA andZ a complete solution is possible, as has been shown by several authors. Here we follow a lead, provided by Shmuel Friedland, who discussed the case where bothA andZ have at leastn-1 linearly independent eigenvectors, and we descibe the problem in terms of Jordan chains and left-Jordan chains for the matricesA, Z. The results give some insight in the question why certain classes of matrices (like the nonderogatory and the rank 1 matrices) allow for a detailed solution of the problems described above; for some of these classes the result of this analysis is presented here for the first time.     

The Chebyshev solution of the linear matrix equationAX+YB=C

Summary In this paper we investigate the properties of the Chebyshev solutions of the linear matrix equationAX+YB=C, whereA, B andC are given matrices of dimensionsm×r, s×n andm×n, respectively, wherer ands. We separately consider two particular cases. In the first case we assumem=r+1 andn=s+1, in the second caser=s=1 andm, n are arbitrary. For these two cases, under the assumption that the matricesA andB are full rank, we formulate necessary and sufficient conditions characterizing the Chebyshev solution ofAX+YB=C and we give the formulas for the Chebyshev error. Then, we propose an algorithm which may be applied to compute the Chebyshev solution ofAX+YB=C for some particular cases. Some numerical examples are also given.     

Characterizations of optimal scalings of matrices

A scaling of a non-negative, square matrixA ≠ 0 is a matrix of the formDAD ^?1, whereD is a non-negative, non-singular, diagonal, square matrix. For a non-negative, rectangular matrixB ≠ 0 we define a scaling to be a matrixCBE ^?1 whereC andE are non-negative, non-singular, diagonal, square matrices of the corresponding dimension. (For square matrices the latter definition allows more scalings.) A measure of the goodness of a scalingX is the maximal ratio of non-zero elements ofX. We characterize the minimal value of this measure over the set of all scalings of a given matrix. This is obtained in terms of cyclic products associated with a graph corresponding to the matrix. Our analysis is based on converting the scaling problem into a linear program. We then characterize the extreme points of the polytope which occurs in the linear program.     

A note on polar decomposition based Geršgorin-type sets

Let B∈C^n×n denote a finite-dimensional square complex matrix. In [L. Smithies, R.S. Varga, Singular value decomposition Geršgorin sets, J. Linear Algebra Appl. 417 (2004) 370-380; N. Fontes, J. Kover, L. Smithies, R.S. Varga, Singular value decomposition normally estimated Geršgorin sets, Electron. Trans. Numer. Anal. 26 (2007) 320-329], Professor Varga and I introduced Geršgorin-type sets which were developed from singular value decompositions (SVDs) of B. In this note, our work is extended by introducing the polar SV-Geršgorin set, Γ^PSV(B). The set Γ^PSV(B) is a union of n closed discs in C, whose centers and radii are defined in terms of the entries of a polar decomposition B=Q|B|. The set of eigenvalues of B, σ(B), is contained in Γ^PSV(B).     

Classification of small (0, 1) matrices

Denote by A_n the set of square (0, 1) matrices of order n. The set A_n, n ? 8, is partitioned into row/column permutation equivalence classes enabling derivation of various facts by simple counting. For example, the number of regular (0, 1) matrices of order 8 is 10160459763342013440. Let D_n, S_n denote the set of absolute determinant values and Smith normal forms of matrices from A_n. Denote by a_n the smallest integer not in D_n. The sets D₉ and S₉ are obtained; especially, a₉ = 103. The lower bounds for a_n, 10 ? n ? 19 (exceeding the known lower bound a_n ? 2f_n − 1, where f_n is nth Fibonacci number) are obtained. Row/permutation equivalence classes of A_n correspond to bipartite graphs with n black and n white vertices, and so the other applications of the classification are possible.     

A perturbation analysis of the intrinsic conditioning of an approximate null vector computed with a SVD

Let A be an m ×n real matrix with singular values σ₁ ? ··· ? σ_n?1 ? σ_n ? 0. In cases where σ_n ? 0, the corresponding right singular vector υ_n is a natural choice to use for an approximate null vector ofA. Using an elementary perturbation analysis, we show that κ = σ₁/(σ_n?1 ? σ_n) provides a quantitative measure of the intrinsic conditioning of the computation of υ_n from A.     

Kantorovič operators of second order

The Kantorovi? operators of second order are introduced byQ _n f= =(B _n+2 F)″ whereF is the double indefinite integraloff andB _n+2 the (n+2)-th Bernstein operator. The operatorsQ _n will reveal a close affinity to the so-called modified Bernstein operatorsC _n introduced bySchnabl [10] on a quite different way. The article contains investigations concerning the asymptotic behavior ofQ _n ^kn f (asn → ∞), where (k _n) is a sequence of natural numbers.     

Perturbation bounds on the polar decomposition

The polar decomposition of ann ×n-matrixA takes the formA=MH whereM is orthogonal andH is symmetric and positive semidefinite. This paper presents strict bounds, (with no order terms), on the perturbationsM,H ofM andH respectively, whenA is perturbed byA. The bounds onM can also be applied to the orthogonal Procrustes problem.     

On the corners of certain determinantal ranges

Let A be a complex n×n matrix and let SO(n) be the group of real orthogonal matrices of determinant one. Define Δ(A)={det(A°Q):Q∈SO(n)}, where ° denotes the Hadamard product of matrices. For a permutation σ on {1,…,n}, define It is shown that if the equation z_σ=det(A°Q) has in SO(n) only the obvious solutions (Q=(ε_iδ_σi,j),ε_i=±1 such that ε₁…ε_n=sgnσ), then the local shape of Δ(A) in a vicinity of z_σ resembles a truncated cone whose opening angle equals , where σ₁, σ₂ differ from σ by transpositions. This lends further credibility to the well known de Oliveira Marcus Conjecture (OMC) concerning the determinant of the sum of normal n×n matrices. We deduce the mentioned fact from a general result concerning multivariate power series and also use some elementary algebraic topology.     

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.     

Congruence of Hermitian matrices by Hermitian matrices

Two Hermitian matrices A,B∈M_n(C) are said to be Hermitian-congruent if there exists a nonsingular Hermitian matrix C∈M_n(C) such that B=CAC. In this paper, we give necessary and sufficient conditions for two nonsingular simultaneously unitarily diagonalizable Hermitian matrices A and B to be Hermitian-congruent. Moreover, when A and B are Hermitian-congruent, we describe the possible inertias of the Hermitian matrices C that carry the congruence. We also give necessary and sufficient conditions for any 2-by-2 nonsingular Hermitian matrices to be Hermitian-congruent. In both of the studied cases, we show that if A and B are real and Hermitian-congruent, then they are congruent by a real symmetric matrix. Finally we note that if A and B are 2-by-2 nonsingular real symmetric matrices having the same sign pattern, then there is always a real symmetric matrix C satisfying B=CAC. Moreover, if both matrices are positive, then C can be picked with arbitrary inertia.     

Some new bounds on the spectral radius of matrices

A new lower bound on the smallest eigenvalue τ(AB) for the Fan product of two nonsingular M-matrices A and B is given. Meanwhile, we also obtain a new upper bound on the spectral radius ρ(A°B) for nonnegative matrices A and B. These bounds improve some results of Huang (2008) [R. Huang, Some inequalities for the Hadamard product and the Fan product of matrices, Linear Algebra Appl. 428 (2008) 1551-1559].     

Backward Perturbation Analysis for the Matrix Equation A~TXA+B~TYB=D

Consider the linear matrix equation A~TXA + B~TYB = D,where A,B are n X n real matrices and D symmetric positive semi-definite matrix.In this paper,the normwise backward perturbation bounds for the solution of the equation are derived by applying the Brouwer fixed-point theorem and the singular value decomposition as well as the property of Kronecker product.The results are illustrated by two simple numerical examples.     

Nearest southeast submatrix that makes multiple a prescribed eigenvalue. Part 1

Given four complex matrices A,B,C and D, where A∈C^n×n and D∈C^m×m, and given a complex number z₀: What is the (spectral norm) distance from D to the set of matrices X∈C^m×m such that z₀ is a multiple eigenvalue of the matrix

     

Small linearly independent zeros of quadratic forms

LetQ be a non-degenerate quadratic form on ? ⁿ and \(L \subseteq \mathbb{R}^n\) a lattice with \(Q(L) \subseteq \mathbb{Z}\) which contains a non-trivial zero ofQ. We give upper bounds for the minimal value of the determinant and of the product of the norms ofn linearly independent zeros ofQ inL.