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$?

everypossible $A$ that is a product of a sequence of $k$ $A_{i}$s? – Felix Goldberg May 21 '12 at 10:19