18
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You need some kind of convergence property on the set of matrices to ensure that the infinite product is defined. $\endgroup$ – András Salamon May 21 '13 at 21:07
  • $\begingroup$ 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? $\endgroup$ – Chad Brewbaker May 21 '13 at 21:15
  • 2
    $\begingroup$ @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. $\endgroup$ – robinson May 22 '13 at 4:45
  • 1
    $\begingroup$ @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. $\endgroup$ – robinson May 22 '13 at 4:49
  • 1
    $\begingroup$ Interestingly, this just in: 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). $\endgroup$ – Joshua Grochow Jun 5 '13 at 1:25
17
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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$)? $\endgroup$ – András Salamon May 22 '13 at 22:25
  • 2
    $\begingroup$ @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. $\endgroup$ – Joshua Grochow May 22 '13 at 22:29
  • 1
    $\begingroup$ @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}$). $\endgroup$ – Joshua Grochow May 23 '13 at 1:52
  • 1
    $\begingroup$ 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). $\endgroup$ – Yuval Filmus May 23 '13 at 16:23
  • 1
    $\begingroup$ @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). $\endgroup$ – Joshua Grochow May 23 '13 at 22:04
6
$\begingroup$

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!

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – robinson Jun 8 '13 at 19:12
  • 2
    $\begingroup$ 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".) $\endgroup$ – Amir Ali Ahmadi Jun 8 '13 at 21:23
  • $\begingroup$ In which case, @AmirAliAhmadi doesn't the answer by Joshua Grochow cover it ? $\endgroup$ – Suresh Venkat Jun 9 '13 at 2:58
  • 2
    $\begingroup$ 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. $\endgroup$ – Amir Ali Ahmadi Jun 9 '13 at 7:29
  • 4
    $\begingroup$ [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. $\endgroup$ – Amir Ali Ahmadi Jun 9 '13 at 7:44
0
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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). $\endgroup$ – Joshua Grochow May 22 '13 at 21:25
  • $\begingroup$ 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. $\endgroup$ – robinson May 22 '13 at 21:52
  • 4
    $\begingroup$ As usual, it is when something is claimed but not proved that the proof fails. Oh well... $\endgroup$ – Yuval Filmus May 22 '13 at 22:41
  • 1
    $\begingroup$ 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. $\endgroup$ – robinson May 23 '13 at 1:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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