\chapter{Linear equations}
\section{Linear independent set}
Let $X$ be any vector space. If vectors $\vect{a_1},\vect{a_2},\ldots ,\vect{a_n} \in X$, then for any scalars $s_1,s_2,\ldots ,s_n \in \mathbb{R}$, the vector
\[ \vect{x}=\sum^n_{i=1}s_i \vect{a_i} \]
is called \emph{a linear combination} of $\vect{a_1},\vect{a_2},\ldots ,\vect{a_n}$.
Let $S$ be a set of vectors $S=\lbrace \vect{a_1},\vect{a_2},\ldots ,\vect{a_n} \rbrace$, where all vectors in $S$ belong to the same vector space $X$. Denote the zero-element of vector space $X$ as $\overline{0}$. If the set $S$ is \emph{linearly independent} then   a linear combination of vectors in $S$ equals zero-element if and only if all scalars in the linear combination are zero.
\[ \sum^n_{i=1}s_i \vect{a_i} = \overline{0} \Leftrightarrow s_i = 0, \forall i \in \lbrace 1,2,\ldots ,n \rbrace \]
\begin{example}
Let $X=\mathbb{R}^2$ and $S=\lbrace \vect{a_1},\vect{a_2}\rbrace$, where $\vect{a_1}=(2,4)$ and $\vect{a_2}=(1,2)$. We have
\begin{meq*}
    s_1\vect{a_1} + s_2\vect{a_2} = \overline{0} & \Leftrightarrow & s_1\cvect{2,4} + s_2\cvect{1,2} = \cvect{0,0} \\
    \Leftrightarrow
    \begin{cases}         
        2s_1 + s_2 &= 0 \\                    
        4s_1 + 2s_2 &= 0                      
    \end{cases}                           
    & \Leftrightarrow & s_2=-2s_1                   
\end{meq*}
Thus, the set $S$ is not linearly independent. Notice that the equation $s_2=-2s_1 $ indicates $\vect{a_1},\vect{a_2}$ are on the same line in the two-dimensional coordinate system. We can use $\vect{a_1}$ to define $\vect{a_2}$ based on the equation $s_2=-2s_1$, and vice versa $\vect{a_1}$ can be defined by $\vect{a_2}$.
\end{example}
\begin{example}
Let $X=\mathbb{R}^2$ be a vector space and $S=\lbrace \vect{a_1},\vect{a_2}\rbrace$, where $\vect{a_1}=(2,4)$ and $\vect{a_2}=(-1,2)$. We have
\begin{meq*}
    s_1\vect{a_1} + s_2\vect{a_2} = \overline{0} & \Leftrightarrow & s_1\cvect{2,4} + s_2\cvect{1,2} = \cvect{0,0} \\
    \Leftrightarrow
    \begin{cases}         
        2s_1 - s_2 &= 0 \\                    
        4s_1 + 2s_2 &= 0                      
    \end{cases}                           
    & \Leftrightarrow &
    \begin{cases}         
        s_2 &= 2s_1 \\                    
        s_2 &= -2s_1                      
    \end{cases}
    \Leftrightarrow s_2=s_1=0                  
\end{meq*}
Thus, the set $S$ is linearly independent. Notice that the equation $s_2=s_1=0$ indicates there is no way to define $\vect{a_1}$ using $\vect{a_2}$, or vice versa.
\end{example}
\begin{example}
Show that vectors $\vect{u},\vect{v}\in \mathbb{R}^5$ does not form a linearly independent set if $\vect{u}=(-1,0,8,5,2)$ and $\vect{v}=(-6,0,48,30,12)$.\par 
The set $\lbrace \vect{u},\vect{v} \rbrace$ is linearly independent if and only if
\begin{equation}
\label{ex1-5}
s_1\vect{u} + s_2\vect{v} = \overline{0} \Leftrightarrow s_1=s_2=0
\end{equation}
We have $s_1\vect{u} + s_2\vect{v} = \overline{0}$ is equivalent to
\begin{equation*}
\begin{cases}
-s_1-6s_2 &=0 \\
8s_1+48s_2 &=0 \\
5s_1+30s_2 &=0 \\
2s_1+12s_2 &=0
\end{cases}
\end{equation*}
All of these equations are equivalent to $s_1+6s_2=0$. There are an infinite number of solutions to this equations, which does not satisfies \eqref{ex1-5}.
\end{example}
Let $X$ be a vector space and the set $A \subseteq X$ is linearly independent. If any vectors $\vect{u}\in X$ is a linear combination of vectors in $A$, then $A$ is a \emph{base of X}. Any set which you can prove is linearly independent and its span is the whole space, is a basis of the vector space.

\section{System of linear equations}
\label{linear-eq}
Given $\vect{A}$ an n-square matrix and two column vectors $\vect{x}=\rvect{x_1,x_2,\ldots ,x_n}^T$ and $\vect{b}=\rvect{b_1,b_2,\ldots ,b_n}^T$. The system of n linear equations in n unknowns is equivalent to the matrix equation: \[ \vect{A}\vect{x}=\vect{b} \]
The matrix $\vect{A}$ is called the \emph{coefficient matrix}. The collection of all columns in $\vect{A}$ form a lineary independent set (rank of $\vect{A}$ is n) iff $\dt{A}\neq 0$. This also means that there exists a unique solution for the equation. On the other hand, if $\dt{A}=0$, then either of two cases occurs: the system has no solutions, or there are an infinite number of solutions. This notebook introduces three matrix-related solutions to solve System of linear equations: Inverse matrix, Crammer's rule, Gaussian elimination.
\subsection{Inverse matrix}
Given the matrix equation $\vect{A}\vect{x}=\vect{b}$ where $\vect{A}$ is an n-square matrix, $\vect{x}=\rvect{x_1,x_2,\ldots ,x_n}^T$ and $\vect{b}=\rvect{b_1,b_2,\ldots ,b_n}^T$. If  $\dt{A}\neq 0$, then $\vect{A}$ is invertible and there is a unique solution to the equation: \[ \vect{x}=\inverse{A}\vect{b} \]
Observe that this method only works if the determinant of the coefficient matrix is nonzero.
\begin{example}
Solve the following system of equation:
\begin{equation}
\begin{cases}
    2x_1+4x_2 &= 8 \\
    7x_1-2x_2 &= 4
\end{cases}
\label{apple}
\end{equation}
Let define matrix $\vect{A}$, $\vect{x}$, and $\vect{b}$ as follow:
\[ \vect{A}=\smtrx{2,4\\ 7,-2} \quad \vect{x}=\cvect{x_1,x_2} \quad \vect{b}=\cvect{8,4} \]
The system of equations is equivalent to 
\begin{equation*}
\vect{A}\vect{x}=\vect{b}
\end{equation*}
The determinant of coefficient matrix is \[ \dt{A}=2\cdot (-2) - 7\cdot 4= -32 \neq 0 \] Thus, the equation has a unique solution, which is
\[ \vect{x}=\inverse{A}\vect{b}=\frac{1}{-32} \smtrx{-2,-4\\-7,2}\cvect{8,4}=\cvect{1,3/2} \]
\end{example}
\subsection{Crammer's rule}
Suppose we need to solve the matrix equation $\vect{A}\vect{x}=\vect{b}$ where $\vect{A}$ is an n-square matrix, $\vect{x}=\rvect{x_1,x_2,\ldots ,x_n}^T$ and $\vect{b}=\rvect{b_1,b_2,\ldots ,b_n}^T$. Let $\vect{A}^{(j)}$ be a matrix $\vect{A}$ but replace \emph{j}th column with $\vect{b}$. Then we have \[ x_j=\frac{\dt{\vect{A}^{(j)}}}{\dt{A}} \] Like Inverse matrix, this method only works if the determinant of the coefficient matrix is nonzero.
\begin{example}
The system of equation \eqref{apple} can solved using Crammer's rule as follow:
\begin{meq*}
    \vect{A} &=& \smtrx{2,4\\7,-2}, \quad \dt{A}=-32 \\
    \dt{A^{(1)}} &=& \dmtrx{8,4\\4,-2}=-32 \Rightarrow x_1=\frac{-32}{-32}=1 \\
    \dt{A^{(2)}} &=& \dmtrx{2,7\\8,4}=-48 \Rightarrow x_2=\frac{-48}{-32}=\frac{3}{2}
\end{meq*}
\end{example}
\subsection{Gaussian elimination}
Gaussian elimination is usually understood as a sequence of operations performed on the corresponding matrix of coefficients. This method can be used to solve system of equations, find the rank of a matrix, calculate the determinant of a matrix, and calculate the inverse of an invertible square matrix.\\

To perform Gaussian elimination, one uses a sequence of elementary row operations to modify the matrix until the lower left-hand corner of the matrix is filled with zeros, as much as possible. There are three types of elementary row operations:
\begin{itemize}
\item Swap the positions of two rows.
\item Multiply a row by a nonzero scalar.
\item Add to one row a scalar multiple of another.
\end{itemize}
These operations are already shown in section \ref{sec:Determinants} as properties of determinants.\par 
\begin{example}
The system of equation \eqref{apple} can solved using Gaussian elimination. Let define matrix $\vect{A}$, $\vect{x}$, and $\vect{b}$ as follow:
\[ \vect{A}=\smtrx{2,4\\ 7,-2} \quad \vect{x}=\cvect{x_1,x_2} \quad \vect{b}=\cvect{8,4} \] 
First, we create the augmented matrix which is formed by merging matrix $\vect{A}$ and $\vect{b}$.
\begin{equation*}
    \left[{\begin{array}{cc|c}
        2&4&8 \\ 7&-2&4
    \end{array}}\right]
\end{equation*}
Swap the positions of two rows, we have:
\begin{equation*}
    \left[{\begin{array}{cc|c}
        7&-2&4 \\ 2&4&8
    \end{array}}\right]
\end{equation*}
Multiply the first row by 1/7, we have:
\begin{equation*}
    \left[{\begin{array}{cc|c}
        1&-2/7&4/7 \\ 2&4&8
    \end{array}}\right]
\end{equation*}
Replace the second row by $R_2 \leftarrow R_2-2R_1$
\begin{equation*}
    \left[{\begin{array}{cc|c}
        1&-2/7&4/7 \\ 0&32/7&48/7
    \end{array}}\right]
\end{equation*}
Multiply the first row by 32/7, we have:
\begin{equation*}
    \left[{\begin{array}{cc|c}
        1&-2/7&4/7 \\ 0&1&48/32
    \end{array}}\right]
\end{equation*}
Replace the first row by $R_1 \leftarrow R_2+ \frac{2}{7} R_1$
\begin{equation*}
    \left[{\begin{array}{cc|c}
        1&0&1 \\ 0&1&48/32
    \end{array}}\right]
\end{equation*}
Thus, $x_1=1$ and $x_2=48/32$.
\end{example}
\section{Linear least squares}
\textbf{Problem:} Let $\vect{A}$ be an $m\times n$ matrix, $\vect{x}$ be an $n\times 1$ matrix and b be an $m\times 1$ matrix. Solve the matrix equation $\vect{A}\vect{x}=\vect{b}$.\\
 
\textbf{Solution:} If $m=n$, we can use three methods mentioned in section \ref{linear-eq}. However, if $m>n$, the solution usually does not exist. In that case, if $\dt{\vect{A}} \neq 0$, then 

\begin{equation*}
\trans{A}\vect{A}\vect{x}=\trans{A}\vect{b}
\end{equation*}

\begin{equation}\label{least-square}
\vect{x}=\left( \trans{A}\vect{A} \right)^{-1} \trans{A}\vect{b}
\end{equation}

The matrix equation now can be solved with the minimum error, meaning $\norm{\vect{A}\vect{x}-\vect{b}}$ is minimum. Using formula \eqref{least-square} to solve a system of equations is called The method of linear least squares.

\begin{exercise}
Suppose we want to draw a best fitting line through three points (4,-2), (5,0), (5,-1), (6,4), (7,5) and (8,5) so a linear function $y=t+kx$ should be given. Determine this function by means of the Method of Least Squares (LSM). Perform calculations by SAGE then plot points and the line in the same coordinate system.
\end{exercise}

\begin{solution}\label{least-square}
The linear function $y=kx+t$ should satisfies the following system of equations with the minimum error:
\begin{equation}
\label{LSM-linear}
\begin{cases}
4k+t &= -2 \\
5k+t &= 0 \\
5k+t &= -1 \\
6k+t &= 4 \\
7k+t &= 5 \\
8k+t &= 5 
\end{cases}
\end{equation}
The equivalent matrix equation of \eqref{LSM-linear} is $\vect{A}\vect{x}=\vect{b}$, where
\[ \vect{A}=\smtrx{4,1\\5,1\\5,1\\6,1\\7,1\\8,1} \quad \vect{x}=\cvect{k,t} \quad \vect{b}=\cvect{-2,0,-1,4,5,5} \]
Using formula \eqref{least-square}, we now can perform calculations by SAGE as follow:
\begin{verbatim}
A=matrix([[4,1], [5,1], [5,1], [6,1], [7,1], [8,1]])
b=matrix([ [-2,0,-1,4,5,5] ]).T
x=(A.T*A).inverse() * (A.T*b)

k=x[0][0]
t=x[1][0]
z=var("z")

S=plot(k*z+t, (z,-1,9))
P = scatter_plot([[4,-2], [5,0], [5,-1], [6,4], [7,5], [8,5]])
show(S+P)
\end{verbatim}
\begin{tikzpicture}
\begin{axis}
[%The axis
    axis lines = middle,
    xlabel = {$x$}, ylabel = {$y$},
    xmin=-3,ymin=-3,xmax=10,ymax=6
]
\addplot [%The line
    domain=3:10, 
    color=red,
]
{131/65*x-129/13};
\addplot[color=blue,mark=square]%The points
coordinates {
(4,-2) (5,0) (5,-1) (6,4) (7,5) (8,5)
};
\end{axis}
\end{tikzpicture}
\end{solution}

\begin{exercise}
Suppose we want to draw a best 4th order polynomial line through 6 points $(7,9),(6,12),(4,4),(2,-1),(-1,0),(6,16)$. Determine this function by means of the Method of Least Squares (LSM). Perform calculations by SAGE and plot the points and the line in the same coordinate system.
\end{exercise}

\begin{solution}
We need to find the coefficients of the following polynomial
\[ y=mx^4+nx^3+px^2+qx+r \]
Substitue $x$ and $y$ to this polynomial, we obtain a system of equations:
\begin{equation*}
\begin{cases}
2401m+343n+49p+7q+r &=9\\
1296m+216n+36p+6q+r &=12\\
256m+64n+16p+4q+r &=4\\
16m+8n+4p+2q+r &=-1\\
m-n+p-q+r&=0\\
1296m+216n+36p+6q+r &=16
\end{cases}
\end{equation*}
,which is equivalent to the follwoing matrix equation
\[ \smtrx{2401,343,49,7,1\\1296,216,36,6,1\\256,64,16,4,1\\16,8,4,2,1\\1,-1,1,-1,1\\1296,216,36,6,1} \cvect{m,n,p,q,r} = \cvect{9,12,4,-1,0,16} \]
Using formula \eqref{least-square}, we now can perform calculations by SAGE as follow:
\begin{verbatim}
A=matrix([[2401,343,49,7,1],[1296,216,36,6,1],[256,64,16,4,1],
        [16,8,4,2,1],[1,-1,1,-1,1],[1296,216,36,6,1]])
b=matrix([[9,12,4,-1,0,16]]).T
x=(A.T*A).inverse() * (A.T*b) 

m=x[0][0]
n=x[1][0]
p=x[2][0]
q=x[3][0]
r=x[4][0]

z=var("z")
S=plot(m*z**4+n*z**3+p*z*z+q*z+r, (z,-2,8))
P = scatter_plot([[7,9],[6,12],[4,4],[2,-1],[-1,0],[6,16]])
show(S+P)
\end{verbatim}
\end{solution}