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.     

Uniqueness for algebraically regular solutions to pathological differential equations

A uniqueness theorem is proved for algebraically regular solutions to the unbounded initial value problem P′ = AP, P(0) = diag(1, 1, 1,…) in the real Banach algebra of infinite matrices $\text{M}$ with standard norm. It is not assumed that $\text{A}$ ∈ $\text{M}$, but it is required that A have an inverse in $\text{M}$, a property which is seen to be implied quite naturally by certain divergent or pathological systems. The conditions for the theorem are motivated by a particular system, previously considered by Hille and Feller, which arises from a divergent, purebirth, time dependent stochastic process, although no restriction requiring the solution matrix to be either stochastic or substochastic is necessary.The theorem may be easily generalized to any Banach algebra with identity.     

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 existence and exactness of the associated sheaf functor

Let $\text{C}$ be a category with inverse limits. A category $\text{x}$is called an $\text{A}$-topos if there is a site (?, τ), i.e. a small category ? together with a Grothendieck topology τ such that $\text{x}$is equivalent to the category Sh_τ[$\text{C}$⁰. $\text{A}$] of τ-sheaves on $\text{C}$ with values in $\text{C}$. If $\text{x}$is an $\text{C}$-topos, then so is Sh_τ'[?⁰, $\text{x}$] for any site (?', τ'). It is shown that if for every site (?,τ) the associated sheaf functor from presheaves to τ-sheaves with values in $\text{A}$ exists (and preserves finite inverse limits), then the same holds if $\text{A}$is replaced by any $\text{A}$-topos $\text{x}$. Roughly speaking, the main result is that for a site (?,τ) the associated sheaf functor [?⁰, $\text{A}$] → Sh_τ [?⁰, $\text{A}$] exists and preserves finite inverse limits, provided $\text{A}$ has filtered direct limits which commute with finite inverse limits, e.g. if $\text{A}$ is a Grothendieck category or a category of sheaves with values in a locally finitely presentable category [8. 7.1]. Analogous results hold in the additive case.     

Overdetermined linear systems satisfying nonnegativity constraints

Let A be a nonnegative m × n matrix, and let b be a nonnegative vector of dimension m. Also, let S be a subspace of $\text{R}$ⁿ such that if P_S is the orthogonal projector onto S, then P_S ? 0. A necessary condition is given for the matrix A to satisfy the following property: For all b ? 0, if min[boxV]b ? Ax[boxV] is attained at x = x₀, then x₀ ? 0 and x₀ ? S. It is also shown that if a nonnegative matrix A has a nonnegative generalized inverse, then any submatrix of A also possesses a nonnegative generalized inverse.     

The rank of a difference of matrices and associated generalized inverses

Various representations are given to characterize the rank of A-S in terms of rank A+k where A and S are arbitrary complex matrices and k is a function of A and S. It is shown that if S=AMA for some matrix M, and if G is any matrix satisfying A=AGA, then

$\text{rank(A-S) = rankA-nullity (I-SG)}$

. Several alternative forms of this result are established, as are many equivalent conditions to have

$\text{rank(A-S) = rankA-rankS}$

. General forms for the Moore-Penrose inverse of matrices A-S are developed which include as special cases various results by Penrose, Wedin, Hartwig and others.     

Smoothness of spectral subbundles and reducibility of quasi-periodic linear differential systems

In this paper we study linear differential systems (1) $\text{x′ =}\text{A}\text{?}\text{(θ + ωt)x,}\text{where}\text{A}\text{?}\text{(θ)}\text{is an}\text{(n × n)}$ matrix-valued function defined on the k-torus T^k and (θ, t) → θ + ωt is a given irrational twist flow on T^k. First, we show that if A ? C^N(T^k), where N ? {0, 1, 2,…; ∞; ω}, then the spectral subbundles are of class C^N on T^k. Next we assume that à is sufficiently smooth on T^k and ω satisfies a suitable “small divisors” inequality. We show that if (1) satisfies the “full spectrum” assumption, then there is a quasi-periodic linear change of variables x = P(t)y that transforms (1) to a constant coefficient system y′ =By. Finally, we study the case where the matrix $\text{A}\text{?}\text{(θ + ωt)}$ in (1) is the Jacobian matrix of a nonlinear vector field $\text{?(x)}$ evaluated along a quasi-periodic solution x = φ(t) of (2) $\text{x′ = ?(x)}$. We give sufficient conditions in terms of smoothness and small divisors inequalities in order that there is a coordinate system (z, ?) defined in the vicinity of $\text{Ω = H(φ)}$, the hull of φ, so that the linearized system (1) can be represented in the form z′ = Dz, ?′ = ω, where D is a constant matrix. Our results represent substantial improvements over known methods because we do not require that à be “close to” a constant coefficient system.     

On the spectra of a family of positive matrices

It is shown that every positive matrix A can be embedded in an analytic family of positive matrices {A(ν) : ν∈$\text{R}$} in such a way that A(1)=A, $\text{A(0)≡}\text{A}\text{?}$ is symmetric, and A(-1)=A^T. A necessary and sufficient condition that A and Å have the same maximal eigenvalue and that their ergodic limits have the same diagonal elements is stated and proved.     

Unit integer quadratic binary programming

This paper presents an efficient method of computing $\text{?′}{}_{\mathrm{<mtext>max</mtext>}}\text{=}\text{max}\text{Y}\text{Y}{}^{\mathrm{<mtext>T</mtext>}}\text{AY}$, where Y is an N-dimensional vector of ±1 entries and A is a real symmetric matrix. The ratio of number of computations required by this method to that by the direct method is approximately ($\text{3}\text{2N}$), where the direct method corresponds to computing Y^TAY for all possible Y and then finding the maximum from these. This problem has important applications in operations research, matrix theory, signal processing, communication theory, control theory, and others. Some of these are discussed in this paper.     

A generalization of Lavoie's inequality concerning the sum of idempotent matrices

Let a complex pxn matrix A be partitioned as A′=(A′₁,A′₂,…,A′_k). Denote by ?(A), A′, and A^? respectively the rank of A, the transpose of A, and an inner inverse (or a g-inverse) of A. Let A⁽¹⁴⁾ be an inner inverse of A such that A⁽¹⁴⁾A is a Hermitian matrix. Let B=(A⁽¹⁴⁾₁,A⁽¹⁴⁾₂,…,A_k⁽¹⁴⁾) and $\text{ρ(A)=}\text{∑}\text{i=1}\text{k}\text{ρ(A}{}_{\mathrm{i}}\text{)}$.Then the product of nonzero eigenvalues of BA (or AB) cannot exceed one, and the product of nonzero eigenvalues of BA is equal to one if and only if either B=A⁽¹⁴⁾ or $\text{A}{}_{\mathrm{i>}}\text{A}{}_{\mathrm{<mtext>j</mtext>}}{}^1\text{=0}$ for all i ≠ j,i, j=1,2,…,k . The results of Lavoie (1980) and Styan (1981) are obtained as particular cases. A result is obtained for k=2 when the condition $\text{ρ(A)=}\text{∑}\text{i=1}\text{k}\text{ρ(A}{}_{\mathrm{i}}\text{)}$ is no longer true.     

Schur complements and statistics

In this paper we discuss various properties of matrices of the type

$\text{S}\text{=}\text{H}\text{?}\text{GE}{}^{\mathrm{?1}}\text{F}$

, which we call the Schur complement of E in

$\text{A}\text{=}\text{E}\text{F}\text{G}\text{H}$

The matrix E is assumed to be nonsingular. When E is singular or rectangular we consider the generalized Schur complements $\text{S}\text{=}\text{H}\text{?}\text{GE}{}^{\mathrm{?}}\text{F}$, where E^? is a generalized inverse of E. A comprehensive account of results pertaining to the determinant, the rank, the inverse and generalized inverses of partitioned matrices, and the inertia of a matrix is given both for Schur complements and for generalized Schur complements. We survey the known results in a historical perspective and obtain several extensions. Numerous applications in numerical analysis and statistics are included. The paper ends with an exhaustive bibliography of books and articles related to Schur complements.     

On the theory of semigroups of operators on locally convex spaces

The behavior of strongly continuous one-parameter semigroups of operators on locally convex spaces is considered. The emphasis is placed on semigroups that grow too rapidly to be treated by classical Laplace transform methods.A space

of continuous E-valued functions is defined for a locally convex space E, and the generalized resolvent $\text{R}$ of an operator A on E is defined as an operator on

. It is noted that $\text{R}$ may exist when the classical resolvent (λ ? A)^?1 fails to exist. Conditions on $\text{R}$ are given that are necessary and sufficient to guarantee that A is the generator of a semigroup T(t). The action of $\text{R}$ is characterized by convolution against the semigroup, and the semigroup is computed as the limit of $\text{R}$ acting on an approximate identity.Conditions on an operator B are introduced that are sufficient to guarantee that A + B is the generator of a semigroup whenever A is. A formula is given for the perturbed semigroup.Two characterizations of semigroups that can be extended holomorphically into some sector of the complex plane are given. One is in terms of the growth of the derivative $\text{(}\text{d}\text{dt}\text{) T(t)}$ as t approaches 0, the other is in terms of the behavior of $\text{R}$ⁿ, the powers of the generalized resolvent.Throughout, the generalized resolvent plays a role analogous to the role of the classical resolvent in the work of Hille, Phillips, Yosida, Miyadera, and others.     

On matrices having equal corresponding principal minors

Let A, B be n × n matrices with entries in a field F. We say A and B satisfy property $\text{D}$ if B or B^t is diagonally similar to A. It is clear that if A and B satisfy property $\text{D}$, then they have equal corresponding principal minors, of all orders. The question is to what extent the converse is true. There are examples which show the converse is not always true. We modify the problem slightly and give conditions on a matrix A which guarantee that if B is any matrix which has the same principal minors as A, then A and B will satisfy property $\text{D}$. These conditions on A are formulated in terms of ranks of certain submatrices of A and the concept of irreducibility.     

On maximizing det (ATA)

Let A be an n × p matrix of ± 1's, n ? p. The problem considered is the destination of the maximal value of det(A^TA). The complete solution is given for p ? 4, and for $\text{p = 5, n}\text{x}\text{?}\text{2}$ (mod 4) if the Hadamard conjecture is true. For p > 5, the maximum value is determined for n sufficiently large compared to p and provided certain Hadamard matrices exist.     

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.     

Inverse matrix representation with one triangular array

We describe a technique that permits the representation of the inverse of a matrix A with only one additional triangular array. Let $\text{L1A = U}$, with L lower and U upper triangular arrays of order N. Algorithms are presented that use A and L to compute the matrix-vector products $\text{A}{}^{-1}\text{1b}$ and $\text{b}{}^{\mathrm{T}}\text{1A}{}^{-1}$ with N² multiplications and additions. The array L can be computed, with N³/3 multiplications, with a technique that avoids the computation of U. Standard Gaussian elimination simultaneously computes L and U as follows: start with $\text{I1A = A}$, where I is the identity matrix; perform identical linear combinations of rows on I and on the right hand side array A; gradually transform I into L and A into U. At an intermediate stage, where A has not yet been fully triangularized, we have $\text{L′1A = U′.L′}$ and Ú represent one of the pairs of arrays present before each linear combination of rows is performed. The key observation is that we only need two elements of Ú to compute each linear combination of rows of ?. Compute them with a scalar product of the appropriate rows of ? and columns of A. Instead of storing the arrays Ú, recompute their few needed elements whenever necessary.     

A Euler-Poincaré characteristic for the open set lattices of finite topologies

Let $\text{T}$ be a finite topology. If P and Q are open sets of $\text{T}$ (Q may be the null set) then P is a minimal cover of Q provided Q ? P and there does not exist any open set R of $\text{T}$ such that Q ? R ? P. A subcollection $\text{D}$ of the open sets of $\text{T}$ is termed an i-discrete collection of $\text{T}$ provided $\text{D}$ contains every open O ∈ $\text{T}$ with the property that ? $\text{D}$ ? O ? ? $\text{D}$, $\text{D}$ contains exactly i minimal covers of ? $\text{D}$, and provided ?$\text{D}$ = ?{O | O ∈ $\text{D}$ and O is a minimal cover of ? $\text{D}$}. A single open set is a O-discrete collection. The number of distinct i-discrete collections of $\text{T}$ is denoted by p($\text{T}$, i). If there does not exist any i-discrete collection then p($\text{T}$,i) = 0, and this happens trivially for the case when i is greater than the number of points on which $\text{T}$ is defined. The object of this article is to establish the theorem: For any finite topology $\text{T}$, the quantity E($\text{T}$) = Σ_{i = 0}^∞ (?1)ⁱp($\text{T}$, i) = 1.