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



Equivalence of entrywise 1-norm and Schatten-1 norm
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\|$.


