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.
 A: 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.
A: 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.
A: 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
