Start by fixing invertible matrics $A\_1, \ldots, A\_m \in \mathbb{Z}^{n \times n}$. 


For a sequence $i\_1, \ldots, i\_k$ we construct $A = A\_{i\_1} \cdots A\_{i\_k}$. We would like to know "Is 1 an eigenvalue of $A$?".


As we are doing this for a large number of sequences (the naive computations when $n \sim 6$, $m \sim 16$, $k \sim 12$ take days) we can assume that any information (for example LU decomposition) wanted about $A\_i$ is essentially free. 



> 
> Is there a faster way to determine if 1 is an eigenvalue of $A$ than computing $A$ and checking if $\det(A - Id\_k) = 0$?
> 
> 
> 



Does a product of matrices have eigenvalue 1
You can use Sylvester's determinant theorem $\det(I+AB) = \det(I+BA)$ to reuse the results.
For example, $\det(I-A\_1 A\_2 A\_3 A\_4) = \det(I-A\_2 A\_3 A\_4 A\_1) = \det(I-A\_3 A\_4 A\_1 A\_2 )$
$ = \det(I-A\_4 A\_1 A\_2 A\_3 )$


