Thread Subject: binary matrix inversion

How to find the inverse of a binary Matrix A ,
Note that the summation is replaced by xor operation.
searching for another matrix B such that A*B=I ( with xor instead of summation) is not efficient, is there another solutions ???

"Mostafa " <mmmedra@yahoo.com> wrote in message <h9ocjr$9ai$1@fred.mathworks.com>...
> How to find the inverse of a binary Matrix A ,
> Note that the summation is replaced by xor operation.
> searching for another matrix B such that A*B=I ( with xor instead of summation) is not efficient, is there another solutions ???

if you have to solve the general problem, use forward and backward gauss elimination (no pivoting is needed, very easy to code) on the matrix [A, I] obtaining [I, invA]
else, if you are looking for efficient encoding of ldpc codes... google for some paper

"Stefano " <s.mangione@gmail.com> wrote in message <h9odlj$itj$1@fred.mathworks.com>...
> "Mostafa " <mmmedra@yahoo.com> wrote in message <h9ocjr$9ai$1@fred.mathworks.com>...
> > How to find the inverse of a binary Matrix A ,
> > Note that the summation is replaced by xor operation.
> > searching for another matrix B such that A*B=I ( with xor instead of summation) is not efficient, is there another solutions ???
>
> if you have to solve the general problem, use forward and backward gauss elimination (no pivoting is needed, very easy to code) on the matrix [A, I] obtaining [I, invA]
> else, if you are looking for efficient encoding of ldpc codes... google for some paper


you are speaking about the inversion of the normal matrix , I am speaking about the binary one.

No, I'm really speaking about the binary one :)
Don't use the xor() function, it's very slow, use mod( ,2) instead.

Stefano

"Mostafa " <mmmedra@yahoo.com> wrote in message <h9tokq$ir6$1@fred.mathworks.com>...

> you are speaking about the inversion of the normal matrix , I am speaking about the binary one.

"Stefano " <s.mangione@gmail.com> wrote in message <h9tqtt$njm$1@fred.mathworks.com>...
> No, I'm really speaking about the binary one :)
> Don't use the xor() function, it's very slow, use mod( ,2) instead.
>
> Stefano
>
> "Mostafa " <mmmedra@yahoo.com> wrote in message <h9tokq$ir6$1@fred.mathworks.com>...
>
> > you are speaking about the inversion of the normal matrix , I am speaking about the binary one.


How then ?

could you write a some code?

% Gauss elimination to invert A
temp = [A,eye(N)];

% forward
for i = 1:N
   % if the current row does not have a 1 in column i, find a row j >
   % i with a 1 in column i and add it to row i
   if temp(i,i) == 0
      % some code here
   end
   % forward gauss elimination
   for j=i+1:N
      if temp(j,i)
         % code here...
      end
   end
end
% backward
for i=N:-1:2
   for j=i-1:-1:1
      if temp(j,i)
         % some more code here...
      end
   end
end
invA = temp(:,N+1:end);

OK?



"Mostafa " <mmmedra@yahoo.com> wrote in message <haaf7d$edk$1@fred.mathworks.com>...
> "Stefano " <s.mangione@gmail.com> wrote in message <h9tqtt$njm$1@fred.mathworks.com>...
> > No, I'm really speaking about the binary one :)
> > Don't use the xor() function, it's very slow, use mod( ,2) instead.
> >
> > Stefano
> >
> > "Mostafa " <mmmedra@yahoo.com> wrote in message <h9tokq$ir6$1@fred.mathworks.com>...
> >
> > > you are speaking about the inversion of the normal matrix , I am speaking about the binary one.
>
>
> How then ?
>
> could you write a some code?

"Stefano " <s.mangione@gmail.com> wrote in message <haahgi$etg$1@fred.mathworks.com>...
> % Gauss elimination to invert A
> temp = [A,eye(N)];
>
> % forward
> for i = 1:N
> % if the current row does not have a 1 in column i, find a row j >
> % i with a 1 in column i and add it to row i
> if temp(i,i) == 0
> % some code here
> end
> % forward gauss elimination
> for j=i+1:N
> if temp(j,i)
> % code here...
> end
> end
> end
> % backward
> for i=N:-1:2
> for j=i-1:-1:1
> if temp(j,i)
> % some more code here...
> end
> end
> end
> invA = temp(:,N+1:end);
>
> OK?
>
>
>
> "Mostafa " <mmmedra@yahoo.com> wrote in message <haaf7d$edk$1@fred.mathworks.com>...
> > "Stefano " <s.mangione@gmail.com> wrote in message <h9tqtt$njm$1@fred.mathworks.com>...
> > > No, I'm really speaking about the binary one :)
> > > Don't use the xor() function, it's very slow, use mod( ,2) instead.
> > >
> > > Stefano
> > >
> > > "Mostafa " <mmmedra@yahoo.com> wrote in message <h9tokq$ir6$1@fred.mathworks.com>...
> > >
> > > > you are speaking about the inversion of the normal matrix , I am speaking about the binary one.
> >
> >
> > How then ?
> >
> > could you write a some code?


Thanks , it worked very nice.

Hello Stefano,
Can you give more details of your code? I am new with Matlab and I'm not familiar with backward Gaussian elimination. Thank you very much!

Hunter

"Stefano " <s.mangione@gmail.com> wrote in message <haahgi$etg$1@fred.mathworks.com>...
> % Gauss elimination to invert A
> temp = [A,eye(N)];
>
> % forward
> for i = 1:N
> % if the current row does not have a 1 in column i, find a row j >
> % i with a 1 in column i and add it to row i
> if temp(i,i) == 0
> % some code here
> end
> % forward gauss elimination
> for j=i+1:N
> if temp(j,i)
> % code here...
> end
> end
> end
> % backward
> for i=N:-1:2
> for j=i-1:-1:1
> if temp(j,i)
> % some more code here...
> end
> end
> end
> invA = temp(:,N+1:end);
>
> OK?
>
>
>
> "Mostafa " <mmmedra@yahoo.com> wrote in message <haaf7d$edk$1@fred.mathworks.com>...
> > "Stefano " <s.mangione@gmail.com> wrote in message <h9tqtt$njm$1@fred.mathworks.com>...
> > > No, I'm really speaking about the binary one :)
> > > Don't use the xor() function, it's very slow, use mod( ,2) instead.
> > >
> > > Stefano
> > >
> > > "Mostafa " <mmmedra@yahoo.com> wrote in message <h9tokq$ir6$1@fred.mathworks.com>...
> > >
> > > > you are speaking about the inversion of the normal matrix , I am speaking about the binary one.
> >
> >
> > How then ?
> >
> > could you write a some code?