Solution Manual of "Elementary Linear Algebra": 1. Linear Equations

This document is the solution manual of “Elementary Linear Algebra” which was written by K. R. Matthews, University of Queensland.
The printable PDF format lecture can be Downloaded Here

Summary

• Row-echelon form
A matrix is in row-echelon form if
• all zero rows (if any) are at the bottom of the matrix and
• if two successive rows are non-zero, the second row starts with more zeros than the first (moving from left to right).
• Example 1 (row-echelon form)
  $$\begin{bmatrix}0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$
• Example 2 (not row-echelon form)
  $$\begin{bmatrix}0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$

Reduced row-echelon form
A matrix is in reduced row-echelon form if

• it is in row-echelon form,
• the leading (leftmost non-zero) entry in each non-zero row is 1,
• all other elements of the column in which the leading entry 1 occurs are zeros.
• Example 1 (reduced row-echelon form)
  $$\begin{bmatrix}1 & 0\\ 0 & 1 \end{bmatrix}$$
• Example 2 (reduced row-echelon form)
  $$\begin{bmatrix}0 & 1 & 2 & 0 & 0 & 2\\ 0 & 0 & 0 & 1 & 0 & 3\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}$$
• Example 3 (not reduced row-echelon form)
  $$\begin{bmatrix}1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 2 \end{bmatrix}$$
• Example 4 (not reduced row-echelon form)
  $$\begin{bmatrix}1 & 2 & 0\\ 0 & 1 & 0\\ 0 & 0 & 0 \end{bmatrix}$$

Elementary row operations
These types of elementary row operations can be performed on matrices:

• Interchanging two rows: $R_i\leftrightarrow R_j$ interchanges rows $i$ and $j$.
• Multiplying a row by a non-zero scalar: $R_i\rightarrow tR_j$ multiplies row $i$ by the non-zero scalar $t$.
• Adding a multiple of one row to another row: $R_j\rightarrow R_j+tR_i$ adds $t$ times row $i$ to row $j$.

Row equivalence
Matrix $A$ is row-equivalence to matrix $B$ if $B$ is obtained from $A$ by a sequence of elementary row operations.

The Gauss-Jordan algorithm
The Gauss-Jordan algorithm is a process which starts with a given matrix $A$ and produces a matrix $B$ in reduced row-echelon form, which is row-equivalent to $A$.
If $A$ is the augmented matrix of a system of linear equations, then $B$ will be a much simpler matrix than $A$ from which the consistency or inconsistency of the corresponding system is immediately apparent and in fact the complete solution of the system can be read off.

Field
A field $F$ is a set $F$ which possesses operations of addition and multiplication which satisfy the familiar rules of rational arithmetic.\\ There are ten basic properties that a field must have:

• $(a+b)+c=a+(b+c)$ for all $a$, $b$, $c$ in $F$;
• $(ab)c=a(bc)$ for all $a$, $b$, $c$ in $F$;
• $a+b=b+a$ for all $a$, $b$ in $F$;
• $ab=ba$ for all $a$, $b$ in $F$;
• there exists an element 0 in $F$ such that $0+a=a$ for all $a$ in $F$;
• there exists an element 1 in $F$ such that $1a=a$ for all $a$ in $F$;
• to every $a$ in $F$, there corresponds an additive inverse $-a$ in $F$, satisfying $$a+(-a)=0;$$
• to every non-zero $a$ in $F$, there corresponds a multiplication inverse $a^{-1}$ in $F$, satisfying $$aa^{-1}=1;$$
• $a(b+c)=ab+ac$ for all $a$, $b$, $c$ in $F$;
• $0\neq1$

$\mathbb{Z}_p$ Field

• $\mathbb{Z}_p$ field contains exactly $p$ elements, where $p$ is a prime number. That is, $\mathbb{Z}_p=\left\{0, 1, \cdots, p-1\right\}$.
• Note that $\mathbb{Z}_p$ forms a field under the operations of modular addition and multiplication mod $p$.
• For instance, the simplest $\mathbb{Z}_2$ field consists of two elements 0 and 1, and we have $1+1=0\Rightarrow 1=-1$.

Problems 1.6 1. Which of the following matrices of rationals is in reduced row-echelon form? (a) $\begin{bmatrix}1 & 0 & 0 & 0 & -3\\ 0 & 0 & 1 & 0 & 4\\ 0 & 0 & 0 & 1 & 2 \end{bmatrix}$ (b) $\begin{bmatrix}0& 1& 0& 0& 5\\ 0& 0& 1& 0& -4\\ 0& 0& 0& -1& 3 \end{bmatrix}$ (c) $\begin{bmatrix}0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& -2 \end{bmatrix}$ (d) $\begin{bmatrix}0& 1& 0& 0& 2\\ 0& 0& 0& 0& -1\\ 0& 0& 0& 1& 4\\ 0& 0& 0& 0& 0 \end{bmatrix}$ (e) $\begin{bmatrix}1& 2& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0 \end{bmatrix}$ (f) $\begin{bmatrix}0& 0& 0& 0\\ 0& 0& 1& 2\\ 0& 0& 0& 1\\ 0& 0& 0& 0 \end{bmatrix}$ (g) $\begin{bmatrix}1& 0& 0& 0& 1\\ 0& 1& 0& 0& 2\\ 0& 0& 0& 1& -1\\ 0& 0& 0& 0& 0 \end{bmatrix}$ Solution: (a), (e), (g) are correct. For (b), $a_{34}=-1$ is wrong; for (c), $a_{32}=1$ is wrong; for (d), $a_{25}=-1$ is wrong; for (f), $a_{24}=2$ is wrong. 2. Find reduced row-echelon forms which are row-equivalent to the following matrices: (a) $\begin{bmatrix}0& 0& 0 \\ 2& 4& 0 \end{bmatrix}$ (b) $\begin{bmatrix}0& 1& 3\\ 1& 2& 4 \end{bmatrix}$ (c) $\begin{bmatrix}1& 1& 1\\ 1& 1& 0\\ 1& 0& 0 \end{bmatrix}$ (d) $\begin{bmatrix}2& 0& 0\\ 0& 0& 0\\ -4& 0& 0 \end{bmatrix}$ Solution: (a) $$\begin{bmatrix}0& 0& 0 \\ 2& 4& 0 \end{bmatrix}\Leftrightarrow R_1\leftrightarrow R_2 \begin{bmatrix}2& 4& 0\\ 0& 0& 0 \end{bmatrix}\Leftrightarrow R_1\rightarrow{1\over2}R_1 \begin{bmatrix}1& 2& 0\\ 0& 0& 0 \end{bmatrix}$$ (b) $$\begin{bmatrix}0& 1& 3\\ 1& 2& 4 \end{bmatrix}\Leftrightarrow R_1\leftrightarrow R_2 \begin{bmatrix}1& 2& 4\\ 0& 1& 3 \end{bmatrix}\Leftrightarrow R_1\rightarrow R_1-2R_2 \begin{bmatrix}1& 0& -2\\ 0& 1& 3 \end{bmatrix}$$ (c) $$\begin{bmatrix}1& 1& 1\\ 1& 1& 0\\ 1& 0& 0 \end{bmatrix} \Leftrightarrow\begin{cases}R_2\rightarrow R_2-R_1\\ R_3\rightarrow R_3-R_1\end{cases}\begin{bmatrix}1& 1& 1\\ 0& 0& -1\\ 0& -1& -1 \end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow R_1+R_3\\ R_3\rightarrow R_3-R_2 \end{cases}\begin{bmatrix}1& 0& 0\\ 0& 0& -1\\ 0& -1& 0 \end{bmatrix} \Leftrightarrow\begin{cases}R_2\leftrightarrow R_3\\ R_2\rightarrow -R_2\\ R_3\rightarrow-R_3\end{cases}\begin{bmatrix}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1 \end{bmatrix}$$ (d) $$\begin{bmatrix}2& 0& 0\\ 0& 0& 0\\ -4& 0& 0 \end{bmatrix}\Leftrightarrow\begin{cases}R_3\rightarrow R_3+R_1\\ R_1\rightarrow{1\over2}R_1\end{cases}\begin{bmatrix}1& 0& 0\\ 0& 0& 0\\ 0& 0& 0 \end{bmatrix}$$ 3. Solve the following systems of linear equations by reducing the augmented matrix to reduced row-echelon form: (a) $\begin{cases} x+y+z=2\\ 2x+3y-z=8\\x-y-z=-8\end{cases}$ (b) $\begin{cases}x_1+x_2-x_3+2x_4=10\\ 3x_1-x_2+7x_3+4x_4=1\\-5x_1+3x_2-15x_3-6x_4=9\end{cases}$ (c) $\begin{cases}3x-y+7z=0\\ 2x-y+4z={1\over2}\\ x-y+z=1\\ 6x-4y+10z=3 \end{cases}$ (d) $\begin{cases}2x_2+3x_3-4x_4=1\\ 2x_3+3x_4=4\\ 2x_1+2x_2-5x_3+2x_4=4\\2x_1-6x_3+9x_4=7 \end{cases}$ Solution: (a) The augmented matrix is $$A=\begin{bmatrix}1& 1& 1& 2\\ 2& 3& -1& 8\\ 1& -1& -1& -8\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_2\rightarrow R_2-2R_1\\ R_3\rightarrow R_3-R_1\end{cases} \begin{bmatrix}1& 1& 1& 2\\ 0& 1& -3& 4\\ 0& -2& -2& -10\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow R_1-R_2\\ R_3\rightarrow R_3+2R_2\end{cases} \begin{bmatrix}1& 0& 4& -2\\ 0& 1& -3& 4\\ 0& 0& -8& -2\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow R_1+{1\over2}R_3\\ R_2\rightarrow R_2-{3\over8}R_3\\ R_3\rightarrow-{1\over8}R_3\end{cases}\begin{bmatrix}1& 0& 0& -3\\ 0& 1& 0& {19\over4}\\ 0& 0& 1& {1\over4}\end{bmatrix}=B$$ Matrix $B$ is an equivalent reduced row-echelon form of $A$. We can read off the solution: $$\begin{cases}x=-3\\ y={19\over4}\\ z={1\over4}\end{cases}$$ (b) The augmented matrix is $$A=\begin{bmatrix}1& 1& -1& 2& 10\\ 3& -1& 7& 4& 1\\ -5& 3& -15& -6& 9 \end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_2\rightarrow R_2-3R_1\\ R_3\rightarrow R_3+5R_1\end{cases} \begin{bmatrix}1& 1& -1& 2& 10\\ 0& -4& 10& -2& -29\\ 0& 8& -20& 4& 59 \end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow R_1+{1\over4}R_2\\ R_3\rightarrow R_3+2R_2\end{cases} \begin{bmatrix}1& 0& {3\over2}& {3\over2}& {11\over4}\\ 0& -4& 10& -2& -29\\ 0& 0& 0& 0& 1 \end{bmatrix}$$ From the last matrix we see that the original system is inconsistent. (c) The augmented matrix is $$A=\begin{bmatrix}3& -1& 7& 0\\ 2& -1& 4& {1\over2}\\ 1& -1& 1& 1\\ 6& -4& 10& 3\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow R_1-3R_3\\ R_2\rightarrow R_2-2R_3\\ R_4\rightarrow R_4-6R_3\end{cases} \begin{bmatrix}0& 2& 4& -3\\ 0& 1& 2& -{3\over2}\\ 1& -1& 1& 1\\ 0& 2& 4& -3\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow R_1-2R_2\\ R_3\rightarrow R_3+R_2\\ R_4\rightarrow R_4-2R_2\end{cases} \begin{bmatrix}0& 0& 0& 0\\ 0& 1& 2& -{3\over2}\\ 1& 0& 3& -{1\over2}\\ 0& 0& 0& 0\end{bmatrix}$$ $$\Leftrightarrow R_1\leftrightarrow R_3\, \begin{bmatrix}1& 0& 3& -{1\over2}\\0& 1& 2& -{3\over2}\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{bmatrix}=B$$ Matrix $B$ is an equivalent reduced row-echelon form of $A$. We can read off the solution: $$\begin{cases}x=-{1\over2}-3z\\ y=-{3\over2}-2z\end{cases} \mbox{with arbitrary}\, z.$$ (d) The augmented matrix is $$A=\begin{bmatrix}0& 2& 3& -4& 1\\ 0& 0& 2& 3& 4\\ 2& 2& -5& 2& 4\\ 2& 0& -6& 9& 7\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_4\rightarrow R_4-R_3\\ R_1\leftrightarrow R_3\end{cases} \begin{bmatrix}2& 2& -5& 2& 4\\ 0& 0& 2& 3& 4\\ 0& 2& 3& -4& 1\\ 0& -2& -1& 7& 3\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow R_1-R_3\\ R_4\rightarrow R_4+R_3\end{cases} \begin{bmatrix}2& 0& -8& 6& 3\\ 0& 0& 2& 3& 4\\ 0& 2& 3& -4& 1\\ 0& 0& 2& 3& 4\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow R_1+4R_2\\ R_3\rightarrow R_3-{3\over2}R_2\\ R_4\rightarrow R_4-R_2\end{cases} \begin{bmatrix}2& 0& 0& 18& 19\\ 0& 0& 2& 3& 4\\ 0& 2& 0& -{17\over2}& -5\\ 0& 0& 0& 0& 0\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow{1\over2}R_1\\ R_2\rightarrow{1\over2}R_2\\ R_3\rightarrow{1\over2}R_3\\ R_2\leftrightarrow R_3\end{cases} \begin{bmatrix}1& 0& 0& 9& {19\over2}\\ 0& 1& 0& -{17\over4}& -{5\over2}\\0& 0& 1& {3\over2}& 2\\ 0& 0& 0& 0& 0\end{bmatrix}=B$$ Matrix $B$ is an equivalent reduced row-echelon form of $A$. We can read off the solution: $$\begin{cases}x_1={19\over2}-9x_4\\ x_2=-{5\over2}+{17\over4}x_4\\ x_3=2-{3\over2}x_4\end{cases} \mbox{with arbitrary}\, x_4.$$ 4. Show that the following system is consistent if and only if $c=2a-3b$ and solve the system in this case. $$\begin{cases}2x-y+3z=a\\ 3x+y-5z=b\\ -5x-5y+21z=c \end{cases}$$ Solution: The augmented matrix is $$A=\begin{bmatrix}2& -1& 3& a\\ 3& 1& -5& b\\ -5& -5& 21& c\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_2\rightarrow R_2-{3\over2}R_1\\ R_3\rightarrow R_3+{5\over2}R_1 \end{cases} \begin{bmatrix}2& -1& 3& a\\ 0& {5\over2}& -{19\over2}& b-{3\over2}a\\ 0& -{15\over2}& {57\over2}& c+{5\over2}a\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow R_1+{2\over5}R_2\\ R_3\rightarrow R_3+3R_2\end{cases}\begin{bmatrix}2& 0& -{4\over5}& {2\over5}(a+b)\\ 0& {5\over2}& -{19\over2}& b-{3\over2}a\\ 0& 0& 0 & -2a+3b+c\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow{1\over2}R_1\\ R_2\rightarrow{2\over5}R_2\end{cases}\begin{bmatrix}1& 0& -{2\over5}& {1\over5}(a+b)\\ 0& 1 & -{19\over5}& {2\over5}b-{3\over5}a\\ 0& 0& 0 & -2a+3b+c\end{bmatrix}$$ From the last matrix we see that the original system is consistent if and only if $-2a+3b+c=0\Rightarrow c=2a-3b$. And the solution is $$\begin{cases}x={a+b\over5}+{2\over5}z\\ y={-3a+2b\over5}+{19\over5}z \end{cases}\mbox{with arbitrary}\, z.$$ 5. Find the value of $t$ for which the following system is consistent and solve the system for this value of $t$. $$\begin{cases}x+y=1\\ tx+y=t\\ (1+t)x+2y=3 \end{cases}$$ Solution: The augmented matrix is $$A=\begin{bmatrix}1& 1& 1\\ t& 1& t\\ 1+t& 2& 3\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_2\rightarrow R_2-tR_1\\ R_3\rightarrow R_3-(1+t)R_1 \end{cases}\begin{bmatrix}1& 1& 1\\ 0& 1-t& 0\\ 0& 1-t& 2-t\end{bmatrix}$$ $$\Leftrightarrow R_2\rightarrow{1\over1-t}R_2(t\neq1)\,\begin{bmatrix}1& 1& 1\\ 0& 1& 0\\ 0& 1-t& 2-t\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow R_1-R_2\\ R_3\rightarrow R_3-(1-t)R_2\end{cases}\begin{bmatrix}1& 0& 1\\ 0& 1& 0\\ 0& 0& 2-t\end{bmatrix}$$ From the last matrix we see that the original system is consistent if and only if $2-t=0\Rightarrow t=2$ and the solution is $$\begin{cases}x=1\\ y=0 \end{cases}$$ 6. Solve the homogeneous system $$\begin{cases}-3x_1+x_2+x_3+x_4=0\\ x_1-3x_2+x_3+x_4=0\\x_1+x_2-3x_3+x_4=0\\x_1+x_2+x_3-3x_4=0 \end{cases}$$ Solution: The coefficient matrix is $$A=\begin{bmatrix}-3& 1& 1& 1\\ 1& -3& 1& 1\\ 1& 1& -3& 1\\ 1& 1& 1& -3 \end{bmatrix}$$ $$\Leftrightarrow \begin{cases}R_1\rightarrow R_1-R_4\\ R_2\rightarrow R_2-R_4\\ R_3\rightarrow R_3-R_4\end{cases}\begin{bmatrix}-4& 0& 0& 4\\ 0& -4& 0& 4\\ 0& 0& -4& 4\\ 1& 1& 1& -3 \end{bmatrix}$$ $$\Leftrightarrow \begin{cases}R_1\rightarrow-{1\over4}R_1\\ R_2\rightarrow-{1\over4}R_2\\ R_3\rightarrow-{1\over4}R_3 \end{cases}\begin{bmatrix}1& 0& 0& -1\\ 0& 1& 0& -1\\ 0& 0& 1& -1\\ 1& 1& 1& -3 \end{bmatrix}$$ $$\Leftrightarrow R_4\rightarrow R_4-R_1-R_2-R_3\, \begin{bmatrix}1& 0& 0& -1\\ 0& 1& 0& -1\\ 0& 0& 1& -1\\ 0& 0& 0& 0 \end{bmatrix}$$ The solution is $$\begin{cases}x_1=x_4\\x_2=x_4\\x_3=x_4\end{cases}\Rightarrow x_1=x_2=x_3=x_4,\, \mbox{with arbitrary}\, x_4.$$ 7. For which rational numbers $\lambda$ does the homogeneous system $$\begin{cases}x+(\lambda-3)y=0\\ (\lambda-3)x+y=0 \end{cases}$$ have a non-trivial solution? Solution: The coefficient matrix is $$A=\begin{bmatrix}1& \lambda-3\\ \lambda-3& 1\end{bmatrix}$$ $$\Leftrightarrow R_2\rightarrow R_2-(\lambda-3)R_1\, \begin{bmatrix}1& \lambda-3\\ 0& -{\lambda}^2+6\lambda-8\end{bmatrix}=\begin{bmatrix}1& \lambda-3\\ 0& -(\lambda-2)(\lambda-4)\end{bmatrix}$$

• $\lambda=2\Rightarrow\begin{bmatrix}1& -1\\ 0& 0\end{bmatrix}\Rightarrow x=y$, with arbitrary $y$.
• $\lambda=4\Rightarrow\begin{bmatrix}1& 1\\ 0& 0\end{bmatrix}\Rightarrow x=-y$, with arbitrary $y$.
• $\lambda\neq2,\, 4\Rightarrow x=y=0$ which is the trial solution.

8. Solve the homogeneous system $$\begin{cases}3x_1+x_2+x_3+x_4=0\\ 5x_1-x_2+x_3-x_4=0 \end{cases}$$ Solution: The coefficient matrix is $$A=\begin{bmatrix}3& 1& 1& 1\\ 5& -1& 1& -1 \end{bmatrix}$$ $$\Leftrightarrow R_2\rightarrow R_2-{5\over3}R_1\, \begin{bmatrix}3& 1& 1& 1\\ 0& -{8\over3}& -{2\over3}& -{8\over3} \end{bmatrix}$$ $$\Leftrightarrow\begin{cases} R_1\rightarrow R_1+{3\over8}R_2\\ R_2\rightarrow-{3\over8}R_2\end{cases} \begin{bmatrix}3& 0& {3\over4}& 0\\ 0& 1& {1\over4}& 1 \end{bmatrix}$$ $$\Leftrightarrow R_1\rightarrow {1\over3}R_1\, \begin{bmatrix}1& 0& {1\over4}& 0\\ 0& 1& {1\over4}& 1 \end{bmatrix}$$ Hence the solution of the given homogeneous system is $$\begin{cases}x_1=-{1\over4}x_3\\x_2=-{1\over4}x_3-x_4 \end{cases}\, \mbox{with arbitrary}\, x_3,\, x_4.$$ 9. Let $A$ be the coefficient matrix of the following homogeneous system of $n$ equations in $n$ unknowns: $$\begin{cases}(1-n)x_1+x_2+\cdots+x_n=0\\ x_1+(1-n)x_2+\cdots+x_n=0\\\cdots\cdots\\x_1+x_2+\cdots+(1-n)x_n=0 \end{cases}$$ Find the reduced row-echelon form of $A$ and hence, or otherwise prove that the solution of the above system is $x_1=x_2=\cdots=x_n$, with $x_n$ arbitrary. Solution: The coefficient matrix is $$A=\begin{bmatrix}1-n& 1&\cdots&1\\ 1& 1-n& \cdots& 1\\ \cdots&\cdots&\cdots&\cdots\\ 1& 1& \cdots& 1-n \end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow R_1-R_n\\ R_2\rightarrow R_2-R_n\\\cdots\\R_{n-1}\rightarrow R_{n-1}-R_n \end{cases}\begin{bmatrix}-n& 0&\cdots&n\\ 0& -n& \cdots& n\\ \cdots&\cdots&\cdots&\cdots\\ 1& 1& \cdots& 1-n \end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow -{1\over n}R_1\\ R_2\rightarrow -{1\over n}R_2\\\cdots\\R_{n-1}\rightarrow -{1\over n}R_{n-1}\end{cases}\begin{bmatrix}1& 0&\cdots&-1\\ 0& 1& \cdots& -1\\ \cdots&\cdots&\cdots&\cdots\\ 1& 1& \cdots& 1-n \end{bmatrix}$$ $$\Leftrightarrow R_n\rightarrow R_n-R_1-R_2\cdots-R_{n-1} \begin{bmatrix}1& 0&\cdots&-1\\ 0& 1& \cdots& -1\\ \cdots&\cdots&\cdots&\cdots\\ 0& 0& \cdots& 0 \end{bmatrix}=B$$ Matrix $B$ is the reduced row-echelon form of $A$. And the solution is $$\begin{cases}x_1=x_n\\ x_2=x_n\\ \cdots\\ x_{n-1}=x_n \end{cases}\Rightarrow x_1=x_2=\cdots=x_{n-1}=x_n,\ \mbox{with arbitrary}\, x_n.$$ 10. Let $A=\begin{bmatrix}a& b\\ c& d\end{bmatrix}$ be a matrix over a field $F$. Prove that $A$ is row-equivalent to $\begin{bmatrix}1 & 0\\ 0 & 1 \end{bmatrix}$ if $ad-bc\neq0$, but is row-equivalent to a matrix whose second row is zero, if $ad-bc=0$. Solution: Assume that $ad-bc\neq0$, then

• $a\neq0$ $$A=\begin{bmatrix}a& b\\ c& d\end{bmatrix}\Leftrightarrow R_2\rightarrow R_2-{c\over a}R_1\, \begin{bmatrix}a& b\\ 0& {ad-bc\over a}\end{bmatrix}(\ast)$$ $$\Leftrightarrow R_1\rightarrow R_1-{ab\over ad-bc}R_2\, \begin{bmatrix}a& 0\\ 0& {ad-bc\over a}\end{bmatrix}\Leftrightarrow\begin{cases}R_1\rightarrow{1\over a}R_1\\ R_2\rightarrow{a\over ad-bc}R_2\end{cases}\begin{bmatrix}1& 0\\ 0& 1\end{bmatrix}$$
• $a=0\Rightarrow c\neq0$, otherwise $ad-bc=0$. Similar to the above case, we can obtain the same row-equivalent matrix $\begin{bmatrix}1& 0\\ 0& 1\end{bmatrix}$.

On the other hand, if $ad-bc=0$, according to $(\ast)$ matrix, we can see that the second row is zero. 11. For which rational numbers $a$ does the following system have (1) no solutions (2) exactly one solution (3) infinitely many solutions? $$\begin{cases}x+2y-3z=4\\ 3x-y+5z=2\\ 4x+y+(a^2-14)z=a+2 \end{cases}$$ Solution: The augmented matrix is $$A=\begin{bmatrix}1& 2& -3& 4\\3& -1& 5& 2\\4& 1& a^2-14& a+2 \end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_2\rightarrow R_2-3R_1\\ R_3\rightarrow R_3-4R_1\end{cases}\begin{bmatrix}1& 2& -3& 4\\0& -7& 14& -10\\0& -7& a^2-2& a-14 \end{bmatrix}$$ $$\Leftrightarrow\begin{cases} R_3\rightarrow R_3-R_2\\ R_2\rightarrow -{1\over7}R_2\end{cases}\begin{bmatrix}1& 2& -3& 4\\0& 1& -2& {10\over7}\\0& 0& a^2-16& a-4 \end{bmatrix}$$ $$\Leftrightarrow R_1\rightarrow R_1-2R_2\begin{bmatrix}1& 0& 1& {8\over7}\\0& 1& -2& {10\over7}\\0& 0& a^2-16& a-4 \end{bmatrix}=B$$ From the last matrix $B$, we have

• $a^2-16\neq0\Rightarrow a\neq\pm4$ $$B=\begin{bmatrix}1& 0& 1& {8\over7}\\0& 1& -2& {10\over7}\\0& 0& a^2-16& a-4 \end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow R_1-{1\over a^2-16}R_3\\ R_2\rightarrow R_2+{2\over a^2-16}R_3\\R_3\rightarrow {1\over a^2-16}R_3\end{cases}\begin{bmatrix}1& 0& 0& {8a+25\over 7(a+4)}\\0& 1&0 & {10a+54\over 7(a+4)}\\0& 0& 1& {1\over a+4} \end{bmatrix}$$ $$\Rightarrow\begin{cases}x={8a+25\over 7(a+4)}\\ y={10a+54\over 7(a+4)}\\ z={1\over a+4}\end{cases}$$ which has exactly one solution.
• $a=4$ $$B=\begin{bmatrix}1& 0& 1& {8\over7}\\0& 1& -2& {10\over7}\\0& 0& a^2-16& a-4 \end{bmatrix}=\begin{bmatrix}1& 0& 1& {8\over7}\\0& 1& -2& {10\over7}\\0& 0& 0& 0 \end{bmatrix}$$ $$\Rightarrow \begin{cases}x={8\over7}-z\\ y={10\over7}+2z \end{cases}\, \mbox{with arbitrary}\, z.$$ which has infinitely many solutions.
• $a=-4$ $$B=\begin{bmatrix}1& 0& 1& {8\over7}\\0& 1& -2& {10\over7}\\0& 0& a^2-16& a-4 \end{bmatrix}=\begin{bmatrix}1& 0& 1& {8\over7}\\0& 1& -2& {10\over7}\\0& 0& 0& -8 \end{bmatrix}$$ The last matrix shows that the system is inconsistent, which means no solution.

12. Solve the following system of homogeneous equations over $\mathbb{Z}_2$: $$\begin{cases}x_1+x_3+x_5=0\\ x_2+x_4+x_5=0\\ x_1+x_2+x_3+x_4=0\\ x_3+x_4=0 \end{cases}$$ Solution: Note that $\mathbb{Z}_2$ consists of two elements 0 and 1. The coefficient matrix is $$A=\begin{bmatrix}1& 0& 1& 0& 1\\0& 1& 0& 1& 1\\ 1& 1& 1& 1& 0\\ 0& 0& 1& 1& 0 \end{bmatrix}$$ $$\Leftrightarrow R_3\rightarrow R_3-R_1\begin{bmatrix}1& 0& 1& 0& 1\\0& 1& 0& 1& 1\\ 0& 1& 0& 1& -1\\ 0& 0& 1& 1& 0 \end{bmatrix}=\begin{bmatrix}1& 0& 1& 0& 1\\0& 1& 0& 1& 1\\ 0& 1& 0& 1& 1\\ 0& 0& 1& 1& 0 \end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow R_1-R_4\\ R_3\rightarrow R_3-R_2\end{cases}\begin{bmatrix}1& 0& 0& -1& 1\\0& 1& 0& 1& 1\\ 0& 0& 0& 0& 0\\ 0& 0& 1& 1& 0 \end{bmatrix} = \begin{bmatrix}1& 0& 0& 1& 1\\0& 1& 0& 1& 1\\ 0& 0& 0& 0& 0\\ 0& 0& 1& 1& 0 \end{bmatrix}$$ $$\Leftrightarrow R_3\leftrightarrow R_4 \begin{bmatrix}1& 0& 0& 1& 1\\0& 1& 0& 1& 1\\0& 0& 1& 1& 0\\ 0& 0& 0& 0& 0 \end{bmatrix}=B$$ Matrix $B$ is the reduced row-echelon form of $A$. And the solution is $$\begin{cases}x_1=-x_4-x_5=x_4+x_5\\ x_2=-x_4-x_5=x_4+x_5\\x_3=-x_4=x_4 \end{cases}$$ where $x_4,\, x_5$ are arbitrary elements of $\mathbb{Z}_2$. 13. Solve the following systems of linear equations over $\mathbb{Z}_5$: (a) $\begin{cases}2x+y+3z=4\\ 4x+y+4z=1\\ 3x+y+2z=0 \end{cases}$ (b) $\begin{cases}2x+y+3z=4\\ 4x+y+4z=1\\ x+y=3 \end{cases}$ Solution: $\mathbb{Z}_5$ consists of 5 elements $\left\{0, 1, 2, 3, 4\right\}$. (a) The augmented matrix is $$A=\begin{bmatrix}2& 1& 3& 4\\ 4& 1& 4& 1\\ 3& 1& 2& 0\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_2\rightarrow R_2-2R_1\\ R_3\rightarrow 2R_3-3R_1 \end{cases}\begin{bmatrix}2& 1& 3& 4\\ 0& -1& -2& -7\\ 0& -1 & -5 & -12\end{bmatrix}=\begin{bmatrix}2& 1& 3& 4\\ 0& 4& 3& 3\\ 0& 4 & 0 & 3\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow 4R_1-R_2\\ R_3\rightarrow R_3-R_2\end{cases}\begin{bmatrix}8& 0& 9& 13\\ 0& 4& 3& 3\\ 0& 0& -3& 0\end{bmatrix}=\begin{bmatrix}2& 0& 1& 2\\ 0& 4& 3& 3\\ 0& 0& 2& 0\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow 2R_1-R_3\\ R_2\rightarrow 2R_2-3R_3\end{cases}\begin{bmatrix}4& 0& 0& 4\\ 0& 8& 0& 6\\ 0& 0& 2& 0\end{bmatrix}=\begin{bmatrix}4& 0& 0& 4\\ 0& 2& 0& 4\\ 0& 0& 2& 0\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow {1\over4}R_1\\ R_2\rightarrow {1\over2}R_2\\ R_3\rightarrow {1\over2}R_3\end{cases}\begin{bmatrix}1& 0& 0& 1\\ 0& 1& 0& 2\\ 0& 0& 1& 0\end{bmatrix}=B$$ Matrix $B$ is the reduced row-echelon form of $A$ over the field $\mathbb{Z}_5$. And the solution is $$\begin{cases}x=1\\ y=2\\ z=0 \end{cases}$$ (b) The augmented matrix is $$A=\begin{bmatrix}2& 1& 3& 4\\ 4& 1& 4& 1\\ 1& 1& 0& 3\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow R_1-2R_3\\ R_2\rightarrow R_2-4R_3\end{cases}\begin{bmatrix}0& -1& 3& -2\\ 0& -3& 4& -11\\ 1& 1& 0& 3\end{bmatrix}=\begin{bmatrix}0& 4& 3& 3\\ 0& 2& 4& 4\\ 1& 1& 0& 3\end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow R_1-2R_2\\ R_3\rightarrow 2R_3-R_2 \end{cases}\begin{bmatrix}0& 0& -5& -5\\ 0& 2& 4& 4\\ 2& 0& -4& 2\end{bmatrix}=\begin{bmatrix}0& 0& 0& 0\\ 0& 2& 4& 4\\ 2& 0& 1& 2\end{bmatrix}$$ $$\Leftrightarrow R_1\leftrightarrow R_3\begin{bmatrix}2& 0& 1& 2\\ 0& 2& 4& 4\\ 0& 0& 0& 0 \end{bmatrix}=\begin{bmatrix}2& 0& -4& 2\\ 0& 2& -6& 4\\ 0& 0& 0& 0 \end{bmatrix}$$ $$\Leftrightarrow \begin{cases} R_1\rightarrow{1\over2}R_1\\ R_2\rightarrow{1\over2}R_2\end{cases}\begin{bmatrix}1& 0& -2& 1\\ 0& 1& -3& 2\\ 0& 0& 0& 0 \end{bmatrix}=B$$ Matrix $B$ is the reduced row-echelon form of $A$ over the field $\mathbb{Z}_5$. And the solution is $$\begin{cases}x=1+2z\\ y=2+3z \end{cases}$$ where $z$ is an arbitrary elements of $\mathbb{Z}_5$. 14. If $(\alpha_1, \cdots, \alpha_n)$ and $(\beta_1, \cdots, \beta_n)$ are solutions of a system of linear equations, prove that $$((1-t)\alpha_1+t\beta_1, \cdots, (1-t)\alpha_n+t\beta_n)$$ is also a solution. Solution: Suppose that $(\alpha_1, \cdots, \alpha_n)$ and $(\beta_1, \cdots, \beta_n)$ are solutions of a system linear equations $$\sum_{j=1}^{n}a_{ij}\cdot x_{j}=b_i,\, 1\leq i \leq n$$ That is, $$\sum_{j=1}^{n}a_{ij}\cdot \alpha_j=b_i$$ and $$\sum_{j=1}^{n}a_{ij}\cdot \beta_j=b_i$$ Let $\gamma_j=(1-t)\alpha_j+t\beta_j$, for $1\leq j \leq n$. Thus, we have $$\sum_{j=1}^{n}a_{ij}\cdot \gamma_j=\sum_{j=1}^{n}a_{ij}\cdot((1-t)\alpha_j+t\beta_j)$$ $$=\sum_{j=1}^{n}a_{ij}\cdot(1-t)\alpha_j+\sum_{j=1}^{n} a_{ij}\cdot t\beta_j$$ $$=(1-t)\sum_{j=1}^{n}a_{ij}\cdot \alpha_j+t\sum_{j=1}^{n}a_{ij}\cdot \beta_j$$ $$=(1-t)b_{i}+t b_{i}=b_i$$ 15. If $(\alpha_1, \cdots, \alpha_n)$ is a solution of a system of linear equations, prove that the complete solution is given by $x_1=\alpha_1+y_1, \cdots, x_n=\alpha_n+y_n$, where $(y_1, \cdots, y_n)$ is the general solution of the associated homogeneous system. Solution: Suppose that $(\alpha_1, \cdots, \alpha_n)$ is a solutions of a system linear equations $$\sum_{j=1}^{n}a_{ij}\cdot x_{j}=b_i,\, 1\leq i \leq n$$ That is, $$\sum_{j=1}^{n}a_{ij}\cdot x_{j} = \sum_{j=1}^{n}a_{ij}\cdot \alpha_j =b_i$$ $$\Rightarrow \sum_{j=1}^{n}a_{ij}\cdot(x_j-\alpha_j)=0$$ which can be seen as the associated homogeneous system of the original linear equations. Let $y_j=x_j-\alpha_j$, for $1\leq j \leq n$, where $(y_1, \cdots, y_n)$ is the general solution of the homogeneous system. Hence, we have $x_1=\alpha_1+y_1,\cdots, x_n=\alpha_n+y_n$. 16. Find the values of $a$ and $b$ for which the following system is consistent. Also find the complete solution when $a = b = 2$. $$\begin{cases}x+y-z+w=1\\ ax+y+z+w=b\\3x+2y+aw=1+a \end{cases}$$ Solution: The augmented matrix is $$\begin{bmatrix}1& 1& -1& 1& 1\\ a& 1& 1& 1& b\\ 3& 2&0& a& 1+a \end{bmatrix}$$ $$\Leftrightarrow \begin{cases}R_2\rightarrow R_2-aR_1\\R_3\rightarrow R_3-3R_1 \end{cases}\begin{bmatrix}1& 1& -1& 1& 1\\ 0& 1-a& 1+a& 1-a& b-a\\ 0& -1&3& a-3& a-2 \end{bmatrix}$$ $$\Leftrightarrow \begin{cases}R_1\rightarrow R_1+R_3\\R_2\rightarrow R_2+(1-a)R_3 \end{cases}\begin{bmatrix}1& 0& 2& a-2& a-1\\ 0& 0& 4-2a& -a^2+3a-2& -a^2+2a+b-2\\ 0& -1&3& a-3& a-2 \end{bmatrix}=B$$

• If $a=2$ $$B=\begin{bmatrix}1& 0& 2& 0& 1\\ 0& 0& 0&0&b-2\\ 0& -1&3&-1& 0 \end{bmatrix}$$
• If $b\neq0$, it is inconsistent.
• If $b=2$ $$B=\begin{bmatrix}1& 0& 2& 0& 1\\ 0& 0& 0&0&0\\ 0& -1&3&-1& 0 \end{bmatrix}$$ $$\Leftrightarrow\begin{cases} R_2\rightarrow -R_2\\ R_2\leftrightarrow R_3\end{cases}\begin{bmatrix}1& 0& 2& 0& 1\\0& 1&-3&1& 0 \\ 0& 0& 0&0&0\end{bmatrix}\Rightarrow \begin{cases}x=1-2z\\ y=3z-w \end{cases}$$ with $z,\, w$ arbitrary.
• If $a\neq2$ $$B=\begin{bmatrix}1& 0& 2& a-2& a-1\\ 0& 0& 4-2a& -a^2+3a-2& -a^2+2a+b-2\\ 0& -1&3& a-3& a-2 \end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_2\leftrightarrow R_3\\ R_2\rightarrow -R_2\\ R_3\rightarrow -R_3 \end{cases}\begin{bmatrix}1& 0& 2& a-2& a-1\\0& 1&-3& 3-a& 2-a \\ 0& 0& 2(a-2)& (a-1)(a-2)& a^2-2a-b+2 \end{bmatrix}$$ $$\Leftrightarrow R_3\rightarrow{1\over2(a-2)}R_3\begin{bmatrix}1& 0& 2& a-2& a-1\\0& 1&-3& 3-a& 2-a \\ 0& 0& 1& {a-1\over2}& {a^2-2a-b+2\over2(a-2)} \end{bmatrix}$$ Thus we can solve for $x,\, y,\, z$ with arbitrary $w$.

In conclusion, when $a\neq2$ or $a=b=2$ the system is consistent. When $a=b=2$, the solution is $\begin{cases}x=1-2z\\ y=3z-w \end{cases}$ with $z,\, w$ arbitrary. 17. Let $F=\{0, 1, a, b\}$ be a field consisting of 4 elements. (a) Determine the addition and multiplication tables of $F$. (Hint: Prove that the elements $1+0$, $1+1$, $1+a$, $1+b$ are distinct and deduce that $1 + 1 + 1 + 1 = 0$; then deduce that $1 + 1 = 0$.) (b) A matrix $A$, whose elements belong to $F$, is defined by $$A=\begin{bmatrix}1& a& b& a\\ a& b& b& 1\\ 1& 1& 1& a \end{bmatrix},$$ prove that the reduced row-echelon form of $A$ is given by the matrix $$B=\begin{bmatrix}1& 0& 0& 0\\ 0& 1& 0& b\\0& 0& 1& 1 \end{bmatrix}.$$ Solution: (a) First, $1+0$, $1+1$, $1+a$, and $1+b$ are distinct, otherwise, for instance, $1+a=1+b\Rightarrow a=b$ which is inconsistent. Thus $$(1+0)+(1+1)+(1+a)+(1+b)=(1+1+1+1)+(0+1+a+b)$$ The second term on the right are the sum of four elements which is equivalent to the left. Hence we have $$1+1+1+1=0.$$ And since $(1+1)\times(1+1)=1+1+1+1=0$, so $$1+1=0.$$ Then we can deduce $a+a$ and $a+b$: $$a+a=a\cdot(1+1)=0\Rightarrow a+a=0$$ $$b+b=b\cdot(1+1)=0\Rightarrow b+b=0$$ Obviously, $a+b\neq0$, otherwise $a+b=a+a=0\Rightarrow a=b$ which is inconsistent. Similarly, $a+b\neq a$ or $b$ since it will deduce that $a=0$ or $b=0$. Hence $$a+b=1.$$ Lastly, $$a+1=a+(a+b)=(a+a)+b=0+b=b.$$ similarly, we can deduce that $$b+1=b+(a+b)=b+b+a=0+a=a.$$ Consequently, the addition table for $F$ is:

Now we will make the multiplication table for $F$. First, $$a\cdot0=0,\, a\cdot1=a, \,$$ If $a\cdot b =b$ then $a=1$ which is inconsistent. So $$a\cdot b=1.$$ Similarly, $$b\cdot0=0,\, b\cdot1=b,\, b\cdot a=1.$$ Next, $a\cdot a=1$ or $a$ or $b$ (if $a\cdot a=0$ then $a=0$). If $a^2=1\Rightarrow (a+1)\cdot(a-1)= b\cdot(a-1)=(a-1)\cdot(a-1)=0\Rightarrow a=1$, which is inconsistent. If $a^2=a\Rightarrow a\cdot(a-1)=0\Rightarrow a=0$ or $a=1$, which are both inconsistent. Thus $$a\cdot a=b$$ Similarly, $$b\cdot b=a.$$ The multiplication table for $F$ is:

(b) According to Table 1 and Table 2, we have $$A=\begin{bmatrix}1& a& b& a\\ a& b& b& 1\\ 1& 1& 1& a \end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_2\rightarrow R_2+aR_1\\ R_3\rightarrow R_3+R_1 \end{cases}\begin{bmatrix}1& a& b& a\\ 0& 0& a& a\\ 0& b& a& 0 \end{bmatrix}$$ $$\Leftrightarrow R_2\leftrightarrow R_3 \begin{bmatrix}1& a& b& a\\0& b& a& 0\\ 0& 0& a& a \end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_2\rightarrow aR_2\\ R_3\rightarrow bR_3\end{cases}\begin{bmatrix}1& a& b& a\\0& 1& b& 0\\ 0& 0& 1& 1 \end{bmatrix}$$ $$\Leftrightarrow\begin{cases}R_1\rightarrow R_1+aR_2\\ R_2\rightarrow R_2+bR_3\end{cases}\begin{bmatrix}1& 0& a& a\\0& 1& 0& b\\ 0& 0& 1& 1 \end{bmatrix}$$ $$\Leftrightarrow R_1\rightarrow R_1+aR_3 \begin{bmatrix}1& 0& 0& 0\\0& 1& 0& b\\ 0& 0& 1& 1 \end{bmatrix}=B$$ Matrix $B$ is the reduced row-echelon form of matrix $A$.