<p>I got a poly-time algorithm for this (rather trivial problem)problem, i.e. for checking whether the joint spectral radius(JSR) is zero or not, in 1995: <a href="http://en.wikipedia.org/wiki/Joint_spectral_radius">http://en.wikipedia.org/wiki/Joint_spectral_radius</a></p>

<p>The story behind the algorithm is roughly as follows: Blondel and Tsitsiklis wrongly stated
that for boolean matrices checking whether JSR &lt; 1 is NP-HARD. For any set of integer matrices
JSR is ether zero or greater or equal 1. So the counter example to their statement was
my algorithm(see the errata to their paper). The main moral: consult the Wikipedia first!</p>

CC BY-SA 3.0
2013-06-18T19:28:23.787Z
2013-06-18T19:28:23.787Z
leonid gurvits
<p>The question you are asking is exactly equivalent to deciding whether the joint spectral radius (JSR) of the set of matrices is strictly less than one. Decidability of this question has remained open for quite some time now. (In control theory, this is equivalent to decidability of stability of switched linear systems under arbitrary switching.)</p>

<p>The following variant of your question is known to be undecidable:
Given a finite set of square matrices, decide whether all products remain bounded; 
<a href="http://www.mit.edu/~jnt/Papers/J081-00-vb-products.pdf" rel="nofollow">see here</a>.</p>

<p>The undecidability of the above remains valid even if you have only 2 matrices of size 47x47: <a href="http://perso.uclouvain.be/vincent.blondel/publications/01BC-pfa.pdf" rel="nofollow">see here</a>.</p>

<p>In the JSR language, the question of testing "is JSR $\le 1$?" is undecidable (see references above), but decidability of testing "is JSR $&lt; 1$?" is open.
The latter question is related to the so-called <a href="http://arxiv.org/pdf/1006.2117v2.pdf" rel="nofollow">"rational finiteness conjecture":</a>
If the rational finiteness conjecture is true, then the question you are asking is decidable.</p>

<p>Finally, unless P=NP, the JSR is not approximable in polynomial time (in the precise sense defined in <a href="http://www.mit.edu/~jnt/Papers/J064-97-vb-spectr.pdf" rel="nofollow">this paper</a>).</p>

<p>As a result, one of the answers above which claims an efficient algorithm must be false.</p>

<p>On the positive side, there are several algorithms (e.g. based on semidefinite programming) for approximating the JSR. The different algorithms come with different performance guarantees. See e.g. the following (shamelessly by myself and my colleagues - but see also references <a href="http://web.mit.edu/~a_a_a/Public/Publications/jsr_path_complete_graph_lyap.pdf" rel="nofollow">therein</a>).</p>

<p>In several special cases, the question you are asking is polynomial time decidable. For example, when the matrices are symmetric, or rank one, or if they commute.</p>

<p>Finally, a great book on the subject is the <a href="http://link.springer.com/book/10.1007/978-3-540-95980-9/page/1" rel="nofollow">following</a>.</p>

CC BY-SA 3.0
2013-06-08T19:12:50.270Z
Please read the formal statement of the  question I asked - it is *not* equivalent to deciding whether the JSR is strictly less than one. You are, perhaps, misled by the title of the question. In short, I'm asking about every product equaling zero in *finite time*, rather than in an asymptotic sense.
robinson
CC BY-SA 3.0
2013-06-08T21:23:46.553Z
Then the question you are asking is much simpler. The following are equivalent:

(i) The condition you define 

(ii) All finite products are nilpotent 

(iii) The JSR = 0 

(iv) All products of length n are zero (n is the dimension, this is independent of the number of matrices k) .


The last condition obviously implies decidability, and if fact you can check the condition in polynomial time. See Section 2.3.1 of the book by Jungers linked at the end of my post.

My apologies for thinking that you meant the asymptotic version. (I was misled by the phrase "all products eventually equal zero".)
Amir Ali Ahmadi
CC BY-SA 3.0
2013-06-09T02:58:11.810Z
In which case, @AmirAliAhmadi doesn't the answer by Joshua Grochow cover it ?
Suresh Venkat
CC BY-SA 3.0
2013-06-09T07:29:26.000Z
It seems to me that it does, with a different algorithm than what I have in mind. (Again, my apologies for thinking that the question was "do all products converge to zero" (i.e., JSR<1?) whose decidability is open.) There are a few differences though with the answer of Joshua. (1) In the equivalence of (i)-(iv) in my previous comment, I don't think Konig's Lemma needs to be used. (2) I don't understand why he is taking linear combinations of the matrices. (3) I copy below a simple alternative algorithm from Section 2.3.1 of the book by Jungers, attributed there to Leonid Gurvits.
Amir Ali Ahmadi
CC BY-SA 3.0
2013-06-09T07:44:40.833Z
[continued from above...] All we need to check is whether all products of length $n$ are zero, but there are $k^n$ such matrices. To avoid this, define the following matrices iteratively: $X_0=I,\ X_j=\sum_{i=1}^k A_i^TX_{j-1}A_i$. Then, one has $X_n=\sum_{A\mbox{ product of length n}}A^TA$. This matrix can be computed by $kn$ matrix multiplications, and is zero if and only if all products of length $n$ are zero.
Amir Ali Ahmadi
CC BY-SA 3.0
2013-06-09T19:37:12.897Z
Very interesting - thank you for the pointer to the thesis.
robinson
CC BY-SA 3.0
2013-06-12T01:48:54.563Z
@AmirAliAhmadi: Very cool! I think (but am not 100% sure) that Konig's Lemma is essentially still used in the proof you cite, in the form of compactness in Lemma 2.2 of the Jungers book. BTW, the reason I considered linear combinations is because that avoids the $k^n$ and replaces it with $n^2$, and I didn't see another way to avoid the $k^n$ at the time. You provided another very elegant such way.
Joshua Grochow
CC BY-SA 3.0
2013-06-08T16:09:08.043Z
2013-06-08T21:27:35.943Z
2013-06-08T21:27:35.943Z
Amir Ali Ahmadi
<p><em><strong>Edit: This answer is unfortunately incorrect. The error is highlighted below.</em></strong> The argument does work if we are allowed to transpose the matrices.</p>

<p>We start by proving a lemma.</p>

<p><b>Lemma.</b> Let $A$ be an $n\times n$ matrix and let $N$ be the $n\times n$ matrix with ones on the secondary diagonal. If $AN^t$ and $N^tA$ are nilpotent for all $t \geq 0$ then $A = 0$. <strong><em>Correct conclusion: $A$ is upper triangular with zeroes on the diagonal.</em></strong> (The original conclusion is recovered if we are also allowed to multiply by powers of the transpose of $N$.)</p>

<p><b>Proof.</b> Suppose for example that $n = 3$, and write
$$ A = \begin{pmatrix} a &amp; b &amp; c \\ d &amp; e &amp; f \\ g &amp; h &amp; i \end{pmatrix}, \quad N = \begin{pmatrix} 0 &amp; 1 &amp; 0 \\ 0 &amp; 0 &amp; 1 \\ 0 &amp; 0 &amp; 0 \end{pmatrix}. $$
We start by calculating $AN^2$:
$$ AN^2 = \begin{pmatrix} 0 &amp; 0 &amp; a \\ 0 &amp; 0 &amp; d \\ 0 &amp; 0 &amp; g \end{pmatrix}. $$
This matrix is in triangular form, and so if $AN^2$ is nilpotent then $g = 0$. Continue with $AN^1$:
$$ AN^1 = \begin{pmatrix} 0 &amp; a &amp; b \\ 0 &amp; d &amp; e \\ 0 &amp; g &amp; h \end{pmatrix} = \begin{pmatrix} 0 &amp; a &amp; b \\ 0 &amp; d &amp; e \\ 0 &amp; 0 &amp; h \end{pmatrix}. $$
Again the matrix is in triangular form, and so if $AN^1$ is nilpotent then $d = h = 0$. Continuing,
$$ AN^0 = \begin{pmatrix} a &amp; b &amp; c \\ 0 &amp; e &amp; f \\ 0 &amp; 0 &amp; i \end{pmatrix}. $$
As before, we conclude that $a = e = i = 0$, and so $A$ is upper triangular with zeroes on the diagonal.</p>

<p>If we now consider $N^2A,N^1A,N^0A$ instead, then we conclude that $A$ is lower triangular with zeroes on the diagonal. <strong><em>In fact, we don't get anything new from considering $N^tA$.</em></strong> Therefore $A = 0$. $\square$</p>

<p><em><strong>This is how the proof would go if the original version of the lemma were correct.</em></strong>
Now back to the problem at hand. Say that the matrices $A_1,\ldots,A_k$ satisfy property P if for every infinite sequence $i_1,\ldots \in [k]$, we have $A_{i_1} \cdots A_{i_m} = 0$ for some $m$. If one of the matrices $A_i$ is <em>not</em> nilpotent then property P clearly fails, so suppose that all the matrices are nilpotent. If all matrices commute then property P clearly holds, so suppose that $A_1 A_2 \neq A_2 A_1$. Change basis so that $A_1$ is in Jordan normal form, and let the corresponding decomposition of the vector space be $V_1 \oplus \cdots \oplus V_t$. Let $V_i$ be a vector space on which $A_1 A_2 \neq A_2 A_1$; note that $\dim V_i &gt; 1$ since $0$ commutes with everything. Restricted to $V_i$, $A_1 = N$ and $A_2 \neq 0$. Therefore the lemma implies that for some $t \geq 0$, either $A_2 A_1^t$ or $A_1^t A_2$ is not nilpotent, and therefore property P clearly fails.</p>

<p>Summarizing, property P holds iff all matrices are nilpotent and all of them commute.</p>

CC BY-SA 3.0
2013-05-22T21:25:57.310Z
The last sentence of your lemma's proof is not correct. $N^2 A$ nilpotent implies $g = 0$, $N^1 A$ nilpotent gives $d = h = 0$, and $N^0 A$ nilpotent gives $a=e=i=0$. So we only conclude that $A$ is upper triangular with zeros on the diagonal, not that $A$ is diagonal (and hence zero).
Joshua Grochow
CC BY-SA 3.0
2013-05-22T21:52:08.910Z
Indeed , this answer is not correct. If no one else does, I'll post a counter example to both the lemma and the final assertion when I get home later today.
robinson
CC BY-SA 3.0
2013-05-22T22:41:17.507Z
As usual, it is when something is claimed but not proved that the proof fails. Oh well...
Yuval Filmus
CC BY-SA 3.0
2013-05-23T01:37:02.263Z
So the example I had in mind was:

$$A_0 = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}, A_1 = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} $$ One can verify that every product of sufficient length of these two matrices is zero but they don't commute, and the second one is not zero.
robinson
CC BY-SA 3.0
2013-05-22T06:08:33.517Z
2013-05-22T22:47:09.920Z
2013-05-22T22:47:09.920Z
Yuval Filmus
<p>Your question is equivalent to whether $A_1, \dotsc, A_k$ generate a nilpotent algebra<strike>, which in turn is equivalent to each of the $A_i$ being nilpotent</strike>. Hence not only is it decidable, but in $\tilde O(n^{2 \omega})$ time where $\omega$ is the exponent of matrix multiplication. </p>

<p>Let $\mathcal{A}$ be the associative algebra generated by the $A_i$: that is, take all linear combinations of the $A_i$ and all finite products thereof. $\mathcal{A}$ is called <em>nilpotent</em> if there is some $N$ such that every product of $N$ elements of $\mathcal{A}$ is zero.</p>

<p>First, let's see why your condition implies that $\mathcal{A}$ is nilpotent. This follows from Konig's Lemma (compactness): every string of length $n$ over the alphabet $\{1, \dotsc, k\}$ corresponds to a product of $A_1, \dotsc, A_k$ of length $n$ in an obvious manner. Consider the infinite $k$-ary rooted tree, whose nodes are naturally in bijective correspondence with strings over $\{1, \dotsc, k\}$. Consider the sub-tree $T$ consisting of those nodes where the corresponding product of the $A_i$ is nonzero. Konig's Lemma says that if $T$ is infinite, then it has an infinite path (exactly violating your property), hence $T$ is finite. We can then take $N$ to be the maximum length of any string in $T$. So your property implies that $\mathcal{A}$ is nilpotent.</p>

<p>The converse is also true, since every element of $\mathcal{A}$ is a linear combination of products of the $A_i$. </p>

<p>Next, note that $\mathcal{A}$ is a subalgebra of $n \times n$ matrices, and hence is finite-dimensional.</p>

<p>Finally: a finite-dimensional associative algebra in characteristic zero has a basis of nilpotent elements (commuting or not - this is the part that contradicts Yuval's answer) iff it is nilpotent (see, e.g., <a href="http://www.encyclopediaofmath.org/index.php/Nilpotent_algebra">here</a>). </p>

<p>Thus, to solve your problem, find a basis for the associative algebra generated by the $A_i$ (by the linear-algebra version of breadth-first search) and check that every matrix in the basis is nilpotent. The upper bound $\tilde O(n^{2\omega})$ comes from solving a system of linear equations in $n^2$ variables in the breadth-first search. As $\dim \mathcal{A} \leq n^2$ the BFS can't last very long, and because these are $n \times n$ matrices to check if a matrix $A$ is nilpotent one needs only check that $A^n = 0$.</p>

CC BY-SA 3.0
2013-05-22T21:55:32.143Z
But it is possible to find two nil potent matrices such that no power of their product is zero: take the upper shift and lowers shift in dimension greater than two. Am I missing something or does this contradict your answer?
robinson
CC BY-SA 3.0
2013-05-22T22:05:18.570Z
@robinson: You are correct. I fixed the answer. The issue is that the associative algebra generated by the upper shift and lower shift does not have a *basis* of nilpotent elements. The condition in the question is not equivalent to the $A_i$ being nilpotent (as I had before), but just to the *algebra they generate* having a basis of nilpotent elements.
Joshua Grochow
CC BY-SA 3.0
2013-05-22T22:25:36.530Z
Do you think there is a way to show this without using any choice principles (even one as weak as König's Lemma, which is equivalent to $\text{AC}_\omega$)?
András Salamon
CC BY-SA 3.0
2013-05-22T22:29:52.213Z
@Andras: I'd say that's a question for Chris Conidis. He's studied questions like that in (computable) reverse mathematics. I'll ask him and point him here.
Joshua Grochow
CC BY-SA 3.0
2013-05-23T01:40:22.073Z
Thank you for this answer. I hope you don't mind if I ask you a bunch of questions while I process it: 1. So do I understand correctly that your argument proves that this problem is decidable?  2. What is a basis for ${\cal A}$? Googling around, it seems that this must mean the usual notion of a basis when viewing the matrices as vectors in $\mathbb{R}^{n^2}$; is this right?
robinson
CC BY-SA 3.0
2013-05-23T01:52:22.957Z
@robinson: 1) Yes, the problem is decidable, in fact in $O(n^{2\omega})$ time where $\omega$ is the exponent of matrix multiplication. This comes from solving systems of linear equations over $\mathbb{Q}$ when doing the linear algebra breadth-first search.  2) Yes, usual notion of basis when viewing the matrices as vectors in $\mathbb{Q}^{n^2}$ (or over $\mathbb{R}$ or $\mathbb{C}$).
Joshua Grochow
CC BY-SA 3.0
2013-05-23T04:12:43.373Z
Could you explain what the linear algebra version breadth-first search is? Without an a-priori upper bounded on the length of nonzero products, I don't see how to get any bound on the time until a basis of ${\cal A}$ is found.
robinson
CC BY-SA 3.0
2013-05-23T16:23:14.110Z
You start with a basis $\mathcal{B}$ of $\mathcal{A}$. Now you try to find matrices $A \in \mathcal{A}$ and $B \in \mathcal{B}$ such that $AB$ or $BA$ is not in the span of $\mathcal{B}$. If you succeed, add the product to $\mathcal{B}$ and continue. Otherwise, multiplying any matrix in the span of $\mathcal{B}$ by any finite product of matrices in $\mathcal{A}$ always ends up in the span of $\mathcal{B}$. Since the dimension of the algebra is bounded, the process terminates (in at most $n^2$ steps).
Yuval Filmus
CC BY-SA 3.0
2013-05-23T21:19:43.093Z
Got it. One more question: suppose you find a basis for the algebra and not every element in it is nil potent. Might the algebra still be nil potent because there is a different nil potent basis for it? If so how do you account for this in your algorithm?
robinson
CC BY-SA 3.0
2013-05-23T22:04:24.707Z
@robinson: No. If the algebra is nilpotent, then *every* element of the algebra is nilpotent. So if you find any non-nilpotent element then the algebra is not nilpotent (and then there are infinite products of your matrices which are never zero).
Joshua Grochow
CC BY-SA 3.0
2013-05-24T23:30:09.850Z
I understand - the basis itself as constructed in the way you outlined will have only elements of the algebra.
robinson
CC BY-SA 3.0
2013-05-24T23:33:39.080Z
Final question: what is a good source for the claim that a finite-dimensional algebra is nilpotent if and only if it has a nilpotent basis?
robinson
CC BY-SA 3.0
2013-05-25T03:03:12.723Z
And by ``good source,'' I mean something I (a person with no background in algebra beyond the usual undergraduate math course) can read and understand. I fully understand such a source may not exist...
robinson
CC BY-SA 3.0
2013-05-22T21:29:11.523Z
2013-05-24T17:03:41.510Z
2013-05-24T17:03:41.510Z
Joshua Grochow
<p>I am interested in the following problem: given integer matrices $A_1,A_2, \ldots, A_k$ decide if every infinite product of these matrices eventually equals the zero matrix.</p>

<p>This means exactly what you think it does: we will say the set of matrices $\{A_1, \ldots, A_k\}$ has the property that all of its products eventually equal zero if there does <em>not</em> exist an infinite sequence $i_1, i_2, i_3\ldots$, all in $\{1, \ldots, k\}$, such that $$ A_{i_1} A_{i_2} \cdots A_{i_l} \neq 0$$ for all $l$. </p>

<p>Has the problem of deciding whether every product eventually equals zero been studied before? Is it decidable? </p>

<p>Seems like it might be related to matrix mortality, which is undecidable, but I do not see a clear connection. </p>

CC BY-SA 3.0
2013-05-21T21:07:41.907Z
You need some kind of convergence property on the set of matrices to ensure that the infinite product is defined.
András Salamon
CC BY-SA 3.0
2013-05-21T21:15:58.847Z
Are you operating in a finite field or integers with unbounded growth? The $k$=1 case is interesting in it's own right. Using integers from -100 to 100 in a 5x5 matrix, what is the highest power you can get to before it zeros out?
Chad Brewbaker
CC BY-SA 3.0
2013-05-21T23:27:50.750Z
@AndrásSalamon The OP doesn't really refer to infinite products, but to infinite sequences of finite products.
Yuval Filmus
CC BY-SA 3.0
2013-05-21T23:38:13.863Z
How is your problem different from matrix mortality? It seems equivalent. If there is a product $A_{i_1} \cdots A_{i_l} = 0$, then your condition fails. If for all products $A_{i_1} \cdots A_{i_l} \neq 0$, then your condition holds for *every* infinite sequence.
Yuval Filmus
CC BY-SA 3.0
2013-05-22T04:45:50.647Z
@YuvalFilmus - I believe it is different from mortality. Let the dimensions of the matrices be $1$, so that we just have numbers, and suppose $A_0 = 0, A_1=1$. Mortal? Yes because $A_0 = 0$. Every product equal zero? No: not the product $1 \cdot 1 \cdot 1 \cdots$. 

On the other hand, if $A_0=0,A_1=0$ then you have a sequence which is both mortal and every product is zero.
robinson
CC BY-SA 3.0
2013-05-22T04:46:59.213Z
@YuvalFilmus - to put it another way, your assertion "If there is a product $A_{i_1} \cdots A_{i_l} = 0$ then your conditions fails" is incorrect.
robinson
CC BY-SA 3.0
2013-05-22T04:49:48.990Z
@ChadBrewbaker - I was thinking that the entries of the matrices are just integers. I suppose the $k=1$ is interesting from the point of view of: just how many operations do you need to check that matrix is nilpotent? 

Note that if $A$ is nilpotent, then it is easy to see that $A^n = 0$ where $n$ is the dimension of $A$ so presumably you could solve it by squaring the matrix $\log n$ times. I have no idea if this is the best you can do.
robinson
CC BY-SA 3.0
2013-06-05T01:25:26.340Z
Interestingly, this just in: http://arxiv.org/abs/1306.0729. Instead of asking if all products are eventually zero, they ask if some product is eventually positive. They show that the problem is NP-hard (or at least that's what I gather from the abstract).
Joshua Grochow
<linear-algebra><decidability>
Checking if all products of a set of matrices eventually equal zero
robinson
# Checking if all products of a set of matrices eventually equal zero

(Asked by: username_0 on 2013-05-21)

I am interested in the following problem: given integer matrices $A\_1,A\_2, \ldots, A\_k$ decide if every infinite product of these matrices eventually equals the zero matrix.

This means exactly what you think it does: we will say the set of matrices $\{A\_1, \ldots, A\_k\}$ has the property that all of its products eventually equal zero if there does *not* exist an infinite sequence $i\_1, i\_2, i\_3\ldots$, all in $\{1, \ldots, k\}$, such that $$ A\_{i\_1} A\_{i\_2} \cdots A\_{i\_l} \neq 0$$ for all $l$.

Has the problem of deciding whether every product eventually equals zero been studied before? Is it decidable?

Seems like it might be related to matrix mortality, which is undecidable, but I do not see a clear connection.

**Tags:** linear-algebra, decidability

> **Comments:**
> **username_1**: You need some kind of convergence property on the set of matrices to ensure that the infinite product is defined.  
> **username_2**: Are you operating in a finite field or integers with unbounded growth? The $k$=1 case is interesting in it's own right. Using integers from -100 to 100 in a 5x5 matrix, what is the highest power you can get to before it zeros out?  
> **username_3**: @AndrásSalamon The OP doesn't really refer to infinite products, but to infinite sequences of finite products.  
> **username_3**: How is your problem different from matrix mortality? It seems equivalent. If there is a product $A_{i_1} \cdots A_{i_l} = 0$, then your condition fails. If for all products $A_{i_1} \cdots A_{i_l} \neq 0$, then your condition holds for *every* infinite sequence.  
> **username_0**: @YuvalFilmus - I believe it is different from mortality. Let the dimensions of the matrices be $1$, so that we just have numbers, and suppose $A_0 = 0, A_1=1$. Mortal? Yes because $A_0 = 0$. Every product equal zero? No: not the product $1 \cdot 1 \cdot 1 \cdots$.   On the other hand, if $A_0=0,A_1=0$ then you have a sequence which is both mortal and every product is zero.  
> **username_0**: @YuvalFilmus - to put it another way, your assertion "If there is a product $A_{i_1} \cdots A_{i_l} = 0$ then your conditions fails" is incorrect.  
> **username_0**: @ChadBrewbaker - I was thinking that the entries of the matrices are just integers. I suppose the $k=1$ is interesting from the point of view of: just how many operations do you need to check that matrix is nilpotent?   Note that if $A$ is nilpotent, then it is easy to see that $A^n = 0$ where $n$ is the dimension of $A$ so presumably you could solve it by squaring the matrix $\log n$ times. I have no idea if this is the best you can do.  
> **username_4**: Interestingly, this just in: http://arxiv.org/abs/1306.0729. Instead of asking if all products are eventually zero, they ask if some product is eventually positive. They show that the problem is NP-hard (or at least that's what I gather from the abstract).  

---

## 4 answers

### Answer by username_4 on 2013-05-22. Score: 17 | Accepted answer

Your question is equivalent to whether $A\_1, \dotsc, A\_k$ generate a nilpotent algebra, which in turn is equivalent to each of the $A\_i$ being nilpotent. Hence not only is it decidable, but in $\tilde O(n^{2 \omega})$ time where $\omega$ is the exponent of matrix multiplication.

Let $\mathcal{A}$ be the associative algebra generated by the $A\_i$: that is, take all linear combinations of the $A\_i$ and all finite products thereof. $\mathcal{A}$ is called *nilpotent* if there is some $N$ such that every product of $N$ elements of $\mathcal{A}$ is zero.

First, let's see why your condition implies that $\mathcal{A}$ is nilpotent. This follows from Konig's Lemma (compactness): every string of length $n$ over the alphabet $\{1, \dotsc, k\}$ corresponds to a product of $A\_1, \dotsc, A\_k$ of length $n$ in an obvious manner. Consider the infinite $k$-ary rooted tree, whose nodes are naturally in bijective correspondence with strings over $\{1, \dotsc, k\}$. Consider the sub-tree $T$ consisting of those nodes where the corresponding product of the $A\_i$ is nonzero. Konig's Lemma says that if $T$ is infinite, then it has an infinite path (exactly violating your property), hence $T$ is finite. We can then take $N$ to be the maximum length of any string in $T$. So your property implies that $\mathcal{A}$ is nilpotent.

The converse is also true, since every element of $\mathcal{A}$ is a linear combination of products of the $A\_i$.

Next, note that $\mathcal{A}$ is a subalgebra of $n \times n$ matrices, and hence is finite-dimensional.

Finally: a finite-dimensional associative algebra in characteristic zero has a basis of nilpotent elements (commuting or not - this is the part that contradicts Yuval's answer) iff it is nilpotent (see, e.g., [here](http://www.encyclopediaofmath.org/index.php/Nilpotent_algebra)).

Thus, to solve your problem, find a basis for the associative algebra generated by the $A\_i$ (by the linear-algebra version of breadth-first search) and check that every matrix in the basis is nilpotent. The upper bound $\tilde O(n^{2\omega})$ comes from solving a system of linear equations in $n^2$ variables in the breadth-first search. As $\dim \mathcal{A} \leq n^2$ the BFS can't last very long, and because these are $n \times n$ matrices to check if a matrix $A$ is nilpotent one needs only check that $A^n = 0$.

> **Comments:**
> **username_0**: But it is possible to find two nil potent matrices such that no power of their product is zero: take the upper shift and lowers shift in dimension greater than two. Am I missing something or does this contradict your answer?  
> **username_4**: @username_0: You are correct. I fixed the answer. The issue is that the associative algebra generated by the upper shift and lower shift does not have a *basis* of nilpotent elements. The condition in the question is not equivalent to the $A_i$ being nilpotent (as I had before), but just to the *algebra they generate* having a basis of nilpotent elements.  
> **username_1**: Do you think there is a way to show this without using any choice principles (even one as weak as König's Lemma, which is equivalent to $\text{AC}_\omega$)?  
> **username_4**: @Andras: I'd say that's a question for Chris Conidis. He's studied questions like that in (computable) reverse mathematics. I'll ask him and point him here.  
> **username_0**: Thank you for this answer. I hope you don't mind if I ask you a bunch of questions while I process it: 1. So do I understand correctly that your argument proves that this problem is decidable?  2. What is a basis for ${\cal A}$? Googling around, it seems that this must mean the usual notion of a basis when viewing the matrices as vectors in $\mathbb{R}^{n^2}$; is this right?  
> **username_4**: @username_0: 1) Yes, the problem is decidable, in fact in $O(n^{2\omega})$ time where $\omega$ is the exponent of matrix multiplication. This comes from solving systems of linear equations over $\mathbb{Q}$ when doing the linear algebra breadth-first search.  2) Yes, usual notion of basis when viewing the matrices as vectors in $\mathbb{Q}^{n^2}$ (or over $\mathbb{R}$ or $\mathbb{C}$).  
> **username_0**: Could you explain what the linear algebra version breadth-first search is? Without an a-priori upper bounded on the length of nonzero products, I don't see how to get any bound on the time until a basis of ${\cal A}$ is found.  
> **username_3**: You start with a basis $\mathcal{B}$ of $\mathcal{A}$. Now you try to find matrices $A \in \mathcal{A}$ and $B \in \mathcal{B}$ such that $AB$ or $BA$ is not in the span of $\mathcal{B}$. If you succeed, add the product to $\mathcal{B}$ and continue. Otherwise, multiplying any matrix in the span of $\mathcal{B}$ by any finite product of matrices in $\mathcal{A}$ always ends up in the span of $\mathcal{B}$. Since the dimension of the algebra is bounded, the process terminates (in at most $n^2$ steps).  
> **username_0**: Got it. One more question: suppose you find a basis for the algebra and not every element in it is nil potent. Might the algebra still be nil potent because there is a different nil potent basis for it? If so how do you account for this in your algorithm?  
> **username_4**: @username_0: No. If the algebra is nilpotent, then *every* element of the algebra is nilpotent. So if you find any non-nilpotent element then the algebra is not nilpotent (and then there are infinite products of your matrices which are never zero).  
> **username_0**: I understand - the basis itself as constructed in the way you outlined will have only elements of the algebra.  
> **username_0**: Final question: what is a good source for the claim that a finite-dimensional algebra is nilpotent if and only if it has a nilpotent basis?  
> **username_0**: And by ``good source,'' I mean something I (a person with no background in algebra beyond the usual undergraduate math course) can read and understand. I fully understand such a source may not exist...  

---

### Answer by username_5 on 2013-06-18. Score: 6

I got a poly-time algorithm for this (rather trivial problem)problem, i.e. for checking whether the joint spectral radius(JSR) is zero or not, in 1995: <http://en.wikipedia.org/wiki/Joint_spectral_radius>

The story behind the algorithm is roughly as follows: Blondel and Tsitsiklis wrongly stated
that for boolean matrices checking whether JSR < 1 is NP-HARD. For any set of integer matrices
JSR is ether zero or greater or equal 1. So the counter example to their statement was
my algorithm(see the errata to their paper). The main moral: consult the Wikipedia first!


---

### Answer by username_6 on 2013-06-08. Score: 5

The question you are asking is exactly equivalent to deciding whether the joint spectral radius (JSR) of the set of matrices is strictly less than one. Decidability of this question has remained open for quite some time now. (In control theory, this is equivalent to decidability of stability of switched linear systems under arbitrary switching.)

The following variant of your question is known to be undecidable:
Given a finite set of square matrices, decide whether all products remain bounded;
[see here](http://www.mit.edu/~jnt/Papers/J081-00-vb-products.pdf).

The undecidability of the above remains valid even if you have only 2 matrices of size 47x47: [see here](http://perso.uclouvain.be/vincent.blondel/publications/01BC-pfa.pdf).

In the JSR language, the question of testing "is JSR $\le 1$?" is undecidable (see references above), but decidability of testing "is JSR $< 1$?" is open.
The latter question is related to the so-called ["rational finiteness conjecture":](http://arxiv.org/pdf/1006.2117v2.pdf)
If the rational finiteness conjecture is true, then the question you are asking is decidable.

Finally, unless P=NP, the JSR is not approximable in polynomial time (in the precise sense defined in [this paper](http://www.mit.edu/~jnt/Papers/J064-97-vb-spectr.pdf)).

As a result, one of the answers above which claims an efficient algorithm must be false.

On the positive side, there are several algorithms (e.g. based on semidefinite programming) for approximating the JSR. The different algorithms come with different performance guarantees. See e.g. the following (shamelessly by myself and my colleagues - but see also references [therein](http://web.mit.edu/~a_a_a/Public/Publications/jsr_path_complete_graph_lyap.pdf)).

In several special cases, the question you are asking is polynomial time decidable. For example, when the matrices are symmetric, or rank one, or if they commute.

Finally, a great book on the subject is the [following](http://link.springer.com/book/10.1007/978-3-540-95980-9/page/1).

> **Comments:**
> **username_0**: Please read the formal statement of the  question I asked - it is *not* equivalent to deciding whether the JSR is strictly less than one. You are, perhaps, misled by the title of the question. In short, I'm asking about every product equaling zero in *finite time*, rather than in an asymptotic sense.  
> **username_6**: Then the question you are asking is much simpler. The following are equivalent:  (i) The condition you define   (ii) All finite products are nilpotent   (iii) The JSR = 0   (iv) All products of length n are zero (n is the dimension, this is independent of the number of matrices k) .   The last condition obviously implies decidability, and if fact you can check the condition in polynomial time. See Section 2.3.1 of the book by Jungers linked at the end of my post.  My apologies for thinking that you meant the asymptotic version. (I was misled by the phrase "all products eventually equal zero".)  
> **username_7**: In which case, @AmirAliAhmadi doesn't the answer by username_4 cover it ?  
> **username_6**: It seems to me that it does, with a different algorithm than what I have in mind. (Again, my apologies for thinking that the question was "do all products converge to zero" (i.e., JSR<1?) whose decidability is open.) There are a few differences though with the answer of Joshua. (1) In the equivalence of (i)-(iv) in my previous comment, I don't think Konig's Lemma needs to be used. (2) I don't understand why he is taking linear combinations of the matrices. (3) I copy below a simple alternative algorithm from Section 2.3.1 of the book by Jungers, attributed there to Leonid Gurvits.  
> **username_6**: [continued from above...] All we need to check is whether all products of length $n$ are zero, but there are $k^n$ such matrices. To avoid this, define the following matrices iteratively: $X_0=I,\ X_j=\sum_{i=1}^k A_i^TX_{j-1}A_i$. Then, one has $X_n=\sum_{A\mbox{ product of length n}}A^TA$. This matrix can be computed by $kn$ matrix multiplications, and is zero if and only if all products of length $n$ are zero.  
> **username_0**: Very interesting - thank you for the pointer to the thesis.  
> **username_4**: @AmirAliAhmadi: Very cool! I think (but am not 100% sure) that Konig's Lemma is essentially still used in the proof you cite, in the form of compactness in Lemma 2.2 of the Jungers book. BTW, the reason I considered linear combinations is because that avoids the $k^n$ and replaces it with $n^2$, and I didn't see another way to avoid the $k^n$ at the time. You provided another very elegant such way.  

---

### Answer by username_3 on 2013-05-22. Score: 0

***Edit: This answer is unfortunately incorrect. The error is highlighted below.*** The argument does work if we are allowed to transpose the matrices.

We start by proving a lemma.

**Lemma.** Let $A$ be an $n\times n$ matrix and let $N$ be the $n\times n$ matrix with ones on the secondary diagonal. If $AN^t$ and $N^tA$ are nilpotent for all $t \geq 0$ then $A = 0$. ***Correct conclusion: $A$ is upper triangular with zeroes on the diagonal.*** (The original conclusion is recovered if we are also allowed to multiply by powers of the transpose of $N$.)

**Proof.** Suppose for example that $n = 3$, and write
$$ A = \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}, \quad N = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}. $$
We start by calculating $AN^2$:
$$ AN^2 = \begin{pmatrix} 0 & 0 & a \\ 0 & 0 & d \\ 0 & 0 & g \end{pmatrix}. $$
This matrix is in triangular form, and so if $AN^2$ is nilpotent then $g = 0$. Continue with $AN^1$:
$$ AN^1 = \begin{pmatrix} 0 & a & b \\ 0 & d & e \\ 0 & g & h \end{pmatrix} = \begin{pmatrix} 0 & a & b \\ 0 & d & e \\ 0 & 0 & h \end{pmatrix}. $$
Again the matrix is in triangular form, and so if $AN^1$ is nilpotent then $d = h = 0$. Continuing,
$$ AN^0 = \begin{pmatrix} a & b & c \\ 0 & e & f \\ 0 & 0 & i \end{pmatrix}. $$
As before, we conclude that $a = e = i = 0$, and so $A$ is upper triangular with zeroes on the diagonal.

If we now consider $N^2A,N^1A,N^0A$ instead, then we conclude that $A$ is lower triangular with zeroes on the diagonal. ***In fact, we don't get anything new from considering $N^tA$.*** Therefore $A = 0$. $\square$

***This is how the proof would go if the original version of the lemma were correct.***
Now back to the problem at hand. Say that the matrices $A\_1,\ldots,A\_k$ satisfy property P if for every infinite sequence $i\_1,\ldots \in [k]$, we have $A\_{i\_1} \cdots A\_{i\_m} = 0$ for some $m$. If one of the matrices $A\_i$ is *not* nilpotent then property P clearly fails, so suppose that all the matrices are nilpotent. If all matrices commute then property P clearly holds, so suppose that $A\_1 A\_2 \neq A\_2 A\_1$. Change basis so that $A\_1$ is in Jordan normal form, and let the corresponding decomposition of the vector space be $V\_1 \oplus \cdots \oplus V\_t$. Let $V\_i$ be a vector space on which $A\_1 A\_2 \neq A\_2 A\_1$; note that $\dim V\_i > 1$ since $0$ commutes with everything. Restricted to $V\_i$, $A\_1 = N$ and $A\_2 \neq 0$. Therefore the lemma implies that for some $t \geq 0$, either $A\_2 A\_1^t$ or $A\_1^t A\_2$ is not nilpotent, and therefore property P clearly fails.

Summarizing, property P holds iff all matrices are nilpotent and all of them commute.

> **Comments:**
> **username_4**: The last sentence of your lemma's proof is not correct. $N^2 A$ nilpotent implies $g = 0$, $N^1 A$ nilpotent gives $d = h = 0$, and $N^0 A$ nilpotent gives $a=e=i=0$. So we only conclude that $A$ is upper triangular with zeros on the diagonal, not that $A$ is diagonal (and hence zero).  
> **username_0**: Indeed , this answer is not correct. If no one else does, I'll post a counter example to both the lemma and the final assertion when I get home later today.  
> **username_3**: As usual, it is when something is claimed but not proved that the proof fails. Oh well...  
> **username_0**: So the example I had in mind was:  $$A_0 = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}, A_1 = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} $$ One can verify that every product of sufficient length of these two matrices is zero but they don't commute, and the second one is not zero.  

---

