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$.
 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\|$.
