This is a basic subject on matrix theory and linear algebra. Emphasis is given to topics that will be useful in other disciplines, including systems of equations, vector spaces, determinants, eigenvalues, similarity, and positive definite matrices.

Lec 1 The Gemetry of Linear Algebra

1.1 Overview

本节课程主要是从两个不同角度去了解什么是线性方程组.

image-20200808072306142

系数矩阵(A): 方程组系数构成的矩阵

未知向量(x): 方程未知数构成的矩阵

向量(b): 等式右侧结果所构成的向量

1.2 Row Figure

Row Figure 是指在 Ax=b 的矩阵表示中, 一次取一行构成方程, 并在坐标轴中做出相应的图形.

image-20200808072846217

但不难发现, 我们很难做高维坐标轴图像, 所以我更倾向于使用 Column Figure 来理解线性方程组.

1.3 Column Figure

从 Column Figure 的角度来看, b 是 linear combinations of columns of A, 也就是 Ax:

image-20200808073724819

图像表示

image-20200808074347051

1.4 Question

Can I solve Ax=b for every b?

这个问题也等于是在问: Do the linear combination of columns of A fill N-D space?

这里我们暂时不解答这个问题, 在后续课程会详细讲解:)

Lec 2 Elimination with Matrices

2.1 Overview

本节课程主要是介绍消元法, 即使”系统化”求解线性方程组所需的方法, Matlab 的方程组求解也是用这种方法.

所谓矩阵的消元法, 与我们初等数学中学习的解二元一次方程组的消元法其实师出同门, 都是通过将不同行的方程进行消元运算来简化方程, 最后能得到简化的方程组, 只不过这里我们把系数单独抽出来进行运算, 寻找一种矩阵情况下的普遍规律而已.

2.2 Intro Example

我们从一个例子入手, 求解线性方程组:

image-20200808080203366

解题思路是”将一行乘倍数加到另一行”, 使主元所在列上的主元以下的元素全为 0.

image-20200808080917241

之后将所得的新 A 和 b 回带(Back Substitution) 求解.

image-20200808081437713

当然有有些时候, 我们会遇到主元位置上是 0 的情况, 这个时候我们只需要交换行即可.

2.3 Advanced Example

上面的例子是从 Intuition 的角度来理解了消元的操作, 但是我们需要一种更系统的方法, 能够被 Computer 理解的方法. 所以我们在这里要引入消元矩阵的概念.

在讲消元矩阵之前, 我们还需要了解 Linear Combination of Rows:

image-20200808082702374

Matrix x Column Vector = Column Vector

Row Vector x Matrix = Row Vector

Ok, 在了解这个知识点之后, 如果我们需要消元下面这个矩阵, 我们需要哪些步骤?

image-20200808080203366

Step 1: Substract 3 x Row1 from Row2

image-20200808083548341

Step 2: Substract 2 x Row2 from Row3

image-20200808083843515

Comb of Step 1 and Step 2:

image-20200808084032447

2.4 Extension

既然已经讲到了消元矩阵, 我想在这里提一下置换矩阵(Permutation Matrix).

Exchange Row1 and Row2:

image-20200808084527151

Exchange Col1 and Col2:

image-20200808084840670

Lec 3 Multiplication and Inverse Matrices

3.1 Overview

上节课我们学习了矩阵和向量之间的乘法, 这节课则是学习矩阵之间的乘法, 并讨论逆矩阵的相关知识点.

3.2 Multiplication

矩阵的乘法有四种理解方式:

1) Standard Rule (Row x Column)

image-20200808091144775

2) Column Way

image-20200808091515971

3) Row Way

image-20200808091749387

4) Column x Row

image-20200808092104530

在显示生活中矩阵的 scale 往往都很大, 所以为了减小计算成本, 我们可以将矩阵划分成 Blocks, 然后再相乘, 即 Block Multiplication.

image-20200808092244258

3.3 Inverse Matrices

逆矩阵的定义:

对于一个方阵A, 如果 A 可逆, 那么则存在一个 $A^{-1}$, 使: $AA^{-1}=I=A^{-1}A$.

A left inverse is also a right inverse, which is only true for square matrices.

如果一个矩阵存在逆矩阵, 我们则称该矩阵 non-singular, 即非奇异的.

我们先来看一个奇异矩阵, 也就是没有逆的矩阵:

image-20200808122223205

Why 这个矩阵是奇异的呢? 这里我介绍三个原因:

  • 我们还没有学行列式, 但是可以先记住 det(A) = 1x6 - 2x3 = 0

  • Linear combinations of columns of A can’t get $\left|\begin{matrix}1\\0\end{matrix}\right|$

  • I can find a non-zero vectro x with Ax=0

image-20200808122731932

Ok, 所以我们怎么计算逆矩阵呢? 直观来说, 我们可以使用 Column Way 的方式构建方程式, 因为$AA^{-1}=I=A^{-1}A$.

image-20200808123222024

但是对于高阶矩阵来说, 这种计算方式的成本太高了. 所以我们这里引入另外一种计算方式:高斯-若尔当方法 (Gauss-Jordan idea)

image-20200808123723069

至于 Gauss-Jordan 成立的原因也非常直观: $E[A\ I] = [I\ ?]$ ==> $EA = I$, so $EI = A^{-1}$

最后, 再介绍两个逆矩阵的性质:

  • Inverse of the product

    $(AB)^{-1}=B^{-1}A^{-1}$

  • Inverse of the transpose

    $(AA^{-1})^{T}=(A^{-1})^{T}A^{T}=(A^{T})^{-1}A^{T}$

Lec 4 Factorization into A=LU

4.1 Overview

本节课主要是结合了之前的消元矩阵和逆矩阵知识, 将矩阵 A 分解为下三角矩阵 L 和上三角矩阵 U.

4.2 A=LU

我们先通过消元矩阵将矩阵 A 转换为上三角矩阵 U 的形式:

image-20200808130047836

根据之前所学的逆矩阵知识我们可知, 消元矩阵 $E_{21}$是可逆的(且不需要行的置换), 所以就有:

image-20200808130221621

那么我们为什么一定要消元矩阵做一次逆矩阵运算呢? 其实这主要是更加直观的反应消元所涉及的步骤:

image-20200808130622700

Lec 5 Transpose, Permutation and Vector Space

5.1 Overview

本节主要是关于我们之前已经有所涉及的置换矩阵, 矩阵的转置和对称矩阵并介绍一点向量空间.

5.2 Permutation

Permutation matrix is the identity matrix with reordered rows.

我们来看一个 3x3 的矩阵有多少个置换矩阵:

image-20200808134204865

一共有 6 = 3! 个置换矩阵, 而且 if multiply any 2 of them together, the result is still in the group, and if inverse, the result is also still in the group.

image-20200808134355068

So, how about 4 x 4 Matrix? ==> 4! = 24 permutation matrices

那么在进行矩阵分解的时候, 我们如果需要行的置换则可以表示为:

$PA=LU \ \ ==> \ A=P^{-1}LU$

5.3 Transpose

转置比较简单 (需要一点几何想象能力)

$(A_{ij})^{T}=A_{ji}$

我们在这里主要是讲如何利用矩阵的转置来创建一个对称矩阵, 对称矩阵的含义是: $A^{T}=A$. 最简单的创建对称矩阵的办法就是: 原矩阵和其转置矩阵相乘.

$(RR^{T})^{T}=RR^{T}$

image-20200808135336399

5.4 Vector Space

This is only breif introduction of vector space. So what is vector space?

Vector space is just a bunch of vectors!

For example:

​ $R^{2}$= All 2-D real vectors

​ $R^{3}$= All real vectors with 3 components

5.5 Subspace

So what is the subspace of a vector space?

subspace 的定义是, 该 subspace 里的任何向量在进行 Addition 和 Multiplication (by a scalar) 之后仍然在该 subspace 中. 数学表示为: cv + dw.

举两个例子:

  • Subspaces of $R^{2}$

    1) All of $R^{2}$, 也就是其本身

    2) Any line through $\left|\begin{matrix}0\\0\end{matrix}\right|$

    3) Zero vector only

  • Subspaces of $R^{3}$

    1) All of $R^{3}$

    2) Any line through the origin

    3) Any plane through the origin

    4) Zero vector only

Ok, 在了解了 Subspace 的相关概念之后, 我们需要思考 How to create subspaces out of Matrix. 这里有两种方式:

  • From Columns

    Column space = C(A) = All the linear combinations of columns of A

  • From Rows

    Row space = All the linear combinations of rows of a matrix = C($A^{T}$) = Column space of $A^{T}$

Lec 6 Column Space and Nullspacce

6.1 Overview

本节从之前学习的子空间开始, 介绍了子空间的部分性质. 并重点介绍了列空间与方程 Ax = b 之间的联系. 并由此引出了零空间, 根据 Ax = b 这个方程给出了两种构建子空间的方法.

6.2 Union and Intersection of Subspaces

我们假设 P 和 L 是$R^{3}$的两个 subspaces, 那么 $P\cup L$ = All vectors in P or L or both.

那么问题来了:

1) Is $P\cup L$ a subspace? ==> No!

2) Is $P \cap L$ a subspace? ==> Yes!

This conclusion will be used in lec 10.

6.3 Column Space of A

我们用一个例子来回顾一下上一节所讲述的列空间知识.

现有矩阵 A = $\left|\begin{matrix}1&1&2\\2&1&3\\3&1&4\\4&1&5\end{matrix}\right|$, 矩阵的列向量$\left|\begin{matrix}1\\2\\3\\4\end{matrix}\right|$,$\left|\begin{matrix}1\\1\\1\\1\end{matrix}\right|$,$\left|\begin{matrix}2\\3\\4\\5\end{matrix}\right|$均是$R^{4}$中的四维向量, 所以 A 的列空间是 $R^{4}$的子空间. 除了包含以上三个列向量, 该矩阵的列空间还包括这个三个列向量的各种线性组合.

那么这个列空间有多大呢? 这就需要 Ax = b 方程来解释了.

还是取上面那个 A, 且 Ax = $\left|\begin{matrix}1&1&2\\2&1&3\\3&1&4\\4&1&5\end{matrix}\right|$$\left|\begin{matrix}x_1\\x_2\\x_3\end{matrix}\right|$=$\left|\begin{matrix}b_1\\b_2\\b_3\\b_4\end{matrix}\right|$=b.

Question 1: Does Ax = b has a solution for every b?

The answer is no! 我们换一种问法, 问同样的问题, Do the linear combinations of columns of Matrix A fill up 4-D space? 很明显答案是 No, 因为三个四维向量的线性组合是无法铺满整个四维空间的, 就如同两个三维向量无法张开一个三维空间一样.

Question 2: Which b allow us to solve Ax = b?

Ax 就表示着 A 列向量的所有线性组合, 也就是 A 的列空间. 上面提到空 C(A)就是$R^{4}$的一个子空间, 所谓对于一个四维向量 b, 只要 b 在”A 的列空间”这个 $R^{4}$的子空间中, 那么就可以找到一种矩阵 A 的列向量的线性组合来构成 b. 也就是使得 Ax = b 有解.

Question 3: If we remove one column from Matrix A, will the C(A) be affected?

观测三个列向量, 我们不难发现第三列是前两节的和, 也就是说第三列对线性组合没有贡献. 所以我们仅仅依靠前两列的线性组合就可以构成 A 的列空间. 我们称$\left|\begin{matrix}1\\2\\3\\4\end{matrix}\right|$,$\left|\begin{matrix}1\\1\\1\\1\end{matrix}\right|$这样的列为主列.

6.4 Nullspace

所谓的零空间, 就是 Ax = 0 的所有解所构成的一个空间.

还是以上面的矩阵 A 为例, 其零空间就是下面这个方程的解所构成的空间:

Ax = $\left|\begin{matrix}1&1&2\\2&1&3\\3&1&4\\4&1&5\end{matrix}\right|$$\left|\begin{matrix}x_1\\x_2\\x_3\end{matrix}\right|$=$\left|\begin{matrix}0\\0\\0\\0\end{matrix}\right|$, 也就是 x = $\left|\begin{matrix}x_1\\x_2\\x_3\end{matrix}\right|$, 可以看到 x 有 3 个 components, 所以其零空间是 $R^{3}$ 的子空间. 所以对于 m*n 的矩阵而言, 列空间是$R^{m}$的子空间, 零空间是$R^{n}$的子空间.

image-20200808152414709

Lec 7 Solving Ax = 0: Pivot Variables and Special Solutions

7.1 Overview

上一个 lecture 中, 我们讨论了零空间的相关问题, 这一节我们主要是从定义过渡到 Nullspace 的计算, 即如何求解这些空间的一般形式. 给出一种可以解出 Ax = 0 中的 x 构成的零空间的算法.

7.2 Algorithm

Step 1: Do elimination

Step 2: Find pivot and free columns

Step 3: Assign value to free variables (1 or 0)

Step 4: Back substitution

image-20200808153614099

7.3 RREF

简化行阶梯形式 (Reduced Row Echelon Form)

image-20200808153842841

Lec 8 Solving Ax = b

8.1 Overview

这一节我们主要研究 Ax = b 的一般求解方法以及有解条件. 并总结出 rank (秩) 对不同形式方程的解的影响.

8.2 Ax = b

我们先通过一个例子来研究 Ax = b 的可接条件:

image-20200808155914163

很明显, 要保证该方程组有解, 必须满足 $b_3-b_2-b_1=0$. 再看这个条件, 它反映了一种线性组合特点, 即 b 向量的第三个分量是前两个分量之和. 反过来看 A 矩阵本身的特点, 发现 A 矩阵第三行也是前两行的和. 我们之前说过, Ax = b 有解的条件是 b 在 A 的列空间中. 这个例子再一次印证了这个条件.

所以我们可以归纳出, Ax = b 的条件:

  • b is in the column space of A
  • If a combination of rows of A give a zero row, then the same combination of entries of b must give 0

8.3 Algorithm

现在给出求解 Ax = b 的一般算法:

Step 1: Find one particular solution ($x_p$), we can do this by setting all free variables to 0, then solve Ax = b for pivot variables

Step 2: Find the nullspace ($x_n$)

Step 3: x = $x_p + x_n$

我们来验证一下:

$A(x_p+x_n)=Ax_p+Ax_n=b+0=b$

8.4 Rank and Solution

这个非常重要!!!

前提: $A_{m\times n}$, rank = r, and r <= m, r <= n

1) Full Column Rank

因为列满秩, 即 r = n 且 m >= n, 所以该矩阵没有 free variables. 这意味着:

  • 该矩阵的零空间 N(A) = zero vector
  • Solution to Ax = b 如果存在那么只有一个解, 即 Ax = b 有 0 or 1 个解

2) Full Row Rank

因为行满秩, 即 r = m 且 n >= m, 那么在进行消元之后, 矩阵一定没有 zero row, 这意味对 b 没有要求, 所以 Ax = b has solution for every b, 即 Ax = n 有 1 or $\infty$ 个解.

3) r = m = n

由前面两个情况可知, r = m = n 意味着, Ax = b 有且只有一个解, 且一定可逆.

4) r < m, r < n

此时, Row Reduced Form 是 $R = \left|\begin{matrix}I&F\\0&0\end{matrix}\right|$, 很明显此时要么无解, 要么有无穷多解.

Lec 9 Independence, Basis and Dimension

9.1 Overview

之前通过消元法处理矩阵的时候, 我们有时会发现矩阵中的某一列是其他几列的线性组合的情况. 这一节就主要关于介绍线性相关或不相关性, 并引入向量空间的两个重要概念: 基 (Basis) 和 维数 (Dimension).

9.2 Independence

Vectors $x_1,x_2,…,x_n$ are linear independent if:

  • No linear combination gives zero vector (except zero comb)
  • Rank = n, which means there’s no free varible. ==> N(A) = zero vector

其余情况都是线性相关.

噢对了, 扁平型的矩阵即对于$A_{m \times n}$而言, m < n. 那么Columns of A 一定是线性相关的. 为什么? 因为 There are non-zero solutions to Ax = 0 since there will be free variables.

9.3 Span

Vectors $x_1,x_2,…,x_n$ span a space means: the space consists of all linear combinations of those vectors.

9.4 Basis

Basis for a space is a sequence of vectors $x_1,x_2,…,x_n$ with two properties:

  • They are linear independent
  • They span the space

我们来看一个例子:

​ Space is $R^{3}$.

​ So one basis is $\left|\begin{matrix}1\\0\\0\end{matrix}\right|$,$\left|\begin{matrix}0\\1\\0\end{matrix}\right|$,$\left|\begin{matrix}0\\0\\1\end{matrix}\right|$; Another basis is $\left|\begin{matrix}1\\1\\2\end{matrix}\right|$,$\left|\begin{matrix}2\\2\\5\end{matrix}\right|$,$\left|\begin{matrix}3\\1\\4\end{matrix}\right|$.

一个重要结论:

For $R^{n}$, n vectors give basis if the nxn matrix with those columns being invertible. 我们可以这样理解: 从线性变换的角度来看, 逆矩阵可理解为原矩阵的反向变换, 比如一个向量被顺时针旋转 90 度, 那么逆矩阵就可以将其逆时针还原 90 度. 然而对于没有满秩的矩阵进行线性变换会导致降维, 试想一下3 维空间被拍平成 2 维矩阵能被还原吗?

9.5 Dimension

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

Lec 10 The Four Fundamental Subspaces

10.1 Overview

这一节我们介绍四个基本子空间, 这是线性代数的核心部分, 非常重要!!!

Suppose A is a m by n matrix, the four fundamental subspaces are:

  • Column Space C(A) $⇒$ subspace in $R^{m}$
  • Nullspace N(A) $\Rightarrow$ subspace in $R^{n}$
  • Row Space C($A^T$) $⇒$ subspace in $R^n$
  • Nullsapce of $A^T$ N($A^T$) $⇒$ subspace in $R^{m}$

image-20200808181618634

10.2 Column Space

列空间是矩阵 A 的列向量线性组合所构成的空间. 对于$A_{m \times n}$而言, 每个列有 m 个分向量, 因此列空间是$R^{m}$的子空间.

设矩阵的秩为 r, 则 A 有 r 个主列, 这 r 个主列就是列空间 C(A) 的一组基, 一组基里面有 r 个向量, 所以列空间维数为 r.

  • rank(A) = r
  • basis = pivot columns
  • dim(C(A)) = r

10.3 Nullspace

零空间即 Ax = 0 的解所构成的空间. 由于 x 本质是对矩阵 A 进行线性组合, A 一共有 n 个列向量, 所以 Nullspace 是$R^{n}$的子空间.

当矩阵 A 的秩为 r 时, 矩阵 A 有 n-r 个free columns, 即 x 中有 n-r 个 free variables. 这意味着 Ax = 0 有 n-r 个特殊解.所以:

  • rank(A) = r
  • basis = special solutions for Ax = 0
  • dimension(N(A)) = n - r

10.4 Row Space

类似列空间, 行空间就是矩阵 A 各行的线性组合所组成的子空间, 也可以理解为 A 的转置矩阵的列空间, 即 C($A^T$). A 的每个行向量都有 n 个分量, 所以行空间是$R^n$的子空间.

A 的行空间可以转化为 $A^T$ 的列空间. 但我们这里还是直接对 A 的行向量进行线性变换来研究行空间的 basis 和 dimension.

image-20200808181808928

从这个例子我们知道:

  • rank(A) = r
  • basis = first r rows of R
  • dim(C($A^T$) = r

10.5 Left Nullspace

左零空间即矩阵 A 的转置矩阵的零空间: N($A^T$)

So 为什么它被称为左零空间?

image-20200808182406994

那么 basis 和 dimension 呢? 我们看下面这个图:

image-20200808183123112

我们不难发现, 在 A 变化到 R 之后, 有一行全是 0, 即说明经过A 的行经过某种线性组合之后, 得到了zero vector, 而造成这种变化的向量即是 Left Nullspace, 也就是 上图中 E 矩阵的第三行. 那么如何得到 E 矩阵呢? 我们就要用到之前介绍过的 Gauss-Jordan Idea, 这里我就不再赘述了.

10.6 Extension of Thoughts

From Vectors to Matrices

Let’s suppose all 3x3 matrices form a new “vector” space M.

Some subspaces of M:

  • Upper Triangular Matrix
  • Symmetric Matrix
  • Diagonal Matrix

So what’s the dimension of these subspace?

image-20200808185010765

Lec 11 Matrix Space: Rank 1, Small World Graph

11.1 Overview

本节我们将承接上文所讲的矩阵空间, 研究矩阵空间的维数和基数等问题. 本节也会介绍秩为 1 的矩阵特点. 并引入图论.

11.2 Matrix Space

我们将所有 3x3 的矩阵都看作”向量空间”中的元素. 很明显, 由所有 3x3 矩阵构成的集合中, 矩阵之间的 Addition 和 Multiplication 都是封闭的, 所以所有 3x3 矩阵构成的集合 M 可以被称为空间.

上文也介绍过, M有三个基本子空间:

  • Upper Triangular Matrix
  • Symmetric Matrix
  • Diagonal Matrix

很明显矩阵空间 M 的维度为 9, basis 如下所示:

image-20200809095011923

那么问题来了: 上面的基本子空间的维数是什么呢?

  • Upper Triangular Matrix: 6

    image-20200809095306456

  • Symmetric Matrix: 6

    image-20200809095337705

  • Diagonal Matrix: 3

    image-20200809095426052

我们之前讨论过两个 subspace 的交集也是 subspace, 正如这里的 Diagonal Matrix 就是 U 和 S 的交集. 那么并集呢? 我们说过并集并不是 subspace. 但是有一个概念不是并集但总容易搞混那就是 Sum of Two Subspaces. 很明显 S + U = M!!! 所以:

  • $dim(S+U)=9$

  • $dim(S)+dim(U)=dim(S+U)+dim(S\cap U)$

11.3 Rank 1 Matrix

研究秩 1 矩阵的原因

  • 它易于分解.

image-20200809100313788

  • 用于搭建其他矩阵

    比如秩为 4 的矩阵可以通过四个秩一矩阵就能搭建出来. 具体过程类似于矩阵乘法中的”列乘行”形式, 通过一列一行搭出一个矩阵.

我们来思考一个问题:

所有秩为 4 的矩阵构成的集合 M, 能被称之为空间吗? 答案是 No! 比较简单的原因是其不包括零向量, 此外还因为: $R(A+B)\leq R(A)+R(B)$.

我们再思考另外一个问题来加深对子空间的理解:

在四维空间中的每个向量都有四个分量 v = $\left|\begin{matrix}v_1\\v_2\\v_3\\v_4\end{matrix}\right|$, 设 S 为一个集合, 其中的向量都满足: $v_1+v_2+v_3+v_4=0$. 那么请思考 S 是不是一个子空间? 若是, 其维度是多少?

很明显 S 是一个子空间, $v_1+v_2+v_3+v_4=0$ 这个条件对 Addition 和 Multiplication 都封闭. 而且 S 中肯定有零向量. 我们也可以用另一种方式来理解: 不难发现 S 是线性方程组 Ax = 0 的零空间, where A = [1, 1, 1, 1]. 所以dim = 3 = n - r, 其基为 Ax = 0 的三个特解 (free variables). 至于左零空间 N($A^T$): A的左零空间即是线性组合各行得到零向量的方式. 很显然, 这个 A 得左零空间只有零向量.

11.4 Small World Graph

image-20200809102742261

Lec 12 Graphs, Networks and Incidence Matrices

12.1 Overview

本节主要介绍图和矩阵之间的关联, 并利用矩阵说明图的特点. 这一节与之前几节的区别主要在于, 前面例子中的矩阵中的元素大都是为了说明性质编造出来的, 而本节中矩阵中的元素都是来源于实际问题, 更能体现出我们之前介绍的性质在实际问题中有什么作用.

12.2 Graphs and Incidence Matrices

我们先给出一个 Graph 和其关联矩阵 (Incidence Matrix):

image-20200809104215371

先简单介绍一下上面的 5x4 的关联矩阵:

  • 每一列代表一个node
  • 每一行代表一条edge 的走势, 该 edge 以哪一个node 为起点, 对于的矩阵中该元素为 -1, 而以哪个 node 为终点, 对应矩阵中该元素为 1.

Ok, 在有些基本了解之后, 我们来研究一下图和矩阵所代表的实际意义. 我们假设 x 为每个 Node 上的电势, 研究 Ax = b 形式下, 我们能得到什么定律!

image-20200809114441365

1) 首先我们研究 b 是零向量, 也就是Ax 构成的 Nullspace 的情况, 这时我们要求 Ax = 0. 基于我们之前所学的知识, 我们不难得到, 当 b = 0 时, 图上各点的电势必须相等. 我们知道, 电势差和电流的形成有直接关系, b = 0 说明我们求解的情况是各个边上都没有电流, 而我们最后解得, 各点电势相等时, 各边电流为 0, 这符合我们初中学的物理学常识.

2) 那么如果 b 不等于 0 呢? 我们可以通过 $X_p+X_n$ 的情况求出不同 b 的情况下方程所对应的解, 代表着不同电势差下, 各点电势的大小.

各边的电流为 $y_1,y_2,y_3,y_4,y_4$, 接下来我们来看一下左零空间 $A^Ty=0$有什么特点. 注意上面我们得到的结果:

  • $-y_1-y_3-y_4=0$
  • $y_1-y_2=0$
  • $y_2+y_3-y_5=0$
  • $y_4+y_5=0$

这个结果阐述了一个定律 ===> Kirchoff’s Current Law (基尔霍夫定律), 即每个 Node 流入流出电流相同. 然后引入一个电阻系数矩阵, 我们就可以得到教授最后引入外加电源的影响的公式:

image-20200809120134440

12.3 Tree

Tree 就是 Graph with no loops.

Lec 13 Orthogonal Vectors and Subspaces

13.1 Overview

这一节我们还是研究四个基本子空间, 但是我们本节主要从正交的角度来探讨这些空间具有的性质和正交向量的特点等.

13.2 Orthogonal Vectors

我们首先了解一下正交的概念, 在线性代数中, 正交即垂直:

image-20200809121228627

13.3 Orthogonal Subspaces

image-20200809120920895

ok 在介绍完向量正交之后, 我们来了解一下空间正交. Orthogonal Spaces 则是指: Every vector in S is orthogonal to every vector in T. 这里有一个问题要注意一下, 这个例子特别容易搞混淆, 黑板与地面的两个平面的子空间并不正交, 因为这两个平面有交线, 而这个交线无法满足空间正交的定义. 这也提醒了我们: 两个平面在某一非零向量处相相交, 那么这两个平面一定不正交.

说了这么多们来看一下子空间正交的简单例子:

以 $R^2$ 的子空间为例, 两个相交的子空间为两条 L 在原点处互相垂直.

Row Space is orthogonal to Nullspace, Why?

我们看一下 Ax = 0, 这里的解是 Nullspace, 而 x 与 A 的每一行点乘均为 0. 我们再引入一个概念: Nullspace 和 Row Space 的关系类似于将一个空间一分为二的两个子空间. 从上图可以发现行空间和列空间的维数之和正好为 n. 我们来看个例子:

image-20200809123132921

在这个例子中, A 的行空间是 1 维的, 而对应零空间是(3-1=2)二维的, 可以理解为垂直于向量(1,2,5) 的一个平面.

注: 这里做一个更正, 矩阵相乘的结果是 $\left|\begin{matrix}0\\0\end{matrix}\right|$

13.4 Solve Ax = b When There is No Solution

在上一节电流电势的应用分析中, 我们了解到矩阵的数据多来源于实际测量, 那么就势必会有测量不准确的情况. 例如有时候我们求解 Ax = b 方程时, 如果 A 的行数太多, 那么其中就很有可能混进去一些不准确的数据. 这时我们以往的手段求解方程并不会求出准确的解, 这就引出了我们这部分内容.

既然无法求出解, 那么我们就用一些手段求出方程的最优解 (Best Solution), 类似于一种拟合. 大致如下:

image-20200809131037994

这部分我们利用了 $A^TA$ 矩阵的特殊性质:

image-20200809131137750

这样我们就能构造出一个新矩阵: $A^TA$, 并利用该矩阵求出最优解. 但我们需要注意新矩阵 $A^TA$ 并不总是可逆的, 所以在在求解时需要注意 A 的特点. 很明显当矩阵 A 列向量线性相关的时候, $A^TA$ 就不可逆了.

image-20200809131410599

那么 $A^TA$ 的可逆的判断依据是什么呢?

image-20200809131510872

具体的证明会在下一节详解. 这里我们得出一个结论, 在求最优解的时候要首先判断 A 的列向量之间是否线性无关, 再进行求解.

Lec 14 Projections on Subspaces

14.1 Overview

这一节主要是关于投影 (Projection), 从向量的投影入手, 并延伸到高维投影. 至于为什么用投影!!! 我们在上节内容有讲存在矩阵的行过多无法求解的情况, 这个时候我们需要求最优解. 我们就需要将 b 投影到矩阵 A 的Column Space 上来求一个最优解.

14.2 Vector Projection

如图所示, 向量 p 是向量 b 在 a 上的投影, 我们注意到向量 p 是向量 a 的倍数, 即 p = xa. 而投影得到的向量 p 和原向量 b 之间的误差是 e = b - p. 同时投影得到的向量 p 也可以直接通过一个投影矩阵 (Projection Matrix), 从 b 变换为 p, 即 p = Pb.

image-20200810122505319

从上图可知, 误差向量 e 是垂直于向量 a 的, 因此 $a^T(b-xa)=0$, 经过一定代数变化之后, 我们不难得到 $x=\frac{a^Tb}{a^Ta}$. 那么 $p=xa=\frac{a^Tb}{a^Ta}a=Pb$, 因此投影矩阵为 $P=\frac{aa^T}{a^Ta}$. 如图所示:

image-20200810123019329

我们再来看看投影矩阵 P 的几个性质:

  • 基于 Lec 11 中的知识点, 我们知道在上图的情况下, 投影矩阵的秩为 1, 而且其列空间为 Line through vector a
  • $P^T=P$, since $aa^t$ 是对称矩阵
  • $P^2=P$, since 二次投影的结果就是一次投影的结果.

14.3 General Projection

我们还是从一个例子入手, 下图中$a_1,a_2$是构成平面的一组基, 向量 p 是向量 b 在平面上的投影. 如图所示

image-20200810124820990

现在 $Ax = b$ 的问题已经转换为求解 $A\hat{x}=p$ 的问题.

image-20200810125544175

我们得到了 $A^T(b-A\hat{x})=0$, 而且也验证了误差向量 e 是在矩阵 A 的左零空间里, 而且垂直于矩阵 A 的列空间, 也就是我们的平面. 我们做进一步推导:

image-20200810130008561

值得一提的是最后我们得到的投影矩阵是 $P=A(A^TA)^{-1}A^T$, 注意这里不可消!!! 因为矩阵 A 并不是一个方阵, 其没有逆矩阵. 加入矩阵 A 是方阵, 那么投影矩阵就是单位矩阵, 等于自身投影到自身. 而且这里的投影矩阵也有着相同的两个性质:

  • $P^T=(A(A^TA)^{-1}A^T)^T=A(A^TA)^{-1}A^T=P$
  • $P^2=P$

14.4 Introduction to Least Squares

image-20200810130925681

Lec 15 Projection Matrices and Least Squares

15.1 Overview

这一节主要是讲最小二乘法, 并对上一节中的投影进行更叫深入的研究. 在上一节的最后一部分我们可以知道, 其实最小二乘法就是一种投影, 保证了误差最小 (最优解). 另外, 投影也与列空间和矩阵的左零空间有关.

15.2 Review on Projection Matrices

对了, 我们在上一节和这一节的假设都是 $A^TA$ 是可逆的.

我们已经知道投影矩阵 $P=A(A^TA)^{-1}A^T$. 投影矩阵 P 是将 vector b 投影到矩阵 A 的列空间上!!!

  • If b in column space of A, Pb = b

    如果向量 b 在矩阵 A 的列空间里面, 那么一定存在一个 x 使得 Ax = b, 将之带入 Pb 我们可以得到, $Pb=A(A^TA)^{-1}A^TAx=Ax=b$

  • If b is perpendicular to column space of A, Pb = 0 ==> 一个点. 这里的 b 将会在矩阵 A 的左零空间, 即 $A^Tb=0$

    image-20200810143944664

这里的 (I-P) 也可以看做一个投影矩阵, 作用是将 b 向量投影到左零空间中.

15.3 Least Squares

书接上文!

image-20200810130925681

很明显, 这个方程无解, 因为这三点不共线. 这是典型的矩阵行比列多, 也就是说方程多于未知数. 既然无法共线那么我们就来找 $Ax$ 和 $b$ 之间的误差, 并将其最小化:

image-20200810201843421

我们可以将这些误差也就是偏移量反应到图上去, 以点 (1, 1) 为例:

image-20200810202111405

其中 b 表示该点的真实位置, e 代表着偏移量也就是误差, p 代表着拟合后的位置, 反映到列空间和左零空间的涂上就是:

img

本质就是将 b 投影到矩阵 A 的列空间中. 现在我们来研究如何拟合, 将矩阵 A 和向量 b 代入 $A^TA\hat{x}=A^Tb$, 我们解一下方程.

image-20200810205552877

但值得注意的一点是: 我们在这里并没有考虑 outliers!!!

对了, 我们在这一节和上一节都用了一个前提假设, 就是 $A^TA$ 是可逆的. 但是什么情况下是可逆的呢? 在上一节我们提出了, 如果矩阵 A 各列线性无关, 则矩阵 $A^TA$ 可逆. 我们接下来证明一下这个结论.

Let’s suppose $A^TAx=0$, 那么如果矩阵 $A^TA$ 要可逆, 那么其对应的 Nullspace 就必须仅含零向量. 那么我们就来证明一下这个 $x$ 只能是零向量.

我们在等式两边同时乘以一个 $x^T$, 得到 $x^TA^TAx=0$, 也就是 $(Ax)^T(Ax)=0$, 这意味着 $Ax=0$. 而我们知道当矩阵 A 各列线性无关的时候, 要使 $Ax=0$, 只能是 $x$ 为零向量.

因此我们证明了: 如果矩阵 A 各列线性无关, 则矩阵 $A^TA$ 可逆.

15.4 Orthonormal vector

这部分是为了下文做出基本介绍.

之前我们见过$\left|\begin{matrix}1\\0\\0\end{matrix}\right|$,$\left|\begin{matrix}0\\1\\0\end{matrix}\right|$,$\left|\begin{matrix}0\\0\\1\end{matrix}\right|$这组基, 它们是互相正交的, 但是它们还有更特殊的性质, 即它们都是单位向量, 长度为 1. 所以我们引入一个新名词: 标准正交向量 (Orthonormal vectors). 同样的标准正交向量还有: $\left|\begin{matrix}cos\theta\\sin\theta\end{matrix}\right|$,$\left|\begin{matrix}-sin\theta\\cos\theta\end{matrix}\right|$

Columns are definitely independent if they are perpendicular vectors.