Proving that a system of polynomial matrix equations over $\mathbb{F_2}$ has no solution

Question

I am working on a problem involving nilpotent matrices over $\mathbb{F}_2$ and I was able to reduce it to proving that the system \begin{equation} \begin{cases} A^2+ BC+ BCA+ ABC+A = I_4 \\ AB+ABD+BCB = 0 \\ CA+DCA+CBC = 0 \\ DCB+CBD = I_4 \\ A^3+BCA+ABC+BDC=0 \\ A^2B+BCB+ABD+BD^2=0 \\ CA^2+DCA+CBC+D^2C=0 \\ CAB+DCB+CBD+D^3=0 \end{cases}\,, \end{equation} has no solution, where $A, B, C, D$ are $4 \times 4$ matrices over $\mathbb{F}_2.$ The first four equations were obtained by plugging-in matrices to some polynomial in $\mathbb{F}_2$ while the other four came from the condition that $$\left[ \begin{array}{c|c} A & B \\ \hline C & D \end{array} \right]^3 = 0.$$

Any advice on how to prove this? Any help would be appreciated.

The original problem is if $$M=\begin{bmatrix} N & 0 \\ 0 & N \end{bmatrix}, \mbox{ where } N=\begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1\end{bmatrix}$$ then $M$ cannot be written as a sum $X+Y$ such that $X^3=0$ and $Y^2=Y.$ Here $M, X, Y$ are matrices over $\mathbb{F}_2$.

Write $X=[x_{i,j}], Y=[y_{i,j}]$. For each $(i,j)$, $i,j \in \{1, \ldots, 8\}$, $x_{i,j}$ and $y_{i,j}$ satisfies the following equations: \begin{equation} \begin{cases} \displaystyle \sum_{k=1}^8\sum_{l=1}^8 x_{i,k}x_{k,l}x_{l,j}=0\\ \displaystyle \sum_{k=1}^8 y_{i,k}y_{k,j}=y_{i,j}\\ x_{i,j}+y_{i,j}=m_{i,j} \\ x_{i,j}^2= x_{i,j} \\ y_{i,j}^2= y_{i,j} \end{cases}\,, \end{equation}

So we want to show that this system has no solution via Groebner basis and implement it using Maple. I have zero background in Maple so I need help with the code. So what I've researched is we start with

with(Groebner);

and define matrix $M$:

M:=[[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,0,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]];

Define the following polynomials for all $(i,j)$:

f_{i,j}= \sum_{k=1}^8\sum_{l=1}^8 x_{i,k}x_{k,l}x_{l,j};
g_{i,j}= \sum_{k=1}^8 y_{i,k}y_{k,j}-y_{i,j};
h_{i,j}=x_{i,j}+y_{i,j}-M[i,j];
q_{i,j}=x_{i,j}^2-x_{i,j};
s_{i,j}=y_{i,j}^2-y_{i,j};

and we let for all $(i,j)$

B:=[f_{i,j},g_{i,j},h_{i,j},q_{i,j},s_{i,j}];

and call

G:=Groebner[Basis](B, plex(x_{i,j},y_{i,j}), characteristic=2);

We expect that the output is

G:=[1]

Is this correct? Also, how do I typeset the summations in Maple, and how do I typeset the polynomials so that I don't have to manually type for all 64 pairs $(i,j)$? Thank you so much.

Answer 1

We can solve quickly this problem using the basis Grobner theory.

Put $X=[x_{i,j}],Y=[y_{i,j}]$.

We consider -over a field of characteristic $2$- the algebraic system in the $128$ unknowns $x_{i,j},y_{i,j}$ constituted by the equations $M=X+Y,X^3=0,Y^2=Y$ -entrywise- and $x_{i,j}^2=x_{i,j},y_{i,j}^2=y_{i,j}$.

With the help of the FGb library of Maple, we obtain (in 36") that there are no solutions.

$\textbf{Answer to the OP.}$ The maple command "with(Groebner)" is not very efficient; prefer the command "with(FGb)". You need to load the patch here (available only on LINUX)

http://www.mathemagix.org/www/mfgb/doc/html/install_fgb.en.html

Otherwise use "with(Groebner) but it may be a long way.

You can also use "Sage" very powerful but not very practical to use. Here is the program I used.

restart:

with(LinearAlgebra):

n := 8:

N := Matrix([[0, 0, 0, 1], [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 1]]):

M := DiagonalMatrix([N, N]):

X := Matrix(8, symbol = x):

Y := Matrix(8, symbol = y):

C := M-X-Y: E := X^3: P := Y^2-Y:

K := NULL:

for i to n do

for j to n do

K := K, x[i, j], y[i, j] end do end do:

K := [K]:

F := NULL:

for i to n do

for j to n do

F := F, C[i, j], E[i, j], P[i, j], x[i, j]^2-x[i, j], y[i, j]^2-y[i, j] end do end do:

F := [F]:

with(FGb):

t := time():

solu := fgb_gbasis(F, 2, K, [], {"index" = 10^7, "verb" = 3});

nops(solu):

t3 := time()-t:

Answer 2

There are only $2^{16}$ possible $4 \times 4$ matrices over $\mathbb{F}_2$. That means that by examining $2^{32}$ possibilities, you can exhaust $A$ and $B$. Once $A$ and $B$ are known, your first equation becomes linear, so it's straightforward to solve for $C$. Given $A, B$ and $C$, your second equation now becomes linear and you can solve for $D$.

You will either find a solution or prove that none exists. I'd imagine that a reasonably efficient program should be able to try all the possibilities in a few seconds.