Real eigenvalues of nonnegative matrices which commute with a symmetric matrix involution

It is well known that if P is a nonnegative matrix, then its spectral radius is an eigenvalue of P (Perron-Frobenius theorem). In this paper it is shown that if P is an n × n nonnegative matrix and it commutes with a nonnegative symmetric involution when n=4m+3, then (1) P has at least two real eigenvalues if n=4m or 4m + 2, (2) P has at least one real eigenvalue if n=4m+1, and (3) P has at least three real eigenvalues if n=4m+3, where m is a nonnegative integer and n ? 1. Examples are given to show that these results are the best possible, and nonnegative symmetric involutions are classified.     

Matrices permutation equivalent to primitive matrices

We give a necessary and sufficient condition for an n×n (0,1) matrix (or more generally, an n×n nonnegative matrix) to be permutation equivalent to a primitive matrix. More precisely, except for two simple permutation equivalent classes of n×n (0,1) matrices, each n×n (0,1) matrix having no zero row or zero column is permutation equivalent to some primitive matrix. As an application, we use this result to characterize the subsemigroup of B_n (B_n is the multiplicative semigroup of n×n Boolean matrices) generated by all the primitive matrices and permutation matrices. We also consider a more general problem and give a necessary and sufficient condition for an n×n nonnegative matrix to be permutation equivalent to an irreducible matrix with given imprimitive index.     

Products of irreducible matrices

In this paper we characterize the subsemigroup of B_n (B_n is the multiplicative semigroup of n × n Boolean matrices) generated by all the irreducible matrices, and hence give a necessary and sufficient condition for a Boolean matrix A to be a product of irreducible Boolean matrices. We also give a necessary and sufficient condition for an n × n nonnegative matrix to be a product of nonnegative irreducible matrices.     

On the exponent of a primitive digraph

We characterize the equality case of the upper bound $\text{γ(D) ? n + s(n ? 2)}$ for the exponent of a primitive digraph in the case s ? 2, where n is the number of the vertices of the digraph D and s is the length of the shortest elementary circuit of D. We also answer a question about the equality case when s = 1. The exponent of an n × n primitive nonnegative matrix A is the same as the exponent of the associated digraph D(A) of A. So every theorem in this paper can be translated into a theorem about nonnegative matrices.     

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.     

Factorization of nonnegative matrices—II

Suppose A is an n×n nonnegative matrix. Necessary and sufficient conditions are given for A to be factored as LU, where L is a lower triangular nonnegative matrix, and U is an upper triangular nonnegative matrix with u_ii = 1.     

The nonnegative rank factorizations of nonnegative matrices

Let A ∈ P^{m × n}_r, the set of all m × n nonnegative matrices having the same rank r. For matrices A in P^{m × n}_n, we introduce the concepts of “A has only trivial nonnegative rank factorizations” and “A can have nontrivial nonnegative rank factorizations.” Correspondingly, the set P^{m × n}_n is divided into two disjoint subsets P₍₁₎ and P₍₂₎ such that P₍₁₎∪P₍₂₎ = P^{m × n}_n. It happens that the concept of “A has only trivial nonnegative rank factorizations” is a generalization of “A is prime in P^{n × n}_n.” We characterize the sets P₍₁₎ and P₍₂₎. Some of our results generalize some theorems in the paper of Daniel J. Richman and Hans Schneider [9].     

A general theory of measures for nonnegative matrices

By a measure μ on the set N of m × n nonnegative matrices we mean that μ is a function from N to the nonnegative reals such that (i) μ(λA)=λμ(A) for all nonnegative λ and all A ∈ N, and (ii) μ(A + B) ? μ(A) for all A,B ? N. This paper develops a theory of such measures and shows how this theory can be applied to particular problems.     

Nonnegative sectional curvature hypersurfaces in a real space form

In this paper, we investigate the nonnegative sectional curvature hypersurfaces in a real space form M ⁿ⁺¹(c). We obtain some rigidity results of nonnegative sectional curvature hypersurfaces M ⁿ⁺¹(c) with constant mean curvature or with constant scalar curvature. In particular, we give a certain characterization of the Riemannian product S ^k (a) × S ^n-k (√1 ? a ²), 1 ≤ k ≤ n ? 1, in S ⁿ⁺¹(1) and the Riemannian product H ^k (tanh² r ? 1) × S ^n-k (coth² r ? 1), 1 ≤ k ≤ n ? 1, in H ⁿ⁺¹(?1).     

Strong shift equivalence and shear adjacency of nonnegative square integer matrices

For two square matrices A, B of possibly different sizes with nonnegative integer entries, write A ≈₁ B if A = RS and B = SR for some two nonnegative integer matrices R,S. The transitive closure of this relation is called strong shift equivalence and is important in symbolic dynamics, where it has been shown by R.F. Williams to characterize the isomorphism of two topological Markov chains with transition matrices A and B. One invariant is the characteristic polynomial up to factors of λ. However, no procedure for deciding strong shift equivalence is known, even for 2×2 matrices A, B. In fact, for n × n matrices with n > 2, no nontrivial sufficient condition is known. This paper presents such a sufficient condition: that A and B are in the same component of a directed graph whose vertices are all n × n nonnegative integer matrices sharing a fixed characteristic polynomial and whose edges correspond to certain elementary similarities. For n > 2 this result gives confirmation of strong shift equivalences that previously could not be verified; for n = 2, previous results are strengthened and the structure of the directed graph is determined.     

Positive orthant scalar controllability of bilinear systems

For the bilinear control system $\dot x = \left( {A + uB} \right)x$ ,x ∈ ? ⁿ ,u ∈ ?, whereA is ann ×n essentially nonnegative matrix, andB is a diagonal matrix, the following controllability problem is investigated: can any two points with positive coordinates be joined by a trajectory of the system? Forn>2, the answer is negative in the generic case: hypersurfaces in ? ⁿ are constructed that are intersected by all the trajectories of the system in one direction.     

Monomial patterns in the sequence Akb

We consider the pattern of zero and nonzero elements in the sequence A^kb, where A is an n × n nonnegative matrix and b is an n × 1 nonnegative column vector. We establish a tight bound of k < n for the first occurrence of a given monomial pattern, and we give a graph theoretic characterization of triples (A, b, i) such that there exists a k, k ⩾ n, for which A^kb is an i-monomial. The appearance of monomial patterns with a single nonzero entry is linked to controllability of discrete n-dimensional linear dynamic systems with positivity constraints on the state and control.     

Lower bounds on the spectra of symmetric matrices with nonnegative entries

If we normalize a symmetric n × n matrix with nonnegative entriesso that its largest entry is 1, then its spectrum is bounded below by $\text{?n}\text{2}$. The lower bound is achieved in all even dimensions for (and only for) adjacency matrices of complete bipartite graphs with equal parts.     

A relationship between stochastic matrices and eigenvalues of products

Let {B₁,…,B_n} be a set of n rank one n×n row stochastic matrices. The next two statements are equivalent: (1) If A is an n×n nonnegative matrix, then 1 is an eigenvalue ofB_kA for each k=1,…,n if and only if A is row stochastic. (2) The n×n row stochastic matrix S whose kth row is a row of B_k for k=1,…,n is nonsingular. For any set {B₁, B₂,…, B_p} of fewer than n row stochastic matrices of order n×n and of any rank, there exists a nonnegative n×n matrix A which is not row stochastic such that 1 is eigenvalue of every B_kA, k=1,…,p.     

On inverse spectrum problems for normal nonnegative matrices

For a set σ with n complex numbers, some sufficient conditions are found for σ to be the spectrum of an n ×n normal (entrywise) nonnegative (positive) matrix. After proving a fundamental theorem and introducing the companion set σ′ of σ which consists of real numbers, we prove that if σ′ satisfies any known sufficient conditions for a real set to be the spectrum of a nonnegative matrix introduced by Suleimanova, Perfect, Salzmann and Kellogg respectively, then σ is the spectrum of an n×n normal nonnegative matrix.     

Nonnegativity of principal minors of generalized inverses of M-matrices

The result of principal interest established in this paper is that if A is an n × n singular irreducible M-matrix, then a large class of generalized inverses of A possesses the property that each of its elements has all its principal minors nonnegative. The class contains both the group and the Moore-Penrose generalized inverses of A. In an application of our results it is shown that the fundamental matrix of a continuous (in time) ergodic Markov chain on a finite state space has all its principal minors nonnegative.     

A matrix of permanents

If A is a matrix of order n×(n?2), n?3, denote by ā the n×n matrix whose (i,j)th entry is zero if i=j, and if i≠j, is the permanent of the submatrix of A obtained by deleting its ith and jth rows. It is shown that if A is a nonnegative n×(n?2) matrix, then ā is nonsingular if and only if A has no zero submatrix of n?1 lines. This is used to give precise consequences of the occurrence of equality in Alexandroff's inequality.     

Characterizations of products of symmetric matrices

Characterizations are obtained for matrices C of the form C = AΣ, where A, Σ are n×n matrices over the real field such that A is symmetric and C is nonnegative definite. Among others, a proof of recent generalization of Cochran's theorem is given.     

On approximation by polynomials increasing to the right of the interval

We obtain sufficient conditions on a real valued function ?, continuous on [0, + ∞), to insure that, for some nonnegative integer n, there is a nonnegative number r(n) so that for any r ? r(n), the polynomial of best approximation to ? on [0, r] from π_n is increasing and nonnegative on [r, + ∞). Here, π_n denotes the set of all real polynomials of degree n or less. The proofs of Theorems 1 and 2 use only properties of Lagrange interpolation while that of Theorem 3 employs results on the location of interpolation points in Chebyshev approximation.