Tropical bounds for eigenvalues of matrices

Abstract: We show that for all k = 1,...,n the absolute value of the product of the k largest eigenvalues of an n-by-n matrix A is bounded from above by the product of the k largest tropical eigenvalues of the matrix |A| (entrywise absolute value), up to a combinatorial constant depending only on k and on the pattern of the matrix. This generalizes an inequality by Friedland (1986), corresponding to the special case k = 1.

Review text

Let \(A=(a_{ij})\) be a complex \(n\)-square matrix with eigenvalues \(\lambda_1\), \dots, \(\lambda_n\), ordered by weakly decreasing absolute value. We may consider \(|A|=(|a_{ij}|)\) as a matrix over the max-times semiring \((\mathbb R_{\geq 0}, \oplus, \otimes)\). The matrix \(|A|\) then has a tropical characteristic polynomial \(\text{per}(|A|\oplus xI)\), whose tropical roots \(\gamma_1\geq\dots\geq\gamma_n\geq 0\) are called tropical eigenvalues. The main result of the paper under review is that, for all \(k\), the ratio \[ |\lambda_1\cdots\lambda_k|/(\gamma_1\cdots\gamma_k)\tag{*} \] is bounded from above by the spectral radius of the \(k\)-th permanental compound of the pattern of \(A\), where the pattern is given by replacing all nonzero entries by ones, and the permanental compound is the \(n\choose k\)-square matrix consisting of the \(k\)-square subpermanents. Note that the spectral radius is \(\leq n!/(n-k)!\). The majorization of \((*)\) by the spectral radius generalizes an inequality by \textit{S. Friedland} [Linear Algebra Appl. 74, 173--178 (1986; Zbl 0588.15015)], which corresponds to \(k=1\). Under certain quite restrictive and technical non-degeneracy conditions, a lower bound for the ratio \((*)\) is also given. In the final section of the paper, the authors give examples where their upper bound is tight, resp.\ not tight. They also compare their upper bound to a classical result by \textit{J. Hadamard} [Journ. de Math. (4) 9, 171--215 (1893; JFM 25.0698.03)], who gave an upper bound for \((*)\) when \(\lambda_1\), \dots, \(\lambda_n\) are the roots of a polynomial \(p\) over the complex numbers, and \(\gamma_1\geq\dots\geq\gamma_n\geq 0\) are what we now call the tropical roots of the max-times relative of \(p\) --- they were classically called `inclinaisons numériques' by \textit{A. Ostrowski} [Acta Math. 72, 99--155, 157--257 (1940; JFM 66.0578.03)].

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Tropical bounds for eigenvalues of matrices

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