Generalized Eigenvectors and Rayleigh bounds for tropical algebraic eigenvalues

This paper addresses the discrepancy between tropical algebraic eigenvalues and standard eigenvectors by introducing generalized tropical eigenvectors that are guaranteed to exist for any eigenvalue, proposing an efficient construction method, and establishing an upper bound for these eigenvalues using tropical Rayleigh quotients.

The Gist

Imagine you are a detective trying to solve a mystery in a very strange city called Tropical Algebra.

In our normal world (classical math), if you have a machine (a matrix) and you feed it a specific input (a vector), it often spits out the same input, just scaled up or down. We call this a "perfect match" or an eigenvector. The amount it scales by is the eigenvalue. It's like a magic mirror that always reflects your face, just bigger or smaller.

The Problem: The Broken Mirror

In the city of Tropical Algebra, the rules are different. Here, "addition" means taking the maximum of two numbers, and "multiplication" means adding them.

The authors of this paper discovered a frustrating glitch: In this city, you can calculate a list of "theoretical eigenvalues" (like a list of suspects) using a standard formula. But when you try to find the actual "eigenvectors" (the suspects that actually fit the crime scene), they often don't exist!

It's like having a list of 5 suspects for a crime, but when you go to the crime scene, none of them actually fit the description. The standard equation $A \times x = \lambda \times x$ simply has no solution for these specific suspects. This left mathematicians stuck.

The Solution: A New Definition (The "Generalized" Detective)

The authors, Kiani and Tavakolipour, decided to stop looking for a "perfect match" and instead look for a "good enough" match. They invented a new concept called the Generalized Tropical Eigenvector.

Instead of demanding the machine output the exact same shape as the input, they asked a different question:

"If I feed this input into the machine, does the 'energy' or 'value' of the output match the 'energy' of the input in a specific way?"

They created a new equation:
$$x^T \otimes A \otimes x = \lambda \otimes x^T \otimes x$$

The Analogy:
Imagine you are testing a new car engine (the matrix $A$).

• Old Rule: The engine must make the car go exactly 60 mph if you press the gas pedal to a specific spot. (This often failed in Tropical Algebra).
• New Rule (Generalized): We don't care about the exact speed. We just care that the relationship between the gas pedal position and the engine's roar matches the theoretical roar we calculated earlier.

The paper proves that for every single theoretical eigenvalue (every suspect on the list), you can always find a generalized eigenvector (a suspect that fits this new, looser definition).

The Toolkit: How to Find Them

The authors didn't just say "it exists"; they gave you a cheap and easy recipe to find these vectors.

• Think of the matrix as a grid of numbers.
• To find the generalized vector for a specific eigenvalue, you just need to look at a few specific numbers in the grid (like the diagonal or the biggest numbers).
• You plug them into a simple formula (like a cooking recipe), and voilà, you have your vector. No complex, expensive calculations needed.

The "Rayleigh" Safety Net

Finally, the paper introduces a safety net called the Tropical Rayleigh Quotient.

In normal math, there's a famous rule (Rayleigh's Theorem) that says: "If you test your machine with any random input, the result will never be higher than the machine's strongest setting."

The authors proved that this rule still works in Tropical Algebra, even though the rules of the city are weird and the matrices aren't "symmetric" (perfectly balanced). It's like saying: "Even in this chaotic city, if you throw a ball at a wall, it will never bounce higher than the height of the wall, no matter how you throw it."

Summary for the Everyday Reader

1. The Issue: In a special type of math called Tropical Algebra, the standard way to find "eigenvectors" often fails. The theoretical answers don't match the reality.
2. The Fix: The authors redefined what an eigenvector is. Instead of a perfect match, they accept a "generalized" match that satisfies a slightly different, more flexible equation.
3. The Guarantee: They proved that for every theoretical answer, a generalized solution always exists.
4. The Method: They provided a simple, fast algorithm (a recipe) to calculate these solutions without needing a supercomputer.
5. The Bonus: They showed that a classic safety rule (Rayleigh bound) still holds true in this weird math world, giving us confidence in our calculations.

In short, they fixed a broken tool in a specialized toolbox, gave us a new, more flexible version of that tool, and showed us exactly how to use it.

Technical Summary

1. Problem Statement

In tropical algebra (specifically the max-plus semiring $\mathbb{R}_{\max} = \mathbb{R} \cup \{-\infty\}$), there is a fundamental disconnect between tropical algebraic eigenvalues and tropical geometric eigenvalues:

• Tropical Algebraic Eigenvalues: Defined as the roots of the tropical characteristic polynomial. An $n \times n$ matrix always has exactly $n$ such eigenvalues (counting multiplicities).
• Tropical Geometric Eigenvalues: Defined as scalars $\lambda$ for which there exists a non-zero vector $x$ satisfying the standard eigenvalue equation $A \otimes x = \lambda \otimes x$.
• The Core Issue: Unlike classical linear algebra, a tropical algebraic eigenvalue does not necessarily correspond to a geometric eigenvector satisfying $A \otimes x = \lambda \otimes x$. This lack of correspondence creates a gap in the spectral theory of tropical matrices, limiting the ability to construct eigenvectors for all algebraic eigenvalues.

The authors aim to resolve this by defining a generalized tropical eigenvector that exists for every algebraic eigenvalue and establishing a Tropical Rayleigh Quotient bound that does not require matrix symmetry.

2. Methodology

The paper employs the following methodological framework:

• Tropical Numerical Range: The authors utilize the concept of the tropical numerical range, $F_{\max}(A)$, defined as the set of values $\{(x^T \otimes A \otimes x) \otimes (x^T \otimes x)^{\otimes -1}\}$ for non-zero vectors $x$. They rely on the established result that $F_{\max}(A)$ is the closed interval $[\min_i a_{ii}, \max_{i,j} a_{ij}]$ and contains all tropical algebraic eigenvalues.
• Generalized Eigenvalue Equation: Instead of the standard linear equation, the authors propose a quadratic relation:
  $$x^T \otimes A \otimes x = \lambda \otimes (x^T \otimes x)$$
  where $\otimes$ denotes tropical multiplication (standard addition) and $\oplus$ denotes tropical addition (maximum).
• Scaling: The analysis focuses on scaled vectors where the max-norm $\|x\| = \max_i x_i = 0$. This normalization simplifies the equations, as $x^T \otimes x = 2\max(x_i) = 0$ for scaled vectors.
• Algorithmic Construction: The authors derive explicit formulas to construct these generalized eigenvectors based on the relationship between the eigenvalue $\lambda$ and the matrix entries $a_{ij}$.

3. Key Contributions

A. Definition of Generalized Tropical Eigenvectors

The paper defines a generalized tropical eigenvector $x$ associated with an algebraic eigenvalue $\lambda$ as any non-zero vector satisfying:
$$x^T \otimes A \otimes x = \lambda \otimes x^T \otimes x$$
Key Theorem (Theorem 4.1): For any tropical matrix $A$ and any of its tropical algebraic eigenvalues $\lambda$, there always exists a non-zero generalized tropical eigenvector. This resolves the existence problem inherent in the standard eigenvalue equation.

B. Computationally Inexpensive Construction Algorithms

The authors provide explicit, low-complexity algorithms (Theorems 5.1 and 5.2) to construct these vectors. The construction depends on the diagonal entries of the matrix relative to $\lambda$:

1. Case 1 (All diagonals $\le \lambda$): If $a_{ii} \le \lambda$ for all $i$, the vector is constructed using an off-diagonal entry $a_{pq} \ge \lambda$. The vector has non-zero entries only at indices $p$ and $q$.
2. Case 2 (At least one diagonal $\ge \lambda$): If there exists a diagonal entry $a_{qq} \ge \lambda$, the vector is constructed using the minimum diagonal entry $a_{pp}$ and the entry $a_{qq}$.
   • The formulas for the non-zero components $x_p$ and $x_q$ are derived directly from the condition $x^T \otimes A \otimes x = \lambda$.
   • These formulas allow for the direct calculation of eigenvectors without iterative methods.

C. Tropical Rayleigh Quotient Upper Bound

The paper establishes a tropical analogue to the classical Rayleigh Quotient theorem (Theorem 6.4).

• Classical Context: In classical algebra, the Rayleigh quotient provides bounds for eigenvalues of Hermitian matrices.
• Tropical Result: The authors prove that for a tropical matrix $A$ with ordered algebraic eigenvalues $\lambda_1 \le \dots \le \lambda_n$, and a subspace $S$ spanned by generalized eigenvectors $\{x_k, \dots, x_n\}$:
  $$\lambda_k = \min_{u \in S, u \neq \varepsilon} \left( (u^T \otimes A \otimes u) \otimes (u^T \otimes u)^{\otimes -1} \right)$$
• Significance: Unlike the classical theorem, this result does not require the matrix to be symmetric or Hermitian. It holds universally for any square tropical matrix.

4. Key Results

• Existence: Proven that the set of generalized tropical eigenvectors is non-empty for every algebraic eigenvalue.
• Explicit Formulas: Provided closed-form solutions for constructing these vectors based on matrix entries, avoiding the need for complex graph-theoretic decompositions used in previous literature (e.g., Nishida et al.).
• Bounds: Established that the $k$-th algebraic eigenvalue is the minimum of the tropical Rayleigh quotient over the subspace spanned by the $k$-th through $n$-th generalized eigenvectors.
• Numerical Example: The paper demonstrates the algorithm on a $4 \times 4$matrix, successfully computing generalized eigenvectors for all four algebraic eigenvalues ($0, 2, 4, 5$) using the derived formulas.

5. Significance and Impact

• Bridging the Gap: The work resolves a long-standing issue in tropical spectral theory where algebraic eigenvalues lacked corresponding eigenvectors. By redefining the eigenvector relation, the authors unify the algebraic and geometric perspectives.
• Computational Efficiency: The proposed construction method is $O(1)$ relative to the matrix size for finding a specific eigenvector (once the eigenvalue is known), making it highly efficient for large-scale discrete event systems and scheduling problems.
• Generalization of Classical Theory: The Tropical Rayleigh Quotient theorem extends a cornerstone of classical linear algebra to the tropical setting without the restrictive symmetry assumption, opening new avenues for optimization and approximation in tropical algebra.
• Applications: These results are relevant for fields relying on tropical algebra, including:
  • Discrete event systems (scheduling, manufacturing).
  • Combinatorial optimization.
  • Approximation of moduli of classical eigenvalues for matrix polynomials.

In summary, Kiani and Tavakolipour provide a robust theoretical foundation and practical tools for handling tropical eigenvalues, ensuring that every algebraic eigenvalue has a corresponding vector representation and establishing powerful variational principles for their estimation.