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:
