Min-Plus Algebra (Operation Question)

Question

I was reading about distance matrices, and they discuss a concept known as min-plus algebra. I am unsure if the operator + means addition in this context, and also unsure what operation goes in the underbrace $\text{min}\lbrace a_1+b_1\rbrace\underbrace{\space}_{} \text{min}\lbrace a_2+b_2\rbrace\underbrace{\space}_{} \text{min}\lbrace a_3+b_3\rbrace$.

I gave an example a problem below which I think will help me understand how to do the problem. How would I go by determining the value for $\text{min}_{k=1}^3\lbrace a_i+b_i\rbrace$ for this example?

Let $a_1=0$, $b_1=3$, $a_2=4$, $b_2=2$, $a_3=1$, and $b_3=5$.

$\text{min}_{k=1}^3\lbrace a_i+b_i\rbrace=?$

Answer 1

The tl;dr version is that $\min_{k=1}^n \{c_i\}$ means $\min\{c_1, c_2, \ldots, c_n\}$. Thus, $\min_{k = 1}^3\{a_i + b_i\} = \min\{a_1 + b_1,\, a_2 + b_2,\, a_3 + b_3\}$, which turns out to be $\min\{3, 6, 6\} = 3$ (from $a_1 + b_1$) in your example

But it was only after I did a bit of background noodling that I was confident this really is the intended calculation. Read on if you're interested, but I'll note that this isn't my field and I haven't played with tropical anythings before (so what follows was primarily me getting myself oriented, but may be of interest to someone else).

---

From the Wikipedia page for distance matrix:

An algebraic formulation of the above can be obtained by using the min-plus algebra. Matrix multiplication in this system is defined as follows: Given two $n\times n$ matrices $A=(a_{ij})$ and $B=(b_{ij})$, their distance product $C=(c_{ij})=A\star B$ is defined as an $n\times n$ matrix such that $c_{ij}=\min _{k=1}^{n}\{a_{ik}+b_{kj}\}$.

From the Wikipedia page for min-plus algebra:

The tropical semiring [...] is a semiring $(\Bbb R \cup \{\infty\}, \oplus, \otimes)$, with the operations as follows:

$x \oplus y = \min\{x, y\}$

$ x\otimes y=x+y$

The notations clash a bit here, so let's try and recast the notation of the matrix page using the tropical notation.

I would assume the "$+$" in $a_{ik} + b_{kj}$ would be written as $a_{ik} \otimes b_{kj}$ with the notation above, leading to $\min_{k=1}^n\{a_{ik} \otimes b_{jk}\}$. But this indexing of the $\min$ operator doesn't appear in tropical notation, so let's see how that should be handled.

Note that $\oplus$ is a binary operation, but much like ordinary addition, it turns out that it's associative, so that $$(x \oplus y) \oplus z = \min\{ \min\{x, y\}, z\} = \underbrace{\min\{x, y, z\}}_{\text{the nice one}} = \min\{ x, \min\{y,z\}\} = x \oplus (y \oplus z),$$ and we can unambiguously write $x \oplus y \oplus z$, and so on for an arbitrary number of tropical summands.

Thus $$\min_{k=1}^n \{a_{ik} \otimes b_{kj}\} = \min\{ a_{i1} \otimes b_{1j},\, a_{i2} \otimes b_{2j},\, \ldots ,\, a_{ik} \otimes b_{kj} \}$$ can be written $%$ $$\big( a_{i,1} \otimes b_{1,j} \big) \oplus \big( a_{i,2} \otimes b_{2, j} \big) \oplus \ldots \oplus \big( a_{ik} \otimes b_{kj} \big) = \displaystyle \bigoplus_{k = 1}^n a_{ik} \otimes b_{kj},$$ $%$ which really is the "tropical analog" of $\displaystyle \sum_{k = 1}^n a_{ik}b_{kj}$, the formula for computing the $(i,j)$ entry of the product $AB$, given matrices $A$ and $B$ with entries $a_{ij}$ and $b_{ij}$.