What are all the binary matrices leading to a given Gramian matrix of non-negative integers as elements?

145 Views Asked by At

A real matrix $\mathbf{G}$ such that for some real matrix $\mathbf{B}$, $\mathbf{G} = \mathbf{B}\mathbf{B}^T$, is called a Gramian matrix. We are interested in a special type of $m \times m$ Gramian matrices $\mathbf{G}$, coming from what we will call a $m \times n$ "basis matrix" $\mathbf{B}$.

This special Gramian matrix $\mathbf{G}$ has the following properties:

  1. All of its values are non-negative integers.
  2. For any row or column, not all of its non-diagonal elements are zero.
  3. The diagonal has the largest non-diagonal element of each row and column as a lower bound.
  4. Every element in the diagonal has the sum of all of its respective row or column non-diagonal elements as an upper bound.

These special possible basis matrices $\mathbf{B}$ have the following properties:

  1. They are binary, this is, composed of only zeroes and ones.
  2. At least one element per column must be different than zero.
  3. Neither the matrix nor any of its column permutations matrices can be written as a direct sum of matrices.

The smallest example where we find two different basis matrices, is apparently the Gramian matrix $$ \mathbf{G_0} = \left( \begin{array}{rrr} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{array} \right).$$ Here, we find two possible basis matrices $$\mathbf{B_1} = \left( \begin{array}{rrr} \textbf{1} & \textbf{1} & \textbf{0} \\ \textbf{0} & \textbf{1} & \textbf{1} \\ 1 & 0 & 1 \end{array} \right),\quad \mathbf{B_2} = \left( \begin{array}{rrrr} \textbf{1} & \textbf{1} & \textbf{0} & 0\\ \textbf{0} & \textbf{1} & \textbf{1} & 0\\ 0 & 1 & 0 & 1 \end{array} \right).$$ We include in the same category their $3!=6$ and $4!=24$ associated matrices coming from columns permutations, for $\mathbf{B_1}$ and $\mathbf{B_2}$ respectively, which leads to the same Gramian matrix $\mathbf{G_0}$. We highlight in bold the common submatrix elements to both solutions.

Can we find all the possible basis matrices $\mathbf{B}$ that can lead to a particular $\mathbf{G}$? How do we do it? Can we know at least the number of possible basis matrices? Or any other related information? Maybe this problem is hard to solve for a general case, but any hint, suggestion, idea, or especially any reference is highly appreciated anyway.

For those of you interested, this problem arises from studying weighted projections from bipartite graphs, and you can check more details here.