On the characterization of generalized inverses by bordered matrices

A method to characterize the class of all generalized inverses of any given matrix A is considered. Given a matrix A and a nonsingular bordered matrix T of A,

$\text{T=}\text{A}\text{P}\text{Q}\text{R}$

the submatrix, corresponding to A, of T^-1 is a generalized inverse of A, and conversely, any generalized inverse of A is obtainable by this method. There are different definitions of a generalized inverse, and the arguments are developed with the least restrictive definition. The characterization of the Moore-Penrose inverse, the most restrictive definition, is also considered.     

Nonnegative factorization of completely positive matrices

Let A be a real symmetric n × n matrix of rank k, and suppose that A = BB′ for some real n × m matrix B with nonnegative entries (for some m). (Such an A is called completely positive.) It is shown that such a B exists with $\text{m?}\text{1}\text{2}\text{k(k+1)?N}$, where 2N is the maximal number of (off-diagonal) entries which equal zero in a nonsingular principal submatrix of A. An example is given where the least m which works is $\text{(k+1)}{}^2\text{4}$ (k odd),$\text{k(k+2)}\text{4}$ (k even).     

Extensions of the Ostrowski-Reich theorem for SOR iterations

The Ostrowski-Reich theorem states that for a system Ax =b of linear equations with A nonsingular, if A is hermitian and if the diagonal of A is positive, then the SOR method converges for each relaxation parameter in (0,2) if and only if A is positive definite. This is actually a special case of the Householder-John theorem, which states that for A=M?N with A,M nonsingular, if A is hermitian and $\text{M}{}^1\text{+N}$ is positive definite, then M^?1N is a convergent matrix if and only if A is positive definite. Our purposes here are to generalize the Householder-John theorem and to provide an insight into how and why the SOR method can converge. As a result the Ostrowski-Reich theorem is extended in two directions; one is when A is hermitian but the diagonal of A is not necessarily positive, so that A is not necessarily positive definite, and the other is when $\text{A+A}{}^1$ is positive definite but A is not necessarily hermitian. In the process, several other convergence results are obtained for general splittings of A. However, no claims are made concerning the case in which the convergence results obtained here can be applied to practical situations.     

A generalization of the fast LUP matrix decomposition algorithm and applications

We show that any m × n matrix A, over any field, can be written as a product, LSP, of three matrices, where L is a lower triangular matrix with l's on the main diagonal, S is an m × n matrix which reduces to an upper triangular matrix with nonzero diagonal elements when the zero rows are deleted, and P is an n × n permutation matrix. Moreover, L, S, and P can be found in O(m^α?1n) time, where the complexity of matrix multiplication is O(m^α). We use the LSP decomposition to construct fast algorithms for some important matrix problems. In particular, we develop O(m^α?1n) algorithms for the following problems, where A is any m × n matrix: (1) Determine if the system of equations $\text{A}\text{x}\text{=}\text{b}$ (where $\text{b}$ is a column vector) has a solution, and if so, find one such solution. (2) Find a generalized inverse, $\text{A}{}^1$, of A (i.e., $\text{AA}{}^1\text{A = A}$). (3) Find simultaneously a maximal independent set of rows and a maximal independent set of columns of A.     

On the square roots of strictly quasiaccretive complex matrices

The square roots of a complex n×n matrix A for which the real part of e^ixA, where $\text{χ?[}\text{?π}\text{2}\text{,}\text{π}\text{2}\text{]}$, is positive definite are investigated. It is shown, for example, that when $\text{χ=}\text{?π}\text{2}$ (i.e., A is strictly dissipative), A has a unique square root whose real and imaginary parts are both positive definite.     

Generalized inverse-positivity and splittings of M-matrices

The concepts of matrix monotonicity, generalized inverse-positivity and splittings are investigated and are used to characterize the class of all M-matrices A, extending the well-known property that A^?1?0 whenever A is nonsingular. These conditions are grouped into classes in order to identify those that are equivalent for arbitrary real matrices A. It is shown how the nonnegativity of a generalized left inverse of A plays a fundamental role in such characterizations, thereby extending recent work by one of the authors, by Meyer and Stadelmaier and by Rothblum. In addition, new characterizations are provided for the class of M-matrices with “property c”; that is, matrices A having a representation A=sI?B, s>0, B?0, where the powers of $\text{(}\text{1}\text{s}\text{)B}$ converge. Applications of these results to the study of iterative methods for solving arbitrary systems of linear equations are given elsewhere.     

On the convergence of the Neumann series in interval analysis

Let $\text{A}$ be a real or complex n × n interval matrix. Then it is shown that the Neumann series $\text{Σ}{}^{\mathrm{\infty }}{}_{\mathrm{k=0}}\text{A}{}^{\mathrm{k}}$ is convergent iff the sequence {$\text{A}$^k} converges to the null matrix $\text{O}$, i.e., iff the spectral radius of the real comparison matrix $\text{B}$ constructed in [2] is less than one.     

Retarded equations on the sphere induced by linear equations

Using a Poincaré compactification, the linear homogeneous system of delay equations {x = Ax(t ? 1) (A is an n × n real matrix) induces a delay system π(A) on the sphere Sⁿ. The points at infinity belong to an invariant submanifold S^{n ? 1} of Sⁿ. For an open and dense set of 2 × 2 matrices A with distinct eigenvalues, the system π(A) has only hyperbolic critical points (including the critical points at infinity). For an open and dense set of 2 × 2matrices $\text{A}$ with complex eigenvalues, the nonwandering set at infinity is the union of an odd number of hyperbolic periodic orbits; if $\text{(}\text{det}\text{A}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{<}\text{3π}\text{2}$, the restriction of $\text{π(}\text{A}\text{)}$ to S¹ is Morse-Smale. For n = 1 there exist periodic orbits of period 4 provided that $\text{?A >}\text{π}\text{2}$ and Hopf bifurcation of a center occurs for ?A near $\text{(}\text{π}\text{2}\text{) + 2kπ, k ? Z}$.     

Resonance in equations with a diagonal field

Let A be a real square matrix, and let J?$\text{R}$ be an interval not containing an eigenvalue of A. Is A–D nonsingular for all diagonal matrices D with entries d_i ∈J? This holds if A is symmetric, but is not true in general. We prove a necessary condition and indicate implications for an equation with a diagonal field.     

On the Minimum Value of the Permanent of a Nearly Decomposable Doubly Stochastic Matrix

Let A be a minimizing matrix for the permanent over the face of Ω_n determined by a fully indecomposable matrix. It is shown that A is fully indecomposable and positive elements of A have permanental minors equal to per(A). Furthermore a zero entry of A has its permanental minor greater than or equal to per(A), provided that same element of the face has its corresponding entry positive. For 2?n?9 the minimum value of the permanent of a nearly decomposable $\text{A∈Ω}{}_{\mathrm{n}}$ is $\text{1}\text{2}{}^{\mathrm{n-1}}$.     

On the dispersion matrix of a matrix quadratic form connected with the noncentral Wishart distribution

Recently Magnus and Neudecker [3] derived the dispersion matrix of vec X′X, when X′ is a p × n random matrix (n > p) and vec X′ has the distribution $\text{N}{}_{\mathrm{np}}\text{(vec M′, I}{}_{\mathrm{n}}\text{? V)}$. This note is concerned with the matrix quadratic form X′AX, where X′ is a defined above and A is a nonrandom (not necessarily symmetric) matrix. The dispersion matrix of vec X′AX is then derived by applying results of Magnus and Neudecker [3] and Neudecker and Wansbeek [4]. This generalizes an earlier result of Giguère and Styan [2] which assumes a symmetric A.     

On the Schur multiplier norm of matrices

The Schur product of two n×n complex matrices A=(a_ij), B=(b_ij) is defined by A°B=(a_ijb_ij. By a result of Schur [2], the algebra of n×n matrices with Schur product and the usual addition is a commutative Banach algebra under the operator norm (the norm of the operator defined on $\text{C}$ⁿ by the matrix). For a fixed matrix A, the norm of the operator B?A°B on this Banach algebra is called the Schur multiplier norm of A, and is denoted by ∥A∥^m. It is proved here that $\text{∥A∥=∥U}{}^1\text{AU∥}{}_{\mathrm{m}}$ for all unitary U (where ∥·∥ denotes the operator norm) iff A is a scalar multiple of a unitary matrix; and that ∥A∥_m=∥A∥ iff there exist two permutations P, Q, a p×p (1?p?n) unitary U, an (n?p)×(n?p)1 contraction C, and a nonnegative number λ such that

$\text{A=λP}\text{U}\text{0}\text{0}\text{C}\text{Q;}$

and this is so iff $\text{∥A°}\text{A}\text{?}\text{∥=∥A∥}{}^2$, where ā is the matrix obtained by taking entrywise conjugates of A.     

Doubly stochastic matrices with equal subpermanents

It has been conjectured that if A is a doubly stochastic n>× n matrix such that per A(i, j)≥perA for all i, j, then either A = J_n, then n × n matrix with each entry equal to $\text{1}\text{n}$, or, up to permutations of rows and columns, $\text{A =}\text{1}\text{2}\text{(I}{}_{\mathrm{n}}\text{+ P}{}_{\mathrm{n}}\text{)}$, where P_n is a full cycle permutation matrix. This conjecture is proved.     

A note on matrix subalgebras containing a full Jordan block

Let A be a subalgebra of the full matrix algebra M_n(F), and suppose J∈A, where J is the Jordan block corresponding to xⁿ. Let $\text{S}$ be a set of generators of A. It is shown that the graph of $\text{S}$ determines whether A is the full matrix algebra M_n(F).     

Geometry of the numerical range of matrices

Some techniques for the study of the algebraic curve C(A) which generates the numerical range W(A) of an n×n matrix A as its convex hull are developed. These enable one to give an explicit point equation of C(A) and a formula for the curvature of C(A) at a boundary point of W(A). Applied to the case of a nonnegative matrix A, a simple relation is found between the curvature of the function Φ(A)=p((1?α)A+ αA^T) (pbeingthePerronroot) at $\text{α=}\text{1}\text{2}$ and the curvature of W(A) at the Perron root of $\text{1}\text{2}\text{(A+A}{}^{\mathrm{T}}\text{)}$. A connection with 2-dimensional pencils of Hermitian matrices is mentioned and a conjecture formulated.     

Spaces of matrices of equal rank

Let M_m,n(F) denote the space of all mXn matrices over the algebraically closed field F. A subspace of M_m,n(F), all of whose nonzero elements have rank k, is said to be essentially decomposable if there exist nonsingular mXn matrices U and V respectively such that for any element A, UAV has the form

$\text{UAV=}\text{A}{}_1\text{A}{}_2\text{A}{}_3\text{0}$

where A₁ is iX(k–i) for some i?k. Theorem: If $\text{K}$ is a space of rank k matrices, then either $\text{K}$ is essentially decomposable or dim $\text{K}$?k+1. An example shows that the above bound on non-essentially-decomposable spaces of rank k matrices is sharp whenever n?2k–1.     

Common solutions to the Lyapunov equations

Let A be an n×n matrix with complex entries. A necessary and sufficient condition is established for the existence of a Hermitian solution H to the equations

$\text{AH+HA}{}^1\text{=HA+A}{}^1\text{H=I}$

.