Skip to main content
Logo image

Applied Discrete Structures

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 \(2^n\) possible \(n\)-tuples to from which to draw a solution set. Assuming \(m \leq n\text{,}\) 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 \(2^{n-m}\) different solutions.
Let’s look at an example, which is coverted to matrix form immediately.
\begin{equation*} \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}} x_1 &{}+{} &x_2 & & &{}+{} & x_4 & & & & &= 1 \\ x_1 & & & {}+{}&x_3 & & &{}+{} & x_5& & &= 0 \\ & & x_2& {}+{}&x_3 & & & & &{}+{}&x_6&= 0 \\ \end{array} \end{equation*}
The augmented matrix of the system is
\begin{equation*} \left( \begin{array}{cccccc|c} 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ \end{array} \right) \end{equation*}
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.
\begin{equation*} \begin{split} \left( \begin{array}{cccccc|c} 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ \end{array} \right) & \overset{\textrm{add }R_1\textrm{ to }R_2}{\text{ }\longrightarrow }\text{ } \left( \begin{array}{cccccc|c} \textbf{1} & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ \end{array} \right)\\ & \text{ }\overset{\textrm{add }R_2\textrm{ to }R_1}{\text{ }\longrightarrow }\text{ }\left( \begin{array}{cccccc|c} \textbf{1} & 0 & 1 & 0 & 1& 0 & 0 \\ 0 & \textbf{1} & 1 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ \end{array} \right) \\ & \overset{\textrm{add }R_2\textrm{ to }R_3}{\text{ }\longrightarrow }\text{ } \left( \begin{array}{cccccc|c} \textbf{1} & 0 & 1 & 0 & 1& 0 & 0 \\ 0 &\textbf{1} & 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{array} \right) \end{split} \end{equation*}
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 \(x_4\) basic.
\begin{equation*} \begin{split} \text{ }&\overset{\textrm{add }R_3\textrm{ to }R_2}{\text{ }\longrightarrow }\text{ } \left( \begin{array}{cccccc|c} \textbf{1} & 0 & 1 & 0 & 1& 0 & 0 \\ 0 & \textbf{1} & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & \textbf{1} & 1 & 1 & 1 \\ \end{array} \right) \end{split} \end{equation*}
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 \(x_1\text{,}\) \(x_2\text{,}\) and \(x_4\text{,}\) while the other three variables are free. The general solution of the system is
\begin{equation*} \begin{array}{c} x_1 = x_3+x_5\\ x_2 = x_3+x_6 \\ x_3 = x_3 \\ x_4 = 1+ x_5+x_6 \\ x_5 = x_5 \\ x_6 = x_6 \\ \end{array} \end{equation*}
With three free variables, there are \(2^3=8\) solutions to this system. For example, one of them is obtained by setting \(x_3=1\text{,}\) \(x_5=1\text{,}\) and \(x_6=0\text{,}\) which produces \((x_1, x_2, x_3, x_4, x_5, x_6) = (0,1,1,0,1,0)\text{.}\)
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 \(\mathbb{Z}_2\text{,}\) and so mod 2 arithmetic should be used in solving them.

1.

Solve the following systems, describing the solution sets completely:
  1. \(\displaystyle \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}} x_1 & {}+{} & x_2 & & & = 0 \\ x_1 & & & {}+{} & x_3 & = 0 \\ \end{array} \)
  2. \(\displaystyle \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}} x_1 & {}+{} & x_2 & & & & & = 0 \\ & & x_2 & {}+{} & x_3& & & = 0\\ & & & & x_3& {}+{} & x_4 & = 1 \\ x_1 & {}+{} & x_2 & {}+{} & x_3& & & = 1 \\ \end{array} \)
Answer.
  1. \(\displaystyle \{(0,0,0),(1,1,1)\}\)
  2. \(\displaystyle \{(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. \(\displaystyle \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}} x_1 & {}+{} &x_2 & & &{}+{} & x_4 &= 1 \\ x_1 & & & {}+{} &x_3 & {}+{} & x_4 &= 0 \\ & & x_2 & {}+{} &x_3 & & &= 1 \\ \end{array}\)
  2. \(\displaystyle \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}} x_1 & {}+{} &x_2 & & &{}+{} & x_4 &= 1 \\ x_1 & & & {}+{} &x_3 & {}+{} & x_4 &= 0 \\ & & x_2 & {}+{} &x_3 & & &= 0 \\ \end{array}\)
Answer.
As suggested here is the augmented matrix with both right sides, and its row reduction:
\begin{equation*} \begin{split} \left( \begin{array}{cccc|cc} 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ \end{array} \right) & \text{ }\longrightarrow \text{ } \left( \begin{array}{cccc|cc} \textbf{1} & 0 & 1 & 1 & 0 & 0 \\ 0 & \textbf{1} & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right)\\ \end{split} \end{equation*}
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\text{,}\) which is always true, and the first two equations yield two free variables, \(x_3\) and \(x_4\text{.}\) The general solution is the set of quadruples \(\{(x_3 +_2 x_4,x_3 +_2 1, x_3, x_4) \mid x_3, x_4 \in \mathbb{Z}_2 \}\text{.}\) 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\text{,}\) 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 \(\mathbb{Z}_{2}^{5}\) and also a subgroup of the group \(\mathbb{Z}_{2}^{5}\) under coordinatewise mod 2 addition.
    \begin{equation*} \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}} x_1 & {}+{} &x_2 & & & & &{}+{} & x_5&= 0 \\ x_1 & & & {}+{} &x_3 & & &{}+{} & x_5&= 0 \\ x_1 & & & {}+{} &x_3 &{}+{} & x_4 & & &= 0 \\ & & x_2 & {}+{} &x_3 &{}+{} & x_4 & & &= 0 \\ \end{array} \end{equation*}
  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.
    \begin{equation*} \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}} x_1 & {}+{} &x_2 & & & & &{}+{} & x_5&= 1 \\ x_1 & & & {}+{} &x_3 & & &{}+{} & x_5&= 0 \\ x_1 & & & {}+{} &x_3 &{}+{} & x_4 & & &= 1 \\ & & x_2 & {}+{} &x_3 &{}+{} & x_4 & & &= 0 \\ \end{array} \end{equation*}
Answer.
  1. Row reduction produces a solution with one free variable, \(x_3\text{.}\)
    \begin{equation*} \begin{split} (x_1, x_2, x_3, x_4, x_5)& =(x_3,x_3,x_3,0,0)\\ & = x_3 (1,1,1,0,0) \\ \end{split} \end{equation*}
    The solution set has only two elements. It is \(\{(0,0,0,0,0), (1,1,1,0,0)\}\text{.}\) Since \(\mathbb{Z}_{2}^{5}\) 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
    \begin{equation*} \begin{split} (x_1, x_2, x_3, x_4, x_5)& =(x_3,1+x_3,x_3,1,0)\\ & = (0,1,0,1,0) + x_3 (1,1,1,0,0) \\ \end{split} \end{equation*}
    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)\text{,}\) which is \(\{(0,1,0,1,0), (1,0,1,1,0)\}\)
You have attempted of activities on this page.