How to resolve linear equation Ax=b using Gaussian Elimination

10 views (last 30 days)
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

Answers (0)

Community Treasure Hunt

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

Start Hunting!