Positive maps and decomposable maps

Consider linear maps between symmetric matrices, i.e., of the form $\Lambda: \mathcal{S}^n \rightarrow \mathcal{S}^n$. A map is said to be a positive map if it maps the PSD cone $\mathcal{S}^n_+$ into the PSD cone $\mathcal{S}^m_+$ (i.e., it preserves positive semidefinite matrices).

(a) Show that any linear map of the form $A \mapsto \sum_i P_i^T A P_i$ where $P_i \in \mathbb{R}^{n \times m}$ is positive. These maps are known as decomposable maps.

(b) Show that the linear map $C:\mathcal{S}^3 \rightarrow \mathcal{S}^3$ (due to M.-D. Choi) given by:

(1)
\begin{align} C : A \mapsto \begin{bmatrix} 2a_{11}+a_{22} & 0 & 0\\ 0 & 2a_{22}+a_{33} & 0\\ 0 & 0 & 2a_{33}+a_{11} \end{bmatrix} - A \end{align}

is a positive map, but is not decomposable.

Hint: Consider the polynomial defined by $p(x,y) := y^T \Lambda(xx^T) y$. How can you express positivity and decomposability of the linear map $\Lambda$ in terms of the polynomial $p$?

SOLUTION

(a) If A is an $n \times n$ positive semidefinite matrix and $P$ is any $n\times m$ matrix, then $P^T A P$ is positive semidefinite. Indeed for any $x \in \mathbb{R}^n$ we verify that $x^T P^T A P x = (Px)^T A (Px) \geq 0$.
Thus if $A$ is positive semidefinite then $\sum_i P_i^T A P_i$ is positive semidefinite and the map $A \mapsto \sum_i P_i^T A P_i$ is positive.

(b) Let $\Lambda:\mathcal{S}^n \rightarrow \mathcal{S}^n$ be a linear map between symmetric matrices and let $p(x,y) = y^T \Lambda(xx^T) y$. We show that

1. $\Lambda$ is positive iff $p$ is nonnegative
2. $\Lambda$ is decomposable iff $p$ is a sums-of-squares

Proofs:

1. $\Lambda$ is positive iff $p$ is nonnegative:

$\Rightarrow$: If $\Lambda$ is positive then $\Lambda(xx^T)$ is positive semidefinite for any $x \in \mathbb{R}^n$, and thus $y^T \Lambda(xx^T) y$ is nonnegative for all $y$. This shows that $p(x,y)$ is nonnegative.

$\Leftarrow$: Assume that $p(x,y)$ is nonnegative. We will show that $\Lambda$ is a positive map. Let $A=\sum_{i=1}^n x_i x_i^T$ be a positive semidefinite matrix. Then for any $y \in \mathbb{R}^n$ we have $y^T \Lambda(A) y = \sum_{i=1}^n y^T \Lambda(x_ix_i^T) y = \sum_{i=1}^n p(x_i,y) \geq 0$. This is true for all $y \in \mathbb{R}^n$ hence $\Lambda(A)$ is positive semidefinite.

2. We now show that $\Lambda$ is decomposable iff $p$ is a sums-of-squares:

$\Rightarrow$: Assume that $\Lambda$ is decomposable. Let $P_i$'s be such that $\Lambda(A) = \sum_i P_i^T A P_i$. Then for any $x$ and $y$ we have:
$p(x,y) = y^T (\sum_i P_i^T xx^T P_i) y = \sum_i (x^T P_i y)^T (x^T P_i y) = \sum_i q_i(x,y)^2$ where $q_i(x,y) = x^T P_i y$. Hence $p$ is SOS.

$\Leftarrow$: Assume that $p$ is SOS. We will show that $\Lambda$ is decomposable. Let $q_i$'s be such that $p(x,y) = \sum_i q_i(x,y)^2$. Observe that since $p$ is homogenenous of degree 4, the $q_i$'s can be chosen to be homogenenous of degree 2. Furthermore observe that $q_i$ cannot contain monomials where the degree of an $x_j$ or a $y_j$ is $\geq$ 1. In other words this means that $q_i$ has the form $q_i(x,y)=\sum_{k,l} (P_i)_{k,l} x_k y_l = x^T P_i y$. Hence we have

(2)
\begin{align} y^T \Lambda(xx^T)y = p(x,y) = \sum_i q_i(x,y)^2 = \sum_i (x^T P_i y)^2 = \sum_i (x^T P_i y)^T (x^T P_i y) = y^T (\sum_i P_i^T xx^T P_i) y \end{align}

Thus for a fixed $x$, we have that for any $y$

(3)
\begin{align} y^T \left[ \Lambda(xx^T) - \left(\sum_i P_i^T xx^T P_i\right) \right] y = 0 \end{align}

which implies $\Lambda(xx^T) - (\sum_i P_i^T xx^T P_i) = 0$ since the matrix is symmetric. Thus this shows that for any $x$ ,$\Lambda(xx^T) = \sum_i P_i^T xx^T P_i$. Hence by linearity of $\Lambda$ this shows that $\Lambda(A) = \sum_i P_i^T A P_i$ for any symmetric matrix $A$, and this means that $\Lambda$ is decomposable.

The example given is the map

(4)
\begin{align} C : A \mapsto \begin{bmatrix} 2a_{11}+a_{22} & 0 & 0\\ 0 & 2a_{22}+a_{33} & 0\\ 0 & 0 & 2a_{33}+a_{11} \end{bmatrix} - A \end{align}

The associated polynomial is

(5)
\begin{align} p(x,y) = 2 \sum_{i=1}^3 x_i^2 y_i^2 + x_1^2 y_3^2 + x_2^2 y_1^2 + x_3^2 y_2^2 - (\sum_{i=1}^3 x_i y_i)^2 \end{align}

We have to show that $p(x,y)$ is nonnegative but is not a sums-of-squares.
One could use Yalmip to show that it is not a SOS:

sdpvar x1 x2 x3 y1 y2 y3
p = 2*(x1^2*y1^2 + x2^2*y2^2 + x3^2*y3^2) + x1^2*y3^2 + x2^2*y1^2 + x3^2*y2^2 - (x1*y1+x2*y2+x3*y3)^2;
F = sos(p);
sol = solvesos(F)


I did not manage though to show that $p(x,y)$ is nonnegative. Did someone manage to do it?

Hint: The polynomial $p(x,y)$ is bihomogeneous in $x$ and $y$. We can think of $p(x,y)$ as a quadratic form in $y$ with coefficients depending on $x$. Write down the matrix of this quadratic form. The entries of the matrix should be quadratic forms in $x$. We need to show that this matrix is positive semidefinite for all values of $x$. — Greg B.