# Part I - Linear Equations

## 1. Views of linear equations

It can be reasonable to state that the the linear equations are the most simple equation system and the one that we know the best. Thus, it constitute the basic part of our toolkit and the study of linear algebra.

For the below linear equations system,

$$
\begin{equation}
2x - y = 0 \\
-x + 2y = 3 \\
\end{equation}
$$

It can be organized the system into a matrix representation as below.And that will lead to two kinds of views of the system.

$$
\begin{equation}
\left[
\begin{matrix}
 2 & -1 \\
-1 &  2 \\
\end{matrix}
\right]
\left[
\begin{matrix}
x \\
y \\
\end{matrix}
\right]
=
\left[
\begin{matrix}
0 \\
3 \\
\end{matrix}
\right]
\end{equation}
$$

And the representation can further be summarized in the general form:

$$\begin{equation}
\rm{A}
\textbf{x}
=
\textbf{b}
\end{equation}$$

where 
$
\begin{equation}
\rm{A}
=
\left[
\begin{matrix}
 2 & -1 \\
-1 &  2 \\
\end{matrix}
\right]
\end{equation}
$
is called the $\textit{coefficient matrix}$,
$
\begin{equation}
\textbf{x}
=
\left[
\begin{matrix}
x \\
y \\
\end{matrix}
\right]
\end{equation}
$
is the $\textit{vector of unknowns}$,
and 
$
\begin{equation}
\textbf{b}
=
\left[
\begin{matrix}
0 \\
3 \\
\end{matrix}
\right]
\end{equation}
$
is the vector coming from the right hand side of the equations.

### View of Row (View of Separate Equations)

By seeing the system as separate equations, we get the view of row.

$$
\begin{equation}
\begin{cases}
2x - y = 0, & Eq1\\
-x + 2y = 3, & Eq2\\
\end{cases}
\end{equation}
$$

Under the view of row, solutions are interpreted as the set of points that satisfy all of the equations. Therefore, in geometry, they are the **intersection points of all the geometric objects (lines/planes/hyperplanes)** these equation represent.

### View of Column (View of Linear Combination)

An alternative view can be: Since all the equations share the same vector of unknowns (if some unknowns are missing, it can be represented as unknowns with 0 coefficient), we can **"factor out"** those unknowns and reshape the system like this.

$$
\begin{equation}
x
\left[
\begin{matrix}
 2 \\
-1 \\
\end{matrix}
\right]
+
y
\left[
\begin{matrix}
-1 \\
2 \\
\end{matrix}
\right]
=
\left[
\begin{matrix}
0 \\
3 \\
\end{matrix}
\right]
\end{equation}
$$

In this view, the different rows of the coefficient vectors are treated as the independent "coordinates". For example, the $2$ and $-1$ in
$
\left[
\begin{matrix}
 2 \\
-1 \\
\end{matrix}
\right]
$
are treated as the x-coordinate and the y-coordinate.
And the solution to the euqations are interpreted as the **correct multiples** of these coefficient vectors such that the sum of them equals the the right hand side $\textbf{b}$.

Following this view, since the coefficient vectors constitute the columns of the coefficient matrix, we call them the $\textit{column vectors}$. And solving the linear equations is equivalent to finding the correct multiples of the column vectors. Or to say, finding the correct $\textit{linear combination}$ of the column vectors.

By linear combination, we mean adding/subtracting and multipling vectors by **scalars (pure numbers)**.

## 2. Gaussian Elimination

### Prerequisite: Matrix Multiplication

The most elementary and mechanical view of matrix multiplication is the **element view**. This view focuses on every single element of the resulting matrix, and is more often used in simple calculations. In particular, for a $m\times{n}$ matrix $\rm{A}$ and a $n\times{p}$ matrix $\rm{B}$, the resulting matrix $\rm{C}=\rm{AB}$ is a $m\times{p}$ matrix. And a general element in row $i$ and column $j$ of matrix $\rm{C}$ is:

$$
\begin{equation}
c_{ij} = \sum_{k=1}^{n} a_{ik}b_{kj}
\end{equation}
$$

From Section 1 we have seen that when a matrix is multiplied by a vector on the right, it is equivalent to taking the $\textit{linear combination}$ of the columns of that matrix. And that helps to introduce the **vector view** of matrix multiplication.

Notice that from the **element view** formula, all of the elements in column $j$ (denoted as $\rm{C_{j}}$) of the resulting matrix $\rm{C}$ are only influenced by the repective column $j$ (denoted as $\rm{B_{j}}$) in matrix $\rm{B}$, rather then the other columns from matrix $\rm{B}$. And the elements of $\rm{C_{j}}$ can be seen as the linear combination of the columns of $\rm{A}$. In other words, $\rm{A}B_{j}=C_{j}$.

For detailed demonstration, think about the case that a $3\times{2}$ matrix $\rm{A}$ multiplies a $2\times{3}$ matrix $\rm{B}$, where the resulting matrix is a $3\times{3}$ matrix $\rm{C}$. The first column of $\rm{C}$ comes from the first columns of $\rm{B}$ with elements computed as follows.

$$
\begin{equation}
\begin{aligned}
c_{11} &= a_{11}b_{11} + a_{12}b_{21} + a_{13}b_{31} \\
c_{21} &= a_{21}b_{11} + a_{22}b_{21} + a_{23}b_{31} \\
c_{31} &= a_{31}b_{11} + a_{32}b_{21} + a_{33}b_{31} \\
\end{aligned}
\end{equation}
$$

Going through the trick we have seen in Section 1 we may have,

$$
\begin{equation}
C_{1}
=
\left[
\begin{matrix}
c_{11} \\
c_{21} \\
c_{31} \\
\end{matrix}
\right]
=
b_{11}
\left[
\begin{matrix}
a_{11} \\
a_{21} \\
a_{31} \\
\end{matrix}
\right]
+
b_{21}
\left[
\begin{matrix}
a_{12} \\
a_{22} \\
a_{32} \\
\end{matrix}
\right]
+
b_{31}
\left[
\begin{matrix}
a_{13} \\
a_{23} \\
a_{33} \\
\end{matrix}
\right]
=
\left[
\begin{matrix}
a_{11} & a_{12} & a_{13}\\
a_{21} & a_{22} & a_{23}\\
a_{31} & a_{32} & a_{33}\\
\end{matrix}
\right]
\left[
\begin{matrix}
b_{11} \\
b_{21} \\
b_{31} \\
\end{matrix}
\right]
=
\rm{AB_{1}}
\end{equation}
$$

Therefore, in **verctor view**, we have the following important conclusions:

For the product of matrix multiplication $\rm{C}=\rm{AB}$,
1. The column of $\rm{C}$ is a linear combination of the columns of of $\rm{A}$.
2. The row of $\rm{C}$ is a linear combination of the rows of of $\rm{B}$.

The second conclusion can be proved like the way we do above. Since matrix multiplication is not commutative, the $\rm{A}$ and $\rm{B}$ cannot be interchanged under most circumstances.

### Warm-up from High Schools

In high school, students learned how to solve simple linear equations through eliminating variables and simplifying the system. For general linear equation systems, since they can be represented by matrices, the idea of finding the solutions is alike but extended to the operation of matrices.

For example, concerning the linear equations below, we may cancel the $x$ variable in $Eq2$ through multiplying the $Eq1$ by 3 and subtract that from $Eq2$, which will result in a new equation $Eq2^{'}$ with no $x$ variable. And then further eliminating $y$ in $Eq3$ by subtracting 2 times of $Eq2^{'}$ from it. Then the equations can be easily solved by $\textit{backsubstitution}$: solving z by $Eq3^{'}$, then using z to solve y by $Eq2^{'}$...

$$
\begin{equation}
\begin{aligned}
x + 2y + z &= 2  &Eq1\\
3x + 8y + z &= 12 &Eq2\\
    4y + z &= 2  &Eq3\\
\end{aligned}
\ \rightarrow\ 
\begin{aligned}
x + 2y + z &= 2  &Eq1\\
   2y - 2z &= 6 &Eq2^{'}\\
    4y + z &= 2 &Eq3\\
\end{aligned}
\ \rightarrow\ 
\begin{aligned}
x + 2y + z &= 2  &Eq1\\
   2y - 2z &= 6 &Eq2^{'}\\
      5z &= -10 &Eq3^{'}\\
\end{aligned}
\end{equation}
$$

### Matrix Representation of the Elimination Process

Since the linear equations can be represented by matrices, the elimination process above can also be stated in the language of matrices. First of all, the original equations can be represented by the following $\textit{augmented matrix}$. By $\textit{augmented}$, we mean adding an extra column to the coefficient matrix $\rm{A}$ to represent the right hand side vector $\textbf{b}$. 

Remember that in order to have the same solution, when multiplying or subtracting the equations in the system should do the same manipulation to the both sides of the equations.

$$
\begin{equation}
\left[
\begin {array}{c|c}
\rm{A}&
\textbf{b}
\end {array}
\right]
=
\left[{
\begin {array}{c|c}
\begin{matrix}
1 & 2 & 1 \\
3 & 8 & 1 \\
0 & 4 & 1 \\
\end{matrix}&
\begin{matrix}
2 \\
12 \\
2\\
\end{matrix}
\end{array}}
\right]
\end{equation}
$$

Given this the elimination above can be restated in matrix language, which again, can be solved in ease.

$$
\begin{equation}
\left[
{\begin{array}{c|c}
\begin{matrix}
1 & 2 & 1 \\
3 & 8 & 1 \\
0 & 4 & 1 \\
\end{matrix}&
\begin{matrix}
2 \\
12 \\
2\\
\end{matrix}
\end{array}}
\right]
\ \rightarrow \ 
\left[
{\begin{array}{c|c}
\begin{matrix}
1 & 2 & 1 \\
0 & 2 & -2 \\
0 & 4 & 1 \\
\end{matrix}&
\begin{matrix}
2 \\
6 \\
2\\
\end{matrix}
\end{array}}
\right]
\ \rightarrow \ 
\left[
{\begin{array}{c|c}
\begin{matrix}
1 & 2 & 1 \\
0 & 2 & -2 \\
0 & 0 & 5 \\
\end{matrix}&
\begin{matrix}
2 \\
6 \\
-10\\
\end{matrix}
\end{array}}
\right]
=
\left[
\begin {array}{c|c}
\rm{U}&
\textbf{c}
\end {array}
\right]
\end{equation}
$$

### Mathematical View of Matrix Operation

The next thing we are going to do is to express the operations in the elimination process through mathematical language. 

In the elimination process, what we have done is taking multiples of the equations and performing addition or subtraction operations among them. 

In matrix language, we are manipulating the rows of the coefficient matrix or the augmented matrix. Recall from matrix multiplication, this can be expressed by multiplying a matrix on the left side, since taking multiples of the rows and performing addition or subtraction operations among them are just taking the $\textit{linear combinations}$.

Basically, the procedures taken in the elimination process can be **decomposed** into fundamental ones represented by the so-called $\textit{elimination matrices}$. In particular, the matrix representing the procedures needed to eliminate the entry $\textit a_{ij}$ is denoted as the elimination matrix $\textit E_{ij}$.

For example, for eliminating the 3 in row 2 and column 1 in the above matrix $\rm{A}$, we need to multiply the first row by 3 and subtract it from the second row of $\rm{A}$. In the language of matrix operation, 
$
\begin{equation}
\textit E_{21}
=
\left[
\begin{matrix}
1 & 0 & 0 \\
-3 & 1 & 0 \\
0 & 0 & 1 \\
\end{matrix}
\right]
\end{equation}
$. 
And 
$\begin{equation}
\textit E_{21}\rm{A}
=
\left[
\begin{matrix}
1 & 2 & 1 \\
0 & 2 & -2 \\
0 & 4 & 1 \\
\end{matrix}
\right]
\end{equation}
$ will eliminate the element $\textit a_{21}=3$.

Then the process can continue to eliminate $\textit a_{32}$ by multiplying
$
\begin{equation}
\textit E_{32}
=
\left[
\begin{matrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -2 & 1 \\
\end{matrix}
\right]
\end{equation}
$ 
and get the final result $\rm{U}$.
Since matrix multiplication is **associative**, all the elimination matrix can be grouped together and computed first, denoted as $\textit{E}$.

$$
\begin{equation}
\textit E_{32}\ (E_{21}\rm{A})
=
(\textit E_{32}\ \textit E_{21})\rm{A}
=
\left[
\begin{matrix}
1 & 2 & 1 \\
0 & 2 & -2 \\
0 & 0 & 5 \\
\end{matrix}
\right]
=
\rm{U}
\end{equation}
$$
$$
\textit E = \textit E_{32}\ \textit E_{21}
$$

And for the equations to have the same solutions as the original ones, the same multiplication should also be applied to the right hand side vector $\textbf{b}$, such that $\textit E\textbf{b} = \textbf{c}$. 

Thus, the original linear equations system 
$
\begin{equation}
\rm{A}
\textbf{x}
=
\textbf{b}
\end{equation}
$
has been transformed into a new system
$
\begin{equation}
(\textit E\rm{A})
\textbf{x}
=
\rm{U}
\textbf{x}
=
\textbf{c}
\end{equation}
$, which can be easily solved by the $\textit{backsubstitution}$ procedure.
And most importantly, the solutions stay the same.

### Additional comments

When conductiong the elimination process, the final elements we put on the diagonal are often called as $\textit{pivot}$, including the elements $\textit u_{11}=1$, $\textit u_{22}=2$, $\textit u_{33}=5$ in the resulting matrix $\rm{U}$. Those are the elements we usually used to eliminate other elements below them. 

What worths noticing is that a $\textit{pivot}$ cannot be zero. In case of seeing a zero in the diagonal position, we will try to do **row exchange** with a row below and make the pivot non-zero. This can be done by multiplying a group of matrices called the $\textit{permutation matrices}$.
However, if no non-zero element is available, then the matrix will have some problems or some additional properties. We called this kind of matrix $\textit{not invertible}$.

For example, if 
$\begin{equation}
\rm{A}
=
\left[
\begin{matrix}
1 & 2 & 1 \\
3 & 6 & 1 \\
0 & 4 & 1 \\
\end{matrix}
\right]
\end{equation}
$,
then after eliminating the $a_{21}=3$,
$\textit E_{21}\rm{A}
=
\left[
\begin{matrix}
1 & 2 & 1 \\
0 & 0 & -2 \\
0 & 4 & 1 \\
\end{matrix}
\right]
$
would have $a_{22}=0$.

At the time, we need to multiply an additional permutation matrix which will perform a swap between row 2 and row 3 of 
$\textit E_{21}\rm{A}$. And the permutation matrix 
$\begin{equation}
P_{23}
=
\left[
\begin{matrix}
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0 \\
\end{matrix}
\right]
\end{equation}
$
would finish the job. (Using the **vector view** of matrix multiplication, multiplying a matrix from the left is taking linear combination of the rows. Therefore, the second row of the product is the third row of $\textit E_{21}\rm{A}$, and the third row is the second row of $\textit E_{21}\rm{A}$.Thus, 
$\begin{equation}
P_{23}\textit E_{21}\rm{A}
=
\left[
\begin{matrix}
1 & 2 & 1 \\
0 & 4 & 1 \\
0 & 0 & -2 \\
\end{matrix}
\right]
\end{equation}
$.)

## 3. Inverse

For square matrices, there is one special family of members that deserves further attention. Each of them, say $\rm{A}$, is paired with another matrix called its $\textit{inverse}$ $\rm A^{-1}$ such that $\rm AA^{-1} = A^{-1}A = I$.

Not all of the square matrices have the corresponding inverse matrices. Those do have their corresponding inverse matrices are called $\textit{invertible}$ or $\textit{non-singular}$. And those cannot find the corresponding inverse matrices are called $\textit{singluar matrices}$.

The most simple example of inverse matrices are those corresponding to the $\textit{elimination matrices}$ or the $\textit{permutation matrices}$, which just undo the elimination or permutation steps.

For example, if 
$
\begin{equation}
\textit E_{21}
=
\left[
\begin{matrix}
1 & 0 & 0 \\
-3 & 1 & 0 \\
0 & 0 & 1 \\
\end{matrix}
\right]
\end{equation}
$,
then the corresponding inverse
$
\begin{equation}
\textit E_{21}^{-1}
=
\left[
\begin{matrix}
1 & 0 & 0 \\
3 & 1 & 0 \\
0 & 0 & 1 \\
\end{matrix}
\right]
\end{equation}
$.

In words, what $\textit E_{21}^{-1}$ is doing is just adding 3 times of the row 1 to row 2 of matrix $\rm{A}$, which is just the opposite of what $\textit E_{21}$ is doing. Therefore, the result of the two operations is just the matrix $\rm{A}$ itself, represented by $\textit E_{21}^{-1}\textit E_{21}=\rm{I}$, ie multiplying an identity matrix.

### Relation with linear equations

The idea of inverse matrices is closely related to the solution of linear equations. If the coefficient matrix $\rm{A}$ has an inverse, then solution of the linear equation system
$
\begin{equation}
\rm{A}
\textbf{x}
=
\textbf{b}
\end{equation}
$
can be easily found by multiplying the inverse $\rm{A^{-1}}$ on both sides, such that

$$
\begin{equation}
\rm{A^{-1}A}
\textbf{x}
=
\rm{A^{-1}}\textbf{b} \\
\textbf{x}
=
\rm{A^{-1}}\textbf{b}
\end{equation}
$$.

Moreover, if $\rm{A}$ has an inverse, the corresponding **homogeneous equation system** $\rm{A}𝐱 = 0$ has the unique solution $𝐱=0$, which means that the column vectors in $\rm{A}$ are $\textit{linear independent}$. The concept of linear independence is the key to finding overall properties of the solutions to a linear equation system 
$
\begin{equation}
\rm{A}
\textbf{x}
=
\textbf{b}
\end{equation}
$
and will be introduced in later parts.

### Gauss-Jordan Elimination

The next issue becomes, how to find an inverse of a square matrix, if it exists. In fact, finding the inverse can also be accomplished through **row operations**, given that $\rm A^{-1}A = I$. 

Assume that we are doing a series of row operations and get the inverse of $\rm{A}$, and the product of those row operation matrices is $E=\rm A^{-1}$. Now suppose we perform these series of operations with two matrices $\rm{A}$ and $\rm{I}$ simutaneously, and record them through two blocks of a matrix. Then the inverse will automatically turn out in the second block.

$$
\begin{equation}
E
\begin{matrix}
\left[
\begin {array}{c|c}
\rm{A}&
\rm{I}
\end {array}
\right]
\end{matrix}
=
\begin{matrix}
\left[
\begin {array}{c|c}
\rm{I}&
E
\end {array}
\right]
\end{matrix}
\end{equation}
$$

Therefore, by **augmenting** an extra block of a identity matrix, we can keep track of the row operations which turn $\rm{A}$ into $\rm{I}$. Specifically, the row operations are done in the manner of Gaussian elimination, but continue to **eliminate the upper right entries** above the diagonal, and normalize the diagonal entries into 1.

For example, to find the inverse of the matrix 
$
\left[
\begin{matrix}
1 & 3  \\
2 & 7  \\
\end{matrix}
\right]
$,
we augment an identity matrix to the right, and start to perform the elimination.

$$
\left[
\begin{array}{c|c}
\begin{matrix}
1 & 3  \\
2 & 7  \\
\end{matrix}&
\begin{matrix}
1 & 0  \\
0 & 1  \\
\end{matrix}
\end{array}
\right]
\ \rightarrow \ 
\left[
\begin{array}{c|c}
\begin{matrix}
1 & 3  \\
0 & 1  \\
\end{matrix}&
\begin{matrix}
1 & 0  \\
-2 & 1  \\
\end{matrix}
\end{array}
\right]
\ \rightarrow \ 
\left[
\begin{array}{c|c}
\begin{matrix}
1 & 0  \\
0 & 1  \\
\end{matrix}&
\begin{matrix}
7 & -3  \\
-2 & 1  \\
\end{matrix}
\end{array}
\right]
$$

## 4. First Factorization: A=LU

The elimination process produces $\textit E\rm{A} = \rm{U}$ and $\rm{U}\textbf{x} = \text{c}$, where $\textit {E}$ is the product of a series of elimination matrices. Assume that we do not need to perform any permutation, or to say multiply any permutation matrices during the elimination process.

We know that the $\textit{elimination matrices}$ always have their corresponding inverses, since what they do is taking $\textit{linear combinations}$ of the rows in $\rm{A}$. For example,
$
\begin{equation}
\textit E_{21}
=
\left[
\begin{matrix}
1 & 0 & 0 \\
-3 & 1 & 0 \\
0 & 0 & 1 \\
\end{matrix}
\right]
\end{equation}
$
above is just taking 3 times of the first row and subtracting it from the second row of matrix $\rm{A}$. Therefore, adding 3 times of the first row to the second row of the **product**, namely multiplying 
$
\begin{equation}
\textit E_{21}^{-1}
=
\left[
\begin{matrix}
1 & 0 & 0 \\
3 & 1 & 0 \\
0 & 0 & 1 \\
\end{matrix}
\right]
\end{equation}
$
on the left will give the identity matrix $\rm{I}$ back.

Back to the product of elimination matrices $\textit {E}$, $\textit {E}$ must have an inverse. If we multiply the inverse $\textit E^{-1}$ on both sides of $\textit E\rm{A} = \rm{U}$. We will get,

$$
\rm{A} = \textit E^{-1}\rm{U}
$$

Notice there are two important properties for the two matrices on the right,
1. $\textit {E}$ and $\textit E^{-1}$ are both lower triangular matrices.
2. $\rm {U}$ is a upper triangular matrix.

The fact that $\rm{U}$ is upper triangular is obvious, since we knock off all the entries below the diagonal in the elimination process. And every elimination matrix $\textit E_{ij}$ is lower triangular, since we always subtract a multiple of one **upper** row from row $i$ that contains the element $a_{ij}$. Similarly, the inverse of $\textit E_{ij}$, which **undo** the row operation in $\textit E_{ij}$, is also a lower triangular matrix. Lastly, the **product** of two lower triangular matrices is once agin a lower triangular matrix, which will give us property 1.

Because of these two properties, we often denote the $\textit E^{-1}$ on the right hand side as $\rm{L}$ to signify its lower triangular nature. Thus, we arrived at the first **factorization** of a matrix.

$$
\rm{A} = \rm{L} \rm{U}
$$

This means the information contains in $\rm{A}$ is now **decomposed** into two parts, storing in $\rm{L}$ and $\rm{U}$ respectively.

### Additional comments

In order to decompose $\rm{A}$ into two triangular matrices $\rm{L}$ and $\rm{U}$, we have assumed that no permutation will need to perform. That is surely not the case all the time. If we do need to perform any permutation, represented by a permutation matrix $\textit{P}$, we will accomplish it **before** the elimination or decomposition process, such that the result of permutation $\textit{P}\rm{A}$, will become a matrix that does not require further permutations.

This additional procedure gives us back to the case discussed above, with a generalized form of

$$
\textit{P} \rm{A} = \rm{L} \rm{U}
$$

75d941b0e3e681662ebca93571d0c2748a078fb9
ipynb
Jupyter Notebook
Part I - Linear Equations.ipynb
Explorer-Ken/Quick-Linear-Algebra
1bdc28ee9f9bb4cf49461c0a0aa08258413a8d12
MIT
Part I - Linear Equations.ipynb
Explorer-Ken/Quick-Linear-Algebra
1bdc28ee9f9bb4cf49461c0a0aa08258413a8d12
MIT
Part I - Linear Equations.ipynb
Explorer-Ken/Quick-Linear-Algebra
1bdc28ee9f9bb4cf49461c0a0aa08258413a8d12
MIT
Qwen/Qwen-72B
1. YES
2. YES