How to prove the associative property of min-plus matrix multiplication?

562 Views Asked by At

According to Zwick, Uri, All pairs shortest paths using bridging sets and rectangular matrix multiplication, J. ACM 49, No. 3, 289-317 (2002). ZBL1326.05157. and Min-plus matrix multiplication (Wikipedia), Min-plus matrix multiplication, also known as the distance product is defined as:

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}\}$. This is standard matrix multiplication for the semi-ring of tropical numbers in the min convention.

One of matrix multiplication property is that it is associative, that is: $(AB)C = A(BC)$. The proof of this property in normal case is well known, however in min-plus algebra, I cannot find any reasoning explanation.