Welcome to MathOverflow

Question

2

1

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

flag	asked May 21 2012 at 10:08 qwerty1793 1,425●1●5●12

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 2012 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? – qwerty1793 May 21 2012 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 2012 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. – qwerty1793 May 21 2012 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 2012 at 14:48

show 1 more comment

Stanislav · Accepted Answer · 2012-05-21 12:36:41Z UTC

9

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

answered May 21 2012 at 12:36

Stanislav
304●2●6

that's a nice one! – Felix Goldberg May 21 2012 at 13:10

Does a product of matrices have eigenvalue 1

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.