# Is the following DNN matrix CP?

Is the following Doubly Non-negative matrix Completely Positive:

$\frac{1}{6}\begin{bmatrix} 2 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\0 & 2 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \\0 & 0 & 2 & 1 & 1 & 0 & 1 & 1 & 0 \\0 & 1 & 1 & 2 & 0 & 0 & 0 & 1 & 1 \\1 & 0 & 1 & 0 & 2 & 0 & 1 & 0 & 1 \\1 & 1 & 0 & 0 & 0 & 2 & 1 & 1 & 0 \\0 & 1 & 1 & 0 & 1 & 1 & 2 & 0 & 0\\1 & 0 & 1 & 1 & 0 & 1 & 0 & 2 & 0\\1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 2\end{bmatrix}$

-
I don't know. What does "completely positive" mean? –  Gerry Myerson Jul 28 '11 at 12:31
It means that the above matrix can be expressed as $WW^T$ with all entries in the $W$ matrix non-negative. The $W$ matrix need not be square. –  Pawan Aurora Jul 28 '11 at 14:43
I think 6 times that matrix can be CP, with W being a 0-1 matrix. Each column of W will have two 1's in it, and W can be divided into three groups of columns such that no row in each group has more than a single 1 in it. This definitely resembles a combinatorial design problem. Gerhard "Ask Me About Combinatorial Design" Paseman, 2011.07.28 –  Gerhard Paseman Jul 29 '11 at 1:35

Edit: I wanted the following matrix to be $W$. Robert Israel suggested I call it $W^T$ instead. I defer to his years of experience and the fact that it gives a better answer to the problem. End Edit.

For 6 times the given matrix, I nominate the following candidate for $W^T$

$$\begin{bmatrix} 1 & & & & 1 & & & & 1 \\\\ 1 & & & & & 1 & & 1 & \\\\ & 1 & & 1 & & & & & 1 \\\\ & 1 & & & & 1 & 1 & & \\\\ & & 1 & 1 & & & & 1 & \\\\ & & 1 & & 1 & & 1 & & \end{bmatrix}$$

Does this help?

Gerhard "Ask Me About Binary Matrices" Paseman, 2011.07.28

-
I did this by hand, and left out the zeroes for readability. I apologize conditionally for any errors in this answer. Gerhard "Ask Me About System Design" Paseman, 2011.07.28 –  Gerhard Paseman Jul 29 '11 at 1:55
Also (assuming the answer helps), I would like in return to know the motivation for the problem. In particular, if I have helped to solve a homework problem, I want the grader to give me some of the credit. Gerhard "Maintain A Good Credit Score" Paseman, 2011.07.28 –  Gerhard Paseman Jul 29 '11 at 1:59
Make that $W^T$ and you're correct. –  Robert Israel Jul 29 '11 at 2:14
@Gerhard Paseman, I am trying to show that the matrices resulting out of an optimization problem are CP. Although not all matrices will have the same structure as the one I posted. Definitely this is not a homework problem. –  Pawan Aurora Jul 29 '11 at 2:53
In my reading of the literature on 0-1 matrices, $G$ is a Gram matrix where $G = MM^T$ and $M$ is some special matrix (for me a square 0-1 matrix, although the definition may be more general) . I suggest looking at Gram matrix literature if you are going to deal with matrices like the one in your question. Also, Will Orrick might be a good person to consult for more detail. Gerhard "Ask Me Not About Transpose" Paseman, 2011.07.28 –  Gerhard Paseman Jul 29 '11 at 3:32
show 2 more comments