Nonnegative matrices having nonnegative Drazin pseudoinverses

Necessary and sufficient conditions for nonnegative matrices having nonnegative Drazin pseudoinverses are obtained. A decomposition theorem which characterizes the class of all nonnegative matrices with nonnegative Drazin pseudoinverses is proved, thus answering a question raised by several people. It is also shown that if a row (or column) stochastic matrix has a nonnegative Drazin pseudoinverse A(^d), then A(^d) is some power of A. These results extend known results for nonnegative group-monotone matrices.     

Nonnegative (s, t)-potent matrices

This paper contains a study of matrices satisfying A^s = A^t for different positive integers s and t. Representations, similar to Flor's well-known characterization of a nonnegative idempotent matrix, are obtained for nonnegative matrices of this type.     

Real rank versus nonnegative rank

We consider the set of m×n nonnegative real matrices and define the nonnegative rank of a matrix A to be the minimum k such that A=BC where B is m×k and C is k×n. Given that the real rank of A is j for some j, we give bounds on the nonnegative rank of A and A².     

On Some Ordering Properties of the Generalized Inverses of Nonnegative Definite Matrices

For any positive definite matrices A and B, it is known that A?B iff B^-1?A^-1. This paper investigates the extensions of the above result to any two real nonnegative definite matrices A and B.     

The scrambling index of symmetric primitive matrices

A nonnegative square matrix A is primitive if some power A^k>0 (that is, A^k is entrywise positive). The least such k is called the exponent of A. In [2], Akelbek and Kirkland defined the scrambling index of a primitive matrix A, which is the smallest positive integer k such that any two rows of A^k have at least one positive element in a coincident position. In this paper, we give a relation between the scrambling index and the exponent for symmetric primitive matrices, and determine the scrambling index set for the class of symmetric primitive matrices. We also characterize completely the symmetric primitive matrices in this class such that the scrambling index is equal to the maximum value.     

On visualization scaling, subeigenvectors and Kleene stars in max algebra

The purpose of this paper is to investigate the interplay arising between max algebra, convexity and scaling problems. The latter, which have been studied in nonnegative matrix theory, are strongly related to max algebra. One problem is that of strict visualization scaling, defined as, for a given nonnegative matrix A, a diagonal matrix X such that all elements of X^-1AX are less than or equal to the maximum cycle geometric mean of A, with strict inequality for the entries which do not lie on critical cycles. In this paper such scalings are described by means of the max algebraic subeigenvectors and Kleene stars of nonnegative matrices as well as by some concepts of convex geometry.     

A conforming decomposition theorem,a piecewise linear theorem of the alternative,and scalings of matrices satisfying lower and upper bounds

A scaling of a nonnegative matrixA is a matrixXAY ^?1, whereX andY are nonsingular, nonnegative diagonal matrices. Some condition may be imposed on the scaling, for example, whenA is square,X=Y or detX=detY. We characterize matrices for which there exists a scaling that satisfies predetermined upper and lower bound. Our principal tools are a piecewise linear theorem of the alternative and a theorem decomposing a solution of a system of equations as a sum of minimal support solutions which conform with the given solutions.     

Tight bounds on the spectral radius of asymmetric nonnegative matrices

For an arbitrary asymmetric nonnegative n × n matrix A we identify a pair of symmetric matrices whose largest eigenvalues bound the spectral radius of A. Furthermore, we show that these bounding matrices are best possible by characterizing matrices A which attain equality with either the upper or the lower bounding matrix. The lower bound may be extended to some matrices with negative entries provided they have no negative cycles.     

On powers of nonnegative matrices

We investigate the structure of powers of nonnegative matrices A, and in particular characterize those A for which some power is (essentially) triangular. We also show how the number of irreducible components of A can be determined from its powers.     

Rational realization of the minimum ranks of nonnegative sign pattern matrices

A sign pattern matrix (or nonnegative sign pattern matrix) is a matrix whose entries are from the set {+,?, 0} ({+, 0}, respectively). The minimum rank (or rational minimum rank) of a sign pattern matrix A is the minimum of the ranks of the matrices (rational matrices, respectively) whose entries have signs equal to the corresponding entries of A. Using a correspondence between sign patterns with minimum rank r ≥ 2 and point-hyperplane configurations in R^r?1 and Steinitz’s theorem on the rational realizability of 3-polytopes, it is shown that for every nonnegative sign pattern of minimum rank at most 4, the minimum rank and the rational minimum rank are equal. But there are nonnegative sign patterns with minimum rank 5 whose rational minimum rank is greater than 5. It is established that every d-polytope determines a nonnegative sign pattern with minimum rank d + 1 that has a (d + 1) × (d + 1) triangular submatrix with all diagonal entries positive. It is also shown that there are at most min{3m, 3n} zero entries in any condensed nonnegative m × n sign pattern of minimum rank 3. Some bounds on the entries of some integer matrices achieving the minimum ranks of nonnegative sign patterns with minimum rank 3 or 4 are established.     

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].     

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.     

A rank characterization of the number of final classes of a nonnegative matrix

Let A be a nonnegative square matrix, and let D be a diagonal matrix whose iith element is $\text{(Ax)}{}_{\mathrm{i}}\text{x}{}_{\mathrm{i}}$, where x is a (fixed) positive vector. It is shown that the number of final classes of A equals n?rank(A?D). We also show that null(A?D) = null(A?D)², and that this subspace is spanned by a set of nonnegative elements. Our proof uses a characterization of nonnegative matrices having a positive eigenvector corresponding to their spectral radius.     

Equilibrants, semipositive matrices, calculation and scaling

For square, semipositive matrices A (Ax>0 for some x>0), two (nonnegative) equilibrants e(A) and E(A) are defined. Our primary goal is to develop theory from which each may be calculated. To this end, the collection of semipositive matrices is partitioned into three subclasses for each equilibrant, and a connection to those matrices that are scalable to doubly stochastic matrices is made. In the process a certain matrix/vector equation that is related to scalability of a matrix to one with line sums 1 is derived and discussed.     

On the spectral radius and the spectral norm of Hadamard products of nonnegative matrices

We prove the spectral radius inequality ρ(A₁°A₂°?°A_k)?ρ(A₁A₂?A_k) for nonnegative matrices using the ideas of Horn and Zhang. We obtain the inequality ‖A°B‖?ρ(A^TB) for nonnegative matrices, which improves Schur’s classical inequality ‖A°B‖?‖A‖‖B‖, where ‖·‖ denotes the spectral norm. We also give counterexamples to two conjectures about the Hadamard product.     

Structured nonnegative matrix factorization with applications to hidden Markov realization and clustering

In this paper, we study the structured nonnegative matrix factorization problem: given a square, nonnegative matrix P, decompose it as P=VAV^? with V and A nonnegative matrices and with the dimension of A as small as possible. We propose an iterative approach that minimizes the Kullback-Leibler divergence between P and VAV^? subject to the nonnegativity constraints on A and V with the dimension of A given. The approximate structured decomposition P?VAV^? is closely related to the approximate symmetric decomposition P?VV^?. It is shown that the approach for finding an approximate structured decomposition can be adapted to solve the symmetric decomposition problem approximately. Finally, we apply the nonnegative decomposition VAV^? to the hidden Markov realization problem and to the clustering of data vectors based on their distance matrix.     

Drazin-monotonicity characterizations for property-n matrices

A square matrix A is said to have property n if there exists a nonnegative power of A. In this paper, necessary and sufficient conditions for such matrices to have a nonnegative Drazin inverse are presented.     

Asymptotics of products of nonnegative random matrices

Asymptotic properties of products of random matrices ξ _k = X _k …X ₁ as k → ∞ are analyzed. All product terms X _i are independent and identically distributed on a finite set of nonnegative matrices A = {A ₁, …, A _m }. We prove that if A is irreducible, then all nonzero entries of the matrix ξ _k almost surely have the same asymptotic growth exponent as k→∞, which is equal to the largest Lyapunov exponent λ(A). This generalizes previously known results on products of nonnegative random matrices. In particular, this removes all additional “nonsparsity” assumptions on matrices imposed in the literature.We also extend this result to reducible families. As a corollary, we prove that Cohen’s conjecture (on the asymptotics of the spectral radius of products of random matrices) is true in case of nonnegative matrices.     

Nonnegative rank factorization—a heuristic approach via rank reduction

Given any nonnegative matrix $A \in \mathbb{R}^{m \times n}$ , it is always possible to express A as the sum of a series of nonnegative rank-one matrices. Among the many possible representations of A, the number of terms that contributes the shortest nonnegative rank-one series representation is called the nonnegative rank of A. Computing the exact nonnegative rank and the corresponding factorization are known to be NP-hard. Even if the nonnegative rank is known a priori, no simple procedure exists presently that is able to perform the nonnegative factorization. Based on the Wedderburn rank reduction formula, this paper proposes a heuristic approach to tackle this difficult problem numerically. Starting with A, the idea is to recurrently extrat, whenever possible, a rank-one nonnegative portion from the previous matrix while keeping the residual nonnegative and lowering its rank by one. With a slight modification for symmetry, the method can equally be applied to another important class of completely positive matrices. No convergence can be guaranteed, but repeated restart might help alleviate the difficulty. Extensive numerical testing seems to suggest that the proposed algorithm might serve as a first-step numerical means for exploring the intriguing problem of nonnegative rank factorization.