3
$\begingroup$

The problem:

$XX^t=A$, $\quad$ ($X_{ij}\in\{0,1\}$, $\quad$ $\sum_{j=1}^m x_{ij}=2$), $\quad$ $X=?$

Details:

$n,m \in N$

$A \in \{0,1,2\}^{n \times n}$

$X \in \{0,1\}^{n \times m}$

$A$ is a $n\times n$ symmetric matrix where the diagonal is always 2 and having off-diagonal elements just $1$ or $0$.

$(i \neq j)$ -> $A_{ij}=A_{ji}\in\{0,1\}$

$A_{ii}=2$

For example:

$A= \left( \begin{array}{ccc} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{array} \right) $

Also, $X$ is a $n \times m$ matrix where its entries are either $1$ or $0$ i.e. $X_{ij}\in\{0,1\}$ and columns have sum equal $2$:

$X_{ij}\in\{0,1\}$ $\sum_{j=1}^m x_{ij}=2$

For example:

$X=X^T= \left( \begin{array}{ccc} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{array} \right) $

And now, $ XX^T= \left( \begin{array}{ccc} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{array} \right) \left( \begin{array}{ccc} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{array} \right) = \left( \begin{array}{ccc} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{array} \right) $

So,

$XX^t=A$

How can to find all $X$ matrices who satisfies this equation?

See this a bit general problem.

I would like a human readable process (to understand the process) and a way how to use Matlab, Mathematica or gap to solve this without brute force algorithms (just clever math).

Looking the answer of the another question. I had found recently these links.

Completly Positive Matrices

Solving X times Transpose of X Is Equal to A - Over Integers

Representation of Groups - An Computational Approach See 2.8.15 on page 161.

  • 0
    Yes @JackManey. That's true. But unfortunally probably we need implement a brute force algorithm. And I would like another way. Edited the question evidenciate this. Th$x$ $a$bout the contribution.2011-10-26

0 Answers 0