Question

The factorization norm, sometimes also called $\gamma_2$ norm play an important role in (quantum) communication complexity and is defined for a $n\times n$ matrix $A$ by:

$\gamma_2(A) = \max || A \circ uv^t||_{\mathrm{tr}}$ where the maximization runs over all unit vectors $u$ and $v$ ($||u||=||v||=1$)

We can find many equivalent definitions such as: $\gamma_2(A) = \min \lambda$ such that $(A)_{ij} = \langle u_i | v_j\rangle$ and $\forall i,j$ we have $ ||u_i||\leq \lambda$ and $||v_j|| \leq \lambda$.

And the trace norm is defined by $||A||_{\mathrm{tr}}=\mathrm{tr}\sqrt{A^\dagger A}$.

These two norms are equivalent, so there exists a constant $C_n$ such that $||A||_{\mathrm{tr}} \geq C_n\gamma_2(A)$. What is the value of $C_n$?

Having played with a few examples I conjecture that $C_n=1$. Also note that the reverse inequality can be easily obtained: $||A||_\mathrm{tr} \leq n\cdot \gamma_2(a)$.

In particular, I am interested by the case where $A$ is definite positive. In this case the trace norm is simply the trace of $A$, and I can prove that $\gamma_2(A) \geq \sqrt{tr(A)}$.

Answer 1

You are right, the best constant is $1$. In fact, the stronger inequality $\gamma_2(A) \leq \|A\|_{\infty}$ is also true (and is stronger since $\|A\|_{\infty}\leq \| A\|_{1}$).

For simplicity I denote $\|\cdot\|_p$ the Schatten $p$-norm. ($p=1$ corresponds to the trace norm, $p=2$ the Hilbert-Schmidt norm and $p=\infty$ the operator norm).

For a proof, one has to show that $\|A \circ u v^t\|_{1} \leq \|A\|_{\infty}$ if $u,v$ are unit vectors in the euclidean space $\mathbb C^n$. (it could be recalled that the notation $\circ$ is the Hadamard product, or product entrywise). Denote by $D_u,D_v$ the diagonal matrices with diagonal entries the coordinates of $u$ and $v$, so that $A \circ u v^t = D_u A D_v$. By Hölder's inequality $\|D_u A D_v\|_1 \leq \|D_u\|_2 \|A\|_\infty\|D_v\|_2 = \|A\|_\infty$.