Revision history [back]

As I explained in the comments, it's unwise to ignore the condition that "each matrix product $A_iA_j$ is a linear combination of $A_i$'s with integer coefficients". If this condition is employed at earlier stages, a supercomputer may not be needed, and if it's ignored until later stages, a supercomputer may not be able to help.

In particular, this condition means that the lattice spanned by matrices $A_i$ must contain all powers of the given matrix $M$. It also follows that the number of matrices should be at least the degree of the minimal polynomial of $M$. In the given example, we have

M = matrix(3,3, [1, 1, 1, -1, 1, 1, -1, -1, 1])
k = M.minpoly().degree()

which gives $k=3$. So, the powers of $M$ span a subspace $V:=\langle M^0, M^1, M^2\rangle$. Since the span $\langle A_1, A_2, A_3, A_4\rangle$ contains $V$, we have all $A_i\in \langle M^0, M^1, M^2, A_1\rangle$. So, one can try to go over all 01-matrices $A_1$, and then find all 01-matrices in $\langle M^0, M^1, M^2, A_1\rangle$ to restrict the set of candidates for $A_2, A_3, A_4$.