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

Improve this question
$\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$
    – Per Alexandersson
    Commented 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$
    – Mark Wildon
    Commented Jun 8, 2014 at 16:47
  • $\begingroup$ @MarkWildon Yes, I think that should actually be a $m.$ $\endgroup$
    – Jernej
    Commented Jun 8, 2014 at 16:50
  • $\begingroup$ It is still not clear whether you intend $m$ to be fixed or not. $\endgroup$
    – Mark Wildon
    Commented Jun 9, 2014 at 10:28
  • $\begingroup$ @MarkWildon I am sorry I have corrected to post to indicate that $m$ is fixed. $\endgroup$
    – Jernej
    Commented Jun 9, 2014 at 10:38

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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