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