Matrix inversion tool

[Oleg Goldshmidt]

Shachar Shemesh <shachar at shemesh.biz> writes:

> Hi all,
>
> I'm looking for a tool/code to invert a matrix. So far, this sounds
> trivial. I have one special requirement. I did not think it was too
> special, except I could not find anywhere that supplied it.
>
> I want the matrix to be over a different field (i.e. - not the real
> numbers). In my particular case, I want it to be over Z2 (zero and
> one).

If you don't find ready code writing your own should be pretty
simple for Z2 - fields don't get any simpler. ;-)

In general, if you have a matrix A, then its inverse is given by

A^(-1) = adj(A)/det(A)               [1]

The determinant of any matrix over Z2 is either 0 or 1. If it is 0 the
matrix is not invertible. If it is 1, then the inverse matrix is the
same as the adjugate of the original matrix.

Now, the adjugate is the transpose of the cofactor matrix, which is

C_ij = (-1)^(i+j)*M_ij                    [2]

where M_ij is A's (ij)-minor, i.e., the determinant of the matrix
derived by deleting the i-th row and the j-th column of A. Thus

adj(A) = C_ji = (-1)^(i+j)*M_ji           [3]

Thus, from equations 1 and 3 we have

{A^(-1)}_ij = (-1)^(i+j)*M_ji             [4]

There are probably library routines to compute minors and cofactors. If
you don't find any, then, given that all you have is zeroes and ones, it
should be easy and safe to write your own. Note that you need to compute
the determinant to determine whether or not your matrix is invertible,
and to compute the determinant you need the cofactors, since

det(A) = Sum_{i=1}^{n} (A_ij*C_ij)   [5]

So, compute det(A), keep the cofactors, transpose (Eq. [3]) - done. Use
normal integer arithmetic and take into account that over Z2 all odd
numbers are 1 and all even numbers are 0 (i.e., get the integer result
modulo 2). If you can overload + and * operators for type Z2 you can
make it pretty simple. And efficient, if you implement addition as XOR
and multiplication - as AND.

If you find, e.g., a decent templatized C++ inversion routine maybe you
can use it as is after overloading + and *?

Hope it helps,

-- 
Oleg Goldshmidt | pub at goldshmidt.org