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)$?

  • $\begingroup$ This is a discrete problem, so perhaps look at 2x2 and 3x3 matrices, and see if there is some obvious bijection/pattern? $\endgroup$ – Per Alexandersson Jun 8 '14 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$ – Mark Wildon Jun 8 '14 at 16:47
  • $\begingroup$ @MarkWildon Yes, I think that should actually be a $m.$ $\endgroup$ – Jernej Jun 8 '14 at 16:50
  • $\begingroup$ It is still not clear whether you intend $m$ to be fixed or not. $\endgroup$ – Mark Wildon Jun 9 '14 at 10:28
  • $\begingroup$ @MarkWildon I am sorry I have corrected to post to indicate that $m$ is fixed. $\endgroup$ – Jernej Jun 9 '14 at 10:38

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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