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?

2more comments