Let $A,B\in M_{n}\mathbb(F_2)$ such that each column has exactly one entry equal to 1 and all the other entries are zero. Can you find a criterion/algorithm to check if there is a sequence of multiples of $A,B$ (like $ABBABAA,BABBA,...$) so that the product equal to $P\in M_{n}\mathbb(F_2)$ - each column of P is $e_i$ for constant $i$?
for example - if both matrices are invertible there is no such sequence so that the product is $P$.
A little Progress:
Let's look at the graph whose the adjacency matrix of the graph is $A$. If:
1) The graph is connected
2) There is exist a single loop
3) there are no cycles
there's exist a positive integer k such that $A^k = P$
Here is an algorithm that runs in $O(n^2)$ time:
First, observe that $A$ and $B$ map every elementary column to another elementary column, so what we really have is a finite set $X=\{\mathbf e_1,\ldots\mathbf e_n\}$ and two functions $f_A, f_B:X\to X$, and we want to know if there is some composition sequence of $f_A$ and $f_B$ that is a constant function.
The crucial fact is now:
Here "only if" is trivial. For "if", suppose we have a certain subset $A\subseteq X$ that we want to compress into a single element. Choose two elements of the subset, and apply the composition sequence that unifies them. The result is of that, $A'=(f_1\circ \cdots\circ f_k)(A)$, has fewer elements than $A$; proceed by induction until $|A|=1$.
Now construct a directed graph whose nodes are the size-2 subsets of $X$, plus a designated "you win" node. The node $\{x_1,x_2\}$ has edges going to $\{f_A(x_1),f_A(x_2)\}$ and $\{f_B(x_1),f_B(x_2)\}$, or to "you win" if either of these is a singleton set.
Now the desired property holds if every node in the graph can reach "you win". This can be checked by a single depth-first through the opposite graph in time linear in the size of the graph -- which means quadratic in $n$.