# trace norm of a matrix

Suppose that $N$ is an $\epsilon$-net (where $\epsilon$ is a small absolute constant) on the unit sphere $S^{n-1}$ in $\mathbb{R}^n$, and $T$ is an $n\times n$ matrix such that $\|Tx\|_2\geq 1$ for all $x\in N$.

Is it true that $\|T\|_\ast \geq cn$ for some (small) constant $c$ (which could depend on $\epsilon$? Here $\|T\|_\ast$ means the trace norm of $T$, that is, $\|T\|_\ast = \sigma_1(T) + \cdots + \sigma_n(T)$, where $\sigma_i(T)$ are the singular values of $T$.

My guess is not. One can choose $T$ be have a big constant singular value and all the rest singular values are tiny (like $1/n$), and the net completely evades the orthogonal complement to the vector associated with the largest singular value. Is it so?

What if $T$ satisfies a further constraint that $\|T\|_F\geq\sqrt{n}$ (where $\|T\|_F$ is the Frobenius norm of $T$), will we have $\|T\|_\ast\geq cn$ in this case?

• What if T is the identity matrix? – Anthony Quas Jan 5 '17 at 2:02
• Could you please explicitly define $\Vert T \Vert$? – Pat Devlin Jan 5 '17 at 2:12
• @PatDevlin yes, i've modified the post. $\|T\|_1$ is the trace norm / nuclear norm of $T$. – user58955 Jan 5 '17 at 5:02
• The nuclear norm is usually denoted by $\| \cdot \|_*$. – Rodrigo de Azevedo Jan 5 '17 at 13:37
• As you say, if $T$ is the matrix with a single non-zero entry of $1/\epsilon$ in the top left coordinate, and $S$ is the collection of all points with $x$ coordinate at least $\epsilon$, then $S$ is a $2\epsilon$ net satisfying your condition, but $\|T\|_*$=1/\epsilon\$. – Anthony Quas Jan 5 '17 at 17:50