3
$\begingroup$

My Question:

We want to find an $8 \times 8$ binary matrix $\bf A$ such that $\bf A$ holds on the next three conditions:

1) The number of non-zero entries of $\bf A$ is $13$.

2) The matrix $\bf A$ is non-singular matrix over $\mathbb{F}_2$ which means $\det({\bf A})=1$ over $\mathbb{F}_2$.

3) All entries of ${\bf A}^5$ are positive integer numbers, denoted with ${\bf A}^5>0$.

When I search with software, I couldn't find an $8 \times 8$ binary matrix which satisfies the mentioned conditions. In fact, all matrices that I obtained has $14$ non-zero entries. For instance, consider the following matrix:

$$\tag{1} {\bf A}= \left( \begin{array}{cccccccc} 0&0&1&0&0&0&1&0\\ 0&0&0&1&0&1&0&0\\ 1&0&0&0&0&0&1&0\\ 0&0&0&0&0&1&0&0\\ 1&1&0&0&0&0&0&0\\ 0&0&0&0&0&0&1&1\\ 0&1&0&0&1&0&0&0\\ 1&0&0&0&0&0&0&0 \end {array} \right). $$

Although the matrix $\bf A$, given in $(1)$, is non-singular over $\mathbb{F}_2$ and ${\bf A}^5>0$, the number of non-zero entries of $\bf A$ are $14$.

My question in terminology of graph theory is that: How to find a directed graph $\bf G$ with $8$ vertexes and $13$ edges such that

1) There is a walk of length $5$ between any two vertices of $\bf G$.

2) The adjacency matrix of $\bf G$ is non-singular over $\mathbb{F}_2$.

Edit: Based on the first comment of Professor Petrov, the first condition, is edited.

Maybe by language of graph theory, it can be proved that the mentioned question has no answer. Please notice that the graph $\bf G$ can have loop and parallel edges.

I appreciate your assistance in this question.

$\endgroup$
  • 1
    $\begingroup$ See: math.stackexchange.com/q/1188600/73324 $\endgroup$ – vadim123 Sep 8 '18 at 15:40
  • $\begingroup$ @ThomasGrubb The matrix $\bf A$ can be a symmetric or asymmetric matrix. We have no this limitation on matrix $\bf A$. I'm eager to see at least one example. Thanks. $\endgroup$ – user0410 Sep 8 '18 at 15:44
  • 1
    $\begingroup$ @user0410 I apologize, I did not see positive integers for the 3rd condition. Interesting problem! $\endgroup$ – TomGrubb Sep 8 '18 at 15:47
  • $\begingroup$ @ThomasGrubb No problem. After one day with a lot of searches just I want to see one example. $\endgroup$ – user0410 Sep 8 '18 at 15:49
  • 1
    $\begingroup$ The requirement that the minimal distance is 5 is different from the requirement that $A^5$ has positive entries. The latter means that there exists a path of length exactly 5 between any two vertices. $\endgroup$ – Fedor Petrov Sep 8 '18 at 16:40
2
$\begingroup$

Here is one solution:

$$A = \left( \begin{array}{cccccccc} 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \right)\qquad A^5 = \left( \begin{array}{cccccccc} 10 & 6 & 3 & 7 & 4 & 8 & 4 & 5 \\ 4 & 2 & 1 & 3 & 1 & 3 & 2 & 2 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 \\ 4 & 1 & 1 & 2 & 1 & 2 & 1 & 2 \\ 7 & 4 & 1 & 5 & 2 & 5 & 2 & 2 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 3 & 1 & 1 & 2 & 1 & 2 & 1 & 2 \\ 6 & 3 & 1 & 4 & 2 & 4 & 2 & 2 \\ \end{array} \right)$$

I found this by using Mathematica's SAT solver on the problem, with an initial guess that $A_{i,i+1\bmod8} = 1$ for $i=1,\dots,8$. (This guarantees that $\det A \ne 0$, which is a good first step for $\det A$ being odd.)

For reference, here is my code. First, the setup:

vars = Flatten@Table[x[i, j], {i, 1, 8}, {j, 1, 8}];
fixPerm = {2, 3, 4, 5, 6, 7, 8, 1};
fixVars = Table[x[i, fixPerm[[i]]], {i, 1, 8}];
vars = Complement[vars, fixVars];
fixRule = Table[v -> True, {v, fixVars}];
fixCond = And @@ fixVars;
count = BooleanCountingFunction[{5}, 56] @@ vars;
det = Xor @@ Table[And @@ Table[x[i, p[[i]]], {i, 1, 8}],
    {p, Permutations[Range[8]]}];
pos = And @@ Flatten@Table[Or @@ Flatten@
    Table[x[i, a] && x[a, b] && x[b, c] && x[c, d] && x[d, j], 
    {a, 1, 8}, {b, 1, 8}, {c, 1, 8}, {d, 1, 8}],
    {i, 1, 8}, {j, 1, 8}];
det = det /. fixRule;
pos = pos /. fixRule;

(Here, count, det, and pos are the three conditions on $A$. We pick the permutation fixPerm for the permutation matrix contained in $A$; if this particular choice didn't work, I was going to try a different one. Then we modify the problem to set the positions indicated by fixPerm to True.)

Then a solution is found using SatisfiabilityInstances[count && det && pos, vars].

$\endgroup$
  • $\begingroup$ I really appreciate you taking the time to find this nice solution. I have a question. Is it possible to ask you to modify your code until that you obtain a solution with 12 or less non-zero elements. I want to thanks again for your nice solution. $\endgroup$ – user0410 Sep 9 '18 at 7:58
  • 1
    $\begingroup$ @user0410 There are no such solutions. This is even easier to check, since - once you fix the initial permutation to set to 1 in only 22 ways, there are only $\binom{56}{0} + \binom{56}{1}+\binom{56}{2}+\binom{56}{3}+\binom{56}{4}$ possibilities to check, so we can try them all. $\endgroup$ – Misha Lavrov Sep 9 '18 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.