CODEWITHSUNDEEP
algorithmmatlabmatrixlinear-algebra
user3051460
user3051460

Reputation: 1485

Find rank of matrix in GF(2) using Gaussian Elimination

I am find the rank of binary matrix in GF(2)( Galois Field). The rank function in matlab cannot find it. For example, Given a matrix 400 by 400 as here. If you use the rank function as

rank(A)
ans=357

However, the correct ans. in GF(2) must be 356 by this code

B=gf(A);
rank(B);
ans=356;

But this way spends a lot a time (about 16s). Hence, I used Gaussian elimination to find the rank in GF(2) with small time. But, it does not works well. Sometime, it returns the true value, but sometime it returns wrong. Please see my code and let me know the problem in my code. Note that, it spend very small time compare with above code

function rankA =GaussEliRank(A) 
    tic
    mat = A;
    [m n] = size(A);              % read the size of the original matrix A
    for i = 1 : n       
        j = find(mat(i:m, i), 1); % finds the FIRST 1 in i-th column starting at i
        if isempty(j)
                mat = mat( sum(mat,2)>0 ,:);
                rankA=rank(mat);               
                return;
        else
            j = j + i - 1;       % we need to add i-1 since j starts at i
            temp = mat(j, :); % swap rows
            mat(j, :) = mat(i, :);
            mat(i, :) = temp;
            % add i-th row to all rows that contain 1 in i-th column
            % starting at j+1 - remember up to j are zeros
            for k = find(mat( (j+1):m, i ))' 
                mat(j + k, :) = bitxor(mat(j + k, :), mat(i, :));
            end
        end
    end
    %remove all-zero rows if there are some
    mat = mat( sum(mat,2)>0 ,:);
    if any(sum( mat(:,1:n) ,2)==0) % no solution because matrix A contains
        error('No solution.');  % all-zero row, but with nonzero RHS
    end    
   rankA=sum(sum(mat,2)>0);
end

Upvotes: 1

Views: 1597

Answers (1)

John
John

Reputation: 3070

Let use the gfrank function. It is suitable for your matrix. Use:

gfrank(A)
ans=
    356

More detail: How to find the row rank of matrix in Galois fields?

Upvotes: 1

Related Questions