matlab - 如何在 MATLAB 中计算 GF(2) 上的矩阵的左零空间？

Question

假设我有一个超过 GF(2) 的矩阵，即一个二进制矩阵。现在如何在 2 的有限域上计算给定矩阵的左零空间？

MATLAB 是否为此提供了内置函数？

Answer 1

我不知道有限空间中线性代数的 Matlab 包，但我编写了一个简单的函数，用于计算以素数 p 为模的矩阵的 LU 分解（例如，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)';