What's the best algorithm to invert a matrix of non-commutative elements? In my case I have a matrix of matrices.
From first principals by equating the elements of M * M' to I (where M' is the inverse) I've worked out the inverse for a 2×2 Matrix:
$$
M=\begin{bmatrix}
A &B \\
C &D \\
\end{bmatrix}
$$
$$
M^{-1}=\begin{bmatrix}
(A-BD^{-1}C)^{-1} &(C-DB^{-1}A)^{-1} \\
-D^{-1}C(A-BD^{-1}C)^{-1} &-B^{-1}A(C-DB^{-1}A)^{-1} \\
\end{bmatrix}
$$
In the above, you only need to perform 4 inversions: B, D and the components of the top row. The bottom row elements are obtained by multiplying the top row by 2 existing matrices.
One further optimisation of this is to choose to 2 "easiest" matrices to invert since you can transpose and/or swap the columns around and obtain the final result by transposing and/or swapping the rows.
As pointed out in the answers, one can use Schur complements to obtain similar / better formulae and recursively apply them to reach the result.
I've implemented the Doolittle LU Decomposition ensuring it respects multiplication order. Is there a better approach? It seems the concept of "pivot" is not really applicable (or at least more complex) when the elements are matrices, which is why I chose the simple Doolittle approach.
Best Answer
If yours matrix is "generic" (i.e. You do not suspect there are some specific algebraic relation between elements) then (as far as I know) there is nothing better than just use LU decomposition carefully putting elements on the right or on the left. (I mean LU can be easyly generalized to noncommutative case but formulas will be a little more complicated).
Actually the formulas which you write in 2*2 are very instructive ! The expressions A - B D^{-1} C called "Schur complements" see http://en.wikipedia.org/wiki/Schur_complement
You can obtain inversion of non-commutative matrix in this way - just consider that D - is $(n-1) \times (n-1)$ matrix since you did not use commutativity in yours formulas - they will work in this case also. So you can inductively go on till $n=1$ - so you obtain the inversion of yours matrix. Actually this is the LU algorithm.
There some math involved for specific matrices with non-commutative entries. For example if and only if [a,c] = [b,d] =0 and [a,d] = [b,d], than you can see that the inverse matrix can be given by the same formula as in commutative case
$$ \frac{ 1 }{ad-cb} d ~~~\frac{ -1 }{ad-cb}b $$ $$ \frac{ -1 }{ad-cb}c ~~~\frac{ 1 }{ad-cb}a $$
Similar fact holds true for $n\times n$ matrix if each 2 by 2 submatrix satisfy the relations above.
We propose to call such matrices "Manin matrices", since Yurii Manin first considered them at 1988-89. For such matrices basically all commutative facts holds true, despite they are quite far from commuative ones.
http://arxiv.org/abs/0901.0235
Another probably most famous examples are - "quantum group" matrices. Here one requires ac=q cb, etc... for some number "q" , then there are q-determinant and also inverse can be written by the usual formula substituting determinants by q-determinants...
There are many other examples super-matrices, Capelli matrices, matrices satisfying "reflection equation"... but the systematic theory is not developped.