11
$\begingroup$

Studying a problem that is not directly related to linear algebra I came across the following problem.

Let $B$ be $n \times n$ symmetric matrix whose entries are non-negative integers. I would like to check whether one can express $B$ as $$B = X X^t \quad (1)$$ where $X$ is a $n \times m$ matrix only having $0$ and $1$ as its entries. Note that $m$ is fixed in this setting.

I can see two necessary conditions for this to be possible

  • The eigenvalues of $B$ are not negative
  • The element on the $i$'th diagonal of $B$ is $\leq m$ and is the largest element of the $i$'th row and column of $B.$

I am not interested in producing such $X$ itself but rather in finding necessary/sufficient conditions when this is actually possible. Hence

Question. What are some necessary conditions for $B$ to be expressed as in $(1)$?

$\endgroup$
8
  • $\begingroup$ This is a discrete problem, so perhaps look at 2x2 and 3x3 matrices, and see if there is some obvious bijection/pattern? $\endgroup$ Jun 8, 2014 at 12:13
  • $\begingroup$ Is $m$ fixed? If $X$ has an all-ones row than $B$ has a main diagonal entry of $m$, so are you also assuming $m \le n$? Or should the $n$ in your second condition be an $m$? $\endgroup$ Jun 8, 2014 at 16:47
  • $\begingroup$ @MarkWildon Yes, I think that should actually be a $m.$ $\endgroup$
    – Jernej
    Jun 8, 2014 at 16:50
  • $\begingroup$ It is still not clear whether you intend $m$ to be fixed or not. $\endgroup$ Jun 9, 2014 at 10:28
  • $\begingroup$ @MarkWildon I am sorry I have corrected to post to indicate that $m$ is fixed. $\endgroup$
    – Jernej
    Jun 9, 2014 at 10:38

1 Answer 1

9
$\begingroup$

Even the case where $B$ is constant on the diagonal and constant off the diagonal is extremely difficult. For example, it includes the question of for which orders a finite projective plane exists. If I got the numbers right, consider $n=m=157$ and $B$ which is 13 on the diagonal and 1 off the diagonal. Then $X$ would be a projective plane of order 12, which is a famous unsolved problem. More generally, the existence problem for balanced incomplete block designs can be posed in this way. So it would be exceedingly interesting if an efficiently computable answer to your question existed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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