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

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.

[James Tursa]

Did you mean "UPPER TRIANGULAR MATRIX", as in what your example shows? If so, then why not just code up your scheme?

[Rishi Balasubramanian]

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?

[Walter Roberson]

Duplicated by https://www.mathworks.com/matlabcentral/answers/727403-gaussian-jordan-elimination-of-matrix?s_tid=srchtitle (now closed)

Answer 1

[James Tursa]

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

[Rishi Balasubramanian]

Can you show how to work on this matrix?

A = [1 1 1 0 0 1 | 1 0 | 1 0 0 0; \
     1 1 1 1 0 0 | 0 1 | 0 1 0 0;  \- %This is the Lower Triangular Matrix
     0 0 0 0 1 1 | 1 0 | 1 1 1 0;  /-
     1 0 0 1 1 0 | 0 0 | 0 1 1 1; /
     ----------------------------
     0 1 0 1 0 0 | 1 1 | 0 0 1 1; %\-this time, I want to convert this part 
     0 0 1 0 1 1 | 0 1 | 1 0 0 1];%/-  into an all zero matrix

I tried changing the error statement from tril to triu and changed U to select the proper LT Matrix. But the result was not all zero at the bottom. Can you help here?

[Rishi Balasubramanian]

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]

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