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

Answer 1

[Jaynik]

Hi @Toan,

Following is a rough algorithm that can be followed to implement the function removeColRow that removes linear columns and zero or dependent rows.

1. Identify independent columns:

• Start with an empty list of independent columns.
• For each column in matrix A, temporarily add it to the list of independent columns.
• Use the rank function to determine if adding this column increases the rank of the submatrix formed by the current list of independent columns. Refer this documentation to read more about the rank function: https://www.mathworks.com/help/matlab/ref/rank.html
• If the rank increases, keep the column in the list; otherwise, discard it.

2. Form the reduced matrix with independent columns, that is, create a new matrix using only the columns identified as independent.

3. Identify independent rows just like we followed steps for indentifying independent columns.

4. Create the final reduced matrix using only the independent rows identified and adjust the vector b to correspond to the rows retained in the reduced matrix.

5. Solve the reduced system after checking if the reduced matrix has full column rank.

Hope this helps!