如何求解线性代数方程 AC=D 其中 A 是非方阵

Question

我有一个二进制矩阵 A（只有 1 和 0），以及伽罗华域 (256) 中的向量 D 向量 C 计算为：

  C = (A^^-1)*D

其中A^^-1表示GF(2)中矩阵A的逆矩阵，*为乘法运算。结果向量 C 必须在 GF(256).

但是，我只有一个矩阵A1是非方阵。上述方程中的矩阵A是通过删除A1的一些依赖行创建的。同理，向量D是通过删除A1中被删除行对应的一些元素来构造的。因此，我们可以求解上述等式。我的问题是我们可以在 MATLAB 中使用任何函数来执行上述步骤吗？

比如我有A1是16x14的矩阵，D1是16x1的向量

A1 =[1     0     0     1     1     0     0     0     0     0     0     0     0     0
     1     1     0     0     0     1     0     0     0     0     0     0     0     0
     1     1     1     0     0     0     1     0     0     0     0     0     0     0
     0     1     1     1     0     0     0     1     0     0     0     0     0     0
     0     0     1     1     0     0     0     0     1     0     0     0     0     0
     1     1     0     1     1     0     0     1     0     1     0     0     0     0
     1     0     1     1     0     1     0     0     1     0     1     0     0     0
     1     1     1     0     0     0     1     1     1     0     0     1     0     0
     0     1     1     1     1     1     1     0     0     0     0     0     1     0
     0     0     0     0     1     1     1     1     1     0     0     0     0     1
     0     1     1     1     1     0     1     1     1     0     1     1     1     0
     0     0     0     1     0     0     0     1     0     0     0     0     0     0
     0     0     1     0     0     0     0     1     0     0     0     0     0     0
     1     1     1     1     0     0     0     0     0     0     0     0     0     0
     0     0     1     1     0     0     0     0     1     1     0     0     0     0
     0     0     1     0     0     0     0     0     0     0     0     0     0     1 ]

D1=[0; 0; 0;  0 ; 0;   0 ;  0;   0 ;  0 ;  0 ;  103 ;  198 ;  105 ;  115;   175  ;  14]

在上面的例子中，我们需要从A1中删除两个依赖rows/cols得到A是14x14矩阵，D1也删除2个元素得到D，那么我的预期结果是

C=A^^-1*D
C= [  103;   187 ;  125;   210 ;  181;   220 ;  161   ; 20 ;  175;   175;  187;   187 ;  220 ;  115]

这是我试过的

%%A1=gf(A1,8);
%%D1=gf(D1,8); %%2^8=256
%% Do something and last step is
%%C=inv(A)*D
[C,vld] = gflineq(A1,D1,8)
Or 
C=gf(A1,8) \ gf(D1,8)

但是，这些方法并没有return 我预期的 C 向量。我发现Gaussian Elimination可以工作，但我不知道如何申请我的案例。你能给我一个正确的解决方案吗？

Answer 1

首先，我无权访问 "Communication system toolbox"，因此为了在 GF(2) 中运行，我必须在代码中添加 mod(stuff,2) 调用，并在为了在 GF(2^8) 中运行，我必须实现一个在此字段中求和的函数。只需使用 gf 定义您的变量，如果您有权访问工具箱，则删除这些调用。

先决条件：在 GF(2^8) 中求和：

在 GF(2^8) 中求和并不简单，因为它的行为类似于 (Z/2Z)^8。为了求和这个字段，我有如下函数。

基本上，GF(2^8)中的元素是8元组，每个元素取{0,1}中的值。例如，(1,1,0,0,0,1,1,0) 就是其中之一。为了求和该字段中的两个元组，ones has，每个元素取 Z/2Z 中的和。例如，如果我们想要 (0,0,0,1,0,0,0,1) 和 (1,1,1,1,1,1,1,1) 的总和：（请记住 Z/2Z、0+0=0、0+1=1、1+0=1 和 1+1=0)

这些元组的第一个元素是 0 和 1，因此总和的第一个元素将是 0+1=1。对所有元素执行此操作，您将获得：

(0,0,0,1,0,0,0,1)+(1,1,1,1,1,1,1,1)=(1,1,1,0,1,1,1,0)

函数操作同理：

1) 将输入转换为二进制数

2) 比较每个数字。如果它们相等，则它们总和为 0 (0+0=0 , 1+1=0)，否则它们总和为 1 (0+1=1 and 1+0=1).

3) 将结果转换回十进制数

function [D] = SumInGF256(D1,D2)
%UNTITLED3 Summary of this function goes here
%   Detailed explanation goes here


A=size(D1);
P=numel(D1);
D=zeros(A);

D1=dec2bin(D1,8);
D2=dec2bin(D2,8);

% TmpD=cell(A);

for jj=1:P

    TmpD1=D1(jj,:);
    TmpD2=D2(jj,:);



    out='';

    for ii=1:8

        if isequal(TmpD1(ii),TmpD2(ii))

            out=strcat(out,'0');

        else

            out=strcat(out,'1');

        end    


    end

    D(jj)=bin2dec(out);

end

GF(2) 中的高斯消元法在本质上与 R 或 C 中的工作方式完全相同，只是由于 1+1=0 的事实，它要容易得多。这是代码：

A1 =[1     0     0     1     1     0     0     0     0     0     0     0     0     0;...
     1     1     0     0     0     1     0     0     0     0     0     0     0     0;...
     1     1     1     0     0     0     1     0     0     0     0     0     0     0;...
     0     1     1     1     0     0     0     1     0     0     0     0     0     0;...
     0     0     1     1     0     0     0     0     1     0     0     0     0     0;...
     1     1     0     1     1     0     0     1     0     1     0     0     0     0;...
     1     0     1     1     0     1     0     0     1     0     1     0     0     0;...
     1     1     1     0     0     0     1     1     1     0     0     1     0     0;...
     0     1     1     1     1     1     1     0     0     0     0     0     1     0;...
     0     0     0     0     1     1     1     1     1     0     0     0     0     1;...
     0     1     1     1     1     0     1     1     1     0     1     1     1     0;...
     0     0     0     1     0     0     0     1     0     0     0     0     0     0;...
     0     0     1     0     0     0     0     1     0     0     0     0     0     0;...
     1     1     1     1     0     0     0     0     0     0     0     0     0     0;...
     0     0     1     1     0     0     0     0     1     1     0     0     0     0;...
     0     0     1     0     0     0     0     0     0     0     0     0     0     1 ];


D1=[0; 0; 0;  0 ; 0;   0 ;  0;   0 ;  0 ;  0 ;  103 ;  198 ;  105 ;  115;   175  ;  14];





for ii=1:14

   % Find ii-th pivot index between row ii and last row
   PivIndex=find(A1(ii:end,ii),1)+ii-1;

   % Switch ii-th row with Pivot row
   A1([ii PivIndex],:)=A1([PivIndex ii],:);
   D1([ii PivIndex])=D1([PivIndex ii]);

   % Find all rows other than row ii containing a 1 in column ii
   RowIndexes=find(A1(:,ii));
   RowIndexes(RowIndexes==ii)==[];

   % Add row ii to all rows in RowIndexes, do the same in D
   A1(RowIndexes,:)=mod(A1(RowIndexes,:)+repmat(A1(ii,:),numel(RowIndexes),1),2);

%% Problem with my answer was here, as the sum in GF(256) doesn t work like that. (GF(256),+) behaves like ((Z/2Z)^8,+)... See prequisite for summing in GF(256)

   % D1(RowIndexes)=mod(D1(RowIndexes)+repmat(D1(ii),numel(RowIndexes),1),256);

   D1(RowIndexes)=SumInGF256(D1(RowIndexes),repmat(D1(ii),numel(RowIndexes),1));

end

% Now A1 is diagonal, with both last rows being zero. Problem is D
% has to be 0 aswell on the 2 last positions to get 0=0..
% Check if D(15:16)==[0;0] if not the system has no solution

if isequal(D1(15:16),[0;0])

A2=A1(1:14,:);
C=D1(1:14)


else

    disp('No solution')

end

这里的输出是你想要的：

C =

103 187 125 210 181 220 161 20 175 175 187 187 220 115

Answer 2

首先，我要感谢 BillBokeey 所做的工作。但是，我在 GF(256) 中工作，它比 GF(2) 更复杂。在 google 之后，我为我的案例找到了一个很好的解决方案。这是 rfc-6330 的源代码。在那个源代码中，他有一个函数是rfc6330_gaussian。对于我上面的问题，很容易通过

应用它

C=rfc6330_gaussian( A1, D1 )

因此结果将与我的预期结果相似

这个答案。对任何有类似我的问题的人都有用。

如何求解线性代数方程 AC=D 其中 A 是非方阵

How to solve linear algebra equation AC=D where A is non-square matrix

matlab

equation

signal-processing

matrix

linear-algebra