# Invariant manifold

**Min-plus matrix multiplication**, also known as the **distance product**, is an operation on matrices.

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}={\mathrm{min}}_{k=1}^{n}\{{a}_{ik}+{b}_{kj}\$.

This operation is closely related to the shortest path problem. If $W$ is an $n\times n$ matrix containing the edge weights of a graph, then $W}^{k$ gives the distances between vertices using paths of length at most $k$ edges, and $W}^{n$ is the distance matrix of the graph.

## References

- Uri Zwick. 2002. All pairs shortest paths using bridging sets and rectangular matrix multiplication.
*J. ACM*49, 3 (May 2002), 289–317. - Liam Roditty and Asaf Shapira. 2008. All-Pairs Shortest Paths with a Sublinear Additive Error. ICALP '08, Part I, LNCS 5125, pp. 622–633, 2008.

## See also

- Floyd–Warshall algorithm
- Tropical geometry: The distance product is equivalent to standard matrix multiplication in the tropical semi-ring.