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
Haven't looked at this since I raised it 9 years ago, but since it seems to have a lot of views I should add that I "solved" the problem at the time in the very naive way by using the using inv = adj/det and ensuring that the steps to create adj and det (i.e. finding minors and cofactors) preserve the multiplication order. This works fine but is obviously hideously slow especially since the determinant results in a matrix of one degree less that then needs to be inverted. I used Schur's formula to repeatedly split into 4 and recurse this but it is still very intensive.
I'm sure that by employing a method like LU decomposition or another standard method would be more fruitful, especially if the number of "divisions" is reduced. To show how quickly the number of calculations grow I generated a random 4x4 fractional quadratic polynomial:
$$ \tiny \begin{bmatrix} 1/(x+8) &2x^2+2x+1)/2 &10 &(4x+7)/(7x^2+9x+1) \\ (5x+9)/(9x^2+5x+2) &(3x+6)/2 &(x^2+5x+6)/(6x+9) &3/(3x^2+5x+8) \\ (x+5)/5 &4/(8x^2+10x+1) &8/5 &(3x^2+3x+8)/(8x+9) \\ (5x^2+8x+5)/(2x^2+3x+3) &(5x^2+6x+9)/4 &(4x^2+10x+9)/(7x+8) &(x^2+x+3)/4 \end{bmatrix} $$
The resulting inverted matrix (verified as correct by multiplication) has 2309 terms of up to degree 79 and the maximum coefficient is 10^64.
Don't know the practical use of what I was trying to do here, but the idea was to be able to have a library of algorithms that could be applied to any mathematical object that fulfilled the correct criteria. So an algorithm for inverting a non-commutative ring may be different to an algorithm to invert a commutative ring.
