Spectral Properties of Positive Definite Matrices over Symmetrized Tropical Algebras and Valued Ordered fields

Marianne Akian, Stephane Gaubert, Dariush Kiani, Hanieh Tavakolipour

Abstract

We investigate the properties of positive definite and positive semi-definite symmetric matrices within the framework of symmetrized tropical algebra, an extension of tropical algebra adapted to ordered valued fields. We focus on the eigenvalues and eigenvectors of these matrices. We prove that the eigenvalues of a positive (semi)-definite matrix in the tropical symmetrized setting coincide with its diagonal entries. Then, we show that the images by the valuation of the eigenvalues of a positive definite matrix over a valued nonarchimedean ordered field coincide with the eigenvalues of an associated matrix in the symmetrized tropical algebra. Moreover, under a genericity condition, we characterize the images of the eigenvectors under the map keeping track both of the nonarchimedean valuation and sign, showing that they coincide with tropical eigenvectors in the symmetrized algebra. These results offer new insights into the spectral theory of matrices over tropical semirings, and provide combinatorial formul\ae\ for log-limits of eigenvalues and eigenvectors of parametric families of real positive definite matrices.

Introduction

Positive definite matrices are fundamental to classical linear algebra, appearing in optimization, stability analysis, and statistics. Translating these concepts to tropical algebra—where addition is the maximum and multiplication is standard addition—presents a significant challenge due to the lack of additive inverses. This paper addresses this by utilizing the symmetrized tropical algebra ($S_{max}$), which introduces a formal "minus" sign to allow for term cancellation, enabling a robust definition of tropical positive definiteness (TPD).

The Symmetrized Tropical Framework

To analyze spectral properties, the authors work within the symmetrized tropical semiring. This extension tracks both the magnitude (valuation) and the sign of an element, categorizing them into positive, negative, and "balance" elements. This structure allows for a more nuanced algebraic treatment than standard tropical semirings.

Definitions of positive, negative, and balance elements in the symmetrized tropical algebra.

TPD matrices are defined using a tropicalized version of the quadratic form $x^T Ax > 0$. The researchers employ tools such as the tropical adjugate matrix and the Kleene star operator ($A^* = I \oplus A \oplus A^2 \dots$) to characterize eigenvectors and solve path-finding problems within the matrix structure.

Key Insights and the Role of Signs

A central theme of the research is that signs are essential. While standard tropical algebra often ignores signs, symmetrization is necessary to distinguish between "strong" eigenvectors (satisfying $Av = \lambda v$) and "weak" ones that only satisfy a balance relation.

A relation table illustrating the balance relation (∇) and order (R) between elements in the symmetrized algebra.

The most striking finding is the Diagonal Rule: for a TPD matrix, the eigenvalues are simply the diagonal entries. In this setting, the "positivity" is so dominant that the diagonal entries effectively "win" the maximum in the characteristic equation, simplifying eigenvalue computation significantly compared to the complex root-finding required in classical algebra.

Bridging Tropical and Classical Algebra

The paper establishes a rigorous connection between tropical results and real-valued matrices, particularly those whose entries are parametric functions (e.g., Puiseux series). The tropical eigenvalues serve as the "log-limits" of the eigenvalues of these real matrices as the parameter $t \to \infty$.

Numerical simulations in MATLAB validated these theoretical findings. For a $100 \times 100$ random positive definite matrix, the relative error between the predicted tropical valuation and the actual classical eigenvalue valuation was found to be less than $1.6 \times 10^{-13}$, demonstrating the high accuracy of these asymptotic predictions.

Conclusion and Future Directions

This work provides combinatorial formulas for the asymptotic behavior of eigenvalues and eigenvectors. While the results are powerful for TPD matrices under "generic" conditions (where matrix entries do not have accidental ties), future work is needed to handle non-generic cases and to extend these characterizations to general symmetric matrices in the symmetrized tropical setting. Additionally, the computational complexity of finding eigenvectors for very large, non-generic matrices remains an area for further optimization.

Summary updated

Abstract

We investigate the properties of positive definite and positive semi-definite symmetric matrices within the framework of symmetrized tropical algebra, an extension of tropical algebra adapted to ordered valued fields. We focus on the eigenvalues and eigenvectors of these matrices. We prove that the eigenvalues of a positive (semi)-definite matrix in the tropical symmetrized setting coincide with its diagonal entries. Then, we show that the images by the valuation of the eigenvalues of a positive definite matrix over a valued nonarchimedean ordered field coincide with the eigenvalues of an associated matrix in the symmetrized tropical algebra. Moreover, under a genericity condition, we characterize the images of the eigenvectors under the map keeping track both of the nonarchimedean valuation and sign, showing that they coincide with tropical eigenvectors in the symmetrized algebra. These results offer new insights into the spectral theory of matrices over tropical semirings, and provide combinatorial formul\ae\ for log-limits of eigenvalues and eigenvectors of parametric families of real positive definite matrices.
BibTeX
@misc{akian2024spectral,
  author = {Marianne Akian and Stephane Gaubert and Dariush Kiani and Hanieh Tavakolipour},
  title = {{Spectral Properties of Positive Definite Matrices over Symmetrized Tropical Algebras and Valued Ordered fields}},
  year = {2024},
  eprint = {2412.10602},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.10602},
}
Figure