The difference between doubly nonnegative and completely positive matrices

The convex cone of n×n completely positive (CP) matrices and its dual cone of copositive matrices arise in several areas of applied mathematics, including optimization. Every CP matrix is doubly nonnegative (DNN), i.e., positive semidefinite and component-wise nonnegative, and it is known that, for n4 only, every DNN matrix is CP. In this paper, we investigate the difference between 5×5 DNN and CP matrices. Defining a bad matrix to be one which is DNN but not CP, we: (i) design a finite procedure to decompose any n×n DNN matrix into the sum of a CP matrix and a bad matrix, which itself cannot be further decomposed; (ii) show that every bad 5×5 DNN matrix is the sum of a CP matrix and a single bad extreme matrix; and (iii) demonstrate how to separate bad extreme matrices from the cone of 5×5 CP matrices.     

The completely positive and doubly nonnegative completion problems

We prove the following. Let G be an undirected graph. Every partially specified symmetric matrix, the graph of whose specified entries is G and each of whose fully specified submatrices is completely positive (equal to BB^T for some entrywise nonnegative matrix B), may be completed to a completely positive matrix if and only if G is a block-clique graph (a chordal graph in which distinct maximal cliques overlap in at most one vertex). The same result holds for matrices that are doubly nonnegative (entrywise nonnegative and positive semidefinite).     

Triangle-free graphs and completely positive matrices

Central European Journal of Operations Research - Completely positive matrices are matrices that can be decomposed as $$BB^T$$ , where B is an entrywise nonnegative matrix. These matrices have many...     

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

Combinatorial results on completely positive matrices

A sufficient condition for complete positivity of a matrix, in terms of complete positivity of smaller matrices, is given. Those patterns for which this condition is also necessary are characterized. These results are used to characterize complete positivity of matrices under some acyclicity assumptions on their graph. The exact value of the factorization index is given for acyche matrices.     

Nonnegative factorization of positive semidefinite nonnegative matrices

We give simple geometric proofs of the known results that, for n ?4, n × n nonnegative positive semidefinite matrices can be factored into n × n nonnegative factors and that, for n ? 5, these conditions are not sufficient to guarantee the existence of such a factorization.     

The critical exponent conjecture for powers of doubly nonnegative matrices

Doubly nonnegative matrices arise naturally in many setting including Markov random fields (positively banded graphical models) and in the convergence analysis of Markov chains. In this short note, we settle a recent conjecture by C.R. Johnson et al. [Charles R. Johnson, Brian Lins, Olivia Walch, The critical exponent for continuous conventional powers of doubly nonnegative matrices, Linear Algebra Appl. 435 (9) (2011) 2175–2182] by proving that the critical exponent beyond which all continuous conventional powers of n-by-n   doubly nonnegative matrices are doubly nonnegative is exactly n−2$n-2$. We show that the conjecture follows immediately by applying a general characterization from the literature. We prove a stronger form of the conjecture by classifying all powers preserving doubly nonnegative matrices, and proceed to generalize the conjecture for broad classes of functions. We also provide different approaches for settling the original conjecture.     

Chains of dog-ears for completely positive matrices

A necessary and sufficient condition to determine the complete positivity of a matrixwith a particular graph, in dependence of complete positivity of smaller matrices, is given. Under some singularity assumptions, this condition furnishes a characterization for completely positive matrices with a “non-crossing cycle” as associated graph. In particular the characterization holds for singular pentadiagonal matrices.     

Sets of nonnegative matrices with positive inhomogeneous products

Let X be a set of k×k matrices in which each element is nonnegative. For a positive integer n, let P(n) be an arbitrary product of n matrices from X, with any ordering and with repetitions permitted. Define X to be a primitive set if there is a positive integer n such that every P(n) is positive [i.e., every element of every P(n) is positive]. For any primitive set X of matrices, define the index g(X) to be the least positive n such that every P(n) is positive. We show that if X is a primitive set, then g(X)?2^k?2. Moreover, there exists a primitive set Y such that g(Y) = 2^k?2.     

The critical exponent for continuous conventional powers of doubly nonnegative matrices

We prove that there exists an exponent beyond which all continuous conventional powers of n-by-n doubly nonnegative matrices are doubly nonnegative. We show that this critical exponent cannot be less than n-2 and we conjecture that it is always n-2 (as it is with Hadamard powering). We prove this conjecture when n<6 and in certain other special cases. We establish a quadratic bound for the critical exponent in general.     

Factorization of cp-rank-3 completely positive matrices

A symmetric positive semi-definite matrix A is called completely positive if there exists a matrix B with nonnegative entries such that A = BB^?. If B is such a matrix with a minimal number p of columns, then p is called the cp-rank of A. In this paper we develop a finite and exact algorithm to factorize any matrix A of cp-rank 3. Failure of this algorithm implies that A does not have cp-rank 3. Our motivation stems from the question if there exist three nonnegative polynomials of degree at most four that vanish at the boundary of an interval and are orthonormal with respect to a certain inner product.     

Extremal numbers of positive entries of imprimitive nonnegative matrices

We determine the maximum and minimum numbers of positive entries of imprimitive nonnegative matrices with a given imprimitivity index. One application of the results is to estimate the imprimitivity index by the number of positive entries. The proofs involve the study of a cyclic quadratic form. This completes a research initiated by Lewin in 1990.     

Possible numbers of positive entries of imprimitive nonnegative matrices

Zhan, X., Extremal numbers of positive entries of imprimitive nonnegative matrix, Linear Algebra Appl. (in press) has determined the maximum and minimum numbers of positive entries of imprimitive irreducible nonnegative matrices with a given imprimitivity index. Let σ( A ) denote the number of positive entries of a matrix A. Let M(n,?k) and m(n,?k) denote the maximum and minimum numbers of positive entries of imprimitive irreducible nonnegative matrices of order n with a given imprimitivity index k, respectively. In this article, we prove that for any positive integer d with m(n,k)≤ d?≤?M(n,k), there exists an n?×?n irreducible nonnegative matrix A with imprimitivity index k such that?σ?(A)=d.     

On the numbers of positive entries of reducible nonnegative matrices

Let RM(n,d) be the class {A∣A is an n×n reducible nonnegative matrix and the greatest common divisor of the lengths of all cycles in D(A) is d}, where D(A) is the associated digraph of A. In this paper we determine the set of numbers of positive entries of A for A∈RM(n,d). We also characterize the reducible nonnegative matrices with the maximum and minimum numbers of positive entries.     

Factorization and cutting planes for completely positive matrices by copositive projection

We consider the problem of projecting a matrix onto the cones of copositive and completely positive matrices. As this can not be done directly, we use polyhedral approximations of the cones. With the help of these projections we obtain a technique to compute factorizations of completely positive matrices. We also describe a method to determine a cutting plane which cuts off an arbitrary matrix from the completely positive (or copositive) cone.     

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

One class of bounded ineffective and completely ineffective normal conservative positive matrices

Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 41, No. 4, pp. 550–553, April, 1989.