Как вычислить левое нулевое пространство для матрицы над GF(2) в MATLAB?

Question

Допустим, у меня есть матрица над GF(2), то есть двоичная матрица. Как мне теперь вычислить левое нулевое пространство данной матрицы над конечным полем 2?

Предоставляет ли MATLAB встроенную функцию для этого?

Answer 1

Я не знаю пакетов Matlab для линейной алгебры в конечном пространстве, но я запрограммировал простую функцию, которая вычисляет LU-факторизации матриц по модулю простого числа p (например, 2):

function [L,D,U,rows,cols] = ModLU(A,p)
%
% LU-factorization of A, modulo p:
%     A(rows,cols) - mod(L * diag(D)*U,p)
%
[m,n] = size(A);

% inverses in mod-p:
%     mod(k*invp(k+1)) = 0 if k==0; 1 otherwise
invp = 2:p-2;
for i = 2:p-2; invp = mod(invp.*[2:p-2],p); end
invp = [0,1,invp,p-1];

% Initialize outputs:
L = eye(m); U = A;
rows = 1:m;
cols = 1:n;

% Sweep
for i = 1:m
   % Pivoting
   [row,col] = find(U(i:end,:));
   if isempty(row); break; end
   row = row(1)+i-1; col = col(1);

   r = 1:m; r(i) = row; r(row) = i;
   c = 1:n; c(i) = col; c(col) = i;
   ri = rows(i); rows(i) = rows(row); rows(row)=ri;
   ci = cols(i); cols(i) = cols(col); cols(col)=ci;

   rinv = 1:m; rinv(r) = 1:m;
   U = U(r,c); L=L(r,r);

   % Gaussian elimination
   L(i+1:end,i    ) = mod(invp(U(i,i)+1) * U(i+1:end,i),p);
   U(i+1:end,i:end) = mod(U(i+1:end,i:end) + (p-L(i+1:end,i)) * U(i,i:end),p);
end

% Factorize diagonal
D = zeros(m,1); D(1:min(m,n)) = diag(U);
U = mod(diag(invp(D+1)) * U,p );

Кроме того, для верхней треугольной матрицы с единицами на диагонали, функция, которая вычисляет пространство с правым нулем по модулю p:

function N = NullPU(U,p)
% for an upper triangular matrix, calculate a base for the null space modulo p:
%   U * N = 0

n = size(U,2);
rank = size(find(diag(U)),1);
A = U(1:rank,:);
for i=rank:-1:2
    A(1:i-1,:) = mod(A(1:i-1,:) + (p-1) * A(1:i-1,i) * A(i,:),p);
end
N = [mod(p-A(:,rank+1:end),p); eye(n-rank)];

Эти функции просто объединяются в функцию, которая вычисляет нулевое пространство матрицы A, по модулю p:

function N = NullP(A,p)
% Calculate a basis for the null space of A, modulo p:
%    mod(A*N,p) = 0
[L,D,U,rows,cols] = ModLU(A,p);
N = NullPU(U,p);
N(cols,:) = N;

Обратите внимание, что эта функция вычисляет базу для правого нулевого пространства A по модулю p. Левое нулевое пространство находится с помощью

N = NullP(A',p)';