16
$\begingroup$

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 2x2 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.

Improve this question
$\endgroup$
1
  • 5
    $\begingroup$ A $k \times k$ matrix of $\ell \times \ell$ matrices is just a $(k \ell) \times (k \ell)$ matrix. Is there a reason not to just invert it that way? $\endgroup$
    – David E Speyer
    Commented Nov 26, 2011 at 15:04

2 Answers 2

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the comprehensive answer. I'm not sure I made the problem statement clear enough. I have a matrix of non-commuting elements - which happen to themselves be matrices. This is different to considering a matrix in blocks (i.e. the method of taking (n-1) sized blocks and reducing it; or David Speyer's suggestion at the top). I think your initial suggestion of using LUD and carefully watching the order of multiplication is what I will have to do. That also means there will be both a left and right inverse. $\endgroup$
    – Alan Swindells
    Commented Nov 26, 2011 at 16:11
6
$\begingroup$

There is a theory of determinants of matrices over non-commutative (in particular, free) rings. It was mainly developed by Gelfand and Retah. I think the first paper is this: Gelfand, I. M., Retakh, V. S. Theory of noncommutative determinants, and characteristic functions of graphs. Funktsional. Anal. i Prilozhen. 26 (1992), no. 4, 1--20, 96; translation in Funct. Anal. Appl. 26 (1992), no. 4, 231–246 (1993) . In particular, they discuss a connection between inverses of matrices ovr non-commutative rings and these "quasi-determinants".

Improve this answer
$\endgroup$
6
  • $\begingroup$ Great, that sounds like what I am looking for. I'll try and find the papers that cover it. Thanks $\endgroup$
    – Alan Swindells
    Commented Nov 26, 2011 at 16:12
  • 1
    $\begingroup$ Quasi-det is NOT direct analogue of the determinant in the commutative case. It is very simple thing. There are by definition not one, but n^2 quasi-determinants. Quasi-determinant with index (i,j) is by definition the (i,j) element of the inverse matrix. More precisely you should invert this element. So you may ask why such a simple thing should be called by loud name "quasi-determinant". The logic of authors (imho) - that for many matrix theorems you do not need determinant, but key thing is inverse matrix and you can reformulate in terms of its elements (i.e. quasi-dets) some theorems $\endgroup$
    – Alexander Chervov
    Commented Nov 26, 2011 at 18:27
  • $\begingroup$ The survey on quasi-dets: arxiv.org/abs/math/0208146 See also arxiv.org/abs/q-alg/9705026. $\endgroup$
    – Alexander Chervov
    Commented Nov 26, 2011 at 18:27
  • $\begingroup$ The example is LU decomposition - you express the elements of L and U in terms of the elements of inverse matrix (i.e. quasi-dets). $\endgroup$
    – Alexander Chervov
    Commented Nov 26, 2011 at 18:28
  • $\begingroup$ Thanks. It's a bit too advanced for me but I'll have some fun trying to figure it out! $\endgroup$
    – Alan Swindells
    Commented Nov 27, 2011 at 8:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .