필터 지우기
필터 지우기

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

조회 수: 19 (최근 30일)
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
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
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 CenterFile Exchange에서 Sparse Matrices에 대해 자세히 알아보기

Community Treasure Hunt

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

Start Hunting!

Translated by