Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
I don't know. What does "completely positive" mean? –  Gerry Myerson Jul 28 '11 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 '11 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 '11 at 1:35
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
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 '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
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.