A touch of background: I'm a CS prof headed back to get a math PhD, which means I have to pass the
qualifying exams next summer, so I'm studying now. One of my texts is Algebra, by
Michael Artin.
For some reason, I am unable to solve what I would consider a pretty remedial question in chapter 3.
This says to me that I am lacking some important understanding.
Here is the question:
Consider the following system of linear equations $AX = B$:
$$
\begin{bmatrix}
6 & -3 \\\\
2 & 6
\end{bmatrix}
\begin{bmatrix}
x_1 \\\\
x_2
\end{bmatrix}
=
\begin{bmatrix}
3 \\\\
1
\end{bmatrix}
$$
- Solve the system in $\mathbb{F}_p$ when $p = 5, 11, 17$.
- Determine the number of solutions when $p = 7$.
Here is my solution:
First, as a sanity check, I'll compute the determinant, $\det A$.
I believe I can compute it in $\mathbb{Z}$ and then "take modulos"
to get the determinant modulo $p$ for the different values of $p$.
$$
\begin{align}
\det A &= 6 \cdot 6 – (-3) \cdot 2 \\\\
&= 42\\\\
&= 2 \pmod{5}\\\\
&= 0 \pmod{7}\\\\
&= 9 \pmod{11}\\\\
&= 8 \pmod{17}.
\end{align}
$$
So, the answer to part 2 is obvious — there are zero solutions. For part 1, I attempted to solve it using row reduction. Here are my steps:
\begin{align}
&
\begin{bmatrix}
6 & -3 & 3\\\\
2 & 6 & 1
\end{bmatrix}
\text{ Augmented matrix;}\\\\
&
\begin{bmatrix}
0 & -21 & 0\\\\
2 & 6 & 1
\end{bmatrix}
\text{ subtract } 3 \text{ times row } 2 \text{ from row } 1\text{;}\\\\
&
\begin{bmatrix}
0 & 1 & 0\\\\
2 & 6 & 1
\end{bmatrix}
\text{ multiply row } 1 \text{ by } -\frac{1}{21} \text{;}\\\\
&
\begin{bmatrix}
0 & 1 & 0\\\\
2 & 0 & 1
\end{bmatrix}
\text{ subtract } 6 \text{ times row } 1 \text{ from row } 2 \text{;}\\\\
&
\begin{bmatrix}
0 & 1 & 0\\\\
1 & 0 & \frac{1}{2}
\end{bmatrix}
\text{ multiply row } 2 \text{ by } \frac{1}{2}.
\end{align}
At this point, I'm ready to declare $x_1 = 0$ and $x_2 = \frac{1}{2}$. There's just
one problem. If I carry out the multiplication, I get the following equations:
\begin{align}
6 x_1 – 3 x_2 = 3 \\\\
2 x_1 + 6 x_2 = 1
\end{align}
And, as is obvious, the solution is actually the other way around:
$x_1 = \frac{1}{2}$ and $x_2 = 0$.
Where is my misunderstanding?
Best Answer
You did not bring the matrix to reduced row echelon form because row 2 has a leading 1 before row 1. You need to exchange the two rows. Then you will get the desired solution.
$$ \vdots \\ \left[\begin{array}{lll} 0 & 1 & 0 \\ 1 & 0 & \frac{1}{2} \end{array}\right] \text { multiply row } 2 \text { by } \frac{1}{2} \text {. } \\ \left[\begin{array}{lll} 1 & 0 & \frac{1}{2}\\ 0 & 1 & 0 \\ \end{array}\right] \text {Swap rows 1 and 2.} $$
So we see that $x_1=1/2$ and $x_2=0$.