Welcome to MathOverflow

Question

0

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

edited Jul 28 2011 at 8:00

asked Jul 28 2011 at 7:55

Pawan Aurora
209●5

I don't know. What does "completely positive" mean? – Gerry Myerson Jul 28 2011 at 12:31

1

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 2011 at 14:43

2

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 2011 at 1:35

Gerhard Paseman · Accepted Answer · 2011-07-29 03:25:44Z UTC

4

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

edited Jul 29 2011 at 3:25

answered Jul 29 2011 at 1:50

Gerhard Paseman
1,201●6●14

1

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 2011 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 2011 at 1:59

2

Make that $W^T$ and you're correct. – Robert Israel Jul 29 2011 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 2011 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 2011 at 3:32

show 2 more comments

Is the following DNN matrix CP?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.