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
    Do you really mean $a_{ii}=0$? The diagonal of $XX^t$ is the dot product of the $i^{th}$-row of $X$ with itself. This is the length of the $i^{th}$-row squared so if it's zero then the entire row is zero and so $X=0$. Your assumption $\sum_{j} x_{ij}=2$ forces the diagonal of $A$ to be 2's.2011-10-19
  • 0
    Yes but, if the diagonal of A is irrelevant to me, can be 0 or 2 or 3 or any other number...I just need the equation holds to the other values of ${a_i}_j$.2011-10-19
  • 0
    Is your constraint that $\sum_{j=1}^{m}x_{ij}=2$ for the $3\times3$ case, or in general?2011-10-19
  • 5
    Note that if $B$ is orthogonal (so $BB^t=I$), then $(XB)(XB)^t=XX^t$, so if your equation has one solution, it has lots and lots of them.2011-10-19
  • 0
    @Mike Wierzbicki, it's for a $nxn$ matrix.2011-10-19
  • 0
    @Gerry Myerson, very interesting, dont thought that. Thx. Unfortunally find solutions is the problem...But I will remember you process, really helpull.2011-10-19
  • 0
    I think it's a really good question to ask. I not intermediate in Linear Algebra so, this recently founded articles above maybe can't help me so much, but I will try to read them all soon. Appreciate if anyone have a easier solution. Thx.2011-10-21
  • 2
    *Hint on why there is a limited response to this question:* This is an [integer programming](http://en.wikipedia.org/wiki/Integer_programming) problem. Actually a variant of TSP.2011-10-25
  • 0
    The change from "its" to "it's" in your last edit was wrong; the contraction of "it is" is spelled with an apostrophe and the possessive pronoun for "it" is spelled without one.2011-10-26
  • 0
    Observation (that you've probably made already): for any such $X$, each row has to have exactly two 1's. For a given $n$, that gives only ${n \choose 2}$ possible candidates (which is probably better than $mn$).2011-10-26
  • 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. Thx about the contribution.2011-10-26

0 Answers 0