Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 (note that C, D is the 2nd row):

M = (A, B, C, D)

M' = ( (A-BD'C)', (C-DB'A)', -D'C(A-BD'C)', -B'A(C-DB'A)' )

(X' is the inverse)

Is is a matter of taking an existing algorithm - say LU Decomposition - and ensuring it respects non-commutativity or is there some more subtle maths involved?

Thanks

Alan

share|improve this question
3  
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? –  David Speyer Nov 26 '11 at 15:04
add comment

2 Answers

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.

share|improve this answer
    
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. –  Alan Swindells Nov 26 '11 at 16:11
add comment

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".

share|improve this answer
    
Great, that sounds like what I am looking for. I'll try and find the papers that cover it. Thanks –  Alan Swindells Nov 26 '11 at 16:12
    
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 –  Alexander Chervov Nov 26 '11 at 18:27
    
The survey on quasi-dets: arxiv.org/abs/math/0208146 See also arxiv.org/abs/q-alg/9705026. –  Alexander Chervov Nov 26 '11 at 18:27
    
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). –  Alexander Chervov Nov 26 '11 at 18:28
    
Thanks. It's a bit too advanced for me but I'll have some fun trying to figure it out! –  Alan Swindells Nov 27 '11 at 8:19
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.