title: Find rank of matrix in GF(2) using Gaussian Elimination
body: <p>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 <a href="https://www.dropbox.com/s/glt4y90mfr6tq06/A.mat?dl=0" rel="nofollow">here</a>. If you use the rank function as</p>
  
  <pre><code>rank(A)
  ans=357
  </code></pre>
  
  <p>However, the correct ans. in GF(2) must be 356 by this code</p>
  
  <pre><code>B=gf(A);
  rank(B);
  ans=356;
  </code></pre>
  
  <p>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</p>
  
  <pre><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)&gt;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)&gt;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)&gt;0);
  end
  </code></pre>