From: Eric Durant <edurant@umich.edu>
Subject: Re: modulo2 matrix inversion
Date: 06 Mar 2000 00:00:00 GMT
Message-ID: <38C41A2A.FC237F11@umich.edu>
Content-Transfer-Encoding: 7bit
References: <38BAA81B.A38DA84C@Infineon.com>
To: pollo@Infineon.com
X-Accept-Language: en
Content-Type: text/plain; charset=us-ascii
X-Complaints-To: news@eecs.umich.edu
X-Trace: news.eecs.umich.edu 952375694 12993 141.213.12.216 (6 Mar 2000 20:48:14 GMT)
Organization: University of Michigan Electrical Engineering & Computer Science Dept.
Mime-Version: 1.0
NNTP-Posting-Date: 6 Mar 2000 20:48:14 GMT
Newsgroups: comp.soft-sys.matlab

pollo wrote:
> Does anyone have a prog. for modulo-2 inversion
> of a matrix (eg. using modulo 2 algebra).
> Using normal inv() I get fractional results
> and not just 0 or 1 !?!

This probably isn't the most efficient way, but if you can recover the
rationals over Z, you can map them to the rationals over GF(2) and then
map the rationals over GF(2) to the elements of GF(2) using the
multiplicative inverse.  You should be able to recover the rational
representation from Matlab's floating point representation with rat() if
the matrix isn't too large.

For example, if your matrix to invert is in A_GF, the following gives
the inverse over GF(2) in AI_GF.  This does not check that the matrix is
invertible over the field.

p = 2; % Field characteristic, must be prime for this method
AI_Q = inv(A_GF);
[N,D] = rat(AI_Q);
% Element-wise multiplicative inverse in GF(p):
DMI_GF = mod(D,p); DMI_GF(DMI_GF==0) = NaN;
AI_GF = mod(N .* DMI_GF,p);

If this works, DMI_GF will be all ones, so we could eliminate the final
multiply, but it is included here to illustrate how this method could be
extended for GF(p), p>2.

If the denominator has 0 elements in GF(2), even if they are nonzero in
Z (..., -4, -2, 2, 4, ...), this method will fail to find an inverse.  I
have not looked carefully at this, but this may indicate that the matrix
inverse does not exist over GF(2), even though it does exist over Q(Z).

As a check, the following will return true (1) if the inversion is
successful:

all(all( mod(A_GF*AI_GF,2) == eye(length(A_GF)) ))

-- Eric Durant
   http://www.edurant.com/