Let $M(n)$ be the time to multiply two $n\times n$ matrices, and let $L(n)$ be the time to compute the LUP decomposition of an $n\times n$ matrix.
How to show that multiplying matrices and computing LUP decompositions of matrices have essentially the same difficulty?
That is, we have to show that
- an $M(n)$-time matrix-multiplication algorithm implies an $O\left(M(n)\right)$-time LUP decomposition algorithm, and
- an $L(n)$-time LUP-decomposition algorithm implies an $O\left(L(n) \right)$-time matrix multiplication algorithm.