Matrix Multiplication, Three Arithmetics
Every entry of a matrix product reduces a row-against-column list of candidates:
\[ (A \otimes B)_{ij} \;=\; \bigoplus_k \; A_{ik} \otimes B_{kj}. \]
The arithmetic decides what the reduction means. Ordinary arithmetic blends: every \(k\) contributes to the sum. Tropical arithmetic selects: one candidate wins the \(\min\) (or \(\max\)), and that winning \(k\) is a witness — the cheapest intermediate stop, or the binding constraint.
What you can do
- Click any cell of the product: the contributing row of \(A\) and column of \(B\) light up, and the trace panel lists every candidate \(A_{ik} \otimes B_{kj}\) with the winner marked.
- Switch the arithmetic between min-plus, max-plus, and ordinary — same matrices, three different products.
- Watch the additive identity flip with the semiring: the same missing entries render as \(+\infty\) (min-plus), \(-\infty\) (max-plus), or \(0\) (ordinary) — in each case the element that contributes nothing.
This is the interactive twin of the paper’s Figure 2 (Section 3). The matrices are the figure’s exact matrices; the three product matrices are pinned as regression values in the artifact’s spec.
Supporting information
Supporting information for When Addition Becomes Optimization: Tropical Algebra, Paths, Schedules, and Semiring Computation (Section 3).