Minimal number of multiplications required to invert a 4x4 matrix Four by four real (well, floating point...) matrices are used in computer graphics to represent projections. Sometimes we need to compute their inverses. How many multiplications are required?


*

*Valve's Source SDK implements the "pen&paper" algorithm: start with a 4x8 matrix whose left hand side is $A$ (the matrix to invert) and whose right hand side is $I_4$ (the 4x4 identity matrix); apply Gauss moves until the left hand side is $I_4$ and the right hand will be $A^{-1}$. This algorithm requires (by inspecting the code) $4 \cdot 8 + 4 \cdot 4 \cdot 8 = 160$ multiplications.

*Solving $AX = I$ applying Cramer's rule for each element and computing each 3x3 determinant with Sarrus's rule improves on that: we need $6 \cdot 16$ multiplications for the cofactors, then $4$ more for the determinant of the 4x4 matrix, plus $16$ multiplications for the inverse of that, for a total of $6 \cdot 16 + 4 + 16 = 116$ multiplications.

*Cleverly precalculating products of two elements as in this answer requires (again inspecting the code) $2\cdot 12 + 6 + 4 \cdot 16 = 94$ multiplications.


Can we do better? Can we prove we can't?
 A: We can invert a 2x2 matrix with 6 multiplies and one inversion. By Strassen's algorithm, we can multiply 2x2 matrices with 7 multiplies.
Partition your 4x4 matrix as
$$\left( \begin{matrix} A & B \\ C & D \end{matrix} \right) $$
We will reduce this to the identity.
Compute the inverse of $A$.
Perform Gaussian elimination
$$\left( \begin{matrix} I & A^{-1} B \\ 0 & D - CA^{-1}B \end{matrix} \right) $$
Let $E = D - C A^{-1} B$. Now compute $E^{-1}$. We can now finish Gaussian elimination.
Repeating these operations on an identity matrix tells us that the inverse is
$$ \left( \begin{matrix} A^{-1} + A^{-1} B E^{-1} C A^{-1} & -A^{-1} B E^{-1}
\\ -E^{-1} C A^{-1} & E^{-1} \end{matrix} \right) $$
The calculation of this inverse requires two matrix inversions (12 multiplies and 2 real inversions), and six 2x2 multiplies:


*

*$C A^{-1}$

*$(C A^{-1}) B$

*$E^{-1} (C A^{-1})$

*$A^{-1} B$

*$(A^{-1} B) E^{-1}$

*$(A^{-1} B)(E^{-1} C A^{-1})$


for 54 multiplies and 2 real inversions in all.
Of course, using Strassen's algorithm for 2x2 matrices is a terrible idea. I don't know if the above organization of the calculation is reasonable or not even if you don't use Strasses algorithm; I suspect it is unlikely.
If $A$ turns out to be singular, you have to partition the matrix differently to do the calculation.
A: In his paper Gaussian Elimination is not optimal, Volker Strassen stated the following:

A more recent treatment of matrix inversion is provided by Intel. However, they are aiming at speed rather than at the minimum number of multiplications.
