From: Eric Durant Subject: Re: modulo2 matrix inversion Date: 10 Mar 2000 00:00:00 GMT Message-ID: <38C9169A.5584A240@umich.edu> Content-Transfer-Encoding: 8bit References: <38BAA81B.A38DA84C@Infineon.com> <38C41A2A.FC237F11@umich.edu> <38C866F9.A7108FC@engin.umich.edu> <38C8D33F.6D604CF9@Infineon.com> X-Accept-Language: en Content-Type: text/plain; charset=iso-8859-1 X-Complaints-To: news@eecs.umich.edu X-Trace: news.eecs.umich.edu 952702544 5397 141.213.12.216 (10 Mar 2000 15:35:44 GMT) Organization: University of Michigan Electrical Engineering & Computer Science Dept. Mime-Version: 1.0 NNTP-Posting-Date: 10 Mar 2000 15:35:44 GMT Newsgroups: comp.soft-sys.matlab pollo wrote: > I used a less sophisticated approach without recovering > the rationale part: > > y = mod(inv(x), 2) > > thatīs really works but only with little matrices, > then you fall into precision problems. > I had the problem of huge GF(2) matrix powers too. That is only guaranteed to work for invertible matrices of size 1 and 2. This is because, for matrices of size 1 and 2, the inverse over Q(Z) of a binary matrix is itself a binary matrix not only over Q(Z), but over Z (more specifically, it contains just the elements -1, 0, 1). Consider the following matrix of size 3, A=[1 1 0; ... 1 0 1; ... 0 1 1]; The inverse over Q(Z) is AI_Q = inv(A) 0.5 0.5 -0.5 0.5 -0.5 0.5 -0.5 0.5 0.5 And your method gives AI_GF=mod(AI_Q,2) 0.5 0.5 1.5 0.5 1.5 0.5 1.5 0.5 0.5 which isn't in the field GF(2). Actually, A does not have an inverse in GF(2). One way to see this is that AI_Q has elements with denominator 2==0 in GF(2), so the multiplicative inverse doesn't exist. Also note that the matrix inverse doesn't exist since R1+R2=R3 in GF(2). For larger matrices, though, your method might still give fractional results where AI_Q had, for example, only denominators of 1 and 3==1, so the matrix inverse over GF(2) would exist, but your method would fail to find it. -- Eric Durant http://www.edurant.com/