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.

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.

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

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.