Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
3  
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? –  quid May 21 '12 at 14:48

1 Answer 1

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|improve this answer
    
that's a nice one! –  Felix Goldberg May 21 '12 at 13:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.