Gaussian elimination GF(2)

Question

I'm solving a system of linear equations in $GF(2)$ and have a problem with detecting free variables. For example, in the following system (the last column is a right sight of the system):

1 2 3 4 5 6 7 8 9 10 11
1 0 0 0 0 0 0 0 0  0  0   0
0 1 0 0 0 0 0 0 0  0  0   0
0 0 1 0 0 0 0 0 0  0  0   0
0 0 0 1 0 0 0 0 0  0  0   0
0 0 0 0 1 0 0 0 0  0  0   1
0 0 0 0 0 0 0 1 1  1  0   0 
0 0 0 0 0 0 1 0 0  0  0   1
0 0 0 0 0 0 0 1 1  1  1   0
0 0 0 0 0 0 0 0 0  0  0   0
0 0 0 0 0 0 0 0 0  0  0   0
0 0 0 0 0 0 0 0 0  0  0   0

variables $x_6$, $x_9$, $x_{10}$, $x_{11}$ thought to be free. But if I assign them the following values: 1, 1, 1, 1 the system doesn't have solutions, and if I assign them: 0, 0, 0, 0 the solution then exists. So, what are free variables? And how should I find them if I have an upper triangular matrix?

Answer 1

The problem is that you haven't completed the row reduction yet.

Your matrix looks like

1 0 0 0 0 0 0 0 0 0 0   0
0 1 0 0 0 0 0 0 0 0 0   0
0 0 1 0 0 0 0 0 0 0 0   0
0 0 0 1 0 0 0 0 0 0 0   0
0 0 0 0 1 0 0 0 0 0 0   1
0 0 0 0 0 0 0 1 1 1 0   0 
0 0 0 0 0 0 1 0 0 0 0   1
0 0 0 0 0 0 0 1 1 1 1   0
0 0 0 0 0 0 0 0 0 0 0   0
0 0 0 0 0 0 0 0 0 0 0   0
0 0 0 0 0 0 0 0 0 0 0   0

If you subtract row six from row eight you get

1 0 0 0 0 0 0 0 0 0 0   0
0 1 0 0 0 0 0 0 0 0 0   0
0 0 1 0 0 0 0 0 0 0 0   0
0 0 0 1 0 0 0 0 0 0 0   0
0 0 0 0 1 0 0 0 0 0 0   1
0 0 0 0 0 0 0 1 1 1 0   0 
0 0 0 0 0 0 1 0 0 0 0   1
0 0 0 0 0 0 0 0 0 0 1   0
0 0 0 0 0 0 0 0 0 0 0   0
0 0 0 0 0 0 0 0 0 0 0   0
0 0 0 0 0 0 0 0 0 0 0   0

To get to the row echelon form you still need to interchange rows six ans seven

1 0 0 0 0 0 0 0 0 0 0   0
0 1 0 0 0 0 0 0 0 0 0   0
0 0 1 0 0 0 0 0 0 0 0   0
0 0 0 1 0 0 0 0 0 0 0   0
0 0 0 0 1 0 0 0 0 0 0   1
0 0 0 0 0 0 1 0 0 0 0   1
0 0 0 0 0 0 0 1 1 1 0   0 
0 0 0 0 0 0 0 0 0 0 1   0
0 0 0 0 0 0 0 0 0 0 0   0
0 0 0 0 0 0 0 0 0 0 0   0
0 0 0 0 0 0 0 0 0 0 0   0

From this you see that the variables $x_6$, $x_9$ and $x_{10}$ are free.

Remember: With a square matrix the number of all zero rows in row echelon form equals the number of free variables.