Perron-Frobenius theorem for nonnegative multilinear forms and extensions

DOI10.1016/J.LAA.2011.02.042MaRDI QIDQ1931765zbMATH OpenOpenAlexFDO

Publication date 16 January 2013

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0905.1626

Collatz-Wielandt's minimax characterization convergence eigenproblems multilinear form nonnegative tensors normalized eigenvector numerical examples Perron eigenvalue Perron-Frobenius theory positive solution power algorithm undirected graph weakly irreducible

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Positive matrices and their generalizations; cones of matrices (15B48) Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Abstract: We prove an analog of Perron-Frobenius theorem for multilinear forms with nonnegative coefficients, and more generally, for polynomial maps with nonnegative coefficients. We determine the geometric convergence rate of the power algorithm to the unique normalized eigenvector.

Review text

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\).

Recommendations

Cites work

Cited in

(only showing first 100 items - show all)

This page was built for publication: Perron-Frobenius theorem for nonnegative multilinear forms and extensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1931765)