Perron-Frobenius theorem for nonnegative multilinear forms and extensions (Q1931765): Difference between revisions

The authors present an analog of Perron-Frobenius theorem for multilinear forms with nonnegative coefficients, and more generally, for polynomials maps with nonnegative coefficients. Let \(f:\mathbb{R}^{m_1} \times \dots \times \mathbb{R}^{m_d} \rightarrow \mathbb{R}\) be a multilinear form, which induces the tensor \({\mathcal F}=[f_{i_1,\dots,i_d}]\in \mathbb{R}^{m_1 \times \dots \times m_d}\). Form \(f\) is called nonnegative if the corresponding tensor \({\mathcal F}\) is nonnegative, meaning that all entries of \({\mathcal F}\) are nonnegative. Let \(S_{p,+}^{m-1}\) be the \(m-1\) dimensional unit sphere in the \(l_p\) norm restricted to \(\mathbb{R}_+^m\). It is known that each critical point \(({\pmb \xi}_1, \dots ,{\pmb \xi}_d) \in S_{p_1,+}^{m_1-1}\times \dots \times S_{p_d,+}^{m_d-1}\) of \(f | S_{p_1,+}^{m_1-1}\times \dots \times S_{p_d,+}^{m_d-1}\), satisfies the equality \[ \sum_{i_j \in [m_j], j \in [d]} f_{i_1,\dots,i_d}x_{i_1,1}\cdots x_{i_{j-1},j-1}x_{i_{j+1},j+1}\cdots x_{i_d,d}=\lambda x_{i_j,j}^{p_j-1}, \tag{1} \] where \([d]\) denotes the set \(\{1,2,\dots,d\}\). The tensor \({\mathcal F}\) is associated with an undirected \(d\)-partite graph \(G({\mathcal F})=(V, E({\mathcal F}))\), where \(V=\bigcup_{j=1}^d V_j\), with \(V_j=[m_j], j \in [d]\). The edge \((i_k,i_l) \in V_k \times V_l\), \(k \neq l\) belongs to \(E({\mathcal F})\) if and only if \(f_{i_1,i_2,\dots,i_d}>0\) for some \(d-2\) indices \(\{i_1,\dots,i_d\}\backslash \{i_k,i_l \}\). \({\mathcal F}\) is called weakly irreducible if the graph \(G({\mathcal F})\) is connected. \({\mathcal F}\) is called irreducible if for each proper nonempty subset \(\emptyset \neq I \subset V\), the following condition holds: let \(J=V\backslash I\), then there exists \(k \in [d]\), \(i_k \in I \bigcap V_k\) and \(i_j \in J \bigcap V_j\) for each \(j \in [d] \backslash \{k\}\) such that \(f_{i_1,\dots,i_d}>0\). The main result of this paper gives sufficient conditions on the uniqueness of positive solution of the system ({1}), for weakly irreducible and irreducible nonnegative tensors. More generally, the authors show that similar conclusions hold for eigenproblems involving polynomial maps with nonnegative coefficients. They derive an analog of Collatz-Wielandt's minimax characterization of the Perron eigenvalue. Computational aspects are also addressed: the authors give a sufficient condition which guarantees that the power algorithm converges to a normalized eigenvector, and they derive a spectral gap type formula for the asymptotic convergence rate. Finally, they present numerical examples showing that the conclusion of the main result no longer holds for \(p_1= \dots =p_d < d\).