Abstract Let λ 1 , … , λ n denote the eigenvalues of a n × n matrix, ordered by nonincreasing absolute value, and let γ 1 ≥ ⋯ ≥ γ n denote the tropical eigenvalues of an associated n × n matrix, obtained by replacing every entry of the original matrix by its absolute value. We show that for all 1 ≤ k ≤ n , | λ 1 ⋯ λ k | ≤ C n , k γ 1 ⋯ γ k , where C n , k is 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 .
The eigenvalues of a matrix polynomial can be determined classically by solving a generalized eigenproblem for a linearized matrix pencil, for instance by writing the matrix polynomial in companion form. We introduce a general scaling technique, based on tropical algebra, which applies in particular to this companion form. This scaling, which is inspired by an earlier work of Akian, Bapat, and Gaubert, relies on the computation of “tropical roots”. We give explicit bounds, in a typical case, indicating that these roots provide accurate estimates of the order of magnitude of the different eigenvalues, and we show by experiments that this scaling improves the accuracy (measured by normwise backward error) of the computations, particularly in situations in which the data have various orders of magnitude. In the case of quadratic polynomial matrices, we recover in this way a scaling due to Fan, Lin, and Van Dooren, which coincides with the tropical scaling when the two tropical roots are equal. If not, the eigenvalues generally split in two groups, and the tropical method leads to making one specific scaling for each of the groups. We show that the sequence of moduli of the eigenvalues of a matrix polynomial is log-majorized, up to universal constants, by a sequence of "tropical roots" depending only on the norms of the matrix coefficients. These tropical roots are the non-differentiability points of an auxiliary tropical polynomial, or equivalently, the opposites of the slopes of its Newton polygon. This extends to the case of matrix polynomials some bounds obtained by Hadamard, Ostrowski and PA³lya for the roots of scalar polynomials. We also obtain new bounds in the scalar case, which are accurate for "fewnomials" or when the tropical roots are well separated.