On the minimum trace norm of (0,1)-matrices

Abstract

The trace norm of a matrix is the sum of its singular values. This paper presents results on the minimum trace norm ${\psi }_n\left(m\right)$ of $\left(0,1\right)$-matrices of size $n\times n$ with exactly $m$ ones. It is shown that: (1) if $n\ge 2$ and $n<m\le 2n,$ then ${\psi }_n\left(m\right)\le \sqrt{m+\sqrt{2\left(m-1\right)}}$ , with equality if and only if $m$ is a prime; (2) if $n\ge 4$ and $2n<m\le 3n,$ then ${\psi }_n\left(m\right)\le \sqrt{m+2\sqrt{2\lfloor m/3\rfloor }}$ , with equality if and only if $m$ is a prime or a double of a prime; (3) if $3n<m\le 4n,$ then ${\psi }_n\left(m\right)\le \sqrt{m+2\sqrt{m-2}}$ , with equality if and only if there is an integer $k\ge 1$ such that $m=12k\pm 2$ and $4k\pm 1,6k\pm 1,12k\pm 1$ are primes.

15 pages. Some mistakes and typos fixed in v3