The maximum cp-rank in order six
A real symmetric matrix $A$ is completely positive if $A = BB^{\mathsf T}$ for an entrywise nonnegative real matrix $B$ with finitely many columns, and its cp-rank $\operatorname{cpr}(A)$ is the least number of columns of such a $B$, with $\operatorname{cpr}(0) = 0$. Let $\mathcal{CP}_n$ be the cone of completely positive $n \times n$ matrices and $p_n = \max\{\operatorname{cpr}(A) : A \in \mathcal{CP}_n\}$. It is classical that $p_n = n$ for $n \le 4$; for $n \ge 5$, $p_n \ge \lfloor n^2/4 \rfloor$, and Shaked-Monderer, Berman, Bomze, Jarre and Schachinger proved $p_n \le n(n+1)/2 - 4$. Drew, Johnson and Loewy conjectured $p_n = \lfloor n^2/4 \rfloor$ for every $n \ge 4$. This holds for $n = 5$ (Loewy and Tam; Shaked-Monderer, Bomze, Jarre and Schachinger) and fails for every $n \ge 7$ (Bomze, Schachinger and Ullrich). In order six, Shaked-Monderer, with a correction by Dickinson, proved the conjectured bound on a part of the boundary of $\mathcal{CP}_6$ that contains every entrywise positive nonsingular boundary matrix, and showed that $p_6$ is attained at a nonsingular matrix with a zero entry.
Problem. Is $\operatorname{cpr}(A) \le 9$ for every $A \in \mathcal{CP}_6$, that is, is every real completely positive $6 \times 6$ matrix a sum of at most nine matrices $bb^{\mathsf T}$ with $b \in \mathbb{R}_{\ge 0}^{6}$, or equivalently $BB^{\mathsf T}$ for some entrywise nonnegative $B \in \mathbb{R}^{6 \times 9}$, zero columns allowed? Equivalently, is $p_6 = 9$?
Source: Drew, Johnson and Loewy (1994), the DJL conjecture p_n = ⌊n²/4⌋ for n ≥ 4, in its case n = 6; singled out by Bomze, Schachinger and Ullrich (2014), §1, and posed, with a conjectured positive answer, by Berman, Dür and Shaked-Monderer (2015), §4.2; see also Shaked-Monderer (2017), §1.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- OC
- Keywords
- completely positive matrices, cp-rank, OpenProblemsInNLA
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{berman2015,
author = {Berman, Abraham and D{\"u}r, Mirjam and Shaked-Monderer, Naomi},
title = {Open problems in the theory of completely positive and copositive matrices},
journal = {Electron. J. Linear Algebra},
volume = {29},
year = {2015},
pages = {46--58},
doi = {10.13001/1081-3810.2943},
}
@article{drew1994,
author = {Drew, John H. and Johnson, Charles R. and Loewy, Raphael},
title = {Completely positive matrices associated with {$M$}-matrices},
journal = {Linear Multilinear Algebra},
volume = {37},
number = {4},
year = {1994},
pages = {303--310},
doi = {10.1080/03081089408818334},
}
@article{shakedmonderer2017,
author = {Shaked-Monderer, Naomi},
title = {On the {DJL} conjecture for order 6},
journal = {Oper. Matrices},
volume = {11},
number = {1},
year = {2017},
pages = {71--88},
doi = {10.7153/oam-11-05},
eprint = {1501.02426},
archivePrefix = {arXiv},
note = {Corrected version: arXiv v3, 1 June 2017; Theorem 1.1 and Corollary 3.2},
}
@article{dickinson2017,
author = {Dickinson, Peter J. C.},
title = {Erratum to: On the {DJL} conjecture for order 6},
journal = {Oper. Matrices},
volume = {11},
number = {4},
year = {2017},
pages = {1197--1200},
doi = {10.7153/oam-2017-11-81},
}
@article{shakedmonderer2015,
author = {Shaked-Monderer, Naomi and Berman, Abraham and Bomze, Immanuel M. and Jarre, Florian and Schachinger, Werner},
title = {New results on the cp-rank and related properties of co(mpletely) positive matrices},
journal = {Linear Multilinear Algebra},
volume = {63},
number = {2},
year = {2015},
pages = {384--396},
doi = {10.1080/03081087.2013.869591},
eprint = {1305.0737},
archivePrefix = {arXiv},
}
@article{loewy2003,
author = {Loewy, Raphael and Tam, Bit-Shun},
title = {{CP} rank of completely positive matrices of order 5},
journal = {Linear Algebra Appl.},
volume = {363},
year = {2003},
pages = {161--176},
doi = {10.1016/S0024-3795(01)00588-2},
}
@article{shakedmonderer2013,
author = {Shaked-Monderer, Naomi and Bomze, Immanuel M. and Jarre, Florian and Schachinger, Werner},
title = {On the cp-rank and minimal cp factorizations of a completely positive matrix},
journal = {SIAM J. Matrix Anal. Appl.},
volume = {34},
number = {2},
year = {2013},
pages = {355--368},
doi = {10.1137/120885759},
}
@article{bomze2014,
author = {Bomze, Immanuel M. and Schachinger, Werner and Ullrich, Reinhard},
title = {From seven to eleven: Completely positive matrices with high cp-rank},
journal = {Linear Algebra Appl.},
volume = {459},
year = {2014},
pages = {208--221},
doi = {10.1016/j.laa.2014.06.025},
}
@article{bomze2015,
author = {Bomze, Immanuel M. and Schachinger, Werner and Ullrich, Reinhard},
title = {New lower bounds and asymptotics for the cp-rank},
journal = {SIAM J. Matrix Anal. Appl.},
volume = {36},
number = {1},
year = {2015},
pages = {20--37},
doi = {10.1137/140973207},
}
@misc{openproblemsinnla-pf04,
author = {Townsend, Alex},
title = {{PF-04}: The maximum cp-rank in order six},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/nonnegative-and-positive-factorizations/PF-04/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
The paper proves that every real completely positive matrix of order six has an entrywise nonnegative factor with at most nine columns, and exhibits a positive definite completely positive matrix of order six with cp-rank nine, so that the maximum cp-rank in order six is nine. The argument uses the published order-five bound and Shaked-Monderer's corrected theorems for matrices orthogonal …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00261, "The maximum cp-rank in order six", clopen.solutions.