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

  • 1
    $\begingroup$ There are homogeneity problems: first in your alternative definition of $\gamma_2(A)$, and then in your last inequality $\gamma_2(A) \geq \sqrt{tr(A)}$. $\endgroup$ Jul 29 '11 at 19:43
  • $\begingroup$ I'm not sure to understand what you mean. $\endgroup$
    – Loick
    Jul 29 '11 at 19:51
  • $\begingroup$ The first $\lambda$ appearing in your question should be a $\lambda^2$. The last inequality cannot be true. Otherwise, replacing $A$ by $tA$ with $t>0$, it becomes $\sqrt t \gamma_2(A) \geq \sqrt{tr A}$. Making $t \to 0$ yields $tr(A)=0$. $\endgroup$ Jul 29 '11 at 19:58
  • $\begingroup$ Oh yes, you are totally right. I miss it somewhere. This solve the case for positive matrices. $\endgroup$
    – Loick
    Jul 29 '11 at 20:16

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

  • $\begingroup$ And this solves the general case. $\endgroup$
    – Loick
    Jul 29 '11 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.