---
title: Linear Algebra Note 3
tags: Linear Algebra, 線性代數, 魏群樹, 大學, 國立陽明交通大學, 筆記
---

# Linear Algebra Note 3

## Vector Spaces and Subspaces (2021.10.27~2021.11.3)

$A_{m \times n},\ rank(A) = r$
| |$R$ 的型式| r, m, n 的關係 | 矩陣種類 | 解的數量 |
|:------:|:---:|:---------------:|:-----------------------:|:-------------:|
| case 1 |$I$| $r = m,\ r = n$ | square & invertible | 1 |
| case 2 |$\left[\begin{array}{c} I\\ O\\ \end{array}\right]$| $r < m,\ r = n$ | tall & full column rank | 0 or 1 |
| case 3 |$\left[\begin{array}{c c} I & F\\ \end{array}\right]$| $r = m,\ r < n$ | wide & full row rank | $\infty$ |
| case 4 |$\left[\begin{array}{c c} I & F\\ O & O\\ \end{array}\right]$| $r < m,\ r < n$ | not full rank | 0 or $\infty$ |

- case 1
- Example
$\left\{\begin{array}{c}
x-y=2 \\
2x+y=7 \\
\end{array}\right.\to A = \left[\begin{array}{c c}
1 & -1 \\
2 & 1 \\
\end{array}\right] \to R = \left[\begin{array}{c c}
1 & 0 \\
0 & 1 \\
\end{array}\right] = I$

$A\vec{x} = \vec{b} \to R\vec{x} = \vec{b'} \implies I\vec{x} = \vec{b'} \\
\therefore A^{-1}(A\vec{x}) = A^{-1}\vec{b} \iff \vec{x_p} =A^{-1}\vec{b} = \vec{b'} \to \text{1 solution}$
For $\vec{X_n}$ , we solve $A\vec{x} = \vec{0}$ by setting $\vec{b} = \vec{0} \implies I\vec{x_n} = \vec{0}$
$\implies \vec{x_n} = \vec{0}$ and $K_n = \{ \vec{0} \} \to \text{1 solution}$

- case 2
- Example
$\left\{\begin{array}{c}
x-y=2 \\
2x+y=7 \\
2x-2y=4\ (or\ 6)
\end{array}\right.\to A = \left[\begin{array}{c c}
1 & -1 \\
2 & 1 \\
2 & -2 \\
\end{array}\right] \to R = \left[\begin{array}{c c}
1 & 0 \\
0 & 1 \\
0 & 0 \\
\end{array}\right] = \left[\begin{array}{c}
I \\
O \\
\end{array}\right]$

$A$ is $m \times n$ with $m > n$ , assume $r = n$ to make $A$ have full column rank

For a tall matrix $A$ with full column rank
1. All columns are pivot columns
2. No free variables , i.e. no special solutions
3. $\mathbb{K_H} = N(A) = \{ \vec{0} \}$
4. If $A\vec{x} = \vec{b}$ has 1 solution, then this is the only solution
- Example
$A = \left[\begin{array}{c c}
1 & 1 \\
1 & 2 \\
-2 & -3 \\
\end{array}\right],\ \vec{b} = \left[\begin{array}{c c}
b_1 \\
b_2 \\
b_3 \\
\end{array}\right] \\
\left[\begin{array}{c c|c}
1 & 1 & b_1 \\
1 & 2 & b_2 \\
-2 & -3 & b_3 \\
\end{array}\right] \to \left[\begin{array}{c c|c}
1 & 1 & b_1 \\
0 & 1 & b_2-b_1 \\
0 & -1 & b_3+2b_1 \\
\end{array}\right] \to \left[\begin{array}{c c|c}
1 & 0 & 2b_1-b_2 \\
0 & 1 & b_2-b_1 \\
0 & 0 & b_3+b_2+b_1 \\
\end{array}\right]$
1. To have a solution, we must have $b_1+b_2+b_3=0$
2. Full column rank $\implies$ all pivot variables and no free variables $\implies \mathbb{K_H} = \{ \vec{0} \}$
3. $\vec{x_p} = \left[\begin{array}{c}
2b_1-b_2 \\
b_2-b_1 \\
\end{array}\right] \to$ the only solution
- case 3
- Example
$\begin{split}\left\{\begin{array}{c}
x-y+z=2 \\
2x+y+z=7 \\
\end{array}\right.\to A = \left[\begin{array}{c c c}
1 & -1 & 1 \\
2 & 1 & 1\\
\end{array}\right] &\to \left[\begin{array}{c c}
1 & -1 & 1 \\
0 & 3 & -1 \\
\end{array}\right] \\
&\to R = \left[\begin{array}{c c}
1 & 0 & {2 \over 3} \\
0 & 1 & {-1 \over 3} \\
\end{array}\right] = \left[\begin{array}{c c}
I & F \\
\end{array}\right]\end{split}$

$A$ is $m \times n$ with $m < n$ , assume $r = m$ to make $A$ have full row rank

For a wide matrix $A$ with full row rank
1. $R$ has no zero rows, all rows have pivots
2. For every $\vec{b} \in \mathbb{R}^m$, $A\vec{x} = \vec{b}$ has at least 1 solution
3. $R$ has free columns, there are free variables $\implies$ infinitely many solutions
4. the number of free variables = $n-m$ = $n-r$
= the number of all unknowns - the number of pivots
= the number of special solutions in $N(A)$
- Example
$A = \left[\begin{array}{c c c}
1 & 1 & 1 \\
1 & 2 & -1 \\
\end{array}\right],\ \vec{b} = \left[\begin{array}{c}
3 \\
4 \\
\end{array}\right] \\
\left[\begin{array}{c c c|c}
1 & 1 & 1 & 3 \\
1 & 2 & -1 & 4 \\
\end{array}\right] \to \left[\begin{array}{c c c|c}
1 & 0 & 3 & 2 \\
0 & 1 & -2 & 1 \\
\end{array}\right] \\
\vec{x_p} = \left[\begin{array}{c}
2 \\
1 \\
0 \\
\end{array}\right],\ \vec{x_n} = \left[\begin{array}{c}
-3 \\
2 \\
1 \\
\end{array}\right],\ \vec{x} = \left[\begin{array}{c}
2 \\
1 \\
0 \\
\end{array}\right]+x_3\left[\begin{array}{c}
-3 \\
2 \\
1 \\
\end{array}\right] \\
\mathbb{K_H} = N(A) = \{c\left[\begin{array}{c}
-3 \\
2 \\
1 \\
\end{array}\right] \mid c \in \mathbb{R}\}$

- case 4
- Example
$\begin{split}\left\{\begin{array}{c}
x-y+z=2 \\
2x+y+z=7 \\
2x-2y+2z=4\ (or\ 5)
\end{array}\right.\to A = \left[\begin{array}{c c c}
1 & -1 & 1 \\
2 & 1 & 1 \\
2 & -2 & 2 \\
\end{array}\right] &\to \left[\begin{array}{c c c c}
1 & -1 & 1 \\
0 & 3 & -1 \\
0 & 0 & 0 \\
\end{array}\right] \\
&\to R = \left[\begin{array}{c c c c}
1 & 0 & {2 \over 3} \\
0 & 1 & {-1 \over 3} \\
0 & 0 & 0 \\
\end{array}\right] = \left[\begin{array}{c c}
I & F \\
O & O \\
\end{array}\right]\end{split}$

$A_{m \times n}$ is not full rank, $r<n$ and $r < m$
$R = \left[\begin{array}{c c}
I & F \\
O & O \\
\end{array}\right]$ has either no solution, or infinitely many solution depending the $\vec{b'}$ corresponding to the zero rows

### Independence, Basis, and Dimension

- Define (linear dependence): A set of vectors $\vec{u_1},\ \vec{u_2},\ \cdots,\ \vec{u_n}$ are linearly dependent if there exists $a_1,\ a_2,\ \cdots,\ a_n \in \mathbb{R}$ such that
1. $a_1,\ a_2,\ \cdots,\ a_n$ are not all zeros
2. $a_1\vec{u_1}+a_2\vec{u_2}+\cdots+a_n\vec{u_n} = \vec{0}$
- Define (linear independence): A set of vectors $\vec{u_1},\ \vec{u_2},\ \cdots,\ \vec{u_n}$ are linearly independent if they are not linearly dependent, i.e. $a_1\vec{u_1}+a_2\vec{u_2}+\cdots+a_n\vec{u_n} = \vec{0}$ if and only if $a_1=a_2=\cdots=a_n=0$
> linear dependence implies that some $\vec{u_1}$ can be expressed as a linear combination of others, e.g.
> $\begin{split}a_1\vec{u_1}+a_2\vec{u_2}+\cdots+a_n\vec{u_n} = \vec{0} \implies \vec{u_1} &= {1 \over a_1}(-a_2\vec{u_2}-\cdots-a_n\vec{u_n}) \\
> &= -{a_2 \over a_1}\vec{u_2}-\cdots-{a_n \over a_1}\vec{u_n}\end{split}$

- Example
$\vec{u_1} = \left[\begin{array}{c}
1 \\
2 \\
1 \\
\end{array}\right],\ \vec{u_2} = \left[\begin{array}{c}
0 \\
1 \\
0 \\
\end{array}\right],\ \vec{u_3} = \left[\begin{array}{c}
3 \\
5 \\
3 \\
\end{array}\right]$, check whether $a_1\vec{u_1}+a_2\vec{u_2}+a_3\vec{u_3} = \vec{0}$ has solutions other than $\left[\begin{array}{c}
a_1 \\
a_2 \\
a_3 \\
\end{array}\right] = \vec{0}$
i.e. to solve $\left[\begin{array}{c c c}
\vec{u_1} & \vec{u_2} & \vec{u_3} \\
\end{array}\right] \left[\begin{array}{c}
a_1 \\
a_2 \\
a_3 \\
\end{array}\right] = O\ (A\vec{x} = \vec{0})$
$\therefore \vec{u_1},\ \vec{u_2},\ \vec{u_3}$ are linearly independent if and only if $N(A) = \{ \vec{0} \}$
$\left[\begin{array}{c c c}
1 & 0 & 3 \\
2 & 1 & 5 \\
1 & 0 & 3 \\
\end{array}\right] \to \left[\begin{array}{c c c}
1 & 0 & 3 \\
0 & 1 & -1 \\
0 & 0 & 0 \\
\end{array}\right] \implies \left.\begin{array}{c}
a_1 = -3a_3 \\
a_2 = a_3 \\
\end{array}\right. \\
\begin{split}\implies N(A) &= \{\left[\begin{array}{c}
a_1 \\
a_2 \\
a_3 \\
\end{array}\right] \mid a_1 = -3a_3,\ a_2 = a_3,\ a_1,a_2,a_3 \in \mathbb{R}\} \\
&= \{\left[\begin{array}{c}
-3a_3 \\
a_3 \\
a_3 \\
\end{array}\right] \mid a_3 \in \mathbb{R}\} \\
&= \{a_3\left[\begin{array}{c}
-3 \\
1 \\
1 \\
\end{array}\right] \mid a_3 \in \mathbb{R}\}\end{split} \\
\therefore N(A) \not= \{ \vec{0} \}$
$\therefore \vec{u_1},\ \vec{u_2},\ \vec{u_3}$ are linearly dependent
- In $\mathbb{R}^m$, any set of $n$ vectors must be linearly dependent if $n>m$
Given a matrix $A_{m \times n} = [\vec{u_1}\ \vec{u_2}\ \cdots \ \vec{u_n}]$ containing $n$ column vectors $(n > m)$
There must be at least $(n-m)$ free variables
$\implies (n-m)$ special solutions
$\implies dim(N(A)) \ge n-m\ \ i.e.\ N(A) \not= \{ \vec{0} \}$
Also, when $A = [\vec{u_1}\ \vec{u_2}\ \cdots \ \vec{u_n}]$ is full column rank, i.e. $n=r \implies$ no free variables
when $r=n \implies n$ pivot variables $\implies 0$ free variables, $\therefore N(A) = \{ \vec{0} \}$

- Theorem
Let $\mathbb{V}$ be a vector space and $\vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n}$ be element in $\mathbb{V}$ s.t. they are linearly dependent. Then, for every $\vec{u}_{n+1} \in \mathbb{V}$, $\vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n},\ \vec{u}_{n+1}$ are also linearly dependent
> Addition of vectors does not affect dependent, but mught affect independent
> （可以讓線性獨立變線性相依，但沒辦法把線性相依變線性獨立）

- Define: A set of vectors $\vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n}$ spans a space $\mathbb{W}$ if their linear combinations fill the entire space
i.e. $span(\{ \vec{u_1}\ \vec{u_2}\ \cdots\ \vec{u_n} \}) = \mathbb{W}$
For $A = [\vec{u_1}\ \vec{u_2}\ \cdots\ \vec{u_n}],\ span(\{ \vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n} \}) = C(A) = \mathbb{W}$
- Example
$span(\{ \left[\begin{array}{c}
1 \\
0 \\
\end{array}\right],\ \left[\begin{array}{c}
0 \\
1 \\
\end{array}\right] \}) = \mathbb{R}^2 \\
span(\{ \left[\begin{array}{c}
1 \\
0 \\
\end{array}\right],\ \left[\begin{array}{c}
0 \\
1 \\
\end{array}\right],\ \left[\begin{array}{c}
4 \\
7 \\
\end{array}\right] \}) = \mathbb{R}^2 \\
\begin{split}span(\{ \left[\begin{array}{c}
1 \\
1 \\
\end{array}\right],\ \left[\begin{array}{c}
-1 \\
-1 \\
\end{array}\right] \}) &= \text{A line in } \mathbb{R}^2 \\
&= \{ c\left[\begin{array}{c}
1 \\
1 \\
\end{array}\right] \mid c \in \mathbb{R} \} \\
&= \text{A subspace of } \mathbb{R}^2\end{split}$

- Define (row space): The row space of a matrix $A_{m \times n}$ is the subspace of $\mathbb{R}^n$ spanned by the rows. The row space of $A$ is the column space of $A^T = C(A^T)$
- Define (Basis): A basis for a vector space $\mathbb{V}$ is a ==linearly independent subset== of $\mathbb{V}$ that spans $\mathbb{V}$
- Example
$\{ \left[\begin{array}{c}
1 \\
0 \\
\end{array}\right],\ \left[\begin{array}{c}
0 \\
1 \\
\end{array}\right]\}$ is a basis of $\mathbb{R}^2$
$\{ \left[\begin{array}{c}
1 \\
0 \\
\vdots \\
0 \\
\end{array}\right],\ \left[\begin{array}{c}
0 \\
1 \\
\vdots \\
0 \\
\end{array}\right],\ \cdots \ ,\left[\begin{array}{c}
0 \\
0 \\
\vdots \\
1 \\
\end{array}\right] \}$ is a basis of $\mathbb{R}^n$
- Example
$A = \left[\begin{array}{c c c}
1 & 0 & 0 \\
1 & 1 & 0 \\
1 & 1 & 1 \\
\end{array}\right]$
$A$ is invertible
$\iff n$ pivots = rank r (full rank)
$\iff$ no free variables
$\iff N(A) = \{ \vec{0} \}$
$\iff$ linearly indepedent
Also, $\forall \ \vec{b} \in \mathbb{R}^n,\ \exists \ \vec{x} \in \mathbb{R}^n\ s.t.\ A\vec{x}=\vec{b},\ \vec{x} = A^{-1}\vec{b}$
$i.e.\ \vec{b} = x_1\left[\begin{array}{c}
1 \\
1 \\
1 \\
\end{array}\right] + x_2\left[\begin{array}{c}
0 \\
1 \\
1 \\
\end{array}\right] + x_3\left[\begin{array}{c}
0 \\
0 \\
1 \\
\end{array}\right] \\
\therefore span(A) = \mathbb{R}^3$
> The vectors $\vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n}$ are a basis for $\mathbb{R}^n$ exactly when they form an $n \times n$ invertible matrix $\iff$ full rank $\iff$ linearly independent

- Theorem
Let $\mathbb{V}$ be a vector space and $\vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n} \in \mathbb{V}$ be a subset of $\mathbb{V}$
Then $\{ \vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n} \} = \mathbb{S}$ is a basis for $\mathbb{V}$ if and only if each $\vec{v} \in \mathbb{V}$ can be uniquely expressed as a linear combination of vector of $\mathbb{S} = \{ \vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n} \}$, i.e. $\vec{v} = a_1\vec{u_1}+a_2\vec{u_2}+\cdots+a_n\vec{u_n}$ for unique $a_1,\ a_2,\cdots,\ a_n \in \mathbb{R}$
- Proof
Let $\mathbb{S}$ be a basis for $\mathbb{V}$
If $\vec{v} \in \mathbb{V}$, then $\vec{v} \in \mathbb{V} = span(\mathbb{S})$
$\therefore \vec{v}$ is a linear combination of vectors in $\mathbb{S}$
Suppose this **NOT** unique
i.e. $\vec{v} = a_1\vec{u_1}+a_2\vec{u_2}+\cdots+a_n\vec{u_n} = b_1\vec{u_1}+b_2\vec{u_2}+\cdots+b_n\vec{u_n}$
Then $(a_1-b_1)\vec{u_1}+(a_2-b_2)\vec{u_2}+\cdots+(a_n-b_n)\vec{u_n} = \vec{O}\ ...①$
Since $\mathbb{S}$ is linearly independent (basis)
① possible only when $a_1-b_1=0,\ a_2-b_2=0,\ \cdots\ ,a_n-b_n=0$
$\iff a_1=b_1,\ a_2=b_2,\ \cdots\ ,a_n=b_n$
$\therefore \vec{v}$ is a unique linear combination of $\mathbb{S} = \{ \vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n} \}$

### How to find a basis of $C(A)$

- Example
$A = \left[\begin{array}{c c c}
1 & 1 & 1 \\
1 & 2 & 1 \\
\end{array}\right] \to R = \left[\begin{array}{c c c}
\color{red}{1} & 0 & 3 \\
0 & \color{red}{1} & -2 \\
\end{array}\right]$
free columns are linear combinations of pivot columns
otherwise, they must be able to create new pivot and become pivot columns themselves
since row operations will **NOT** affect this structure, the pivot columns of $A$ will be a basis for $C(A)$
> Although $N(A) = N(R),\ C(A) \not= C(R)$ in general
> But we can use the columns of $A$ that correspond to pivot columns of $R$ as a basis

- Theorem
Every basis for a same vector space must have the same number of vectors
i.e. for $\vec{v_1},\ \vec{v_2},\cdots,\ \vec{v_m}$ and $\vec{w_1},\ \vec{w_2},\cdots,\ \vec{w_n}$, both bases for $\mathbb{V}$,
$m = n =$ dimension of the vector space $\mathbb{V}$
- Proof
(Assume $n>m$) Since $\vec{v_1},\ \vec{v_2},\cdots,\ \vec{v_m}$ is a basis for $\mathbb{V}$, every element in $\mathbb{V}$ can be expressed as a linear combination of $\vec{v_1},\ \vec{v_2},\cdots,\ \vec{v_m}$
Particularly, let
$\left.\begin{array}{c}
\vec{w}_1 = a_{11}\vec{v_1}+a_{21}\vec{v_2}+\cdots+a_{m1}\vec{v_m} \\
\vec{w}_2 = a_{12}\vec{v_1}+a_{22}\vec{v_2}+\cdots+a_{m2}\vec{v_m} \\
\vdots \\
\vec{w}_n = a_{1n}\vec{v_1}+a_{2n}\vec{v_2}+\cdots+a_{mn}\vec{v_m} \\
\end{array}\right.$
$\iff \left[\begin{array}{c c c c}
\vec{w}_1 & \vec{w}_2 & \cdots & \vec{w}_n \\
\end{array}\right] = \left[\begin{array}{c c c c}
\vec{v}_1 & \vec{v}_2 & \cdots & \vec{v}_n \\
\end{array}\right] \left[\begin{array}{c c c c}
\vec{a}_{11} & \vec{a}_{12} & \cdots & \vec{a}_{1n} \\
\vec{a}_{21} & \vec{a}_{22} & \cdots & \vec{a}_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
\vec{a}_{m1} & \vec{a}_{m2} & \cdots & \vec{a}_{mn} \\
\end{array}\right]$
$A$ is a $m \times n$ (wide) matrix $\implies N(A) \not= \{ \vec{0} \}$
$\therefore \exists$ nonzero $\vec{x} \in \mathbb{R}^n$ s.t. $A\vec{x} = \vec{0} \implies VA\vec{x} = \vec{0} \implies W\vec{x} = \vec{0}$
$\therefore N(W) \not= \{ \vec{0} \}$ violating the fact that $\vec{w_1},\ \vec{w_2},\cdots,\ \vec{w_n}$ is a basis (vectors in a basis must be linearly independent)
similarly, we can prove that $n<m$ is impossible either, $\therefore n=m$
> we have learned $dim(N(A)) =$ the number of free variables = the number of special solutions
> Check that these special solutions form a basis for $N(A)$
> i.e. $N(A) = span\{special\ solutions\}$ where special solutions are linearly independent

- Example
1. $\mathbb{M}_a \triangleq \{ \text{All } 2 \times 2 \text{ real matrices} \} \to dim(\mathbb{M}_a) = 4$
one basis is $\{ \left[\begin{array}{c c}
1 & 0 \\
0 & 0 \\
\end{array}\right], \left[\begin{array}{c c}
0 & 1 \\
0 & 0 \\
\end{array}\right], \left[\begin{array}{c c}
0 & 0 \\
1 & 0 \\
\end{array}\right], \left[\begin{array}{c c}
0 & 0 \\
0 & 1 \\
\end{array}\right]\}$
2. $\mathbb{M}_b \triangleq \{ \text{All } n \times n \text{ real matrices} \} \to dim(\mathbb{M}_b) = n^2$
3. $\mathbb{M}_c \triangleq \{ \text{All } n \times n \text{ upper triangular matrices} \} \to dim(\mathbb{M}_c) = {n(n+1) \over 2}$

### Dimension of the Four Fundamental Subspaces

$A_{m \times n},\ rank(A)=r,\ R=EA,\ R \le m$

| Subspace | Dimension | $\in$ |
|:--------:|:---------:|:--------------:|
| $C(A)$ | $r$ | $\mathbb{R}^m$ |
| $C(A^T)$ | $r$ | $\mathbb{R}^n$ |
| $N(A)$ | $n-r$ | $\mathbb{R}^n$ |
| $N(A^T)$ | $n-r$ | $\mathbb{R}^m$ |


- Example
$\begin{split}A_{3 \times 5} = \left[\begin{array}{c c c c c}
1 & 3 & 5 & 0 & 7 \\
0 & 0 & 0 & 1 & 2 \\
1 & 3 & 5 & 1 & 9 \\
\end{array}\right] \to R &= \left[\begin{array}{c c c c c}
1 & 3 & 5 & 0 & 7 \\
0 & 0 & 0 & 1 & 2 \\
0 & 0 & 0 & 0 & 0 \\
\end{array}\right] \\
&= E_{32}E_{31}A &= \left[\begin{array}{c c c}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -1 & 1 \\
\end{array}\right]\left[\begin{array}{c c c}
1 & 0 & 0 \\
0 & 1 & 0 \\
-1 & 0 & 1 \\
\end{array}\right]A \\
&= EA &= \left[\begin{array}{c c c}
1 & 0 & 0 \\
0 & 1 & 0 \\
-1 & -1 & 1 \\
\end{array}\right]A\end{split}$
1. Find a basis for $C(A)$
$\begin{split}C(A) \not= C(R),\ dim(C(A)) &= dim(C(R)) \\
&= dim(span\{ \left[\begin{array}{c}
1 \\
0 \\
0 \\
\end{array}\right], \left[\begin{array}{c}
3 \\
0 \\
0 \\
\end{array}\right], \left[\begin{array}{c}
5 \\
0 \\
0 \\
\end{array}\right], \left[\begin{array}{c}
0 \\
1 \\
0 \\
\end{array}\right], \left[\begin{array}{c}
7 \\
2 \\
0 \\
\end{array}\right]\}) \\
&= dim(span\{ \left[\begin{array}{c}
1 \\
0 \\
0 \\
\end{array}\right], \left[\begin{array}{c}
0 \\
1 \\
0 \\
\end{array}\right] \}) = 2 = rank(A)\end{split}$
A basis for $C(A) = \{ \left[\begin{array}{c}
1 \\
0 \\
1 \\
\end{array}\right], \left[\begin{array}{c}
0 \\
1 \\
1 \\
\end{array}\right] \}$ (pivot columns in $A$)
2. Find a basis for $C(A^T)$
$\begin{split}dim(C(A^T)) &= \text{pivot columns in } A^T \\
&= \text{pivot rows in } A \\
&= dim(span\{ \left[\begin{array}{c}
1 \\
3 \\
5 \\
0 \\
7 \\
\end{array}\right], \left[\begin{array}{c}
0 \\
0 \\
0 \\
1 \\
2 \\
\end{array}\right] \}) = 2\end{split}$
3. Find a basis for $N(A)$
$\begin{split}N(A) = N(R) \to dim(N(A)) &= dim(N(R)) \\
&= \text{the number of special solutions} \\
&= \text{the number of free variables} = n-r\end{split}$
4. Find a basis for $N(A^T)$
$dim(N(A^T)) = m-r$

## Orthogonality (2021.11.3~2021.11.5)

- Define(Inner Product)
Let $\vec{v},\ \vec{w} \in \mathbb{R}^n,\ \vec{v} =\left[\begin{array}{c}
v_1 \\
v_2 \\
\vdots \\
v_n \\
\end{array}\right],\ \vec{w} =\left[\begin{array}{c}
w_1 \\
w_2 \\
\vdots \\
w_n \\
\end{array}\right]$, the inner product of $\vec{v}$ and $\vec{w}$ is defined as
$<\vec{v},\ \vec{w}> = \vec{v}^T\vec{w} = \sum\limits_{i = 0}^n v_iw_i = \sum\limits_{i = 0}^n w_iv_i = \vec{w}^T\vec{v} = <\vec{w},\ \vec{v}>$

- Define(norm)
The norm (length) of a vector $\vec{v}$ in $\mathbb{R}^n$ is
$\begin{Vmatrix}
\vec{v}
\end{Vmatrix} = \sqrt{<\vec{v},\ \vec{v}>} = \sqrt{\vec{v}^T\vec{v}} = \sqrt{v_1^2+v_2^2+\cdots+v_n^2}\ ,\ \begin{Vmatrix}
\vec{v}
\end{Vmatrix} = 0 \iff \vec{v} = \vec{0},\ i.e. v_i = 0$

- Define(Orthogonal): Two vectors $\vec{v}$ and $\vec{w}$ are orthogonal if $\vec{w}^T\vec{v}=0$, denoted by $\vec{v} \perp \vec{w}$
- Example
$\left[\begin{array}{c}
2 \\
0 \\
\end{array}\right]^T\left[\begin{array}{c}
0 \\
1 \\
\end{array}\right] = 2 \cdot 0 + 0 \cdot 1 = 0 \implies \left[\begin{array}{c}
2 \\
0 \\
\end{array}\right] \perp \left[\begin{array}{c}
0 \\
1 \\
\end{array}\right] \\
\left[\begin{array}{c}
1 \\
1 \\
\end{array}\right]^T\left[\begin{array}{c}
1 \\
-1 \\
\end{array}\right] = 1 \cdot 1 + 1 \cdot (-1) = 0 \implies \left[\begin{array}{c}
1 \\
1 \\
\end{array}\right] \perp \left[\begin{array}{c}
1 \\
-1 \\
\end{array}\right]$

- Theorem
$\vec{v}$ and $\vec{w}$ are orthogonal if and only if $\begin{Vmatrix}
\vec{v}+\vec{w}
\end{Vmatrix}^2 = \begin{Vmatrix}
\vec{v}
\end{Vmatrix}^2 + \begin{Vmatrix}
\vec{w}
\end{Vmatrix}^2$
- Proof
$\begin{split}\begin{Vmatrix}
\vec{v}+\vec{w}
\end{Vmatrix}^2 &= (\sqrt{<(\vec{v}+\vec{w}), (\vec{v}+\vec{w})>})^2 \\
&= <(\vec{v}+\vec{w}), (\vec{v}+\vec{w})> \\
&= (\vec{v}+\vec{w})^T(\vec{v}+\vec{w}) \\
&= (\vec{v}^T+\vec{w}^T)(\vec{v}+\vec{w}) \\
&= \vec{v}^T\vec{v} + \vec{v}^T\vec{w} + \vec{w}^T\vec{v} + \vec{w}^T\vec{w} \\
&= \vec{v}^T\vec{v} + 0 + 0 + \vec{w}^T\vec{w} = \begin{Vmatrix}
\vec{v}
\end{Vmatrix}^2+\begin{Vmatrix}
\vec{w}
\end{Vmatrix}^2\end{split}$

- Define(Orthogonal subspaces): Two subspaces $\mathbb{V}$ and $\mathbb{W}$ within a vector space and orthogonal if every $\vec{v} \in \mathbb{V}$ is orthogonal to every vector $\vec{w} \in \mathbb{W}$, i.e. $\forall\ \vec{v} \in \mathbb{V},\ \forall\ \vec{w} \in \mathbb{W},\ \vec{v} \perp \vec{w} \text{ as } \mathbb{V} \perp \mathbb{W}$

- Define(Orthogonal complement): The orthogonal complement of a subspace $\mathbb{V}$ contains every vector that is orthogonal to $\mathbb{V}$. The orthogonal complement of $\mathbb{V}$ is denoted by $\mathbb{V}^{\perp}$

- Theorem
$\mathbb{V}^{\perp}$ is a subspace
- Proof
1. $\forall\ \vec{v} \in \mathbb{V},\ \vec{v}^T\vec{0} = \vec{0} \implies \vec{0} \in \mathbb{V}^{\perp}$
2. Let $\vec{w}_1$ and $\vec{w}_2 \in \mathbb{V}^{\perp}$
$\forall\ \vec{v} \in \mathbb{V},\ \vec{v}^T\vec{w}_1=0,\ \vec{v}^T\vec{w}_2=0 \\
\therefore \vec{v}^T(\vec{w}_1+\vec{w}_2) = \vec{v}^{\perp}\vec{w}_1+\vec{v}^{\perp}\vec{w}_2 = 0 \implies \vec{w}_1+\vec{w}_2 \in \mathbb{V}^{\perp}$
3. Let $c \in \mathbb{R}$
$\vec{v}^T(c\vec{w}_1) = c\vec{v}^T\vec{w}_1 = 0 \implies c\vec{w_1} \in \mathbb{V}^{\perp}$

- Theorem
$C(A^T) \perp N(A)$, moreover, $C(A^T) = N(A)^{\perp}$ and $N(A) = C(A^T)^{\perp}$
- Proof
By definition $N(A)$ contains all $\vec{x} \in \mathbb{R}^n$
s.t. $A\vec{x} = \vec{0} = \left[\begin{array}{c}
row\ 1 \\
row\ 2 \\
\vdots \\
row\ m \\
\end{array}\right]\vec{x} = \left[\begin{array}{c}
0 \\
0 \\
\vdots \\
0 \\
\end{array}\right]$ i.e. $\left.\begin{array}{c}
[row\ 1]\vec{x} = 0 \\
[row\ 2]\vec{x} = 0 \\
\vdots \\
[row\ m]\vec{x} = 0 \\
\end{array}\right.$
$\iff \vec{u} \cdot \vec{x} = 0,\ \vec{u} =$ any linear combination of row vectors $\in C(A^T)$
$\iff C(A^T) \perp N(A)$
similarly, we can show $C(A) \perp N(A^T)$

- Theorem
Let $v_1,\ v_2,\ \cdots,\ v_r$ be a basis for $C(A^T)$ and $w_1,\ w_2,\ \cdots,\ w_{n-r}$ be a basis for $N(A)$ $(dim(C(A^T)) = r,\ dim(N(A)) = n-r)$
show that $v_1,\ v_2,\ \cdots,\ v_r,\ w_1,\ w_2,\ \cdots,\ w_{n-r}$ form a basis for $\mathbb{R}^n$
- Proof
For $\vec{0} \in \mathbb{R}^n$
$\begin{split}\vec{0} &= a_1\vec{v}_1+a_2\vec{v}_2+\cdots+a_r\vec{v}_r+b_1\vec{w}_1+b_2\vec{w}_2+\cdots+b_{n-r}\vec{w}_{n-r} \\
&\implies a_1\vec{v}_1+a_2\vec{v}_2+\cdots+a_r\vec{v}_r = -(b_1\vec{w}_1+b_2\vec{w}_2+\cdots+b_{n-r}\vec{w}_{n-r}) = \vec{y} \\
&\implies \vec{y} \in C(A^T),\ \vec{y} \in N(A) \\
&\implies \vec{y} \in C(A^T) \cap N(A) \\
&\because C(A^T) \perp N(A)\ \therefore \vec{y} = \vec{0}\end{split}$
Meanwhile, since $v_1,\ v_2,\ \cdots,\ v_r$ form a basis of $C(A^T)$ and $w_1,\ w_2,\ \cdots,\ w_{n-r}$ form a basis of $N(A)$
$\implies v_1,\ v_2,\ \cdots,\ v_r,\ w_1,\ w_2,\ \cdots,\ w_{n-r}$ form a basis of $\mathbb{R}^n$

### Projections

Projection of $\vec{b}$ onto
1. Z-axis is $\left[\begin{array}{c}
0 \\
0 \\
4 \\
\end{array}\right] = \vec{P}_1 = P_1\vec{b} = \left[\begin{array}{c c c}
0 & 0 & 0 \\
0 & 0 & 0 \\
0 & 0 & 1 \\
\end{array}\right] \left[\begin{array}{c}
2 \\
3 \\
4 \\
\end{array}\right]$
2. XY-plane is $\left[\begin{array}{c}
2 \\
3 \\
0 \\
\end{array}\right] = \vec{P}_2 = P_2\vec{b} = \left[\begin{array}{c c c}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 0 \\
\end{array}\right] \left[\begin{array}{c}
2 \\
3 \\
4 \\
\end{array}\right]$

$\vec{P}_1 = \vec{P}_2 = \vec{b},\ P_1 + P_2 = \left[\begin{array}{c c c}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{array}\right] = I$
Z-axis and XY-plane are orthogonal compliments

### Projection onto a Subspace


To find a $\vec{p} \in$ the subspace that is closest to $\vec{b}$ ( minimal error $(\vec{p},\ \vec{b})$ )
For a given vector $\vec{b} \in \mathbb{R}^m$ and a subspace of $\mathbb{R}^m$ spanned by basis $\vec{a}_1,\ \vec{a}_2,\ \cdots,\ \vec{a}_n$ , the projection of $\vec{b}$ onto the subspace, $\vec{p}$, is given by $P \cdot \vec{b} = \vec{p}$ where $P$ is the projection matrix
Let $A = [\vec{a}_1\ \vec{a}_2\ \cdots\ \vec{a}_n],\ \vec{p} = \hat{x_1}\vec{a}_1+\hat{x_2}\vec{a}_2+\cdots+\hat{x_n}\vec{a}_n$ where $\hat{x_1},\ \hat{x_2},\ \cdots,\ \hat{x_n} \in \mathbb{R} \implies \vec{p} = A\vec{x}$
Let the error $\vec{e} = \vec{b} - \vec{p}$
$\because \vec{e} \perp \vec{p},\ \vec{e}^{\perp}\vec{p} = 0$ , i.e. $\vec{e}^T\vec{a}_1=0,\ \vec{e}^T\vec{a}_2=0,\ \cdots,\ \vec{e}^T\vec{a}_n=0$
$\begin{split}\therefore \vec{e}^TA = (\vec{b}-\vec{p})^TA = \vec{0} \iff \vec{b}^TA &= (\vec{p}+\vec{e})^TA \\
&= \vec{p}^TA + \vec{e}^TA \\
&= \vec{p}^TA + 0 = \vec{p}^TA \\
&= (A\vec{x})^TA = \vec{x}^TA^TA\end{split} \\
\vec{b}^TA = \vec{x}^TA^TA \iff A^TA\vec{x} = A^T\vec{b} \\
\therefore (A^TA)^{-1}(A^TA)\vec{x} = (A^TA)^{-1}A^T\vec{b} \implies \vec{x} = (A^TA)^{-1}A^T\vec{b} \\
\vec{p} = A\vec{x} = A(A^TA)^{-1}A^T\vec{b} = P\vec{b} \implies P = A(A^TA)^{-1}A^T$
> since $n < m$, $A_{m \times n}$ is a tall matrix with full column rank ($\because$ basis) $\implies A^TA$ is invertible

> For $n=1$
> $\begin{split}\hat{x} = {\vec{a}^T\vec{b} \over \vec{a}^T\vec{a}},\ \vec{p} = \vec{a}{\vec{a}^T\vec{b} \over \vec{a}^T\vec{a}},\ P = {\vec{a}\vec{a}^T \over \vec{a}^T\vec{a}}\end{split}$

- Theorem
$A^TA$ is invertible if and only if $A$ has linearly independent columns
- Proof
First, show that $A^TA$ has the same null space as $A$
i.e. $N(A) \subseteq N(A^TA)$ and $N(A^TA) \subseteq N(A)$
$\forall \vec{x} \in N(A),\ A\vec{x} = \vec{0} \\
\implies A^TA\vec{x} = A^T\vec{0} = \vec{0} \\
\implies \vec{x} \in N(A^TA)\ \therefore N(A) \subseteq N(A^TA)...① \\
\forall \vec{x} \in N(A^TA),\ (A^TA)\vec{x} = \vec{0} \\
\implies \vec{x}^T(A^TA)\vec{x} = \vec{x}^T\vec{0} = \vec{0} \\
\vec{x}^T(A^TA)\vec{x} = \begin{Vmatrix}
A\vec{x}
\end{Vmatrix}^2 = 0$
i.e. $A\vec{x}$ is a vector with norm = 0
$\therefore A\vec{x}=\vec{0},\ \vec{x} \in N(A) \implies N(A^TA) \subseteq N(A)...②$
From ① and ②, $N(A) = N(A^TA)$
Note that $A$ is $m \times n$ , and $A^TA$ is $n \times n$ , given $rank(A) = r$
$\because N(A) = N(A^TA) \\
\implies dim(N(A)) = dim(N(A^TA)) \\
\implies n-r = n-rank(A^TA) \\
\implies rank(A) = r$
As $A$ has linearly dependent columns i.e. $rank(A)=n,\ rank(A^TA)=n \implies A^TA$ is invertible