# Linear System
The goal of Gaussian elimination is to solve a system of linear equations by simplifying it into a form that is easy to solve. We achieve this by using a set of powerful tools called elementary row operations on an augmented matrix.

## Solving a Linear System
:::info
**Definition (System of Linear Equations)**
A system of linear equations is a collection of equations of the form:
$$
\begin{cases}
a_{11}x_1 &+ a_{12}x_2+ \ldots+a_{1n}x_n &= b_1 \\
a_{21}x_1 &+ a_{22}x_2+ \ldots +a_{2n}x_n &= b_2 \\
& \vdots &\vdots \\
a_{m1}x_1 &+ a_{m2}x_2+ \ldots +a_{mn}x_n &= b_m
\end{cases}
$$

This system can be written in a compact matrix equation form: $Ax=\mathbf{b}$, where:
* $A$ is the m×n coefficient matrix.
* $\mathbf{x}$ is the $n \times 1$ variable vector.
* $\mathbf{b}$ is the $m \times 1$ constant vector.

To solve the system, we first combine the coefficient matrix $A$ and the constant vector $\mathbf{b}$ into a single augmented matrix $[A \mid \mathbf{b}]$.

$$
\left[\begin{array}{cccc|c}
a_{11} & a_{12}& \ldots & a_{1n} & b_1 \\
a_{21} & a_{22}& \ldots & a_{2n} & b_1 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
a_{m1} & a_{m2}& \ldots & a_{mn} & b_n \\
\end{array}\right]
$$
:::

## The Three Steps of Gaussian Elimination
1. **Build the Augmented Matrix:** Construct the matrix $[A \mid \mathbf{b}]$.
2. **Perform Row Operations:** Use elementary row operations to transform the augmented matrix into a **(reduced) row echelon form**.
3. **Find the Solution:** Read the solution(s) from the simplified matrix using **back substitution**.

## Elementary Row Operations
:::info
**Definition (Elemantary Row Operations)**
There are three types of elementary row operations. Each operation corresponds to an elementary matrix that can be multiplied on the left of the augmented matrix to achieve the transformation.

1. Interchange two rows (swapping two equations).
$\longleftrightarrow$ permutation matrix $P_{ij}$, $i \neq j$
2. Multiply a row by a nonzero constant (multiplying an equation by a number).
$\longleftrightarrow$ diagonal matrix $I_m + (c-1) E_{ii}$
3. Add a multiple of one row to another (adding one equation or a multiple of it to another).
$\longleftrightarrow$ $I_m + c \cdot E_{ij}$, $i \neq j$
:::

These operations are crucial because they do not change the solution set of the system.

:::warning
**Example**
$$\begin{cases}
3x + 4y + z &= 1 \\
2x + 3y &= 0 \\
4x + 3y - z &= -2
\end{cases}$$

* In matrix form:
$$
\underbrace{\begin{bmatrix}
3 & 4 & 1 \\
2 & 3 & 0 \\
4 & 3 & -1\end{bmatrix}}_{A} \begin{bmatrix}
x\\ y\\ z
\end{bmatrix}
=\underbrace{\begin{bmatrix}1\\0\\-2\end{bmatrix}}_{\mathbf{b}}
$$
* Interchanging rows:
$$
\begin{bmatrix}
0 & 1 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1
\end{bmatrix}
\left[\begin{array}{c|c}
A & \mathbf{b}
\end{array}\right] = \left[\begin{array}{ccc|c}
2 & 3 & 0 & 0\\
3 & 4 & 1 & 1 \\
4 & 3 & -1 & -2
\end{array}\right]
$$
* Multiply a row by $\frac{1}{3}$:
$$
\begin{bmatrix}
\frac{1}{3}& 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
\left[\begin{array}{c|c}
A & \mathbf{b}
\end{array}\right] =
\left[\begin{array}{ccc|c}
1 & \frac{4}{3} & \frac{1}{3} & \frac{1}{3}\\
2 & 3 & 0 & 0 \\
4 & 3 & -1 & -2
\end{array}\right]
$$
* Subtract the first row from the second row:
$$
\begin{bmatrix}
1& -1 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
\left[\begin{array}{c|c}
A & \mathbf{b}
\end{array}\right]
= \left[\begin{array}{ccc|c}
1 & 1 & 1 & 1\\
2 & 3 & 0 & 0 \\
4 & 3 & -1 & -2
\end{array}\right]
$$
:::

:::success
**Exercise**
1. Let $I$ be the identity matrix of size $N$ and let $R$ be the $N$ by $N$ matrix with all zeros except for nonzero scalar $c$ at index $(i,j)$ where $i \neq j$. That is, the entry of $R$ in row $i$ and column $j$ is $c$ and all other entries of $R$ are $0$. Let $E=I+R$ and let $A$ be any $N$ by $N$ matrix. Matrix multiplication $EA$ is equivalent to which operation on $A$?
2. Let $I$ be the identity matrix of size $N$ and let $R$ be the $N$ by $N$ matrix with all zeros except for nonzero scalar $c$ at index $(i,j)$ where $i \neq j$. That is, the entry of $R$ in row $i$ and column $j$ is $c$ and all other entries of $R$ are $0$. Let $E=I+R$ and let $A$ be any $N$ by $N$ matrix. Matrix multiplication $AE$ is equivalent to which operation on $A$?
3. If $P$ is a permutation matrix such that $PA$ interchanges $2$ rows of $A$, then $P^2=I$
:::

## Row Echelon Form
The goal of Gaussian elimination is to transform a matrix into a **row echelon form (REF)**.

:::info
**Definition (Row Echelon Form)**
A matrix is in REF if it satisfies the following conditions:

1. All zeros rows are at bottom.
2. The first nonzero entry in a row is 1.
2. The first nonzero entry (from the left) is located to the right of the first nonzero entry in each row above it.

For example, this matrix is in REF:
$$
\begin{bmatrix}
1 & 2 & 3 & 4 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0
\end{bmatrix}
$$

A matrix is in **reduced row echelon form (RREF)** if, in addition to the REF rules, every pivot is the only non-zero entry in its column.

For example, this matrix is in RREF:

e.g
$$
\begin{bmatrix}
1 & 0 & 0 & 3 \\
0 & 1 & 0 & 8 \\
0 & 0 & 1 & 7 \\
0 & 0 & 0 & 0 \\
\end{bmatrix}
$$
:::

:::danger
**Theorem**
Every matrix can be transformed into a (reduced) row echelon form by a sequence of elementary row operations. This algorithm is called **Gaussian eimination**.
:::

:::warning
**Example 1: No Solution**
Solve the system:
\begin{cases}
3x + 1y + -4z &= 1 \\
x + 10z &= 0 \\
4x + y + 6z &= -2
\end{cases}

First, we translate the system into an augmented matrix:
$$\begin{bmatrix}
3 & 1 & -4 \\
1 & 0 & 10 \\
4 & 1 & 6
\end{bmatrix}
\begin{bmatrix}
x\\ y\\z\end{bmatrix}
=\begin{bmatrix}-1\\5\\1\end{bmatrix}$$

Now, apply elementary row operations to transform it into REF:
\begin{aligned}
\left[\begin{array}{ccc|c}
3 & 1 & -4 & -1 \\
1 & 0 & 10 & 5 \\
4 & 1 & 6 & 1
\end{array}\right]
&\xrightarrow{r_1 \Leftrightarrow r_2} \left[\begin{array}{ccc|c}
1 & 0 & 10 & 5 \\
3 & 1 & -4 & -1 \\
4 & 1 & 6 & 1
\end{array}\right] \\
&\xrightarrow{\substack{r_2:r_2 - 3r_1\\ r_3 :r_3 - 4r_1 } }
\left[\begin{array}{ccc|c}
1 & 0 & 10 & 5 \\
0 & 1 & -34 & -16 \\
0 & 1 & -34 & -19
\end{array}\right] \\
&\xrightarrow{r_3 : r_3 - r_2 } \left[\begin{array}{ccc|c}
1 & 0 & 10 & 5 \\
0 & 1 & -34 & -16 \\
0 & 0 & 0 & -3
\end{array}\right]
\end{aligned}

The last row of the matrix translates to the equation 0=−3, which is a contradiction. Therefore, the system has no solution.
:::

:::warning
**Example 2: Infinitely Many Solutions**
Solve the system:
\begin{cases}
x_1 - 2x_2 - x_3 + 3x_4 &= 1 \\
2x_1 + 4x_2 + x_3 &= 5 \\
x_1 - 2x_2 + 2x_3 - 3x_4 &= 4
\end{cases}

In augmented matrix form:
$$
\begin{bmatrix}
1 & -2 & -1 & 3 \\
2 & -4 & 1 & 0 \\
1 &-2 & 2 & -3
\end{bmatrix}
\begin{bmatrix}
x_1\\ x_2\\x_3\end{bmatrix}
=\begin{bmatrix}1\\5\\4\end{bmatrix}
$$

Apply elementary row operations to find the RREF:
\begin{aligned}
\left[\begin{array}{cccc|c}
1 & -2 & -1 & 3 &1 \\
2 & -4 & 1 & 0 & 5 \\
1 &-2 & 2 & -3 & 4
\end{array}\right]
&\xrightarrow{\substack{r_2 : r_2 - 2r_1\\ r_3 : r_3 - r_1 }} \left[\begin{array}{cccc|c}
1 & -2 & -1 & 3 &1\\
0 & 0 & 3 & -6 & 3 \\
0 & 0 & 3 & -6 & 3 \\
\end{array}\right] \\
&\xrightarrow{r_2 = \frac{1}{3}r_2 }
\left[\begin{array}{cccc|c}
1 & -2 & -1 & 3 &1\\
0 & 0 & 1 & -2 & 1 \\
0 & 0 & 3 & -6 & 3 \\
\end{array}\right]\\
&\xrightarrow{r_3 : r_3 - 3r_2 }
\left[\begin{array}{cccc|c}
1 & -2 & -1 & 3 &1\\
0 & 0 & 1 & -2 & 1 \\
0 & 0 & 0 & 0 & 0 \\
\end{array}\right] \\
&\xrightarrow{r_1 : r_1 + r_2 }
\left[\begin{array}{cccc|c}
1 & -2 & 0 & 1 &2\\
0 & 0 & 1 & -2 & 1 \\
0 & 0 & 0 & 0 & 0 \\
\end{array}\right]\\
\end{aligned}

The RREF translates to the system:
$$
\begin{cases}
x_1 -2x_2 +x_4 &= 2 \\
x_3- 2x_4 &= 1 \\
0 &= 0
\end{cases}
$$

Notice that the variables $x_2$ and $x_4$ are not leading variables (they don't correspond to a pivot), so we can treat them as free variables. Let $x_2=s$ and $x_4=t$. We can then express the leading variables in terms of the free variables:
\begin{align}
x_3 &= 1 + 2x_4 = 1+2t \\
x_1 &= 2 + 2x_2 - x_4 = 2+2s-t
\end{align}

The general solution is given by:
$$
\begin{cases} x_1 = 2+2s-t \\
x_2=s\\
x_3 = 1+2t \\
x_4 = t\end{cases}
$$

Since the free variables can be any real number, the system has **infinitely many solutions**.
:::

## Solvability of Linear Equations
The number of solutions to a linear system $Ax=\mathbf{b}$ can be determined by comparing the **rank** of the coefficient matrix A and the augmented matrix $[A \mid b]$.

:::info
**Definition (Rank)**
The rank is the number of non-zero rows in the row echelon form of a matrix.
:::

* If A is $m \times n$ and $b$ is $m \times 1$, then
* $\textrm{rank}(A) \leq \min(m,n)$
* $\textrm{rank}(A) \leq \textrm{rank}(\left[\begin{array}{c|c} A & b \end{array}\right]) \leq \textrm{rank}(A)+1$

:::info
**Definition**
* If $\textrm{rank}(A) < \textrm{rank}(\left[\begin{array}{c|c}A & \mathbf{b} \end{array}\right])$, the system is **inconsistent** and has **no solution**. This happens when a row becomes $\left[\begin{array}{cccc|c} 0&0&\dots& 0&1 \end{array}\right]$ after row operations.
* If $\textrm{rank}(A) = \textrm{rank}(\left[\begin{array}{c|c}A & \mathbf{b} \end{array}\right])$, the system is **consistent** and has at least one solution.
* If the rank equals the number of variables ($r=n$), the system has a **unique solution**.
* If the rank is less than the number of variables ($r<n$), the system has **infinitely many solutions**, with $n−r$ free variables.
:::

A square matrix $A$ (where $m=n$) has a unique solution for every $\mathbf{b}$ if and only if $\textrm{rank}(A)=n$. This is also equivalent to $A$ being an invertible matrix. In this case, the solution is $x=A ^{−1} \mathbf{b}$.

:::warning
**Example**
In previous examples:
1. $\textrm{rank}(A) =2, \textrm{rank}(\left[\begin{array}{c|c} A & \mathbf{b}\end{array}\right]) = 3$, the system is inconsistent.
2. $\textrm{rank}(A) = \textrm{rank}(\left[\begin{array}{c|c}
A & \mathbf{b}
\end{array}\right]) = 2< n=4$, the system is consistent and has infinite many solutions controlled by 2 parameters.
:::

### How to compute $A^{-1}$?
The inverse of a square matrix $A$ can be found using Gaussian elimination. The idea is to find a sequence of elementary matrices $E_1, \ldots, E_n$ that transform $A$ into the identity matrix $I$.

$$
E_n \ldots E_1 \left[\begin{array}{c|c}
A & I_n\end{array}\right] = \left[\begin{array}{c|c}
I_n & E_n \ldots E_1
\end{array}\right]
$$

:::success
**Exercise**

4.
a.) Let $A$ be a $m$ by $n$ matrix such that $m>n$ and $\textrm{rank}(A)=n$. There is a unique solution of $A\mathbf{x}=\mathbf{b}$ for any $\mathbf{b}$.
b.) Let $A$ be a $m$ by $n$ matrix such that $m<n$ and $\textrm{rank}(A)=m$. There is infinitely many solution of $A\mathbf{x}=\mathbf{b}$ for any $\mathbf{b}$.
5. Find a value $c$ such that the system $A\mathbf{x}=\mathbf{b}$ has infinitely many solutions where
$$
A = \begin{bmatrix} 3 & -1 & 2 \\
1 & 1& 1 \end{bmatrix}, \quad b = \begin{bmatrix} 3 \\2\\
1\end{bmatrix}
$$
:::