Skip to main content

Linear Algebra Gathering and Sharpening Tools

Ryan Higginbottom

Section 2.2 Solving Linear Systems Over Fields

Having now defined a field, in this section we will show how the problems of chapter 1 can be solved in this general setting. We have laid the groundwork for reproducing the results of the first three sections of Chapter 1 for a general field \(\ff\) instead of the real numbers.
🔗
We now return to where we began in Section 1.1: the humble linear equation. If fields are generalizations of the real numbers, and if we can solve linear equations when everything in sight comes from the real numbers, we should be able to solve linear equations when everything in sight comes from a general field.
🔗

Example 2.2.1.

Consider the following equation where all variable values, constants, and coefficients are drawn from \(\ff_5\text{:}\)
\begin{equation*} 3x + 2 = 1\text{.} \end{equation*}
Solving this equation in \(\rr\) would be easy; let’s solve it in \(\ff_5\text{.}\)
🔗
We first note that the additive inverse of \(2\) in \(\ff_5\) is \(3\text{,}\) so our first step is to add \(3\) to both sides of the equation:
\begin{align*} 3x + 2 + 3 \amp =1 + 3\\ 3x \amp =4\text{.} \end{align*}
We now need the multiplicative inverse of \(3\) in \(\ff_5\text{,}\) which is \(2\text{.}\) We multiply both sides by \(2\) to get our answer:
\begin{align*} 2(3x) \amp = 2(4)\\ x \amp =3\text{.} \end{align*}
🔗
When we check that our solution works (we plug \(x=3\) back into the original equation and perform the computations in \(\ff_5\)), we find that it does:
\begin{equation*} 3x+2 = 3(3)+2 = 9+2=11 = 1\text{.} \end{equation*}
🔗
🔗
The point of this section is that the algorithm for solving linear systems (Algorithm 1.3.8) which worked for \(\rr\) also works for a general field \(\ff\text{.}\) In order to be comfortable with this notion, we need to talk quickly through the development of that algorithm in this general setting.
🔗
Because a general field contains both \(0\) and \(1\) (or rather, an additive and a multiplicative identity), and because within a field we can perform all of the operations needed to solve linear systems, everything we want to do is legitimate. The definitions of the coefficient and augmented matrices, the elementary row operations, the echelon forms, pivots, and the row reduction algorithm (all found in Section 1.2 and Section 1.3) are the same once we move away from \(\rr\text{.}\) Similarly, the three important theorems we have encountered so far (which we will reproduce below) all hold over a general field \(\ff\text{.}\) We will omit the proofs of these theorems because the earlier proofs, when translated from \(\rr\) to \(\ff\text{,}\) are still valid.
🔗
The algorithm for solving a linear system, supported by these theorems, remains the same as in Algorithm 1.3.8. We will finish this section with two examples where we go through this algorithm carefully.
🔗

Example 2.2.5.

The following is a linear system over \(\ff_3\text{:}\)
\begin{align*} x_1 + 2x_2 + x_3 \amp =1\\ 2x_1 + 2x_2 \amp =1\\ x_1+2x_3 \amp =0\text{.} \end{align*}
We will begin to solve this system by forming the augmented matrix:
\begin{equation*} \left[\begin{array}{@{}ccc|c@{}} 1 \amp 2 \amp 1 \amp 1 \\ 2 \amp 2 \amp 0 \amp 1 \\ 1 \amp 0 \amp 2 \amp 0 \end{array}\right]\text{.} \end{equation*}
Since working with fields other than \(\rr\) is still new, we will explain all of the steps needed to reduce this matrix to its RREF. We first add the first row to the second row to produce a \(0\) in the \((2,1)\) position. (Remember that \(1\) is the additive inverse of \(2\) in \(\ff_3\text{!}\)) This matrix is the result:
\begin{equation*} \left[\begin{array}{@{}ccc|c@{}} 1 \amp 2 \amp 1 \amp 1 \\ 0 \amp 1 \amp 1 \amp 2 \\ 1 \amp 0 \amp 2 \amp 0 \end{array}\right]\text{.} \end{equation*}
🔗
We now add twice the first row to the third to produce a \(0\) in the \((3,1)\) position. Here is that matrix:
\begin{equation*} \left[\begin{array}{@{}ccc|c@{}} 1 \amp 2 \amp 1 \amp 1 \\ 0 \amp 1 \amp 1 \amp 2 \\ 0 \amp 1 \amp 1 \amp 2 \end{array}\right]\text{.} \end{equation*}
🔗
We now notice that the second and third rows are the same. This means the third row will end up being a row of zeros, and we can achieve this by adding twice the second row to the third (in \(\ff_3\text{,}\) this is the same as subtracting the second row from the third):
\begin{equation*} \left[\begin{array}{@{}ccc|c@{}} 1 \amp 2 \amp 1 \amp 1 \\ 0 \amp 1 \amp 1 \amp 2 \\ 0 \amp 0 \amp 0 \amp 0 \end{array}\right]\text{.} \end{equation*}
🔗
The final step in reducing this matrix is to take care of the entry which is above the pivot in the \((2,2)\) position. We add the second row to the first, and this is the matrix which results:
\begin{equation*} \left[\begin{array}{@{}ccc|c@{}} 1 \amp 0 \amp 2 \amp 0 \\ 0 \amp 1 \amp 1 \amp 2 \\ 0 \amp 0 \amp 0 \amp 0 \end{array}\right]\text{.} \end{equation*}
🔗
Our matrix is now in RREF, and from Theorem 2.2.2 we can conclude that this linear system is consistent. Further, from Theorem 2.2.3 we can see that there is not a unique solution to this system. We can write the solutions to this system, however:
\begin{equation*} \left\{ \begin{array}{l} x_1 = x_3 \\ x_2 = 2+2x_3 \\ x_3 \text{ is free.} \end{array} \right. \end{equation*}
Since \(\ff_3\) has three elements, there are three possible values for \(x_3\text{,}\) meaning that there are three solutions to this linear system.
🔗
🔗

Note 2.2.6.

A linear system over a field \(\ff\) will have either no solutions, a unique solution, or a number of solutions related to the size of the field and the number of free variables. When the field is infinite, we have what is sometimes known as the “trichotomy law”, namely that the number of solutions to a linear system over such a field will either be zero, one, or infinite. This law needs some modification when the field is finite. (See Exercise 1.3.12 and compare it to Exercise 2.2.11.)
🔗
🔗

Example 2.2.7.

The following is a linear system over \(\cc\text{:}\)
\begin{align*} (2-i)x_1 + (2+4i)x_2 + (-7+6i)x_3 \amp = 2-6i \\ (1-2i)x_1 + (5+2i)x_2 + (-2+12i)x_3 \amp = -3-8i \\ -3x_1 + (1-5i)x_2 + 9x_3 \amp =-4+3i \text{.} \end{align*}
This example may seem a bit intimidating at first, especially for readers who have not dealt much with \(\cc\text{.}\) But when we follow our step-by-step approach, we should arrive at a solution with minimal problems.
🔗
First, we write down the augmented matrix of this system:
\begin{equation*} \left[\begin{array}{@{}ccc|c@{}} 2-i \amp 2+4i \amp -7+6i \amp 2-6i \\ 1-2i \amp 5+2i \amp -2+12i \amp -3-8i \\ -3 \amp 1-5i \amp 9 \amp -4+3i \end{array}\right]\text{.} \end{equation*}
To start row reducing this matrix, we need a \(1\) in the \((1,1)\) entry. Instead of following Algorithm 1.3.8 rigidly by exchanging rows and then dividing (or multiplying by an inverse), we will skip the first step and handle the rows as they are.
🔗
For a nonzero element \(a+bi\) of \(\cc\text{,}\) the multiplicative inverse is
\begin{equation*} \frac{a}{a^2+b^2} - \frac{b}{a^2+b^2}i\text{.} \end{equation*}
This means that the inverse of \(2-i\) is \(\frac{2}{5}+\frac{1}{5}i\text{.}\) So, in order to get a \(1\) in the \((1,1)\) position, we multiply the first row of the matrix by \(\frac{2}{5}+\frac{1}{5}i\text{.}\) Here is the result:
\begin{equation*} \left[\begin{array}{@{}ccc|c@{}} 1 \amp 2i \amp -4+i \amp 2-2i \\ 1-2i \amp 5+2i \amp -2+12i \amp -3-8i \\ -3 \amp 1-5i \amp 9 \amp -4+3i \end{array}\right]\text{.} \end{equation*}
🔗
We now work to clear out the other entries in the first column. We add \((-1+2i)\) times the first row to the second and we add \(3\) times the first row to the third. (We are taking care of two steps at once here.) This is the result:
\begin{equation*} \left[\begin{array}{@{}ccc|c@{}} 1 \amp 2i \amp -4+i \amp 2-2i \\ 0 \amp 1 \amp 3i \amp -1-2i \\ 0 \amp 1+i \amp -3+3i \amp 2-3i \end{array}\right]\text{.} \end{equation*}
(For readers who are new to \(\cc\text{,}\) verifying these calculations would be an excellent exercise!)
🔗
Since we already have a \(1\) in the \((2,2)\) entry, we can use that to produce a zero below it in that column. We add \((-1-i)\) times the second row to the third row, and we get this:
\begin{equation*} \left[\begin{array}{@{}ccc|c@{}} 1 \amp 2i \amp -4+i \amp 2-2i \\ 0 \amp 1 \amp 3i \amp -1-2i \\ 0 \amp 0 \amp 0 \amp 1 \end{array}\right]\text{.} \end{equation*}
🔗
Even though this matrix is not yet in RREF, we do not need to continue with our algorithm. Theorem 2.2.2 tells us that the original system is inconsistent because of the pivot in the final column. Therefore, this system has no solution.
🔗
🔗

Note 2.2.8.

Readers will be able to put a matrix over \(\rr\) into RREF without difficulty using various computational means—handheld calculators, smartphone applications, and any number of online matrix manipulators. However, working with matrices over fields which are not \(\rr\) presents some difficulties for most of these applications.
🔗
Students can find similar online calculators for matrices over the complex numbers through online searches. Finite fields are a bit trickier. David Augustat has created the website Matrixer
 3 
matrixer.davidaugustat.com/
for this purpose, and we encourage readers to take advantage of this resource after they have first mastered the mechanics themselves. (That is, tools like this are best used to check work that is done by hand and then, when the by-hand calculations are no longer the main point, to streamline the process.)
🔗
Finally, we have written an R package called matrixmodp, which can be found on CRAN
 4 
cran.r-project.org/web/packages/matrixmodp/index.html
. This package can handle matrices over finite, prime fields, but it does not have the capability to handle matrices over more exotic finite fields. (We are aware that R is not the best vehicle for matrix algebra, but this book was largely written when we were also learning R, and this was a good excuse to learn how to author a package in that language.)
🔗
🔗

Reading Questions Reading Questions

1.

Solve the following linear equation over \(\cc\text{.}\) List the steps you take in solving the equation in terms of the axioms of a field.
\begin{equation*} (1-3i)x + (4+2i) = -1-3i \end{equation*}
🔗
🔗

2.

The following is a matrix with entries from \(\ff_5\text{.}\) Reduce this matrix to REF. (It is not necessary to reduce the matrix to RREF.) Describe each step you take.
\begin{equation*} \begin{bmatrix} 4 \amp 2 \amp 0 \amp 1 \\ 3 \amp 1 \amp 1 \amp 3 \\ 2 \amp 0 \amp 4 \amp 4 \end{bmatrix} \end{equation*}
🔗
🔗
🔗

Exercises Exercises

1.

Solve the following linear system over \(\ff_2\text{:}\)
\begin{align*} x + z \amp = 1\\ y+z \amp = 0\\ x+y+z \amp = 1\text{.} \end{align*}
🔗
Answer.
This system has the solution \(x=1\text{,}\) \(y=0\text{,}\) \(z=0\text{.}\)
🔗
🔗
🔗

2.

Solve the following linear system over \(\ff_3\text{:}\)
\begin{align*} 2x + y + z \amp =0\\ x + 2z \amp = 2\\ y + z \amp = 1\\ 2x + 2y \amp = 1\text{.} \end{align*}
🔗
Answer.
This linear system is inconsistent.
🔗
🔗
🔗

3.

Solve the following linear system over \(\ff_7\text{:}\)
\begin{align*} 2x_1 + 3x_2 + x_4 \amp = 4\\ 3x_1 + x_3 + 5x_4 \amp = 6\\ 4x_1 + x_2 + 2x_3 \amp = 5\text{.} \end{align*}
🔗
🔗

4.

The following matrix \(A\) is defined over \(\cc\text{:}\)
\begin{equation*} A = \begin{bmatrix} i \amp 1+i \amp 3 \\ 1-i \amp -3+2i \amp 6+10i \end{bmatrix}\text{.} \end{equation*}
Put this matrix into RREF.
🔗
🔗

5.

Solve the following linear system over \(\cc\text{:}\)
\begin{align*} (-i)x + (3-i)z \amp = -1\\ (3+2i)x + y + (-1+9i)z \amp = 6-3i\\ (1+i)x + (2-i)y - (2i)z \amp = 10-5i\text{.} \end{align*}
🔗
Answer.
This system is inconsistent.
🔗
🔗
🔗

6.

Solve the following linear system over \(\ff_5\text{:}\)
\begin{align*} 4x + y \amp = 2\\ 3x + 2y + 2z \amp = 1\\ x + 3y + z \amp = 0\text{.} \end{align*}
🔗
Answer.
The unique solution is \(x = 2\text{,}\) \(y = 4\text{,}\) and \(z = 1\text{.}\)
🔗
🔗
🔗

7.

The following matrix \(A\) is defined over \(\qq[\sqrt{2}]\) (see Exercise 2.1.9):
\begin{equation*} A = \begin{bmatrix} 1+\sqrt{2} \amp 2 \amp 3 \amp -1+2\sqrt{2} \\ 3\sqrt{2} \amp 1-\sqrt{2} \amp 0 \amp 2+\sqrt{2} \\ 4 \amp -5+2\sqrt{2} \amp 3 + \sqrt{2} \amp -1 \end{bmatrix}\text{.} \end{equation*}
Put this matrix into RREF.
🔗
🔗

8.

The following matrix \(A\) is defined over \(\ff_3[\alpha]\) (see Exercise 2.1.7):
\begin{equation*} A = \begin{bmatrix} 2 + \alpha \amp 2\alpha \amp 1 \\ 1+2\alpha \amp \alpha \amp 2 \\ 0 \amp 1+\alpha \amp 2+2\alpha \end{bmatrix}\text{.} \end{equation*}
Put this matrix into RREF.
🔗
🔗

Writing Exercises

9.
  1. Suppose that the following is a linear system over \(\ff_3\text{:}\)
    \begin{align*} ax + by \amp =e\\ cx + dy \amp =f\text{.} \end{align*}
    Show that if \(ad + 2bc \neq 0\text{,}\) then this linear system has a unique solution. (For reference, see Exercise 1.3.11.)
    🔗
    🔗
  2. Suppose that the system stated in part (a) of this problem is a system over \(\ff_p\text{.}\) What is the correct inequality the coefficients \(a\text{,}\) \(b\text{,}\) \(c\text{,}\) and \(d\) must satisfy in order for the system to have a unique solution? State your answer and prove it is correct.
    🔗
    🔗
🔗
Answer.
  1. The same argument as in Exercise 1.3.11 works here, recognizing that \(2=-1\) in \(\ff_3\text{.}\)
    🔗
    🔗
  2. The correct inequality is \(ad+(p-1)bc \neq 0\text{.}\)
    🔗
    🔗
🔗
🔗
🔗
10.
Consider a linear system
\begin{align*} a_{11}x_1 + \cdots + a_{1n}x_n \amp =b_1\\ \vdots \amp \\ a_{m1}x_1 + \cdots + a_{mn}x_n \amp =b_m\text{,} \end{align*}
with all coefficients and constants in the integers.
  1. Show that if the system has a solution \(\bfx \in \rr^n\) then it must have a solution \(\bfy \in \qq^n\text{.}\)
    🔗
    🔗
  2. Show that if the system has a unique solution \(\bfx \in \qq^n\) then \(\bfx\) is also the unique solution in \(\rr^n\text{.}\)
    🔗
    🔗
🔗
Answer.
  1. If all of the coefficients and constants begin as integers, all of the elementary row operations will produce coefficients and constants within \(\qq\text{.}\) None of the elementary row operations can produce an irrational number when beginning with integers.
    🔗
    🔗
  2. If there is a unique solution, there are no free variables, so whether one considers the solution in \(\qq^n\) or \(\rr^n\text{,}\) there cannot be another solution. Thus, the numbers in the solution set must be rational numbers.
    🔗
    🔗
🔗
🔗
🔗
11.
Give descriptions of linear systems with each of the following properties, or state why such a system is impossible. Specific numbers and equations are not necessary, but your description should include what field is involved, the number of equations and variables, the number of free variables, etc. Explain your answers.
  1. A consistent system with exactly 8 solutions
    🔗
    🔗
  2. A consistent system with exactly 10 solutions
    🔗
    🔗
  3. A consistent system with exactly 9 solutions
    🔗
    🔗
  4. A consistent system with exactly 17 solutions
    🔗
    🔗
🔗
🔗
🔗
🔗
🔗
PrevTopNext