zbMATH — the first resource for mathematics

Rational and real positive semidefinite rank can be different. (English) Zbl 1408.15016
Summary: Given a \(p \times q\) nonnegative matrix \(M\), the psd rank of \(M\) is the smallest integer \(k\) such that there exist \(k \times k\) real symmetric positive semidefinite matrices \(A_1, \ldots, A_p\) and \(B_1, \ldots, B_q\) such that \(M_{i j} = \langle A_i, B_j \rangle\) for \(i = 1, \ldots, p\) and \(j = 1, \ldots, q\). When the entries of \(M\) are rational it is natural to consider the rational-restricted psd rank of \(M\), where the factors \(A_i\) and \(B_j\) are required to have rational entries. It is clear that the rational-restricted psd rank is always an upper bound to the usual psd rank. We show that this inequality may be strict by exhibiting a matrix with psd rank four whose rational-restricted psd rank is strictly greater than four.

15B48 Positive matrices and their generalizations; cones of matrices
Full Text: DOI
[1] Cohen, J.; Rothblum, U., Nonnegative ranks, decompositions, and factorizations of nonnegative matrices, Linear Algebra Appl., 190, 149-168, (1993)
[2] Fawzi, H.; Gouveia, J.; Parrilo, P. A.; Robinson, R. Z.; Thomas, R. R., Positive semidefinite rank, Math. Program., 153, 1, 133-177, (2015)
[3] Fiorini, S.; Massar, S.; Pokutta, S.; Tiwary, H.; de Wolf, R., Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds, (Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC’12, (2012), ACM), 95-106
[4] Gouveia, J.; Parrilo, P.; Thomas, R., Lifts of convex sets and cone factorizations, Math. Oper. Res., 38, 2, 248-264, (2013)
[5] Gouveia, J.; Robinson, R. Z.; Thomas, R. R., Polytopes of minimum positive semidefinite rank, Discrete Comput. Geom., 50, 3, 679-699, (2013)
[6] T. Lee, D.O. Theis, Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix, 2012. ArXiv Preprint arXiv:1203.3961v4.
[7] Y. Shitov, Nonnegative rank depends on the field, ArXiv Preprint arXiv:1505.01893.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.