unable to find the inverse of large matrix using gaussian elimination.

Hi All,

I am using the code below to find the inverse of a square boolean matrix. It is working fine for smaller matrix sizes say 4x4,5x5 or even 12x12 but around the size of 20x20 or 30x30, I am unable to find the inverse. Can someone point out to me where the bug can lie ?

    [arow , acol]= size(A);
     b=eye(arow);
      i=1;
for i=1:acol
    % code to make sure that the diagonal elements are 1's
    if (A(i,i)==0)
        t =  min ( find ( A(i+1:arow,i) ~= 0 ) + i );
       % t=abs(min( find ( A(1:i-1,i) ~= 0)-i));
        temp  = A(i,:);     tb = b(i,:);
        A(i,:)= A(t,:);   b(i,:) = b(t,:);
        A(t,:)= temp;     b(t,:) = tb;
    end

    % the lower triangular matrix is all zeros
    for j=i+1:arow
        m= -A(j,i)/A(i,i);
        A(j,i)=0;
        A(j, i+1:acol) = mod(A(j, i+1:acol) + m * A(i, i+1:acol),2);
        b(j,:) = mod(b(j,:) + m * b(i,:),2);
    end

    for j= 1:i-1
        m= -A(j,i)/A(i,i);
        A(j,i)=0;
        A(j, i+1:acol) = mod(A(j, i+1:acol) + m * A(i, i+1:acol),2);
         %A(i+1:arow,j) = A(i+1:arow,j) + m * A(i+1:arow,i);
        b(j,:) = mod(b(j,:) + m * b(i,:),2);
    end

end

Can someone point out the error to me ?

[Bhavya PH]

the matrix A is converted to an identity matrix and matrix b is the inverse of A

Answer 1

[Andrei Bobrov]

my old function InvMatrix

EDIT 2

function dout = InvMatrix(c)
m = size(c,1);
c = [c eye(m)];
n = m*2;
for j1 = 1:m
   [ind,ind] = sortrows(abs(c(j1:end,j1:end)),-1);
   c(j1:end,j1:end) = c(j1-1+ind,j1:end);
   c1 = c(:,j1)*ones(1,n);
   c1(j1,:) = zeros(1,n);
   if c(j1,j1) == 0, k=1; else k = c(j1,j1); end
   c2 = ones(m,1)*c(j1,:)/k;
   c(j1,:) = c2(j1,:);
   c = c - c2.*c1;
end
dout = c(:,m+1:end);

use

A = rand(30);
out = InvMatrix(A)

check

out*A

or

rref([A eye(30)]))

[Bhavya PH]

Hi andrei thanks for the above code, but unfortunately I am not able to understand the code too well, is c the final inverse of the above code snippet ? I am able to only view an identity matrix ? I am passing a simple 30x30 matrix and I getting the output to be a matrix of a dimension different from 30x30.

[Andrei Bobrov]

corrected

[Bhavya PH]

Hello Andrei, thanks but my input is a boolean 30x30 matrix. with the suggested code i get NAN's. Thanks

[Andrei Bobrov]

A- your boolen matrix

if det(A+0) == 0, out - array NaNs.

eg

>> A = logical([0 0 0 1 1

1 0 0 0 1

0 0 1 1 0

1 1 1 1 0

1 1 1 0 0]);

>> det(A+0)

ans =

1

>> dout = InvMatrix(A)

dout =

-1 1 0 1 -1

1 -1 -1 0 1

0 0 1 -1 1

0 0 0 1 -1

1 0 0 -1 1

[Andrei Bobrov]

>> A = logical([...

0 1 1 0 0

1 1 1 0 0

1 0 0 0 1

1 0 0 0 0

1 0 1 0 0]);

>> det(A+0)

ans =

0

>> dout = InvMatrix(A)

dout =

NaN NaN NaN NaN NaN

NaN NaN NaN NaN NaN

NaN NaN NaN NaN NaN

NaN NaN NaN NaN NaN

NaN NaN NaN NaN NaN

[Andrei Bobrov]

more edit

Answer 2

[Bhavya PH]

Hi Andrei, Thanks for the hint on the determinant value, though the det value is not zero I am unable to the inverse matrix.

PS the entries are no longer NAN and I am doing some post processing to determine if the obtained inverse is correct or not, have not obtained a breakthrough yet in this direction.