# Complexity of matrix multiplication and Gaussian elimination

It is said that if matrix multiplication of $n\times n$ matrices is doable in $O(n^\omega)$ for some $\omega\geq 2$, so is Gaussian elimination and vice versa.

Now, this could imply that it is somehow possible to do Gaussian elimination by multiplying some matrices (independent of $n$), but I cannot think of anything how this should be possible. Another possibility could be that we can split the matrix into parts and do Gaussian elimination (somehow by matrix multiplication) on those and then do Gaussian elimination on those 4 matrix parts. But again I can't think of any way this is possible. I am equally confused about the inverse problem.

So, I am curious on how to prove the above statement (both directions). Just the (more or less precise) idea would be awesome.

The general idea of Gaussian Elimination involves multiplying by permutation matrices but in a computer, they use a series of other matrices. These are actually never multiplied. The time complexity of Gaussian elimination is $$\mathcal{O}(n^{3})$$
$$A = LU$$ $$L_{m-1}\cdots L_{2}L_{1}A = U$$ which gives us the product of the L matrices is actually inverse L $$L^{-1} = \prod_{i=1}^{m-1} L_{i}$$ Which has to do with the following. In Trefethan the asymptotic analysis is derived geometrically from the following algorithm.
The is most done by the by the vector operation in the inner loop which is executing one scalar-vector multiplication and one vector subtraction. $$u_{j,k:m} = u_{j,k:m} - \ell_{jk}u_{k,k:m}$$ given here that l = m-k+1 is the length of the row then the number of flops is two flops per entry then we get the following analysis.
For each value k, the inner loop is repeated for rows $$k+1, \cdots, m$$ This gives us a pyramid yielding the work $$\approx \frac{2}{3}m^{3}flops$$