11.4 Linear Equation

Equation

System of linear equation

Theorem

Let $A\in M_{m\times n}\left(\mathbb{F}\right)$ and $0\neq b\in M_{m\times n}\left(\mathbb{F}\right)$. The solution set of the homogeneous system $Ax=0$ is a subspace $W$ (We've proved)

The set of solutions of non-homogeneous system $Ax=b$ is the affine subspace $x_0+W$ of $\mathbb{F}^n$ where $x_0$ is one solution of $Ax=b$ and $x_0+W=\{x_0+w:w\in W\}$

Proof:

$x_0 + W \subseteq$ solutions: $x_0+w\in x_0+W$, $A(x_0+w)=Ax_0+Aw=b+0=b$.
solutions $\subseteq x_0 + W$

Let take any $\tilde{x}_0$ be the solution of $Ax=b$ such that $A\tilde{x}_0=b$\, N.T.P. $\tilde{x}_0\in x_0+W$

Since we know $Ax_0=b,Aw=0$, then $Ax_0+Aw=A(x_0+w)=b\Rightarrow x_0+w=\frac{A}{b}\in x_0+W$

Also since $\frac{A}{b}=\tilde{x}_0\in x_0+W$

Examples

$\{\,x+y=1\,,X_0=(1,0),\,W=\{(x,-x):x\in\mathbb{R}\}\,\}$

$\begin{cases} x + y + z = 1 \ x - y + z = -1 \end{cases} \quad \sim \quad X_0 = (0, 1, 0), \quad W = \left{ (x, 0, -x) : x \in \mathbb{R} \right} $

Equivalent systems

Let $\#$$\begin{cases} a_{11} x_1 + \dots + a_{1n} x_n = b_1 \\ \vdots \\ a_{m1} x_1 + \dots + a_{mn} x_n = b_m \end{cases}$be a system of $m$ equations in $n$ unknowns over $\mathbb{F}$ (non-homogeneous).

Operations

$\#$ can be transformed by the following three types of operations:

Type 1: multiply one equation of $\#$ by $0 \neq \lambda \in \mathbb{F}$. So that we obtain

$\#_1=\begin{cases}a_{11}x_1+\dots+a_{1n}x_{n}=b_1,\\ \vdots\\ \lambda(a_{i1}x_1+\dots+a_{in}x_{n})=\lambda b_{i},\\ \vdots\\ a_{m1}x_1+\dots+a_{mn}x_{n}=b_{m}\end{cases}$

Type 2: interchange or switch two different equations. So that, we obtain:

$\#_2=\begin{cases}a_{11}x_1+\dots+a_{1n}x_{n}=b_1,\\ \vdots\\ a_{ji}x_1+\dots+a_{jn}x_{n}=b_{j},\quad\text{equation }i\\ a_{ii}x_1+\dots+a_{in}x_{n}=b_{i},\quad\text{equation }j\\ \vdots\\ a_{m1}x_1+\dots+a_{mn}x_{n}=b_{m}\end{cases}$

Type 3: replace the $i$th equation by itself plus a multiple of equation $j$ $(j \neq i)$. So that, we obtain:

$\#_{3}= \begin{cases} a_{11}x_{1}+\dots+a_{1n}x_{n}=b_{1}, \\ \vdots \\ \left(a_{i1}x_{1}+\dots+a_{in}x_{n}\right)+\lambda\left(a_{j1}x_{1}+\dots+a_{jn}x_{n}\right)=b_{i}+\lambda b_{j},\quad\text{equation }i \\ \vdots \\ a_{m1}x_{1}+\dots+a_{mn}x_{n}=b_{m} \end{cases}$

Definition of equivalence

Two systems of the same size are equivalent, if they have the same solutions.

Remark

This is an equivalence relation.

If $\tilde{\#}$ is obtained from $\#$ by a finite number of operations of type 1-3, then $\tilde{\#}$ and $\#$ are equivalent.
Every operation of type 1-3 can be undone by an operation of the same type.

(*) In fact, all equations from $\#$ and $\tilde{\#}$ are equal, but equation $i$:

Type 1: These are $a_{i1} x_1 + \dots + a_{in} x_n = b_i$ and $\lambda (a_{i1} x_1 + \dots + a_{in} x_n) = \lambda b_i$.

Clearly both hold simultaneously or don't hold.

Type 2: The equations of $\#$ and $\tilde{\#}$ are exactly the same.

Type 3: All equations of $\#$ and $\tilde{\#}$ are equal, but the $i$-th:

$a_{i1}x_1+\dots+a_{in}x_{n}=b_{i},a_{j1}x_1+\dots+a_{jn}x_{n}=b_{j}$ and $(a_{i1} x_1 + \dots + a_{in} x_n) + \lambda (a_{j1} x_1 + \dots + a_{jn} x_n) = b_i + \lambda b_j$.

‍

Examples

$\begin{cases}2x-y+z=1\\ x+3y-z=0\end{cases}\sim(Type1)\begin{cases}2x-y+z=1\\ 2x+6y-2z=0\end{cases}\sim(Type3)\begin{cases}2x-y+z=1\\ y-3z=-\frac17\end{cases}\sim\begin{cases}2x+\frac47z=\frac67\\ y-\frac37z=-\frac17\end{cases}$

$\Rightarrow x = \frac{3}{7} - \frac{2}{7}z, \quad y = -\frac{1}{7} + \frac{3}{7}z$

Therefore, $X_0=\left(\frac37,-\frac17,0\right),\quad W=\left\{\left(-\frac27z,\frac37z,z\right):z\in\mathbb{R}\right\}$

Elementary row operations and row-equivalent matrices

The operations of type 1-3 on system $\#$ correspond to the following operations on the coefficient matrix of $\#$ and the independent vector of $\#$.

Assume that $\#$ can be written as $AX = b$. Consider the augmented matrix $(A|b)$.

Operation on $\#$	Row operation on $(A\\|b)$
Type 1	multiply one row by $\lambda \neq 0$
Type 2	switch rows $i$ and $j$
Type 3	replace row $i$ by itself plus a multiple of row $j$ $(j \neq i)$

Example

$\begin{pmatrix}2 & 1 & -1 & | & 1\\ 1 & 0 & 1 & | & -1\end{pmatrix}$$\sim\begin{pmatrix}1 & \frac12 & -\frac12 & | & \frac12\\ 1 & 0 & 1 & | & -1\end{pmatrix}\sim\begin{pmatrix}1 & \frac12 & -\frac12 & | & \frac12\\ 0 & -\frac12 & \frac32 & | & -\frac32\end{pmatrix}\sim\begin{pmatrix}1 & \frac12 & -\frac12 & | & \frac12\\ 0 & 1 & -3 & | & 3\end{pmatrix}$ $\sim \begin{pmatrix} 1 & 0 & 1 & | & -1 \\ 0 & 1 & -3 & | & 3 \end{pmatrix}$

Solutions: $X_0 = (-1, 3, 0)$ Check it: $AX_0=\begin{pmatrix}2 & 1 & -1\\ 1 & 0 & 1\end{pmatrix}\begin{pmatrix}-1\\ 3\\ 0\end{pmatrix}=\begin{pmatrix}1\\ -1\end{pmatrix}$

$W = \{ (-z, 3z, z) : z \in \mathbb{R} \}$ Check it: $AW = \begin{pmatrix} 2 & 1 & -1 \\ 1 & 0 & 1 \end{pmatrix} \begin{pmatrix} -z \\ 3z \\ z \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} \quad \checkmark \checkmark \checkmark$

Definition of row-equivalence

Two matrices of the same size are said to be row-equivalent if one of them can be obtained from the other one by a finite number of row operations (types 1-3).

Remark

Row-equivalence is an equivalence relation.

$(A|b)$ is row-equivalent to $(B|c)$ if and only if the systems $AX = b$ and $BX = c$ are equivalent.

Definition of row-reduced echelon matrix

An $A \in M_{m \times n}(\mathbb{F})$ is called a row-reduced echelon matrix, if:

(a) The first non-zero element of a non-zero row is $1$ (we call this $1$ a pivot).

(b) Each column containing a pivot has all its other entries equal to $0$.

(c) Every zero row appears below all non-zero rows.

(d) If the pivots occur in entries $(i_1, j_1), (i_2, j_2), \dots, (i_k, j_k)$ for $i_1 < i_2 < \dots < i_k$, then $j_1 < j_2 < \dots < j_k$. (So the pivots are accommodated in this direction: ↘ )

$\begin{pmatrix}1 & 0 & 1 & 2 & 3\\ 0 & 0 & 1 & -1 & 0\\ 0 & 0 & 0 & 0 & 0\end{pmatrix}\times$ $\begin{pmatrix}0 & 1 & 0 & 1 & -1\\ 0 & 0 & 0 & 2 & 0\\ 1 & 0 & -1 & 1 & 1\end{pmatrix}\times$

Remark

Row-reduced matrix:

Feature	Row Echelon Form (REF)	Reduced Row Echelon Form (RREF)
Leading Entry	Can be any non-zero number	Must be exactly 1
Non-zero Entries in Columns	Can have non-zero entries above or below pivots	Must be zero above and below each pivot
Uniqueness	Not unique; multiple REF forms possible	Unique; one specific RREF for each matrix

Theorem

Every $A \in M_{m \times n}(\mathbb{F})$ is row-equivalent to a row-reduced echelon matrix.

Remark

Moreover, $A$ is row-equivalent to a unique row-reduced echelon matrix. This is called its row-reduced echelon form.

Proof.

(a) can be achieved by using row operations of type 1. Namely, multiply the corresponding row by the inverse of its first non-zero element.

(c) can be achieved by using row operations of type 2.

(d) Similarly, by using row operations of type 2.

(b) can be achieved by using row operations of type 3, noting that the columns with pivots to the left are not being changed.

Operation on \(\#\)	Row operation on \((A\\|b)\)
Type 1	multiply one row by \(\lambda \neq 0\)
Type 2	switch rows \(i\) and \(j\)
Type 3	replace row \(i\) by itself plus a multiple of row \(j\) \((j \neq i)\)