---
# System prepended metadata

title: 'Linear Algebra - Lec 05~07: Linear System and Solutions'
tags: [Linear Algebra - HungYiLee]

---

---
tags: Linear Algebra - HungYiLee
---

Linear Algebra - Lec 05~07: Linear System and Solutions
===

[TOC]

# [課程網站](http://speech.ee.ntu.edu.tw/~tlkagk/courses_LA18.html)

# [Lecture 5: Matrix-vector Product](https://www.youtube.com/watch?v=K2zzvo28X0g&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=5)

$Ax=b,\,A\in\mathbb R^{m\times n},\,x\in\mathbb R^n$

矩陣 $A$ 和向量 $x$ 的乘積可以有兩種觀點
- row aspect
- column aspect

## Row Aspect

- $b_i$ 就是 $A$ 的第 $i$ 個 row 和 $x$ 去做內積
![](https://i.imgur.com/QhIzaTh.png)

## Column Aspect

- $b$ is **linear combination of $A$'s columns**
    - $a_1=\begin{bmatrix}a_{11}\\a_{21}\\\vdots\\a_{m1}\end{bmatrix}, a_2=\begin{bmatrix}a_{12}\\a_{22}\\\vdots\\a_{m2}\end{bmatrix}, ..., a_n=\begin{bmatrix}a_{1n}\\a_{2n}\\\vdots\\a_{mn}\end{bmatrix}$
    - $A=\begin{bmatrix}a_1&a_2&\cdots&a_n\end{bmatrix}, x=\begin{bmatrix}x_1\\x_2\\\vdots\\x_n\end{bmatrix}$
    - $b=x_1a_1+x_2a_2+...+x_na_n$

![](https://i.imgur.com/SzDTtyo.png)

# [Lecture 6: Having Solution or Not](https://www.youtube.com/watch?v=-E67rZSjTNI&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=6)

Given $A$ and $b$, sometimes $Ax=b$ has one or more solutions $x$, sometimes not. 

- A system of linear equations is called **consistent** if it has one or more solutions
- otherwise it's called **inconsistent**
- 總之 **consistent 就是有解；inconsistent 就是無解**

## Linear Combination

$v = c_1u_1+c_2u_2+...+c_ku_k$
- $c_i$ is a scalar
- $u_i$ is a vector

### Review matrix-vector product: column aspect
- $Ax=b$ ，$b$ 其實就是 $A$ 的 column vector 的 linear combination

所以**問 $Ax=b$ 是否有解，其實等同於問 $b$ 是否為 $A$ 的 column vector 的 linear combination**

## Span

Given vector set $S = \{u_1, u_2, ..., u_k\}$
- **Span** $S$ is the vector set of **all linear combinations** of $u_1, u_2, ..., u_k$
- **Span** $S = \{c_1u_1+c_2u_2+...+c_ku_k|\forall c_1,c_2,...,c_k\in\mathbb R\}$

vector set $V = Span(S)$ 換句話說就是
- "$S$ is a **generating set** for $V$" or "$S$ generates $V$"

### Standard Vector

**standard vector** 就是只有其中一維是 1，其他都 0 的 vector
- $e_1 = \begin{bmatrix}1\\0\\0\end{bmatrix},e_2 = \begin{bmatrix}0\\1\\0\end{bmatrix}, e_3 = \begin{bmatrix}0\\0\\1\end{bmatrix}$

$\mathbb R^3$ 其實可以說是 $Span \{e_1,e_2,e_3\}$

### 問某 linear equation 是否有解

前面說過，可以說成是
- 問 **$b$ 是否為 $A$ 的 column vector 的 linear combination**

其實也可以說成是
- 問 **$b$ 是否在 $A$ 的 column vector 的 Span 當中**

# [Lecture 7: How many solutions?](https://www.youtube.com/watch?v=34HlThINCsc&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=7)

- $A\in\mathbb R^{m\times n}$
- $x\in \mathbb R^n$
- $b\in \mathbb R^m$


在 $Ax=b$ 有解的前提下，有多少解呢?

- 若以下**任一條件**成立，則其他條件也會成立，且 linear equation **洽有一組解**
    - $A$ 的所有 $n$ 個 columns 是 independent 的
    - $rank(A) = n$
    - $Nullity(A) = 0$
- 若以下**任一條件**成立，則其他條件也會成立，且 linear equation **有無窮多組解**
    - $A$ 的 columns 是 dependent 的
    - $rank(A) < n$
    - $Nullity(A) > 0$
- 後面會說明 rank 的定義

## Dependent and Independent

### Definition

- A set of $n$ vectors $\{a_1, a_2, ..., a_n\}$ is linear **dependent**
    - if exists scalars $x_1, x_2, ..., x_n$ **not all 0**, such that $x_1a_1+x_2a_2+...+x_na_n=0$
    - 其實若找得到一組這樣的 scalar $x$，就找得到無窮多組
- A set of $n$ vectors $\{a_1, a_2, ..., a_n\}$ is linear **independent** 
    - $x_1a_1+x_2a_2+...+x_na_n=0$ only if $x_1=x_2=...=x_n=0$

### More Intuitive Explanation

- vector set $\{a_1, a_2, ..., a_n\}$ 是 linear dependent 的，則存在某個 vector $a_i$ 是其他 vector 的 linear combination


### zero vector

- **注意：$\begin{bmatrix}3\\-1\\7\end{bmatrix}, \begin{bmatrix}0\\0\\0\end{bmatrix}, \begin{bmatrix}-2\\5\\1\end{bmatrix}$ 是 linear dependent** 的
- **zero vector 是任何其他 vector 的 linear combination**

## Intuition

若 $A$ 的 column 是 dependent 的，則
- 一旦 $Ax=b$ 有解，就有無窮多解
    - 可以用 lecture 5 的 **column aspect** 來思考

### Proof

證明以下兩件事等價 (iff, if and only if)
- Columns of $A$ are dependent $\implies$ if $Ax=b$ have solutions, it will have infinite solutions
- If $Ax=b$ has infinite solutions, columns of $A$ are dependent

#### Homogeneous Linear Equations

$Ax=0$
- $A=[a_1,...,a_n]$
- $a_i\in\mathbb R^m$

#### Based on the **definition**
- A set of $n$ (column) vectors $a_1, ..., a_n$ is linear **dependent**  $\leftrightarrow$  $Ax=0$ **has non-zero solution (infinite)**
- A set of $n$ (column) vectors $a_1, ..., a_n$ is linear **independent**  $\leftrightarrow$  $Ax=0$ **only has zero solution**

之後的證明暫略，just try to prove it

## Rank and Nullity

**rank**
- **maximum** number of linearly **independent columns** in the matrix

**nullity**
- **number of columns 減去 rank，即 $n-Rank(A)$**

### example

$A = \begin{bmatrix}1&3&10\\2&6&20\\3&9&30\end{bmatrix}$
- $Rank(A) = 1$
- $Nullity(A) = 2$

#### 單一 vector 形成的 vector set 之 dependent/independent
- 這裡要注意，根據 **definition**，若 vector set 中只有一個 vector $\{v\}$
    - 若 $v$ 為 **zero vector**，則該 **vector set 是 dependent** 的
    - 若 $v$ **不是** zero vector，則該 **vector set 是 independent** 的
- 可以利用上述結論判斷以下兩個 example 的 rank

$A = \begin{bmatrix}0&0&0\\0&0&0\\0&0&0\end{bmatrix}$
- $Rank(A) = 0$
- $Nullity(A) = 3$

$A = \begin{bmatrix}0&3\\0&5\end{bmatrix}$
- $Rank(A) = 1$
- $Nullity(A) = 1$

### Conclusions

Coumns of $A$ are independent **iff**
- $Rank(A)=n$ **iff** 
- $Nullity(A)=0$

### 可以用兩種順序來判斷 linear system 有多少解

1. ![](https://i.imgur.com/0v4AujK.png)
2. ![](https://i.imgur.com/pUS62S5.png)
