Growth of bilinear maps III: Decidability

Abstract

The following notion of growth rate can be seen as a generalization of joint spectral radius: Given a bilinear map $\ast :{\mathbb{R}}^d\times {\mathbb{R}}^d\to {\mathbb{R}}^d$ with nonnegative coefficients and a nonnegative vector $s\in {\mathbb{R}}^d$, denote by $g(n)$ the largest possible entry of a vector obtained by combining $n$ instances of $s$ using $n-1$ applications of $\ast$. Let $\hat{I}»$ denote the growth rate ${\mathrm{limsup}}_{n\to \infty }\sqrt[n]{g(n)}$. Rosenfeld showed that the problem of checking $\hat{I}»\le 1$ is undecidable by reducing the problem of joint spectral radius. In this article, we provide a simpler reduction using the observation that matrix multiplication is actually a bilinear map. Moreover, we extend the reduction to show that checking $\hat{I}»\le 1$ is still undecidable even if $s$ is positive. If there is no restriction on the signs, we can also show that the problem of checking if the system can produce a zero vector is undecidable by reducing the problem of checking the mortality of a pair of matrices. This answers a question asked by Rosenfeld. Beside that, we confirm a remark of Rosenfeld that the problem does not become harder when we introduce more bilinear maps and more starting vectors. It is known that if the vector $s$ is strictly positive, then the limit superior $\hat{I}»$ is actually a limit. However, we show that when $s$ is only nonnegative, the problem of checking the existence of the limit is undecidable. This also answers a question asked by Rosenfeld. We provide a formula for the growth rate $\hat{I}»$ in terms of the diagonals of matrices corresponding to a special structure called ``linear pattern''. A condition is given so that the limit $\hat{I}»$ exists. This actually provides a simpler proof for the existence of the limit $\hat{I}»$ when $s>0$. An important corollary of the formula is the computability of the growth rate,....

17 pages; proves undecidability of the positive setting unconditionally, minor corrections before publication