The Fifth Power of a Special $8 \times 8$ Binary Matrix

Question

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.

Answer 1

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].