---
tag: 64G0VSC5F4
kind: concept
name: Max-plus algebra
msc: [15A80, 14T10, 90C24]
sources:
  - url: https://en.wikipedia.org/wiki/Tropical_semiring
---

## Summary

Max-plus algebra is linear algebra in which addition is replaced by taking the maximum and multiplication is replaced by ordinary addition.
These operations make $\R \cup \set{-\infty}$ a semiring, the max-plus semiring.
It is one form of the tropical semiring.
Matrices over it describe longest paths in weighted graphs.
They also model the timing of systems that wait for several events, such as train schedules.

## Explanations

### L1 human

In max-plus arithmetic, "$a$ plus $b$" means $\max(a, b)$ and "$a$ times $b$" means $a + b$.
So $3 \oplus 5 = 5$ and $3 \otimes 5 = 8$.
A matrix product then picks the best route: entry $(i, j)$ of $A \otimes B$ is $\max_k (a_{ik} + b_{kj})$.
If $a_{ik}$ is the time to go from station $i$ to station $k$, then powers of $A$ give the longest travel times along chains of steps.