0
$\begingroup$

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}$

Improve this question
$\endgroup$
3
  • $\begingroup$ I don't know. What does "completely positive" mean? $\endgroup$
    – Gerry Myerson
    Commented Jul 28, 2011 at 12:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – Pawan Aurora
    Commented Jul 28, 2011 at 14:43
  • 2
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jul 29, 2011 at 1:35

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jul 29, 2011 at 1:55
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jul 29, 2011 at 1:59
  • 2
    $\begingroup$ Make that $W^T$ and you're correct. $\endgroup$
    – Robert Israel
    Commented Jul 29, 2011 at 2:14
  • $\begingroup$ @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. $\endgroup$
    – Pawan Aurora
    Commented Jul 29, 2011 at 2:53
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jul 29, 2011 at 3:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .