A linear gap for the maximal cp-rank

A mix of human-written and AI-generated textHuman understanding: all partsmath.CO — Combinatorics math.OC — Optimization and Control

Contributed by Yair Lavi ↗

Version 1 / Nov 11, 2026/ arXiv: 2610.02289 / CC BY 4.0

Abstract

We prove that the maximal cp-rank

p_n

satisfies

p_n\ge n(n-3)/2

for odd

n\ge5

and

p_n\ge n(n-3)/2-1

for even

n\ge6

. Together with the known upper bound

p_n\le\binom{n+1}{2}-4

, this gives

p_n=n^2/2+O(n)

.

J. H. Drew, C. R. Johnson, and R. Loewy, ``Completely positive matrices associated with M-matrices,'' Linear and Multilinear Algebra 37 (1994), 303--310. DOI (https://doi.org/10.1080/03081089408818334).DOI
N. Shaked-Monderer, A. Berman, I. M. Bomze, F. Jarre, and W. Schachinger, ``New results on the cp rank and related properties of co(mpletely)positive matrices,'' Linear and Multilinear Algebra 63 (2015), 384--396. DOI (https://doi.org/10.1080/03081087.2013.869591).DOI
I. M. Bomze, W. Schachinger, and R. Ullrich, ``New lower bounds and asymptotics for the cp-rank,'' SIAM Journal on Matrix Analysis and Applications 36 (2015), 20--37. DOI (https://doi.org/10.1137/140973207).DOI
W. Schachinger, ``Lower bounds for maximal cp-ranks of completely positive matrices and tensors,'' Electronic Journal of Linear Algebra 36 (2020), 519--541. DOI (https://doi.org/10.13001/ela.2020.5323).DOI
I. M. Bomze, W. Schachinger, and R. Ullrich, ``From seven to eleven: completely positive matrices with high cp-rank,'' Linear Algebra and Its Applications 459 (2014), 208--221. DOI (https://doi.org/10.1016/j.laa.2014.06.025).DOI
R. Hildebrand, ``The extreme rays of the $5\times5$ copositive cone,'' Linear Algebra and its Applications 437 (2012), 1538--1547. DOI (https://doi.org/10.1016/j.laa.2012.04.017).DOI