MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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)}$. – Mikael de la Salle Jul 29 '11 at 19:43
I'm not sure to understand what you mean. – Loick Jul 29 '11 at 19:51
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$. – Mikael de la Salle Jul 29 '11 at 19:58
Oh yes, you are totally right. I miss it somewhere. This solve the case for positive matrices. – Loick Jul 29 '11 at 20:16
up vote 2 down vote accepted

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

share|cite|improve this answer
And this solves the general case. – Loick Jul 29 '11 at 20:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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