How to show that if there's a fast matrix inversion algorithm, then there's a fast multiplication algorithm? Is there a way to show this and vice versa?
Suppose $F_n$ is the number of flops required by some algorithm to perform the inversion of an $n-by-n$ matrix. Assume that there exists a constant $c_1$ and a real number $\alpha$ such that $F_n <= c_1n^{\alpha}$.
How do I show that there exists a method that computes the product of two $n-by-n$ matrices with fewer than $c_2n^{\alpha}$ where $c_2$ is a constant independent of $n$?
 A: To compute $XY$ using $*^{-1}$ function.
Since there is no upper limit on $c_2$, you can construct a matrix larger than $X$ and $Y$ by any constant factor (two times larger, three times larger, etc) and invert it.
So looking at http://en.wikipedia.org/wiki/Invertible_matrix#Blockwise_inversion we want to find a matrix whose block inverse contains $XY$ or something that allows that to be calculated quickly, like $W \pm (XY \pm Z)^{-1}$.
$$
\begin{bmatrix} A & B \\ C & D \end{bmatrix}^{-1} = 
\begin{bmatrix}
A^{-1} + A^{-1}B(D - CA^{-1}B)^{-1}CA^{-1} &
A^{-1}B(D - CA^{-1}B)^{-1} \\
-(D - CA^{-1}B)^{-1}CA^{-1} & 
(D - CA^{-1}B)^{-1}
\end{bmatrix}$$
Choosing $A = D = I$ and $B=Y$ and $C=X$, you get:
$$\begin{align}
\begin{bmatrix} I & Y \\ X & I \end{bmatrix}^{-1} &= 
\begin{bmatrix}
I^{-1} + I^{-1}Y(I - XI^{-1}Y)^{-1}XI^{-1} &
I^{-1}Y(I - XI^{-1}Y)^{-1} \\
-(I - XI^{-1}Y)^{-1}XI^{-1} & 
(I - XI^{-1}Y)^{-1}
\end{bmatrix} \\ &= 
\begin{bmatrix}
I + Y(I - XY)^{-1}X &
Y(I - XY)^{-1} \\
-(I - XY)^{-1}X & 
(I - XY)^{-1}
\end{bmatrix}
\end{align}$$
So the bottom right of the matrix is $E = (I - XY)^{-1}$, and $XY$ can be computed as $XY = I - E^{-1}$.
