Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

It is known that a $n^2 \times n^2$ positive semidefinite matrix $A$ cannot always be written as a finite sum $$ A=\sum_{j} B_j \otimes C_j $$ with $B_j$ and $C_j$ positive semidefinite matrices (of size $n \times n$). For example, it can be seen that the matrix $$ \begin{pmatrix} 1 & 0 & 0 & 1 \\\ 0 & 0 & 0 & 0 \\\ 0 & 0 & 0 & 0 \\\ 1 & 0 & 0 & 1 \end{pmatrix} $$ is not the finite sum of Kronecker products of positive semidefinite $2 \times 2$ matrices.

Is the statement true if $A$ is positive definite? (i.e., $A$ is invertible?).

Edit: this question is a slight variant of a previous question.

share|improve this question

1 Answer 1

up vote 8 down vote accepted

The following is just a minor variation of Martin Argerami's proof of the old question. I am even copying his equations and some of his text. If you are +1ing this post, please also +1 his one (if not already done).

Here is a counterexample for $n=2$. Let $\varepsilon $ be a positive real $< \dfrac{1}{2}$. The matrix

$ a= \begin{bmatrix} 1 & 0 & 0 & 1-\varepsilon \\ 0 & \varepsilon & 0 & 0 \\ 0 & 0 & \varepsilon & 0 \\ 1-\varepsilon & 0 & 0 & 1 \end{bmatrix} \in \mathrm{M}_{4}\left( \mathbb{C}\right) $

is positive-definite, but it cannot be written as a sum of tensor products of nonnegative-semidefinite $2\times 2$-matrices. Here is why:

Assume the contrary. Thus, $a$ is written in the form

$a=\sum_{j} \left[ \begin{matrix} \alpha _{j} & \overline{\gamma _{j}} \\ \gamma _{j} & \beta _{j} \end{matrix} \right] \otimes \left[ \begin{matrix} \alpha _{j}^{\prime } & \overline{\gamma _{j}^{\prime }} \\ \gamma _{j}^{\prime } & \beta _{j}^{\prime } \end{matrix} \right] =\left[ \begin{matrix} \sum_{j}\alpha _{j}^{\prime }\alpha _{j} & \sum_{j}\alpha _{j}^{\prime } \overline{\gamma _{j}} & \sum_{j}\overline{\gamma _{j}^{\prime }}\alpha _{j} & \sum_{j}\overline{\gamma _{j}^{\prime }}\gamma _{j} \\ \sum_{j}\alpha _{j}^{\prime }\gamma _{j} & \sum_{j}\alpha _{j}^{\prime }\beta _{j} & \ast & \ast \\ \ast & \ast & \sum_{j}\beta _{j}^{\prime }\alpha _{j} & \ast \\ \ast & \ast & \ast & \ast \end{matrix}\right] $,

where $j$ ranges from $1$ to some positive integer $N$. Since each $ \begin{bmatrix} \alpha _{j} & \overline{\gamma _{j}} \\ \gamma _{j} & \beta _{j} \end{bmatrix} $ is nonnegative-semidefinite, we have $\alpha _{j}\geq 0$, $\beta _{j}\geq 0$, and $\alpha _{j}\beta _{j}\geq \left\vert \gamma _{j}\right\vert ^{2}$ for all $j$. Similarly, $\alpha _{j}^{\prime }\geq 0$, $\beta _{j}^{\prime }\geq 0$, and $\alpha _{j}^{\prime }\beta _{j}^{\prime }\geq \left\vert \gamma _{j}^{\prime }\right\vert ^{2}$ for all $j$.

Now, comparing the entries of $a$ in this equation, we get $\varepsilon =\sum_{j}\alpha _{j}^{\prime }\beta _{j}$ (from the $\left( 2,2\right) $-th entry) and $\varepsilon =\sum_{j}\beta _{j}^{\prime }\alpha _{j}$ (from the $ \left( 3,3\right) $-th entry). Taking the arithmetic mean of these two equations, we get

$\varepsilon =\dfrac{1}{2}\left( \sum_{j}\alpha _{j}^{\prime }\beta _{j}+\sum_{j}\beta _{j}^{\prime }\alpha _{j}\right) =\sum_{j}\dfrac{\alpha _{j}^{\prime }\beta _{j}+\beta _{j}^{\prime }\alpha _{j}}{2}\geq \sum_{j}\sqrt{\alpha _{j}^{\prime }\beta _{j}\beta _{j}^{\prime }\alpha _{j}}$

(by AM-GM, since we are dealing with nonnegative reals). But for every $j$, we have

$\sqrt{\alpha _{j}^{\prime }\beta _{j}\beta _{j}^{\prime }\alpha _{j}}=\sqrt{\alpha _{j}\beta _{j}}\sqrt{\alpha _{j}^{\prime }\beta _{j}^{\prime }}\geq \left\vert \gamma _{j}\right\vert \left\vert \gamma _{j}^{\prime }\right\vert $

(since $\alpha _{j}\beta_{j}\geq \left\vert \gamma _{j}\right\vert ^{2}$ and $\alpha _{j}^{\prime }\beta _{j}^{\prime }\geq \left\vert \gamma _{j}^{\prime }\right\vert ^{2}$ ), so this becomes

$\varepsilon \geq \sum_{j}\underbrace{\left\vert \gamma _{j}\right\vert \left\vert \gamma _{j}^{\prime }\right\vert }_{=\left\vert \overline{\gamma _{j}^{\prime }}\gamma _{j}\right\vert } = \sum_{j}\left\vert \overline{\gamma _{j}^{\prime }}\gamma _{j}\right\vert \geq \left\vert \sum_{j}\overline{\gamma _{j}^{\prime }}\gamma _{j}\right\vert $

(by the triangle inequality). But since $1-\varepsilon =\sum_{j}\overline{\gamma _{j}^{\prime }}\gamma _{j}$ (by comparing the $ \left( 1,4\right) $-th entry of the matrices in the above equation), this becomes $\varepsilon \geq \left\vert 1-\varepsilon \right\vert $, what contradicts the definition of $\varepsilon $.

share|improve this answer
4  
For an easier proof, observe that the partial transpose $\mathbf 1 \otimes T$ of $a$ is not positive semidefinite for small $\varepsilon$ (while it is obviously positive semidefinite for every matrix that is decomposable in the above sense). –  Michael Jan 15 '12 at 9:37
    
Michael: Can you explain further? What is the "partial transpose $1 \otimes T$ of $a$ ? Thanks. –  Ruben A. Martinez-Avendano Jan 16 '12 at 18:19
1  
There is a canonical isomorphism $\mathrm M_4\left(\mathbb C\right) \to \mathrm M_2\left(\mathbb C\right) \otimes \mathrm M_2\left(\mathbb C\right)$. The partial transpose is the endomorphism $1\otimes T$ of $ \mathrm M_2\left(\mathbb C\right) \otimes \mathrm M_2\left(\mathbb C\right)$, where $1$ denotes the identity endomorphism of $ \mathrm M_2\left(\mathbb C\right)$ and $T$ denotes the transposition endomorphism of $ \mathrm M_2\left(\mathbb C\right)$. (Endomorphism means vector-space endomorphism.) –  darij grinberg Jan 16 '12 at 19:17
    
(The only reason why I haven't +1ed Michael's comment is that I was too lazy to check how $1\otimes T$ acts on that matrix...) –  darij grinberg Jan 16 '12 at 19:17

Your Answer

 
discard

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.