# How to check whether a matrix is completely positive or not?

The definition: cone of completely positive matrices $$\mathcal{C}=\left\{ \sum_{i=1}^kx_ix_i^T : \text{x_i\in\mathbb{R}^n_+ for i=1,2,\ldots,k} \right\}.$$

I just don't know how to check whether a matrix belongs to $\mathcal C$. To be more specific, is the following matrix completely positive?

$$\begin{pmatrix}8 & 2& 4+2\sqrt{2}\\ 2&2+\sqrt{2}&2+\sqrt{2}\\ 4+2\sqrt{2}& 2+\sqrt{2} &4+2\sqrt{2}\end{pmatrix}$$

Any thoughts or reference? Thanks very much.

• Your "completely positive" matrices are just symmetric positive matrices. Any textbook will tell you how to check that a given matrix has that property.
– abx
Apr 8, 2014 at 20:05
• For abx: the membership problem on the completely positive cone is NP-hard (optimization-online.org/DB_FILE/2011/05/3041.pdf). Apr 8, 2014 at 20:17
• @abx The $x_i$ are required to be $\geq 0$; this is more restrictive than being positive definite. (I was confused by this for quite a while as well.) Apr 9, 2014 at 0:26
• I suspect the closers misread this question as the far easier one abx understood; I'm voting to reopen. Apr 9, 2014 at 0:27
• Oops! My mistake, I indeed missed the ${}_+$ on $\mathbb{R}^n$. I apologize, and I vote to reopen.
– abx
Apr 9, 2014 at 5:20

As mentioned by Robert Bryant, in the $n = 3$ case, checking that the matrix is positive semidefinite and has all entries $\geq 0$ is both necessary and sufficient. In fact, the same is true when $n = 4$, but this is only a necessary (not sufficient) test for complete positivity when $n \geq 5$ (see "L. J. Gray and D. G. Wilson. Nonnegative Factorization of Positive Semidefinite Nonnegative Matrices. Linear Algebra Appl., 31:119-127, 1980", for example).

When $n \geq 5$, things get harder (NP-hard), but there are still some things that you can do, at least for small $n$. The usual approach is to approximate the set of completely positive matrices from the outside by other convex cones of matrices:

$\mathcal{K}_0 \supset \mathcal{K}_1 \supset \mathcal{K}_2 \supset\cdots \supset \mathcal{C},$

where $\mathcal{C}$ is the set of completely positive matrices, $\mathcal{K}_0$ is the set of "doubly-nonnegative matrices" (i.e., positive semidefinite matrices that also have all entries $\geq 0$, which were mentioned earlier), and $\mathcal{K}_i$ for $i \geq 1$ are better and better approximations of $\mathcal{C}$ (and in particular, $\lim_{i \rightarrow \infty} \mathcal{K}_i = \mathcal{C}$). Furthermore, the $\mathcal{K}_i$'s are defined in such a way that determining whether or not a matrix is a member of $\mathcal{K}_i$ can be phrased as a semidefinite program, and is thus computationally tractable for small $n$ and small $i$ (the semidefinite program takes more and more effort to solve as $i$ increases). I'm having trouble tracking down the original paper that discusses how the $\mathcal{K}_i$'s are defined, but "J. Povh and F. Rendl. Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optimization, 9:231-241, 2009" goes over these things in Section 3.

The upshot of this is that, in practice, we can determine when a matrix is not completely positive, by showing that is it not a member of $\mathcal{K}_i$ for some $i$. However, I am not aware of any methods for proving that a matrix is completely positive that work very well in practice.

• Thanks! I had more-or-less convinced myself that $n=4$ worked the same way, but didn't have time to check it completely, and it was clear that the simple nonnegativity of entries wouldn't work for sufficiently large $n$. I'm glad to know that the $n=5$ case is the one where it actually does break down. Apr 9, 2014 at 23:43

At least for $3$-by-$3$ matrices, the test for complete positivity of a matrix $A$ is not hard. Basically, you need that $A$ be positive-semi-definite and that the off-diagonal entries be non-negative. (I don't think this works for $n$-by-$n$ when $n>3$, though.)

Note: When I was writing the above, I was taking $\mathbb{R}^n_+$ to mean the closed principal $n$-orthant, i.e., the vectors in $\mathbb{R}^n$ with nonnegative entries. However, if you want $\mathbb{R}^n_+$ to be the interior of this orthant, i.e., the vectors with strictly positive entries, then you need (when $n=3$), in addition to $A$ being positive semi-definite, that all of the entries of $A$ are actually positive.

In the case of your particular matrix above, yes, it is completely positive: The entries $a_{ij}=a_{ji}$ are of the form $a_{ij} = v_i\cdot v_j$ where the three $v_i\in\mathbb{R}^3$ are linearly dependent and the greatest angle between any two is less than $\frac12\pi$, so the three vectors $v_i$ can be rotated simultaneously into the principal octant of $\mathbb{R}^3$, and this suffices.

• @RobertBrayant I think for $n=3$ the first paragraph of your answer is not a sufficient condition. a more necessary conition is $tr(A)\geq offtr(A)$. Apr 9, 2014 at 17:06
• @AliTaghavi: Your inequality is a consequence of the inequalities needed for $A$ to be positive semi-definite: When $A$ is positive semi-definite, we can write $a_{ij} = v_i\cdot v_j$ for three vectors $v_i$. Let $r_i = \sqrt{a_{ii}}\ge0$ and note that $a_{11}+a_{22}+a_{33}={r_1}^2+{r_2}^2+{r_3}^2\ge r_1r_2+r_2r_3+r_3r_1$ since the $r_i$ are nonnegative and that $r_1r_2+r_2r_3+r_3r_1\ge a_{12}+a_{23}+a_{31}$ by Cauchy-Schwartz. Apr 9, 2014 at 18:39

For general CP factorization of 3x3 matrices, you may consult pp.8-9 in

http://www.optimization-online.org/DB_HTML/2009/08/2381.html