# Schedule

• Four fundamental subspaces (for matrix A)

# 4 Subspaces – 4个子空间

• C(A) : column-space
• N(A) : null-space
• C(A^T) : row-space = all combs of rows = all combs of columns of A^T
• N(A^T) : null-space of A^T = left null space of A

N(A)中包含的是n维向量,且是Ax=0的解. 所以N(A)是在R^n中的.
C(A)是在R^m中,C(A^T)R^n中,N(A^T)R^m

• C(A) 列空间
列空间的维度\dim C(A) = r
C(A)中的一组基是所有主列.

• C(A^T) 行空间
行空间的维度\dim C(A^T) = r

• N(A) 零空间
N(A)中的一组基是特殊解们,共有(n-r)个特殊解,所以\dim N(A)=n-r

• N(A^T) 左零空间
左零空间的维数是m-r

Example:
A=\begin{bmatrix}1&2&3&1\\1&1&2&1\\1&2&3&1\end{bmatrix}\rightarrow\begin{bmatrix}1&0&1&1\\0&1&1&0\\0&0&0&0\end{bmatrix}=R

AR的行空间的基是R中的非零r行.

Basis of row space is the r rows of R.

N(A^T)为什么叫左零空间?

Guass-Jordan 方法
[A_{m\times n} I_{m\times m}] \rightarrow [R_{m\times n}E_{m\times m}]

# New vector space – 新的向量空间

M来表示由所有3\times 3矩阵组成的矩阵”空间”

# Schedule

• Linear independence
• Spanning a space
• Basis and Dimension
该章节中说到的无关性和张成空间均指的是向量组而非矩阵.

# Independence – 线性无关性

Suppose A is m\times n with m, then there are nonzero solutions to Ax=0 (more unknowns than equations).
The reason why there is solution is there will be free variables.

When vectors x_1,x_2,…x_n are independent?

c_1x_1 + c_2x_2 + … + c_nx_n \ne 0 除非 all\phantom{1}c_i=0

When v_1,v_2,…v_n are columns of A:

• They are independent if the null-space of A is only zero vector \rightarrow (r=n).
• Then are dependent if Ac=0 for some non-zero c \rightarrow (r.

# Spanning – 张成

Vectors v_1,…v_l span a space means the space consists of all combinations of those vectors.

Basis for a space is a sequence of vectors v_1,v_2,…v_d that has two properties:

• they are independent.
• they span the space.

Example:
Space is R^3.

For R^n, n vectors give basis if the n\times n matrix with those columns is invertible.

Given a space, every basis for the space has the same number of vectors and this number is the dimension of the space.

Independence, that looks at combinations not being zero.
Spanning, that looks at all the combinations.
Basis, that’s the one that combines independences and spanning.
Dimension, the number of vectors in any basis.

Example:
Space is C(A) = \begin{bmatrix}1&2&3&1\\1&1&2&1\\1&2&3&1\end{bmatrix}
2 = rank(A) = # pivot columns = dimension of C(A)

dimC(A) = r
dimN(A) = n-r = \text{# free variables}

# Schedule

• Complete solution of Ax=b
• Rank r
• r=m : Solution & Exists
• r=n : Solution is Unique

# Complete solution of Ax=b

x_1+2x_2 +2x_3+2x_4 = b_1\\2x_1+4x_2+6x_3+8x_4=b_2\\3x_1+6x_2+8x_3+10x_4=b_3

Argumented Matrix = [A |b]=\begin{bmatrix}\fbox1&2&2&2&b_1\\2&4&6&8&b_2\\3&6&8&10&b_3\end{bmatrix}=\begin{bmatrix}\fbox1&2&2&2&b_1\\0&0&\fbox2&4&b_2-2b_1\\0&0&2&4&b_3-3b_1\end{bmatrix}=\begin{bmatrix}\fbox1&2&2&2&b_1\\0&0&\fbox2&4&b_2-2b_1\\0&0&0&0&b_3-b_2-b_1 \end{bmatrix}

Argumented Matrix = [A |b]=\begin{bmatrix}\fbox1&2&2&2&1\\0&0&\fbox2&4&3\\0&0&0&0&0\end{bmatrix}

Solvability is the condition on b.

Ax=b is solvable if when exactly when b is in the column space of A.

The same combination of the entries of b must give 0(not zero row, but number 0).

Question Mark Here:

## Find complete solution to Ax=b – 求Ax=b的所有解

Step one : A particular solution.

Set all free variable to zero and then solve Ax=b for pivot variables.

x_{\text{particular solution}} = \begin{bmatrix}-2\\0\\1.5\\0\end{bmatrix}

Step two : add on X anything out of the null space.
Step three : 从而求得x=x_p+ x_n

The complete solution is the one particular solution plus any vector out of the null space.

Ax_p = bAx_n=0 两者相加,同样得到A(x_p+x_n)=b

x_{complete} =\begin{bmatrix}-2\\0\\1.5\\0\end{bmatrix} + c_1\begin{bmatrix}-2\\1\\0\\0\end{bmatrix} + c_2 \begin{bmatrix}2\\0\\-2 \\1\end{bmatrix}
x_p是一个特定解,x_n是整个零空间,

Ax=b特解表示为particular solution(特定解), Ax=0基为special solution(特殊解).

## m\times n matrix A of rank r – 秩为r的m\times n矩阵

1. Full column rank means r=n\lt m
这种情况下每列均有一个主元,从而没有自由变量. 这样的话零空间中将会只有零向量.
那么对于Ax=b来说,其全部解为特解x_p一个(如果有解的话), 将其称为unique solution(唯一解).
也就是说,对于r=n的情况下,其解的情况为0或者1个解(特定解).
举个例子:

2. Full row rank means r=m\lt n
这种情况下每行均有一个主元,自由变量数为n-r个.
因为在消元过程中没有产生零行,所以求解Ax=b对于b来说没有要求(Can solve Ax=b for every right-hand side),所以必然有解.
举个例子(上个例子的转置):

A=\begin{bmatrix}1&2&6&5\\3&1&1&1\end{bmatrix}(r=2)\rightarrow R= \begin{bmatrix}1&2&6&5\\0&-5&-17&-14\end{bmatrix}

3. r=m=n
零空间中只有零向量.
举个例子:
A=\begin{bmatrix}1&2\\3&1\end{bmatrix}\rightarrow R= I
必然有解,唯一解.

r=m=n\rightarrow R=I\rightarrow 1 solution(特定解)
r=n\lt m\rightarrow R=I/0\rightarrow 0 or 1 solution(特定解)
r=m\lt n\rightarrow R=[I|F]\rightarrow 1 or infinitely many solutions(特定解或特定解和零向量空间的组合)
r\lt m,r\lt n\rightarrow 0 or infinitely many solutions(特定解和零向量空间的组合)

The rand tells everything about the number of solutions .

# Schedule

• Computing the null-space (Ax=0)
• Pivot variable with Free variable
• Special Solutions — rref(A)=R
这章主要讨论的是长方矩阵(rectangular matrix)

# Computing the Nullspace – 计算零空间

A=\begin{bmatrix}1&2&2&2\\2&4&6&8\\3&6&8&10\end{bmatrix}

A=\begin{bmatrix}\fbox1&2&2&2\\2&4&6&8\\3&6&8&10\end{bmatrix}=\begin{bmatrix}1&2&2&2\\0&0&2&4\\0&0&2&4\end{bmatrix}

A=\begin{bmatrix}\fbox1&2&2&2\\2&4&6&8\\3&6&8&10\end{bmatrix}=\begin{bmatrix}\fbox1&2&2&2\\0&0&\fbox2&4\\0&0&2&4\end{bmatrix}=\begin{bmatrix}\fbox1&2&2&2\\0&0&\fbox2&4\\0&0&0&0\end{bmatrix}=U

Rank of A = # of pivots

\begin{bmatrix}-2\\1\\0\\0\end{bmatrix} 和 \begin{bmatrix}2\\0\\-2\\1\end{bmatrix}

The null space contains exactly all the combinations of the special solutions.

There is one special solution for every free variable.

R = reduced row echelon form
U=\begin{bmatrix}\fbox1&2&2&2\\0&0&\fbox2&4\\0&0&0&0\end{bmatrix}=\begin{bmatrix}\fbox1&2&0&-2\\0&0&\fbox2&4\\0&0&0&0\end{bmatrix}=\begin{bmatrix}\fbox1&2&2&2\\0&0&\fbox1&2\\0&0&0&0\end{bmatrix}=R=rref(A)

notice \begin{bmatrix}1&0\\0&1\end{bmatrix} = I in pivot rows and pivot column.

rref(A)中的全零行表示该行原为其他行的线性组合,可以被消元过程中去除.

x_1+2x_2-2x_4=0 \\ x_3+2x_4=0

# rref – 简化行阶梯形式

R=\begin{bmatrix}I&F\\0&0\end{bmatrix}

N = \text{null-space matrix(columns of special solutions)}=\begin{bmatrix}-F\\I\end{bmatrix}

# Schedule

• Vector spaces and Subspaces
• Column space of A : Solving Ax=b
• Nullspace of A

# Vector space requirements – 向量空间满足条件

v+w and c*v are in the space. 满足相加和数乘.
All combs cv+dw are in the space. 满足相加和数乘的线性组合.

To subspaces S and T, intersection S \cap T is a subspace.

1. 加法(Sum)封闭
2. 数乘(Scale of Multiplication)封闭

# Column space of a matrix A – A的列空间

A=\begin{bmatrix}1&1&2\\2&1&3\\3&1&4\\4&1&5\end{bmatrix}

Column space of A is subspace of R^4, which is all linear combs of columns of A.

A的列空间与线性方程式组联系起来.

Does Ax=b have a solution for every b ?

Which b allow this system to be solved ?

Ax=\begin{bmatrix}1&1&2\\2&1&3\\3&1&4\\4&1&5\end{bmatrix}*\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=\begin{bmatrix}b_1\\b_2\\b_3\\b_4\end{bmatrix}=b

Can solve Ax=b exactly when b is in C(A).

# Null space – 零空间

Null space of A is N(A) contains all solutions x=\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix} to the equation Ax=0.
Ax=\begin{bmatrix}1&1&2\\2&1&3\\3&1&4\\4&1&5\end{bmatrix}*\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=\begin{bmatrix}0\\0\\0\\0\end{bmatrix}=0

The solutions to Ax=0 always give a subspace.

Ax=\begin{bmatrix}1&1&2\\2&1&3\\3&1&4\\4&1&5\end{bmatrix}*\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=\begin{bmatrix}1\\2\\3\\4\end{bmatrix}=b

1. 可以从几个向量,通过线性组合的方式得到子空间;
Given a few vectors and fill it out, take combinations;
2. 可以从一个方程式组中,通过让x满足特定条件来得到子空间.
Given a system of equations the requirements that the x-s have to satisfy.

# Schedule

• PA=LU
• Vector Spaces and Subspaces

# Permutations – 置换矩阵

Permutations P : execute row exchanges.

Permutations P is the identity matrix with reordered rows.

# Transpose – 转置矩阵

A^T中第i行第j列的元素等于A中第j行第i列的元素,即(A^T)_{ij}=A_{ji}.

# Symmetric Matrix – 对称矩阵

e.g.
\begin{bmatrix}1&3\\2&3\\4&1\end{bmatrix}*\begin{bmatrix}1&2&4\\3&3&1\end{bmatrix}=\begin{bmatrix}10&11&7\\11&13&11\\7&11&17\end{bmatrix}

(R^TR)^T=R^T(R^T)^T=R^TR

# Vector Spaces – 向量空间

e.g.
R^2=\text{all 2-dim real vectors} = \text{x-y plane}, 例如: \begin{bmatrix}3\\2\end{bmatrix},\begin{bmatrix}0\\0\end{bmatrix},\begin{bmatrix}\pi\\e\end{bmatrix}
R^3= \text{all vectors with 3 components}, 例如:\begin{bmatrix}3\\2\\0\end{bmatrix}
R^n= \text{all column with n(n is real number) components}

A vector space has to be closed under multiplication and addition of vectors. In other words, linear combinations.

1. all vectors of R^2 所有的二维向量
2. any line through \begin{bmatrix}0\\0\end{bmatrix} 任意过原点的直线
3. zero vector(零向量), Z=\begin{bmatrix}0\\0\end{bmatrix} 仅含零向量的空间

1. all vectors of R^3 所有的三维空间
2. any plane through \begin{bmatrix}0\\0\\0\end{bmatrix} 任意过原点的平面
3. any line through \begin{bmatrix}0\\0\\0\end{bmatrix} 任意过原点的直线
3. zero vector(零向量), Z=\begin{bmatrix}0\\0\\0\end{bmatrix} 仅含零向量的空间

# Subspace – 如何构造子空间?

A=\begin{bmatrix}1&3\\2&3\\4&1\end{bmatrix}

All these linear combinations form a subspace.

# Schedule

• Inverse of AB, A^T
• Product of elementation matrices
• A=LU (no row exchanges)

# Inverse of AB, A^T – AB 和 A^T 的逆

AB 的逆是 A 的逆和 B 的逆的逆序相乘,也就是 B^{-1}A^{-1} .

B^TA^T=D ,其中 D_{ij}=\sum_{k=1}^nB^T_{ik}A^T_{kj}.

# Product of elimination matrices – 消元矩阵的乘积

e.g. 假设有矩阵 A=\begin{bmatrix}2&1\\8&7\end{bmatrix} ,经过转换 E_{21}=\begin{bmatrix}1&0\\-4&1\end{bmatrix} ,得到矩阵 U=\begin{bmatrix}2&1\\0&3\end{bmatrix} , 即:

\begin{bmatrix}1&0\\-4&1\end{bmatrix}*\begin{bmatrix}2&1\\8&7\end{bmatrix}=\begin{bmatrix}2&1\\0&3\end{bmatrix}

\begin{bmatrix}2&1\\8&7\end{bmatrix}=\begin{bmatrix}1&0\\4&1\end{bmatrix} \cdot \begin{bmatrix}2&1\\0&3\end{bmatrix}=\begin{bmatrix}1&0\\4&1\end{bmatrix} \cdot \begin{bmatrix}2&0\\0&3\end{bmatrix} \cdot \begin{bmatrix}1&\frac{1}{2}\\0&1\end{bmatrix}

\begin{bmatrix}1&0&0\\0&1&0\\0&-5&1\end{bmatrix} \cdot \begin{bmatrix}1&0&0\\-2&1&0\\0&0&1\end{bmatrix}=\begin{bmatrix}1&0&0\\-2&1&0\\10&-5&1\end{bmatrix}=E\leftarrow(EA=U)\\ \begin{bmatrix}1&0&0\\2&1&0\\0&0&1\end{bmatrix} \cdot \begin{bmatrix}1&0&0\\0&1&0\\0&5&1\end{bmatrix}=\begin{bmatrix}1&0&0\\2&1&0\\0&5&1\end{bmatrix}=L\leftarrow(A=LU)

If no row exchanges, multipliers go directly into L.

# Transposes and Permutations – 转置和置换

\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}, \begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix},\begin{bmatrix}0&0&1\\0&1&0\\1&0&0\end{bmatrix},\begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix},\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix},\begin{bmatrix}0&0&1\\1&0&0\\0&1&0\end{bmatrix}

# Schedule

• Matrix Multiplication (4 ways) 矩阵乘法的四种形式
• Inverse of A , AB , A^T
• Gauss-Jordan method to find A^{-1}

# Matrix Multiplication – 矩阵乘法

## 点乘法

C_{34} = (\text{row 3 of A}) * (\text{col 4 of B}) = a_{31} * b_{14} + a_{32}*b_{24}+…=\sum_{k=1}^n a_{3k}b_{k4}

## Column Way – 列角度

Columns of C are combinations of columns of A.

Tips :

m 是行数, 也可以理解为 A 中列的长度, 所以是 A 中的列按照 B 中的每列进行 p 次自由组合, 这 p 次组合保留了 A 中每列的长度, 也就是 m.

## Row Way – 行角度

Rows of C are combinations of rows of B.

## Columns times Rows – 列与行相乘

\begin{bmatrix} 2 \\ 3 \\ 4 \end{bmatrix} \cdot \begin{bmatrix} 1 & 6 \end{bmatrix} = \begin{bmatrix} 2 & 12 \\ 3 & 18 \\ 4 & 24 \end{bmatrix}

AB 等于 A 各列与 B 各行乘积之和.

AB= \text{Sum of (cols of A)} \cdot \text{(rows of B)}

e.g.

\begin{bmatrix} 2 & 7 \\ 3 & 8 \\ 4 & 9 \end{bmatrix} * \begin{bmatrix} 1 & 6 \\ 0 & 0 \end{bmatrix}=\begin{bmatrix} 2 \\ 3 \\ 4 \end{bmatrix} * \begin{bmatrix} 1 & 6 \end{bmatrix}+\begin{bmatrix} 7 \\ 8 \\ 9 \end{bmatrix} * \begin{bmatrix} 0 & 0 \end{bmatrix}

## Block Multiplication – 块乘法

\begin{bmatrix} A_1 & A_2 \\ A_3 & A_4 \end{bmatrix} * \begin{bmatrix} B_1 & B_2 \\ B_3 & B_4 \end{bmatrix} = \begin{bmatrix} A_1 * B_1 + A_2 * B_3 & A_1 * B_2 + A_2 * B_4 \\ A_3 * B_1 + A_4 * B_3 & A_3 * B_2 + A_4 * B_4 \end{bmatrix}

# Inverses(square matrices)

• 如果一个矩阵是方阵,那么这个方阵是否可逆?
• 如果一个矩阵可逆, 如何求逆?

对于方阵来说,其左逆等于其右逆,即 A^{-1}A=AA^{-1}=I (证明很简单,在等式两边各乘以求中一个逆即可).

对于非方阵来说,左逆是不等于右逆的,因为形状不同所以无法相乘.

# 求逆

\begin{bmatrix} 1 & 3 \\ 2 & 7 \end{bmatrix} \cdot \begin{bmatrix} a & c \\ b & d \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}

A times column j of A^{-1} = column j of I

# Gauss-Jordan 高斯-约旦 消元法

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

# N linear equations, N unknows – 方程式组和矩阵

\begin{bmatrix}2 & -1 \\\\ -1 & 2 \end{bmatrix} * \begin{bmatrix}x \\\\ y \end{bmatrix} = \begin{bmatrix} 0 \\\\ 3 \end{bmatrix}

A matrix is just a rectangular array of numbers.

# Row Picture

Row Picture, 也就是从行的角度来考虑矩阵内在的含义.

# Column Picture

x\begin{bmatrix} 2 \\\\ -1\end{bmatrix} + y\begin{bmatrix} -1 \\\\ 2\end{bmatrix} = \begin{bmatrix} 0 \\\\ 3\end{bmatrix}

2x-y=0 \\\\ -x+2y-z=-1 \\\\ -3y+4z=4

x\begin{bmatrix}2\\\\-1\\\\0\end{bmatrix} + y\begin{bmatrix}-1\\\\2\\\\-3\end{bmatrix}+z\begin{bmatrix}0\\\\-1\\\\4\end{bmatrix}=\begin{bmatrix}0\\\\-1\\\\4\end{bmatrix}

Can I solve $$Ax=b$$ for every $$b$$ ?
Or
Do the linear combinations of the columns fill three dimensional space?

# Matrix Form – 矩阵形式

e.g.
\begin{bmatrix}2&5\\\\1&3\end{bmatrix}*\begin{bmatrix}1\\\\2\end{bmatrix}

\begin{bmatrix}2&5\\\\1&3\end{bmatrix}*\begin{bmatrix}1\\\\2\end{bmatrix} = 1\begin{bmatrix}2\\\\1\end{bmatrix} + 2\begin{bmatrix}5\\\\3\end{bmatrix} = \begin{bmatrix}12\\\\7\end{bmatrix}

\begin{bmatrix}2&5\\\\1&3\end{bmatrix}*\begin{bmatrix}1\\\\2\end{bmatrix} =\begin{bmatrix}2*1+5*2\\\\1*1+3*2\end{bmatrix} =\begin{bmatrix}12\\\\7\end{bmatrix}

$$Ax$$ is a combination of the columns of $$A$$ .