Use Gaussian Jordan Elimination to convert binary matrix to All zero Matrix

10 次查看（过去 30 天）
Rishi Balasubramanian
评论： James Tursa 2021-1-27
Hello,
Consider I have my binary matrix. I want to use Gauss Jordan Elimination to convert a part of my matrix to all zero. Below is an illustrative example of what I seek
% ***** All '+' correspond to XOR operations where 0+0=0; 1+0=1; 0+1=1; 1+1=0; ***** %
a b c d | e f | g h i j k l
--------|-----|------------|
1 1 0 0 | 0 1 | 1 0 1 0 1 0| R1
0 1 1 1 | 0 1 | 0 1 0 0 1 0| R2
0 0 1 1 | 1 0 | 1 0 1 1 0 0| R3
0 0 0 1 | 0 1 | 1 1 0 1 0 1| R4
--------|-----|------------|
1 1 0 0 | 1 0 | 0 1 1 0 0 1| R5
1 0 1 0 | 1 0 | 0 0 0 1 1 1| R6
%\______/
||
\/
%Assume I
%want to
%convert
%this to
%all zero
R5 = R1+R5
1 1 0 0 0 1 1 0 1 0 1 0
+ 1 1 0 0 1 0 0 1 1 0 0 1
------------------------
R5 = 0 0 0 0 1 1 1 1 0 0 1 1
------------------------
Now we work for Row 6.
Ans = R1+R6
1 1 0 0 0 1 1 0 1 0 1 0
+ 1 0 1 0 1 0 0 0 0 1 1 1
-----------------------
Ans = 0 1 1 0 1 1 1 0 1 1 0 1
-----------------------
Ans1 = R2+ans
0 1 1 1 0 1 0 1 0 0 1 0
+ 0 1 1 0 1 1 1 0 1 1 0 1
-----------------------
Ans1 = 0 0 0 1 1 0 1 1 1 1 1 1
-----------------------
Ans2 = R4+Ans1
0 0 0 1 0 1 1 1 0 1 0 1
+ 0 0 0 1 1 0 1 1 1 1 1 1
-----------------------
Ans2 = 0 0 0 0 1 1 0 0 1 0 1 0
-----------------------
Final Matrix Becomes
a b c d | e f | g h i j k l
--------|-----|------------|
1 1 0 0 | 0 1 | 1 0 1 0 1 0| R1
0 1 1 1 | 0 1 | 0 1 0 0 1 0| R2
0 0 1 1 | 1 0 | 1 0 1 1 0 0| R3
0 0 0 1 | 0 1 | 1 1 0 1 0 1| R4
--------|-----|------------|
0 0 0 0 | 1 1 | 1 1 0 0 1 1| R5
0 0 0 0 | 1 1 | 0 0 1 0 1 0| R6
%\______/
||
\/
%Converted
%into an all
%zero matrix
By hand it is probably an elementary easy operation. But it does get out of hand when I want to automate this process. It gets out of hand when I want to create a generalised code that can work on any (mxn) matrix. Don't even imagine how to do this on a 93x155 matrix(That is what I am working on).
One good thing about this is that the matrix above the part I want to convert to all zero will always be a 'LOWER TRIANGULAR MATRIX'. So getting an answer IS possible.
But how, thats the question. If anyone of you scholars, Professionals can help me out on this one, It'll be great. Thanks in advance.
  3 个评论
显示 1更早的评论
Rishi Balasubramanian
Rishi Balasubramanian 2021-1-27
Yes Upper Triangular Matrix. My Bad.
If I knew how to, I wouldn't be taking this effort of fashioning an example and posting a question online looking for someone to help me, right?

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

James Tursa
James Tursa 2021-1-27
编辑：James Tursa 2021-1-27
Here is the code, which implements your stated algorithm directly. The input n is the known size of the upper triangular block in the upper left corner. The code then zeros out the block below this.
function B = zeroblock(A,n)
U = A(1:n,1:n);
if( any(any(tril(U,-1))) || any(diag(U)==0) )
error('Upper Left NxN block is not full rank upper triangular');
end
B = A;
m = size(A,1);
for j=1:n
for i=n+1:m
if( B(i,j) )
B(i,:) = xor(B(i,:),B(j,:));
end
end
end
end
  3 个评论
显示 1更早的评论
Rishi Balasubramanian
Rishi Balasubramanian 2021-1-27
This is what I did and my code works. It's just too confusingly complicated. Thats why I am looking for an answer. This is for the type where LT Matrix is on Right Side and Matrix to be eleiminated is on Bottom Right
H = A; %some m by n matrix with a LT Matrix on Right side
[m, n] = size(H);
g = m - (find(H(:, n), 1, 'first')); %To find the begining row of Matrix to be Eliminated - E Matrix
E = H(m-g+1:end,n-m+g+1:end); %E Matrix
[em, en] = size(E);
Eri = m-g+1; %First Row of E in H
Eci = n-m+g+1; %First Col of E in H
for ei = 1:em
while (nnz(H(Eri, Eci:end))~=0) %Loop until there are no non zeros in selected part of matrix(E Matrix in H)
subrow = Eci - 1 + find(H(Eri, Eci:end), 1, 'first'); %Select row of E to be permuted
add = find(H(1:Eri-1, subrow), 1, 'first'); %Find a row before E matrix with non zero element in same column as selected row to be permuted
H(Eri, :) = xor(H(Eri, :), H(add,:)); %XOR
end
Eri = Eri+1; %Go to next row
end
Can you see if this code can be simplified? or any other simple version is fine too.
James Tursa
James Tursa 2021-1-27
Just process things in reverse order from the end and use the same basic algorithm. So a slight change in the indexing. E.g.,
function B = zeroblockr(A,n)
N = size(A,2);
L = A(1:n,N-n+1:N); % upper right n x n block
if( any(any(triu(L,1))) || any(diag(L)==0) )
error('Upper Right NxN block is not full rank lower triangular');
end
B = A;
m = size(A,1);
for j=n:-1:1
J = j + N - n;
for i=n+1:m
if( B(i,J) )
B(i,:) = xor(B(i,:),B(j,:));
end
end
end
end

请先登录，再进行评论。

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Sparse Matrices 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by