论文标题
双线性地图III的生长：可判决性
Growth of bilinear maps III: Decidability
论文作者
论文摘要
以下增长率的概念可以看作是联合光谱半径的概括：给定双线性地图$*：\ Mathbb r^d \ times \ Mathbb r^d \ to \ Mathbb r^d $，具有非阴性系数，并通过\ mathbb r r^d $ in \ r r^d $ g（n）$ s n a v（N） $ n $实例使用$ n-1 $ $*$的应用程序。令$λ$表示增长率$ \ limsup_ {n \ to \ infty} \ sqrt [n] {g（n）} $。罗森菲尔德（Rosenfeld）表明，通过减少关节光谱半径的问题，检查$λ\ le 1 $的问题是不可确定的。 在本文中，我们使用观察到矩阵乘法实际上是双线性图。此外，我们扩展了减少功能，以表明检查$λ\ le 1 $即使$ s $是正面的，仍然是不确定的。如果对符号没有限制，我们还可以证明检查系统是否可以通过减少检查一对矩阵的死亡率的问题来检查系统是否产生零向量。这回答了罗森菲尔德问的一个问题。除此之外，我们证实了罗森菲尔德的评论，当我们引入更多的双线性地图和更多的启动向量时，问题并不困难。 众所周知，如果vector $ s $严格为正，那么限制上级$λ$实际上是限制。但是，我们表明，当$ s $只是非负数时，检查限制的存在的问题是不可决定的。这也回答了罗森菲尔德问的一个问题。 我们提供了一个与矩阵的对角线有关的增长率$λ$的公式，该矩阵的对角线对应于一种称为``线性模式''的特殊结构。给出条件，以使限制$λ$存在。实际上，当$ s> 0 $时，这为存在$λ$的存在提供了更简单的证明。该公式的重要推论是增长率的可计算性。
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,....
