Growth of Bilinear Maps

Abstract

We study a problem that is algebraic in nature but has certain applications in graph theory. It can be seen as a generalization of the joint spectral radius.

Given a bilinear map $*:\mathbb R^d\times\mathbb R^d\to\mathbb R^d$ and a vector $s\in\mathbb R^d$, both with nonnegative coefficients and entries, among an exponential number of ways to combine $n$ instances of $s$ using $n-1$ applications of $*$, we are interested in the largest possible entry in a resulting vector. Let $g(n)$ denote this value, the asymptotic behaviour of $g(n)$ is investigated through the growth rate \[ \lambda=\limsup_{n\to\infty} \sqrt[n]{g(n)}. \]

It is known that checking $\lambda\le 1$ is undecidable, as a consequence of the corresponding fact for the joint spectral radius. However, efficient algorithms are available to compute it exactly in certain cases, or approximate it to any precision in general. Furthermore, when the vector $s$ is positive, there exists some $r$ so that \[ \const n^{-r}\lambda^n\le g(n)\le \const n^r\lambda^n. \] It means $\lambda$ is actually a limit when $s>0$. However, checking if this is the case in general is also undecidable. Some types of patterns for optimal combinations are proposed and studied as well, with some connections to the finiteness property of a set of matrices.

The techniques that are used for our problem can be applied well for the joint spectral radius, and they produce some stronger results by even simpler arguments. For example, if $\|\Sigma^n\|$ denotes the largest possible entry in a product of $n$ matrices drawn from a finite set $\Sigma$ of nonnegative matrices, whose joint spectral radius is denoted by $\rho(\Sigma)$, then there exists some $r$ so that \[ \const n^r\rho(\Sigma)^n\le \|\Sigma^n\|\le \const n^r\rho(\Sigma)^n. \]