On commuting matrices in max algebra and in classical nonnegative algebra (Q651200)

The authors study spectral properties of commuting matrices in \textit{max algebra,} i.e., in a linear algebra over the \textit{max-times semiring} of nonnegative numbers under the operation of maximum as addition and ordinary multiplication as multiplication. This is also known as \textit{tropical algebra}, although the logarithmic notation where multiplication is replaced by ordinary addition and nonnegative numbers by reals (together with \(-\infty\)) is perhaps more common. In the last section of the paper, it is explained that most of the results hold also in classical nonnegative algebra (Perron-Frobenius theory). Note that (in both settings) every square matrix has a (nonnegative) eigenvalue. The largest eigenvalue is called the \textit{Perron root} of the matrix. The first main result of the paper is that commuting matrices have a common eigenvector. More precisely, if \(A_1\), \dots, \(A_r\) commute in pairs and \(\alpha_1\) is any eigenvalue of \(A_1\), then there exists an eigenvalue \(\alpha_j\) of \(A_j\) for \(j=2,\dots, r\) and and a nonnegative vector \(v\neq 0\) such that \(A_jv=\alpha_jv\) for \(j=1,2,\dots, r\). As a consequence, \(p(\alpha_1,\alpha_2,\dots, \alpha_r)\) is an eigenvalue of \(p(A_1,A_2,\dots, A_r)\) for any polynomial \(p\). Moreover, if \(\alpha_1\) is no longer fixed, then all eigenvalues of \(p(A_1,\dots, A_r)\) are obtained in this manner. (This is the max analog of a result of \textit{F. Frobenius} [Borchardt J. LXXXIV, 1--63 (1877; JFM 09.0085.02); Berl. Ber., 601--614 (1896; JFM 27.0109.04)], reproved by \textit{I. Schur} [Berl. Ber. 120--125 (1902; JFM 33.0171.04)].) It follows that the Perron root of \(p(A_1,\dots, A_r)\) is at most \(p\) of the Perron roots of the \(A_i\). A more precise max analog of the Frobenius-Schur result is given under the extra assumption that for each \(i\), the diagonal submatrices corresponding to the strongly connected components of the digraph given by the nonzero entries of \(A_i\) have pairwise distinct Perron roots. In this case, it is also shown that the \(A_i\) can be put into Frobenius normal form by a common simultaneous permutation of rows and columns. For the case of max algebra only, the intersection of eigencones of commuting matrices is described. The authors consider connections with Boolean algebra which enable them to prove that, in max algebra, two commuting matrices having strongly connected digraphs always have a common \textit{eigennode}. An eigennode of a matrix \(A\) is an index \(i_1\) such that, for some \(1\leq k\leq n\) and some \(i_2,\dots, i_k\), the \textit{cycle geometric mean} \(({a_{i_1i_2}\cdots a_{i_ki_1}})^{1/k}\) is maximal among all cycle geometric means for all \(k\), i.e., it equals the Perron root of \(A\). Some of the most important results of the paper are illustrated by numerical examples.