# Classical matrix multiplication via Min-Plus matrix multiplication

Just a thought I had in mind. I can use classical matrix multiplication to compute min-plus matrix multiplication. Generally speaking, considering $$(n+1)^{a_{i,j}}$$ for each entry and then taking the smallest value.

But what about the other way around? I want to compute classic matrix multiplication by using as a blackbox an algorithm that computes min-plus. Not really sure which ideas... (And what would be the runtime)

• Do you allow logarithms/antilogarithms or other functions? Commented Jul 24 at 8:15
• You can emulate the $\max$ operator as $\sqrt[p]{a^p+b^p}$ with very large $p$. But I can't see how you would emulate a sum from a minimum, as one of the arguments is completely lost. Commented Jul 24 at 8:20

Basically, you want to compute $$\hat{c}_{i,j} = \min\limits_{k=1}^n \{a_{i,j} + b_{i,j}\}$$ from a blackbox (classical matrix multiplication), which computes $$c_{i,j} = \sum\limits_{k=1}^n a_{i,j} \times b_{i,j}$$. So basically, we need to convert a multiplication into an addition operation and a minimum into a summation. You need to process the input elements so that the desired effect can be achieved.
exploit the $$\log$$ operation
exploit the $$L_\infty$$ norm