

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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

share|cite|improve this question
I'm not sure I understand. For a fixed sequence of indices you get just a $n \times n$ matrix, whose spetrcum is seemingly easy to compute. So - do you actually mean to ask if $1$ is an eigenvalue of $A$ for every possible $A$ that is a product of a sequence of $k$ $A_{i}$s? – Felix Goldberg May 21 '12 at 10:19
Yes the spectrum is easy to compute (this is even easier as I just want to know if 1 is in the spectrum or not) but is there a faster way to do this than the naive computation. As I'm doing this repeatedly for various sequences is there anyway to reuse some of the information I find out about one sequence to determine some information about another 'similar' sequence? – Mark Bell May 21 '12 at 12:20
Ok, so the answer to my question is 'no', right? You do consider each sequence (or many of them) separately, you just want to do it in an efficient way. correct? – Felix Goldberg May 21 '12 at 13:11
Correct, you could also think of my problem as "produce a list of all sequences i_1, ..., i_k such that 1 is an eigenvalue of A_i_1 ... A_i_k". Currently I just consider each sequence in turn, compute the product and check if 1 is an eigenvalue or not by computing a determinant. Sorry for the confusion. – Mark Bell May 21 '12 at 13:18
Just to be sure, by 'sequence' you actually mean a sequence in (1,...,m), so repetitions allowed and not necessarily ascending? Say, something like 3,3,3,1, would be admissible, or are there some restrictions? – user9072 May 21 '12 at 14:48
up vote 10 down vote accepted

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

share|cite|improve this answer
that's a nice one! – Felix Goldberg May 21 '12 at 13:10

Your Answer


