Вычислить ранг двоичной матрицы с большим размером

Question

У меня все проблемы при вычислении ранга бинарной матрицы, которая имеет только 1 или 0. Ранг бинарной матрицы будет основываться на сокращении строк с использованием булевых операций XOR. Посмотрю, операцию XOR:

1 xor 1 =0 
1 xor 0= 1 
0 xor 0= 0 
0 xor 1= 1 

Учитывая бинарную матрицу, как

A = 

    1  1  0  0  0  0 
    1  0  0  0  0  1 
    0  1  0  0  0  1 

Мы видим третий ряд равен первую строку XOR со вторым рядом. Следовательно, ранг матрицы А равен 2, а не 3 по ранговой матричной функции. У меня есть один способ вычисления extractly ранга двоичной матрицы с помощью этого кода

B=gf(A) 
rank(B) 

Он вернется 2. Однако, когда я вычислить с большим размером матрицы, например, 400 на 400. Это не вернуть ранг (никогда не останавливаться). Не могли бы вы предложить мне хороший способ найти ранг бинарной матрицы для больших размеров? Спасибо всем UPDATE: это время вычисления с помощью Tic Toc

N=50; Elapsed time is=0.646823 seconds 
N=100;Elapsed time is 3.123573 seconds. 
N=150;Elapsed time is 7.438541 seconds. 
N=200;Elapsed time is 11.349964 seconds. 
N=400;Elapsed time is 66.815286 seconds. 

Обратите внимание, что регистрация ранг только условие в моем алгоритме. Тем не менее, это занимает очень много времени, то это повлияет на мой метод. Основание на предположении R. Я буду использовать гауссово исключение, чтобы найти ранг. Это мой код. Тем не менее, он вызывает функцию рангов (потратить некоторое время вычисления). Могли бы вы изменить мне помощь без использования функции ранга?

function rankA=GaussEliRank(A) 
    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); %%Here 
       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=rank(mat); %%Here 

end 

Пусть проверить матрицу А на here. Правильный ans равен 393 для ранга A.

Answer 1

Как только вы получите матрицу в форме эшелона строк с гауссовским исключением, ранг - это число ненулевых строк. Вы должны иметь возможность заменить код после цикла чем-то вроде rankA=sum(sum(mat,2)>0);.