# Equivalence of entrywise 1-norm and Schatten-1 norm

Let $A \in \mathbb{R}^{m\times n}$ and $\|A\| = \sum_{i, j} |A_{i,j}|$.

I am looking for constants $\alpha, \beta \in \mathbb{R}$ such that

$\alpha \|A\| \leq \|A\|_* \leq \beta \|A\|$

The function $\|\cdot\|_*$ is the Schatten-1 norm, or the sum of the singular values of $A$.

The best such inequality that depends only on $m$ and $n$ is: $$\frac{1}{\sqrt{mn}}\|A\| \leq \|A\|_* \leq \|A\|$$ The right inequality is tight when $A$ is a matrix with a $1$ in the top-left corner and zeroes elsewhere. The left inequality is tight when $A$ is the matrix all of whose entries are $1$. These examples also show that you cannot get any better constants even if you let them depend on the rank of $A$.
To see that the inequalities actually hold, let's start with the left inequality. Write $A$ in its singular value decomposition: $$A = \sum_i \sigma_i \mathbf{x}_i\mathbf{y}_i,$$ where $\{\sigma_i\}$ are the singular values of $A$ and $\{\mathbf{x}_i\}$ and $\{\mathbf{y}_i\}$ all have Euclidean norm $1$: $\|\mathbf{x}_i\| = \|\mathbf{y}_i\| = 1$ for all $i$. Then $$\|A\| = \big\| \sum_i \sigma_i \mathbf{x}_i\mathbf{y}_i \big\| \leq \sum_i \sigma_i \big\|\mathbf{x}_i\mathbf{y}_i\big\| \leq \sqrt{mn}\sum_i \sigma_i \big\|\mathbf{x}_i\mathbf{y}_i\big\|_2 = \sqrt{mn}\sum_i \sigma_i = \sqrt{mn}\|A\|_*,$$ where $\|\cdot\|_2$ is the entrywise $2$-norm (sometimes called the Frobenius norm).
To see the right inequality, we recall that one formulation of the Schatten $1$-norm is as an infimum over all rank-$1$ decompositions of $A$: $$\|A\|_* = \inf\big\{ \sum_i |c_i| : A = \sum_i c_i \mathbf{x}_i\mathbf{y}_i^*, \|\mathbf{x}_i\| = \|\mathbf{y}_i\| = 1 \big\}.$$
Well, one such rank-$1$ decomposition of $A$ is just the very naive one that writes it in terms of standard basis vectors $\{\mathbf{e}_i\}$: $$A = \sum_{i,j} A_{ij} \mathbf{e}_i\mathbf{e}_j^*.$$
Since $\|A\| = \sum_{i,j} |A_{ij}|$, it follows immediately that $\|A\|_* \leq \|A\|$.