---
title: "MIT OCW 18.06SC Linear Algebra Unit 2: Least Squares, Determinants and Eigenvalues"
---

# <u>MIT OCW 18.06SC Linear Algebra - Unit 2 </u><br><span>Least Squares, Determinants and Eigenvalues</span>
###### tags: `mit_ocw`, `linear_algebra`, `note`

<style>
.markdown-body h1 > span:last-child{
font-size: 18pt;
float: right;
width: 100%;
text-align: right;
border-bottom: 1pt #EEE solid;
padding-bottom: 5pt;
margin-bottom: 5pt
}

.markdown-body h1{
border: none;
}

.markdown-body h2{
border-bottom: double #DC965A80 4px;
display: block;
position: relative;
width: 100%;
line-height: 15pt;
}

.markdown-body h2::after{
--size: 8pt;
content: '';
position: absolute;
right: 0;
width: 0;
height: 0;
border-style: solid;
border-width: 0 var(--size) var(--size) 0;
border-color: transparent khaki transparent transparent;
}

.markdown-body strong{
color: darkseagreen;
text-transform: uppercase;

}

.markdown-body{
tab-size: 2;
}
</style>

$$
\require{enclose}
\require{textmarcos}
\newcommand\hlight[1]{\enclose{roundedbox}[mathcolor=gold]{#1}}
\newcommand\bmat[1]{\begin{bmatrix}#1\end{bmatrix}}
\newcommand\vmat[1]{\begin{vmatrix}#1\end{vmatrix}}
\newcommand\inv[1]{#1^{\text{-}1}}
\newcommand\transpose[1]{#1^\textrm{T}}
\newcommand\colsp[1]{\mathrm{C}(#1)}
\newcommand\rowsp[1]{\colsp{\transpose{#1}}}
\newcommand\nulsp[1]{\mathrm{N}(#1)}
\newcommand\lnulsp[1]{\nulsp{\transpose{#1}}}
\newcommand\nobj[1]{#1_1,\ #1_2, \dots, #1_n}
\newcommand\ssssub[1]{{_{_{#1}}}}
\newcommand\ddstrike[1]{\enclose{downdiagonalstrike}{#1}}
$$

## Orthogonality
Two vectors, $\vec{a}, \vec{b}$ are called **Orthoganal** if $a^Tb=b^Ta=0$, denoted as $\vec{a}\perp\vec{b}$.

Among the 4 foundamental subspaces,
$$
\begin{align}
\colsp{A} &\perp \lnulsp{A} \\
\rowsp{A}&\perp \nulsp{A}
\end{align}
$$

## Projections

The projection of $\vec{b}$ on $\vec{a}$ is $\vec{p}$, which point $p$ is the closest point to $b$ on $a$.

Since $\vec{a} \perp (\vec{b}-x\vec{a})$, where $x$ is the scalor for $\vec{p}=x\vec{a}$,
$$
\begin{align}
\transpose{a}(b-xa)=0 &\Rightarrow x\transpose{a}a=\transpose{a}b \\
&\Rightarrow x=\frac{\transpose{a}b}{\transpose{a}a} \\
&\Rightarrow p=ax=a\frac{\transpose{a}b}{\transpose{a}a}
\end{align}
$$

## Solve Ax=b when b is out of C(A)
Instead, we project $\mathbf{b}$ to $\mathbf{p} \in \colsp{A}$ and try to solve $A\hat{\mathbf{x}}=\mathbf{p}$.

For $\{\nobj{\mathbf{a}}\}$ as basis of $\colsp{A}$, we know $\displaystyle\forall_{i\in [1\ ..\ \mathrm{rank}(A)]}:\mathbf{a}_i\cdot(\mathbf{b}-A\hat{\mathbf{x}})=0$, or simply,

$$
\begin{align}
\transpose{A}(\mathbf{b}-A\hat{\mathbf{x}})=0 &\Rightarrow \transpose{A}A\hat{\mathbf{x}}=\transpose{A}\mathbf{b} \\
&\Rightarrow \hat{\mathbf{x}}=\inv{(\transpose{A}A)}\transpose{A}\mathbf{b} \\
&\Rightarrow \mathbf{p}=A\hat{\mathbf{x}}=A\inv{(\transpose{A}A)}\transpose{A}\mathbf{b} \\
&\Rightarrow P=A\inv{(\transpose{A}A)}\transpose{A}
\end{align}
$$

## Projection Matrix
The **Projection Matrix** $P$ maps $\vec{b}$ to $\vec{p}$, or $p=Pb$,
For $\mathbb{R}^2$, we know $p=Pb=xa=\displaystyle\frac{a\transpose{a}}{\transpose{a}a}b$, so
$$
P=\displaystyle\frac{a\transpose{a}}{\transpose{a}a}
$$

For higher dimension spaces,
$$
P = A\inv{(\transpose{A}A)}\transpose{A}.
$$
Projection matrices satisfies that $\begin{cases}\transpose{P}=P \\ P^2=P\end{cases}$

## Component of vector b
Any vector $\vec{b}$ would have a component $\vec{p}$ (projected onto $\colsp{A}$) and a component $\vec{e}$ (projected onto $\lnulsp{A}$):
$$
\begin{align}
\vec{e}=\vec{b}-\vec{p} \Rightarrow \vec{e}&=I\vec{b}-P\vec{b} \\
&= (I-P)\vec{b} \\
&= P_{\lnulsp{A}}\vec{b}
\end{align}
$$

## The Least Square
In **Linear Regression**, we'd like to find the closest line $y=c_nx^n+c_{n-1}x^{n-1}+\dots+c_0x^0$ to a set of points $\{(x_1, y_1), (x_2, y_2) \dots (x_n, y_n)\}$; *closest* means the lowest sum of error(distance on $y$) from the point to the line, a.k.a., minimize the value $\|{\mathbf{b}-A\mathbf{x}}\|^2=\|\mathbf{e}\|^2$.

The system is equvalent to finding a solution for the set of equations, or the equation $A\mathbf{x=b}$, ==but unsolvable==:
$$
\begin{array}{ccc}
& & A & \mathbf{x} & & \mathbf{b} \\
\begin{cases}
c_nx_1^n+c_{n-1}x_1^{n-1}+&\dots&+c_0x_1^0 = y_1 \\
c_nx_2^n+c_{n-1}x_2^{n-1}+&\dots&+c_0x_2^0 = y_2 \\
&\vdots& \\
c_nx_n^n+c_{n-1}x_n^{n-1}+&\dots&+c_0x_n^0 = y_n
\end{cases} & \Rightarrow & \bmat{x_1^n & x_1^{n-1} & \dots & x_1^1 & 1 \\ x_2^n & x_2^{n-1} & \dots & x_2^1 & 1 \\ \vdots & \vdots & \ddots & \vdots\\ x_n^n & x_n^{n-1} & \dots & x_n^1 & 1} & \bmat{c_n \\ c_{n-1} \\ \vdots \\ c_0} & = & \bmat{y_1 \\ y_2 \\ \vdots \\ y_n}
\end{array}
$$

We try to obtain the nearest values $\mathbf{p}=\{\nobj{p}\}$, and the errors $\mathbf{e}=\{\nobj{e}\}$, which $\mathbf{p}$ is the projection of $\mathbf{b}$ onto $\colsp{A}$ and $\mathbf{e}$ is the projection of $\mathbf{b}$ onto $\lnulsp{A}$.

Using the equation $\transpose{A}A\hat{\mathbf{x}}=\transpose{A}\mathbf{b}$ along $A\hat{\mathbf{x}}=\mathbf{p}$, we could obtain $\hat{\mathbf{x}}=\bmat{\hat{c}_n \\ \hat{c}_{n-1} \\ \vdots \\ \hat{c}_0}$ and thus the closest line $y=\hat{c}_nx^n+\hat{c}_{n-1}x^{n-1}+\dots+\hat{c}_0x^0$, $\mathbf{p}$ and $\mathbf{e}$.

## Orthonormal Vectors
The vectors $\nobj{\vec{q}}$ are said to be **orthonormal** if
$$
\begin{cases}
\transpose{q}_iq_j = 0\ \ \ \text{ if }\ \ \ i\neq j \\
\transpose{q}_iq_j = 1\ \ \ \text{ if }\ \ \ i=j
\end{cases}
$$

That is, the vectors are **unit vectors** whose length equals $1$ and are orthogonal to each others.

Orthonormal vectors are always independent.

## Orthonormal Matrix
If vectors in matrix $Q=\bmat{| & | & & | \\ q_1 & q_2 & \dots & q_n \\ | & | & & |}$ are orthonormal, then $\transpose{Q}Q=I$.

If a orthonormal matrix is a *square*, we then calls it an **orthogonal matrix**.
They also satisfies $\transpose{Q}=\inv{Q}$.

When computing a projection matrices, orthonormal matrices helps because $P=Q\inv{(\transpose{Q}Q)}\transpose{Q}=Q\transpose{Q}$ since $\inv{(\transpose{Q}Q)}=I$.

:::info
$$
\bmat{1 & 1 \\ 1 & -1}\ \ \bmat{1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1}
$$

The above matrices type are called **Hadamard matrix**, which has properties that
+ All columns are orthogonal
+ Consists by only of $1$ and $-1$

Since its clear that all vectors forming the matrix has the same length, by dividing the whole maatrix by the length we could also get a orthogonal matrix.
:::

## Gram-Schmidt
For a set of independent vectors $\{\nobj{\mathbf{v}}\}$, the set of orthonormal vectors $\{\nobj{\mathbf{q}}\}$ that ==spans the same space== can be calculated by:
$$
\begin{cases}
\mathbf{q}_i &= \displaystyle\frac{\mathbf{u}_i}{||\mathbf{u}_i||} \\
u_i &= \mathbf{v}_i - \displaystyle\sum^{n-1}_{t=1}\frac{\transpose{\mathbf{u}_t}\mathbf{v}_i}{\transpose{\mathbf{u}_t}\mathbf{u}_t}\mathbf{u}_t
\end{cases}
$$

Each terms within the sum calculates the part of the vector which is not orthogonal to $\mathbf{q}_t$.

:::spoiler <u>Click to view example</u>
Say we have 3 independent vectors $\mathbf{a}$, $\mathbf{b}$ and $\mathbf{c}$, which corresponds to orthogonal vectors $\mathbf{A}$, $\mathbf{B}$ and $\mathbf{C}$ that *spans the same space*.

Then the orthonormal basis of said space would be $\{q_a=\displaystyle\frac{\mathbf{A}}{||\mathbf{A}||}, q_b=\displaystyle\frac{\mathbf{B}}{||\mathbf{B}||}, q_c=\displaystyle\frac{\mathbf{C}}{||\mathbf{C}||}\}$

1. First, let $\mathbf{A} = \mathbf{a}$
2. Then, $\mathbf{B} = \mathbf{b} - \displaystyle\frac{\transpose{\mathbf{A}}\mathbf{b}}{\transpose{\mathbf{A}}\mathbf{A}}\mathbf{A}$
3. Then, $\mathbf{C} = \mathbf{c} - \displaystyle\frac{\transpose{\mathbf{A}}\mathbf{c}}{\transpose{\mathbf{A}}\mathbf{A}}\mathbf{A}-\displaystyle\frac{\transpose{\mathbf{B}}\mathbf{c}}{\transpose{\mathbf{B}}\mathbf{B}}\mathbf{B}$
:::

## A=QR
An matrix $A$ could be decomposite as $A=QR$, which $Q$ is the orthonormal matrix and $R$ is an upper triangle matrix which is built as:
$$
R_{ij} = \mathbf{a}_j \cdot \mathbf{q}_i
$$

For example,
$$
\begin{array}{ccc}
A & & Q & R \\
\bmat{1 & 2 & 4 \\ 0 & 0 & 5 \\ 0 & 3 & 6} & = &
\bmat{1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0} &
\bmat{1 & 2 & 4 \\ 0 & 3 & 6 \\ 0 & 0 & 5}
\end{array}
$$

## Determinant
Every square matrix has an value associated to it, called its **determinant**,
denoted as $\textrm{det}(A)$ or $|A|$.

:::info
> Not in the lecture

Viewing a square matrix as a _linear transformation_ for a space, ==the determinant is how an region would be changed by some factor==. For example, the unit square $\bmat{1 & 0 \\ 0 & 1}$ under the transformation $A=\bmat{-1 & -1 \\ 1 & -1}$ would have an area of $2 = \textrm{det}(A)$ after the transformation.
:::

Assuming $A$ as an $n\times n$ matrix, the following properties are followed ($i \neq j$):
1. $\det(I) = 1$

2. $\begin{cases}A &=& \bmat{ & | & & | & \\ \cdots & \mathbf{c}_i & \cdots & \mathbf{c}_j & \cdots \\ & | & & | & } \\ A' &=& \bmat{ & | & & | & \\ \cdots & \mathbf{c}_j & \cdots & \mathbf{c}_i & \cdots \\ & | & & | & }\end{cases} \implies \det(A) = -\det(A')$
3. $\begin{cases}A &=& \bmat{& | & \\ \cdots & \mathbf{c}_i & \cdots \\ & | &} \\ A' &=& \bmat{& | & \\ \cdots & t\mathbf{c}_i & \cdots \\ & | &}\end{cases}\implies \det(A')=t\det(A)$
4. $A = \bmat{& | & \\ \cdots & \mathbf{c}_i+\mathbf{v} & \cdots \\ & | &} \implies \det(A) = \begin{vmatrix}& | & \\ \cdots & \mathbf{c}_i & \cdots \\ & | &\end{vmatrix} + \begin{vmatrix}& | & \\ \cdots & \mathbf{v} & \cdots \\ & | &\end{vmatrix}$

----
From the above properties, we are able to derive the followings:

+ $\begin{cases}A &=& \bmat{ & | & & | & \\ \cdots & \mathbf{c}_i & \cdots & \mathbf{c}_j & \cdots \\ & | & & | & } \\ \mathbf{c}_i &=& \mathbf{c}_j \\ i &\neq& j \end{cases} \implies \det(A) = 0$
+ $\begin{cases}A &=& \bmat{ & | & & | & \\ \cdots & \mathbf{c}_i & \cdots & \mathbf{c}_j & \cdots \\ & | & & | & } \\ A' &=& \bmat{ & | & & | & \\ \cdots & \mathbf{c}_i & \cdots & \mathbf{c}_j - t\mathbf{c}_i & \cdots \\ & | & & | & } \end{cases} \implies \det(A) = \det(A')$
+ $\begin{cases}A &=& \bmat{& | & \\ \cdots & \mathbf{c}_i & \cdots \\ & | &} \\ \mathbf{c}_i &=& 0 \end{cases} \implies \det(A)=0$
+ $U = \bmat{d_1 & \ast & \ast & \cdots & \ast \\ 0 & d_2 & \ast & \cdots & \ast \\ 0 & 0 & d_3 & \cdots & \ast \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & d_n} \implies \det(U)=d_1d_2d_3\ldots d_n$
+ $A \text{ is singular} \implies \det(A)=0$
+ $\det(AB)=\det(A)\det(B)$
+ $\det(A) = \det(\transpose{A})$

:::info
+ Matrices are invertible only when $\det (A) != 0$
+ $\det (P)$ is generally $0$, but only when $P = I$ then $\det(P) = 1$:
- Since $P^2 = P$, we know $\det(A^2) = \det(A)$ but also $\det(A^2) = \det(A)\det(A)$,
thus $k^2 = k$ only when $k \in \{0, 1\}$.
- If $\det(A) = 0$, $P$ is trivil
- If $\det(A) = 1$, \begin{align} &\color{#D9EDF7}{\Rightarrow} P^2 = P \\ &\Rightarrow P^2\inv{P} = p\inv{P} \\ &\Rightarrow P = I \end{align}
:::

## Formula of Determinants
For $2\times 2$ matrices, the formula could be obtained by:

$$
\begin{align}
\vmat{a & b \\ c & d} &= \vmat{a & 0 \\ c & d}+\vmat{0 & b \\ c & d}
\\
&= \ddstrike{\vmat{a & 0 \\ c & 0}} + \vmat{a & 0 \\ 0 & d} + \vmat{0 & b \\ c & 0} + \ddstrike{\vmat{0 & b \\ 0 & d}}
\\
&= \vmat{a & 0 \\ 0 & d} + \bigg(-\vmat{c & 0 \\ 0 & b}\bigg)
\\
&= ad\vmat{1 & 0 \\ 0 & 1}-bc\vmat{1 & 0 \\ 0 & 1} = ad-bc
\end{align}
$$

Simular steps could be also use to derive $3 \times 3$ matrices.

## Big Formula For Determinant of Any Square Matrix
+ $S_n$ being ==the set of all series of number that is a permutation of $[1 .. n]$
+ $\text{sp}(\omega)$ denoting how many swaps is required to produce the permutation $\omega$

The formula could be defined as:
$$
\det(A)=\displaystyle\sum_{\omega\ \in\ S_n}(-1)^{\text{sp}(\omega)}a^{}_{1\omega^{}_{_{1}}}a^{}_{2\omega^{}_{_{2}}}\ldots a^{}_{n\omega^{}_{_{n}}}
$$

<br>

## Determinant Formula Using Cofactors
For any one $i \in [1..n]$, where $A'$ is the matrix produced by deleting row $i$ and col $j$ of $A$,
$$
\det(A) = \displaystyle\sum^{n}_{j = 1}(-1)^{i+j}a_{ij}\det(A')
$$

Or in short, summing the **cofactor** times entry of any row/column.

## Formula for inverse of matrix A
The formula for the inverse of an $n\times n$ matrix $A$ is:
$$
\inv{A} = {1\over \det(A)}\transpose{C}
$$

Where $C$ is the **cofactor matrix** that:
$$
c_{ij} = \text{cofactor of } a_{ij}
$$

To verify the formula, we could check if $A\transpose{C}=\det(A)$ is true. $A\transpose{C}=\displaystyle\sum^{n}_{j = 1}a_{1j}c_{j1}$ which is exatly the cofactor formula for calculating the determinant of $A$.

## Cramer's Rule
$$
A\mathbf{x}=\mathbf{b} \rightarrow \mathbf{x}=\inv{A}\mathbf{b} = {1\over \det(A)}\transpose{C}\mathbf{b}
$$
Since summingup cofactors at certain rows multiplied by some numbers is exactly what we do to obtain the result, the result of $\transpose{C}b$ for each element in $\mathbf{x}$ could actually be seen as $\det(B)$s, where
$$
B_k = \bmat{| & & | & | & | & & | \\
\mathbf{a}_1 & \cdots & \mathbf{a}_{k-1} & \mathbf{b} & \mathbf{a}_{k + 1} & \cdots & \mathbf{a}_n \\
| & & | & | & | & & |
}
$$

And thus,
$$
\mathbf{x}_i = \frac{\det{B_i}}{\det(A)}.
$$

## det(A) As Volume Surrounded By Vectors
The value of $\det(A)$ is exactly the volume surrounded by the vectors of the matrix, since they satisfies all the properties of determinants. For example in 2D:
1. $\det(I) = \bmat{1 & 0 \\ 0 & 1} = 1$, that is, a unit square.
2. Swapping the rows/columns doesn't change the absolute value of the determinant, neither changes the volume.
3. Multiplying the legth of any vector simply creates a rectangle, which the volume grows with the same factor.
4. Adding vectors acts as dividing a big paralellpiped into 2 little ones, as the figure show:

## Eigenvalue And Eigenvectors
A matrix $A$ acts on a vector $\mathbf{x}$ like an function, producing another vector $A\mathbf{x}$.

An **eigunvector** is the vector who's corresponding prodect is ==parallel== to itself, or in equation,
$$
A\mathbf{x} = \lambda\mathbf{x}
$$

which $\lambda$ is the **eigenvalue** to the eigenvector, which is the scalor to $\mathbf{x}$ that has the same effect as $A$.

+ Eigenvalues could be complex.
+ Eigenvalues are not always distinct.
+ ==Eigenvalues of a triangular matrix is exactly the diagonal entries==.

### Cayley-Hamiliton Therom
Let $p(\lambda)$ be a function for $\lambda$ so that
$$
p(\lambda) = det(\lambda I - A) = c_n\lambda^n + c_{n-1}\lambda^{n-1} + \ldots + c_1\lambda + c_0
$$

Then $p(A) = c_nA^n + c_{n-1}A^{n-1} + \ldots + c_1A + I = 0$

### Relationship When Operations On Original Matrix
| Original Matrix | $A$ | $\inv{A}$ | $A^2$ | $A - kI$ | $ka$ |
| :-: | :-: | :-: | :-: | :-: | :-: |
| **Eigenvalue** | $\lambda$ | $\inv{\lambda}$ | $\lambda^2$ | $\lambda - k$ | $k\lambda$ |
| **Eigenvector** | $\mathbf{v}$ | $\mathbf{v}$ | $\mathbf{v}$ | $\mathbf{v}$ | $\mathbf{v}$ |

### λ = 0
If the eigenvalue is zero then $a\mathbf{x} = 0\mathbf{x} = 0$.
+ *The eigenvectors to eigenvalue zero makes up the nullspace of $A$*.
+ If $A$ is *singular*, $0$ is one of the eigenvalue to $A$.

### Trace
The **Trace** of a matrix is the sum of diagonal entries:
$$
\textrm{Trace}(A_{n\times n})=\displaystyle\sum^{n}_{i = 1}a_{i, i}
$$

## The Characteristic Equation det(A-λI) = 0
To find the eigenvalues,
$$
\begin{align}
A\mathbf{x} &= \lambda\mathbf{x} \\
\Rightarrow (A - \lambda I)\mathbf{x} &= 0
\end{align}
$$

the matrix $A-\lambda I$ must be singular inorder for the vector $\mathbf{x}$ to have other value than zero. In other words, ==$\det(A-\lambda I) = 0$==.

Solving the equation would result in $n$ eigenvalues, and by finding the basis of the nullspace of each $A-\lambda_k I$ we could find the corresponding eigenvectors.

:::info
Since $\transpose{(A - \lambda I)} = \transpose{A} - \lambda I$, eigenvalues for $A$ are also eigenvalues for $\transpose{A}$.
:::

## Diagonolizations
A matrix $A$ can be **diagonolized** into the form $AS = \Lambda S$, or $\inv{S}AS = \Lambda$, or $A = $S\Lambda \inv{S}$, where:
+ $S$ is the matrix whose columns are the *eigenvectgors*.
+ $\Lambda$ is the diagonal matrix where the entries are all of the *eigenvalues*

Since $S$ must be invertiable, ==the eigenvalues must be all distinct.==

### Power of matrix A
For $A^k$, we know the eigenvector stays the same and only the eigenvalues get powered:
$$
\begin{align}
A^k &= (S\Lambda \inv{S})^k \\
&= S\Lambda \ddstrike{\inv{S}S}\Lambda \ddstrike{\inv{S}S }\ldots \ddstrike{\inv{S}S}\Lambda \inv{S} \\
&= S\Lambda^{k}\inv{S}
\end{align}
$$

## First Order Difference Equation
For a vector $\mathbf{u}$, the equation $\mathbf{u}_{k + 1} = A\mathbf{u}_{k}$ is a **First Order Difference Equation** and the solution for $\mathbf{u}_k$ is $A^{k}\mathbf{u}_0$.
The solution could be decomposed as (Where $\mathbf{x}_i$ are the eigenvectors for A):

$$
\begin{align}
\mathbf{u}_0&= c_1\mathbf{x}_1 + c_2\mathbf{x}_2 + \ldots + c_n\mathbf{x}_n \\
\Rightarrow A\mathbf{u}_0&= c_1\lambda_1\mathbf{x}_1 + c_2\lambda_2\mathbf{x}_2 + \ldots + c_n\lambda_n\mathbf{x}_n \\
\Rightarrow \mathbf{u}_k &= A^k\mathbf{u}_0 = c_1\lambda_1^k\mathbf{x}_1 + c_2\lambda_2^k\mathbf{x}_2 + \ldots + c_n\lambda_n^k\mathbf{x}_n \\
&= \Lambda^k S\mathbf{c}
\end{align}
$$

### Steps: Finding The Solution Of The Fibonacci Sequence
1. Let $\mathbf{u}_i = \bmat{F_i \\ F_{i - 1}}$, we get the first order difference equation:
$$
\mathbf{u}_{k + 1} = \bmat{F_{k + 2} \\ F_{k + 1}} = A\mathbf{u}_{k} = A\bmat{F_{k + 1} \\ F_{k}} = \bmat{1 & 1 \\ 1 & 0}\bmat{F_{k + 1} \\ F_{k}}
$$

2. From $A = \bmat{1 & 1 \\ 1 & 0}$ we find its eigenvalues $\lambda_1, \lambda_2$:
$$
\begin{align}
&\color{white}{\Rightarrow}\det(A - \lambda I) = \vmat{1 - \lambda & 1 \\ 1 & -\lambda} = \lambda^2 - \lambda - 1 = 0 \\
&\Rightarrow \lambda_1 = {1 + \sqrt{5} \over 2}, \lambda_2 = {1 - \sqrt{5} \over 2}
\end{align}
$$

3. Find the eigenvectors by solving the basis of each $\nulsp{A-\lambda I}$
$$\displaystyle
A - \lambda_1 I = \bmat{1 - \sqrt{5} \over 2 & 1 \\ 1 & \frac{1+\sqrt{5}}{-2}} \rightarrow \bmat{1 - \sqrt{5} \over 2 & 1 \\ 0 & \color{white}{1\over 2}0\color{white}{1\over 2}} \Rightarrow \nulsp{A - \lambda_1 I} = x_2\bmat{-2 \over 1 - \sqrt{5} \\ 1} = x_2\bmat{1 + \sqrt{5} \over 2 \\ 1} = x_2\bmat{\lambda_1 \\ 1} \Rightarrow \mathbf{x}_1 = \bmat{\lambda_1 \\ 1} \\
A - \lambda_2 I = \bmat{1 + \sqrt{5} \over 2 & 1 \\ 1 & \frac{1-\sqrt{5}}{-2}} \rightarrow \bmat{1 + \sqrt{5} \over 2 & 1 \\ 0 & \color{white}{1\over 2}0\color{white}{1\over 2}} \Rightarrow \nulsp{A - \lambda_2 I} = x_2\bmat{-2 \over 1 + \sqrt{5} \\ 1} = x_2\bmat{1 - \sqrt{5} \over 2 \\ 1} = x_2\bmat{\lambda_2 \\ 1} \Rightarrow \mathbf{x}_2 = \bmat{\lambda_2 \\ 1}
$$

4. Find $(c_1, c_2)$ for $\displaystyle\mathbf{v}_0 = \bmat{F_1 \\ F_0} = \bmat{1 \\ 0} = c_1\mathbf{x}_1 + c_2\mathbf{x}_2$, we get $\displaystyle(c_1, c_2) = ({1 \over \sqrt{5}}, -{1 \over \sqrt{5}})$

5. Finally, from $\mathbf{u}_k = \bmat{F_{k + 1} \\ F_{k}} = c_1\lambda_1^k\mathbf{x_1} + c_2\lambda_2^k\mathbf{x}_2$, we get: $$\displaystyle F_k = {1 \over \sqrt{5}}\Big({1 + \sqrt{5} \over 2}\Big)^k - {1 \over \sqrt{5}}\Big({1 - \sqrt{5} \over 2}\Big)^k$$

## First Order Differential Equations
The system over $t$:
$$
\begin{cases}
\displaystyle\frac{du_1}{dt} &= -u_1 + 2u_2 \\
\displaystyle\frac{du_2}{dt} &= u_1 - 2u_2 \\
u_1(0) &= 1 \\
u_2(0)& = 0
\end{cases}
$$

is a system of **first order differential equation** and can be written into the vector form:
$$
\displaystyle\frac{d\mathbf{u}}{dt} = A\mathbf{v} = \bmat{-1 & 2 \\ 1 & -2}\bmat{u-1 \\ u_2}, \mathbf{u}(0) = \bmat{1 \\ 0}
$$

### Steps: Solving a First Order Differential Equation
1. Transform the equation into the form $\frac{d\mathbf{u}}{dt} = A\mathbf{v}$
$$
\begin{cases}
\displaystyle\frac{du_1}{dt} &= c_{1, 1}u_1 + c_{1, 2}u_2 + \ldots + c_{1, n}u_n\\
\displaystyle\frac{du_2}{dt} &= c_{2, 1}u_1 + c_{2, 2}u_2 + \ldots + c_{2, n}u_n\\
&\vdots \\
\displaystyle\frac{du_n}{dt} &= c_{n, 1}u_1 + c_{n, 2}u_2 + \ldots + c_{n, n}u_n
\end{cases} \Rightarrow
\begin{cases}
\displaystyle\frac{d\mathbf{u}}{dt} = \bmat{c_{1, 1} & c_{1, 2} & \cdots & c_{1, n} \\ c_{2, 1} & c_{2, 2} & \cdots & c_{2, n} \\ \vdots & \vdots & \ddots & \vdots \\ c_{n, 1} & c_{n, 2} & \cdots & c_{n, n}}\bmat{u_1 \\ u-2 \\ \vdots \\ u_n} \\
\mathbf{u}(0) = \bmat{u_1(0) \\ u_2(0) \\ \vdots \\ u_n(0)}
\end{cases}
$$

2. Find the eigenvalues $\nobj{\lambda}$ and the corresponding eigenvectors $\nobj{\mathbf{x}}$.
3. The general solution to the system should be:
$$
\mathbf{u}(\mathrm{t}) = c_1e^{\lambda_1\mathrm{t}}\mathbf{x}_1 + c_2e^{\lambda_2\mathrm{t}}\mathbf{x}_2 + \ldots + c_ne^{\lambda_1\mathrm{t}}\mathbf{x}_n
$$

4. Using $\mathbf{u}(0)$, plug in $t = 0$ a.k.a. $S\mathbf{c} = \mathbf{u}(0)$, to find $\nobj{c}$:
$$
\bmat{u_1(0) \\ u_2(0) \\ \vdots \\ u_n(0)} = c_1\mathbf{x}_1 + c_2\mathbf{x}_2 + \ldots + c_n\mathbf{x}_n
$$

### Steps: Diagonalize The System
5. Set another vector $\mathbf{v}$ so that $\mathbf{u} = S\mathbf{v}$, which $S=\bmat{| & | & & | \\\mathbf{x}_1 & \mathbf{x}_2 & \cdots & \mathbf{x}_n \\ | & | & & | }$:
$$
\begin{align}
S\frac{d\mathbf{v}}{dt} &= AS\mathbf{v} \\
\Rightarrow \frac{d\mathbf{v}}{dt} &= \inv{S}AS\mathbf{v} = \Lambda\mathbf{v}
\end{align}
$$

6. We now get another general solution for the system:
$$
\begin{cases}
\mathbf{v}(\mathrm{t}) &= e^{\Lambda\mathrm{t}}\mathbf{v}(0) \\
\mathbf{u}(\mathrm{t}) &= Se^{\Lambda\mathrm{t}}\inv{S}\mathbf{v}(0) = e^{A\mathrm{t}}\mathbf{u}(0)\\
\end{cases}
$$

## Exponential Of A Matrix
The exponential of a matrix $A$, using infinity could be written as
$$
\begin{align}
e^{A\mathrm{t}} &= \displaystyle\sum^{\infty}_{n = 0} \frac{(At)^n}{n!} = I + At + \frac{(At)^2}{2!} + \frac{(AT)^3}{3!} + \ldots \\
&= S\inv{S} + S\Lambda\inv{S}t + \frac{S\Lambda^2\inv{S}}{2!}t^2 + \frac{S\Lambda^3\inv{S}}{3!}t^3 + \ldots \\
&= Se^{\Lambda t}\inv{S}
\end{align}
$$

Where could be easily calculated since
$$
e^{\Lambda t} = \bmat{e^{\lambda_1\mathrm{t}} & 0 & \cdots & 0 \\ 0 & e^{\lambda_2\mathrm{t}} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & e^{\lambda_n\mathrm{t}}}
$$

## Higher Order Differential Equations
For higher order systems $y^{(n)} + b_{n - 1}y^{(n - 1)} + \ldots + b_1y' + b_0y = 0$, simply setup $\mathbf{u}$ so the system turns into a first order system:
$$
\mathbf{u} = \bmat{y^{(n - 1)} \\ y^{(n - 2)} \\ \vdots \\ y' \\ y} \Rightarrow \mathbf{u}' = A\mathbf{u} = \bmat{-b_{n - 1} & -b_{n - 2} & \cdots & -b_1 & -b_0 \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0}\bmat{y^{(n - 1)} \\ y^{(n - 2)} \\ \vdots \\ y' \\ y}
$$

## Markov Matrix
A **Markov matrix** is a matrix whose each columns adds up to $1$. For example,
$$
M = \bmat{0.5 & 0.1 & 0.13 \\ 0.25 & 0.09 & 0.44 \\ 0.25 & 0.81 & 0.43}
$$
+ $1$ is always an eigenvalue for a markov matrix $M$.
+ For all eigenvalues of $M$, $|\lambda_{M}| \leq 1$.
+ $M^2$ is still a markov matrix.

### Steps: Finding The Equation For A Changing System Via Markov Matrix
1. Define the system using the equation $\mathbf{u}_{k + 1} = A\mathbf{u}_k$ where $A$ is the markov matrix $M$.
$$
\begin{array}{ccc}
\mathbf{u}_{k + 1} & & M & \mathbf{u}_k \\
\bmat{u'_1 \\ u'_2 \\ \vdots \\ u'_n} & = & \bmat{m_{1, 1} & m_{1, 2} & \cdots & m_{1, n} \\ m_{2, 1} & m_{2, 2} & \cdots & m_{2, n} \\ \vdots & \vdots & \ddots & \vdots \\ m_{n, 1} & m_{n, 2} & \cdots & m_{n, n}} & \bmat{u_1 \\ u_2 \\ \vdots \\ u_n}
\end{array}
$$

2. Find the eigenvalues $\nobj{\lambda}$ and the corresponding eigenvectors $\nobj{\mathbf{x}}$
3. Use the property that when eigenvectors of $M$ are independent (*a.k.a., all eigenvalues are distinct*), $\mathbf{u}_k = A^k\mathbf{u}_0 = c_1\lambda_1^k\mathbf{x}_1 + c_2\lambda_2^k\mathbf{x}_2 + \ldots + c_n\lambda_n^k\mathbf{x}_n$, with $k=0$ to solve $\nobj{c}$:
$$
\mathbf{u}_0 = c_1\mathbf{x}_1 + c_2\mathbf{x}_2 + \ldots + c_n\mathbf{x}_n
$$

## Orthonormal Basis
For a set of orthonormal basis $\nobj{\mathbf{n}}$, we can write any vector $\mathbf{v}$ as the form:
$$
\mathbf{v} = c_1\mathbf{q}_1 + c_2\mathbf{q}_2 + \ldots + c_n\mathbf{q}_n
$$

Where for any $i \in [1..n]$, since $\transpose{\mathbf{q}_i}\mathbf{q}_j = \begin{cases}1 \text{ if } i = j \\ 0 \text{ if } i \neq j\end{cases}$,
$$
\transpose{\mathbf{q}_i}\mathbf{v} = c_1\transpose{\mathbf{q}_i}\mathbf{q}_1 + c_2\transpose{\mathbf{q}_i}\mathbf{q}_2 + \ldots + c_n\transpose{\mathbf{q}_i}\mathbf{q}_n = x_i
$$

Then we can say in matrix terms,
$$
\bmat{| & | & & | \\ \mathbf{q}_1 & \mathbf{q}_2 & \cdots & \mathbf{q}_n \\ | & | & & |}\bmat{c_1 \\ c_2 \\ \vdots \\ c_n} = Q\mathbf{c} = \mathbf{v} \\
\Rightarrow x = \inv{Q}\mathbf{v} = \transpose{Q}\mathbf{v}
$$