Minimal \(cp\) rank (Q2778504)

An \(n \times n\) matrix \(A\) is called a completely positive (\(cp\)) matrix if there exists an entrywise nonnegative (not necessarily square) matrix \(B\) such that \(A=BB^T\). The minimal \(m\) for which there exists an \(m \times n\) nonnegative matrix \(B\) satisfying \(A=BB^T\) is called the \(cp\)-rank of \(A\) and denoted by \(cp\)-rank of \(A\). An upper bound on \(cp\)-rank \(A\) was established in previous works and much smaller bound of \(cp\) matrices with special graphs has been proved by \textit{J. H. Drew, C. R. Johnson} and \textit{R. Loewy} [Linear Multilinear Algebra 37, No. 4, 303-310 (1994; Zbl 0815.15019)]. NEWLINENEWLINENEWLINEIn this work all graphs \(G\) on \(n\) vertices which attain this lower bound, \(cp\)-rank \(G \geq n\), are characterized. A graph \(G\) is of type \(I\) if every nonsingular \(cp\) matrix \(A\) with graph \(G\) satisfies \(cp\)-rank \(A\) \(=\) rank \(A\). A graph \(G\) is of type \(II\) if every \(cp\) matrix \(A\) with graph \(G\) has \(cp\)-rank \(A=\text{rank } A\). It is shown that a graph is of type \(I\) if and only if it does not contain a triangle free graph with more edges than vertices, and a graph is of type \(II\) if and only if it contains no even cycle and no triangle free graph with more edges than vertices.