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

9 visualizaciones (últimos 30 días)
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 comentarios
Rishi Balasubramanian
Rishi Balasubramanian el 27 de En. de 2021
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?

Iniciar sesión para comentar.

Respuesta aceptada

James Tursa
James Tursa el 27 de En. de 2021
Editada: James Tursa el 27 de En. de 2021
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 comentarios
Rishi Balasubramanian
Rishi Balasubramanian el 27 de En. de 2021
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 el 27 de En. de 2021
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

Iniciar sesión para comentar.

Más respuestas (0)

Categorías

Más información sobre Creating and Concatenating Matrices en Help Center y File Exchange.

Community Treasure Hunt

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

Start Hunting!

Translated by