How to resolve linear equation Ax=b using Gaussian Elimination

As you known Gaussian Elimination (GE) is common method to find solution of x given by

    Ax=b

However, it only works when the rank of matrix A is full rank (assume `x` is m by 1 then rank of `A` at least `m`). My goal is that I try to find solution of `x`, although A is small than `m`. The solution will be find as soon as possible. For example, I have equation

    x1+x2+x3+x4 =1; (1)
    x1+x2       =0; (2)
          x3+x4 =1; (3)
    x1+x2+x3    =0; (4)

The A matrix can rewritten:

    A=  1 1 1 1
        1 1 0 0
        0 0 1 1
        1 1 1 0

And b is

    b= 1 
       0 
       1
       0

Note that x={x1,x2...} are performed in binary domain ([defined][1]). For this example, we can see that the equation (1) can find from (2) and (3). So we only can find solution of `x4=1 (from (1),(4)),` and `x3=0 (from (3)).` Hence I want to develop a method to find solution of Ax=b using GE without full rank matrix. That can implement as following

1. Delete all linear columns, and set -1 (unresolved) for x corresponding to index of linear column. For example, A has col1 and col2 are dependency (similar), then I delete them I put x=[-1 -1 1 1], where -1 denotes unresolved and 1 denote resolve (x1 and x2 are unresolved, while x3,x4 are resolve)
2. Second, Delete all zero rows and linear rows (maintain at least one linear row) in matrix A and corresponding rows in b vector. After step1, A is

     A=  [1 1;
          0 0;
          1 1;
          1 0]

The second rows is zero; first row and third rows are dependent. We will delete second rows and third row, A will be

    A= 1 1
       1 0
    b= 1 
       0

Now we can use GE to find solution. Finally, the expected result is

    x=[-1 -1 0 1]

These are my explanation for my algorithm. However, I have a problem when I try to delete all linear columns and second step. Please help me write 1 function to do step 1 and 2. The function look like

    %%Remove all linear cols and zero rows, linear rows
    function [Anew bnew]=removeColRow(A,b)
    %%do here
    end

[1]: http://en.wikipedia.org/wiki/Exclusive_or