Skip to main content
Logo image

Applied Discrete Structures

Al Doerr, Ken Levasseur

🔗

Section 12.6 Linear Equations over the Integers Mod 2

🔗

Subsection 12.6.1 Row reduction mod 2

🔗
The methods we have studied for solving systems of equations up to this point can be applied to systems in which all arithmetic is done over other algebraic systems, including the integers modulo 2. The mod 2 case will become particularly useful in our later study of coding theory.
🔗
When solving systems of equations with mod 2 arithmetic, the elementary row operations are still fundamental. However, since there is only one nonzero element, 1, you never need to multiply a row by a nonzero constant. One other big difference is that the number of possible solutions is always finite. If you have m linear equations in n unknowns, each unknown can only take on one of two values, 0 or 1. Therefore there are only 2n possible n-tuples to from which to draw a solution set. Assuming m≤n, you typically (but not always) will have m basic variables after row-reduction and n−m free variable. If this is the case, and any solution exists, there will be 2n−m different solutions.
🔗
🔗
Let’s look at an example, which is coverted to matrix form immediately.
x1+x2+x4=1x1+x3+x5=0x2+x3+x6=0
🔗
🔗
The augmented matrix of the system is
(110100110101000110010)
🔗
The steps in row-reducing this matrix follow. Entries on which we “pivot” are displayed in bold face to more easily identify the basic variables.
(110100110101000110010) ⟶add R1 to R2 (110100101111010110010)  ⟶add R2 to R1 (101010001111010110010) ⟶add R2 to R3 (101010001111010001111)
🔗
🔗
Notice that at this point, we cannot pivot on the third row, third column since that entry is zero. Therefore we move over to the next column, making the x4 basic.
  ⟶add R3 to R2 (101010001100100001111)
🔗
🔗
This completes the row reduction and we can now identify the solution set. Keep in mind that since addition is subtraction, terms can be moved to either side of an equals sign without any change in sign. The basic variables are x1, x2, and x4, while the other three variables are free. The general solution of the system is
x1=x3+x5x2=x3+x6x3=x3x4=1+x5+x6x5=x5x6=x6
🔗
With three free variables, there are 23=8 solutions to this system. For example, one of them is obtained by setting x3=1, x5=1, and x6=0, which produces (x1,x2,x3,x4,x5,x6)=(0,1,1,0,1,0).
🔗
We can check our row reduction with SageMath:
🔗

Exercises 12.6.2 Exercises

🔗
In all of the exercises that follow, the systems of equations are over Z2, and so mod 2 arithmetic should be used in solving them.
🔗

1.

🔗
🔗
Solve the following systems, describing the solution sets completely:
  1. x1+x2=0x1+x3=0
  2. x1+x2=0x2+x3=0x3+x4=1x1+x2+x3=1
Answer.
  1. {(0,0,0),(1,1,1)}
  2. {(1,1,1,0)}
🔗

2.

🔗
🔗
This exercise provides an example in which the number of basic variables is less than the number of equations. The only difference between the two systems below is the right hand sides. You can start with an augmented matrix having two right side columns and do row reduction for both systems at the same time.
  1. x1+x2+x4=1x1+x3+x4=0x2+x3=1
  2. x1+x2+x4=1x1+x3+x4=0x2+x3=0
Answer.
As suggested here is the augmented matrix with both right sides, and its row reduction:
(110111101100011010) ⟶ (101100011010000001)
There are only two basic variables here because the left side of the last equation is the sum of the left sides of the first two equations.
  1. Ignoring the last column of both matrices, we see that the last equation of the first system reduces to 0=0, which is always true, and the first two equations yield two free variables, x3 and x4. The general solution is the set of quadruples {(x3+2x4,x3+21,x3,x4)∣x3,x4∈Z2}. The cardinality of the solution set is 4.
  2. If we replace the fifth column with the sixth one, the last row indicates that 0=1, which means that the solution set is empty.
🔗

3.

🔗
🔗
This exercise motivates the concept of a coset in Chapter 15.
  1. Solve the following system and prove that the solution set is a linear combination of vectors in Z25 and also a subgroup of the group Z25 under coordinatewise mod 2 addition.
    x1+x2+x5=0x1+x3+x5=0x1+x3+x4=0x2+x3+x4=0
  2. Describe the solution set to the following system as it relates to the solution set to the system in the previous part of this exercise.
    x1+x2+x5=1x1+x3+x5=0x1+x3+x4=1x2+x3+x4=0
Answer.
  1. Row reduction produces a solution with one free variable, x3.
    (x1,x2,x3,x4,x5)=(x3,x3,x3,0,0)=x3(1,1,1,0,0)
    The solution set has only two elements. It is {(0,0,0,0,0),(1,1,1,0,0)}. Since Z25 is a finite group, the solution set is a subgroup because it is closed with respect to coordinatewise mod 2 addition.
  2. The row-reduced augmented matrix of coefficients provides the solution
    (x1,x2,x3,x4,x5)=(x3,1+x3,x3,1,0)=(0,1,0,1,0)+x3(1,1,1,0,0)
    Therefore, the solution to this system is a shift of the solution set to the homogeneous system by the vector (0,1,0,1,0), which is {(0,1,0,1,0),(1,0,1,1,0)}
You have attempted of activities on this page.
PrevTopNext