Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2201.09850 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- The following notion of growth rate can be seen as a generalization of joint spectral radius: Given a bilinear map $*:\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 $*$. Let $λ$ denote the growth rate $\limsup_{n\to\infty} \sqrt[n]{g(n)}$. Rosenfeld showed that the problem of checking $λ\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 $λ\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 $λ$ 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 $λ$ in terms of the diagonals of matrices corresponding to a special structure called ``linear pattern''. A condition is given so that the limit $λ$ exists. This actually provides a simpler proof for the existence of the limit $λ$ when $s>0$. An important corollary of the formula is the computability of the growth rate,....