Max-plus algebra

Remarks

$(\R_{\max}, \oplus, \otimes)$ is a commutative semiring with zero element $-\infty$ and unit element $0$. It is idempotent: $a \oplus a = a$ for all $a$. Example: $2 \oplus 7 = 7$, $2 \otimes 7 = 9$, and $2 \otimes (3 \oplus 7) = 9 = (2 \otimes 3) \oplus (2 \otimes 7)$, which checks distributivity in one case. Non-example: $\R_{\max}$ is not a ring, since $5$ has no additive inverse: $\max(5, b) = -\infty$ has no solution $b$. Let $A$ be an $n \times n$ matrix, with $a_{ij}$ the weight of an arc from $i$ to $j$. Then $(A^{\otimes k})_{ij}$ is the largest weight of a path with $k$ arcs from $i$ to $j$. The min-plus semiring $(\R \cup \set{+\infty}, \min, +)$ is isomorphic to it by $x \mapsto -x$.