Checking if all products of a set of matrices eventually equal zero

Question

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.

Answer 1

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

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

Answer 2

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 3

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.

The undecidability of the above remains valid even if you have only 2 matrices of size 47x47: see here.

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": 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).

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

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.

Answer 4

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.