Schedule

• Four fundamental subspaces (for matrix A)

4 Subspaces – 4个子空间

假定A为m\times n的矩阵, 与其相关有如下四个子空间:

• 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

可以看出,在n维空间R^n中存在两个子空间,一个是r维的行空间,另一个是n-r维的零空间, 两个空间的维数和为n.
同样的,在m维空间R^m中,存在两个子空间,一个是r维的列空间,另一个是m-r维的左零空间,两个空间的维数和为m.

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
矩阵A在经过消元和行变换之后得到R, 可以看出C(R)\ne C(A),但是有相同的行空间(row space).
A和R的行空间的基是R中的非零r行.

Basis of row space is the r rows of R.

行空间没有发生变化的原因是因为在消元和行变化的过程中,发生变化的是行与行之间的加减和数乘,这可以理解为原来同处于同一空间内的两个向量的线性组合仍处于同一空间.

为什么这个基(R的非零r行)的张成空间是行空间?也就是为什么矩阵A的各行是这些行的线性组合?
这是因为通过各行消元的逆操作,可以从R逆向推导出A.

N(A^T)为什么叫左零空间?
假设左零空间中的向量为y, 则A^Ty=0. 同时对等式两边进行转置, 得到y^tA^{TT}=0^T,也就是y^TA=0, 因为y^T在A的左边,所以叫左零空间.

如何求解左零空间?
Guass-Jordan 方法
[A_{m\times n} I_{m\times m}] \rightarrow [R_{m\times n}E_{m\times m}]
在第二章中我们提到过通过Guass-Jordan方法获取A的逆(如果A可逆的话), 只不过那时对应R的是单位矩阵I.而在这里A因为是m\times n的长方形矩阵,所以不可逆.
求出E是为了求解左零空间的基和维数.

New vector space – 新的向量空间

对于所有3\times 3的矩阵, 将矩阵看做”向量”, 每个3\times 3的矩阵都是一个”向量”.
为什么可以这么做? 这是因为同样的3\times 3的矩阵都可以互相相加, 也可以进行数乘, 同样也可以进行线性组合, 也存在某个线性组合的结果为零矩阵, 所以可以在一定程度上将这些矩阵看做”向量空间”.
用M来表示由所有3\times 3矩阵组成的矩阵”空间”
这像是把R^n的概念延伸到了R^{n*n}, 在这个空间里仍然可以进行相加和数乘(忽略矩阵可以相乘的性质).

Schedule

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

Independence – 线性无关性

假设A是一个m\times n的矩阵(m)(即A是一个长方形矩阵),那么对于Ax=0来说一定有非零解,这是因为一定存在自由变量.

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.

什么时候向量x_1,x_2,…x_n是线性无关的?

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

从而可以得出, 零向量和任意向量均相关.
所以如果向量组中有一个零向量,那么该向量组必定相关.

那么对于位于同一平面内的三个非零向量v_1,v_2,v_3,它们是否一定线性相关呢? 答案是肯定的.
理由是由v_1,v_2,v_3组成的向量组经过消元后必定有自由变量,所以肯定有非零解.
假设该向量组为A=[v_1,v_2,v_3]=\begin{bmatrix}2&1&2.5\\1&2&-1.5\end{bmatrix},那么对于Ac=0的A的零空间存在非零组合,则向量组相关.

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.

当向量组(n个列向量)线性无关时,则由向量组构成的矩阵秩为n, 所有的列均为主列, 这是因为自由列的实质是主列的线性组合.

Spanning – 张成

向量v_1,…v_l张成一个空间意味着这个空间由这些向量的线性组合构成.

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.
其中的一个基是\begin{bmatrix}1\\0\\0\end{bmatrix},\begin{bmatrix}0\\1\\0\end{bmatrix},\begin{bmatrix}0\\0\\1\end{bmatrix}.
这并不是唯一的一个基,还有其他的基类似于\begin{bmatrix}1\\1\\2\end{bmatrix},\begin{bmatrix}2\\3\\5\end{bmatrix},\begin{bmatrix}3\\3\\8\end{bmatrix}.

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)
这里需要注意的是,2是A的列空间的维数,而不是A的维数,这是因为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}
可以看出,如果方程式组有解的话,行三必须得到满足,即b_3-b_2-b_1=0

假设取b=\begin{bmatrix}1\\5\\6\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}
这样的话,行三的方程组可以得到解. 那么什么样的b可以满足方程式组?

Solvability is the condition on b.

可解性指的是b满足什么条件,才能使得Ax=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:
这里一直不明白的问题是,为什么b属于A的列空间或者b满足A的线性组合就可以说方程式组有解?
以上述例子为例,即使满足行三方程式, 那么行一和行二就一定会满足么?
实际上是的,因为在上节课中Ax=0的学习中可以知道,自由列的值变化,不影响解.
所以在增广矩阵经过行消元后得到的矩阵中,如果行三,也就是零行得到满足,则剩余其他非零行可以通过自由变量赋值0从而求得特定解.

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_2和x_4设置为0(自由变量),可以回代 求得x_1=-2, x_3=1.5,从而求得一个特解(particular solution).
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 = b和Ax_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矩阵

可以得出r与m之间初步的关系是r\le m, 因为主元的个数不会超过行的个数.同样,r\le 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,如下所示:
A=\begin{bmatrix}1&2&2&2\\2&4&6&8\\3&6&8&10\end{bmatrix}
可以看出列二是列一的倍数,所以它们是相关的.
同样,行三是行一和行二的和,所以它们也是相关的.

在消元的过程中,可能会出现主元位置元素为零的情况.

在消元的过程中,零空间不会改变.这是因为在消元的过程中,一行加上另一行的倍数不会改变解,因此零空间也不会变(也是因为b全部为零,所以解不会变).实际上,改变的是列空间.

消元步骤如下:
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
这里,我们得到了矩阵的阶梯形式(echelon form),非零元素以一种阶梯形式出现.

矩阵中非零主元的数被称为矩阵的秩(rank).

Rank of A = # of pivots

消元至此,我们从求解Ax=0转换成求解Ux=0,在转换过程中解不变,零空间不变.

主元所在的列被称为主列,其余的列被称为自由列.

被称为自由列的原因是因为在求解Ux=0的过程中,x_2,x_4可以被赋予任意值而不影响求解,最后求解x_1,x_3即可.

这里因为自由列共有两列,所以需要对不同的自由变量进行赋值.
假设将x_2,x_4进行赋值,x_2=1,x_4=0,求得x_1=-2,x_3=0;
假设将x_2,x_4进行赋值,x_2=0,x_4=1,求得x_1=2,x_3=-2.

从而求得两个特殊解(special solutions):
\begin{bmatrix}-2\\1\\0\\0\end{bmatrix} 和 \begin{bmatrix}2\\0\\-2\\1\end{bmatrix}
被称为特殊解是因为在于给自由变量分配的特定值.

通过特殊解的线性组合可以得到零空间,即x=c\begin{bmatrix}-2\\1\\0\\0\end{bmatrix}+d\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.

如果m\times n的矩阵有r个主元,那么共有n-r个自由变量,也就是有n-r个特殊解.

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)中的全零行表示该行原为其他行的线性组合,可以被消元过程中去除.

所以R所代表的方程式组为:
x_1+2x_2-2x_4=0 \\ x_3+2x_4=0
对于所有的主列来说,系数矩阵为I=\begin{bmatrix}1&0\\0&1\end{bmatrix}
对于所有的自由列来说,系数矩阵为F=\begin{bmatrix}2&-2\\0&2\end{bmatrix}

---

rref – 简化行阶梯形式

典型的简化行阶梯形式如下:
R=\begin{bmatrix}I&F\\0&0\end{bmatrix}

如何一次求出满足Rx=0的所有特殊解?

通过构造零空间矩阵N(nullspace matrix)可以做到,即RN=0.

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. 满足相加和数乘的线性组合.

常见的三维空间R^3中,可以看出,通过原点的直线和平面都可以构成一个子空间.

那么对于两个子空间,P(通过原点的平面)和L(通过原点的直线),它们之间的组合会不会构成子空间? 即 P \cup L=all vectors in P or L or both.
对于上述举的例子,很容易证明其并非是一个子空间,理由很简单,直线上任意的一个向量和平面上任意的一个向量的线性组合(例如加法)未必一定在两个子空间的并集上, 有可能会在平面和直线之外的空间中.

那么对于P \cap L= all vectors in both P and L是否构成一个子空间呢?
针对例子中的直线和平面,可以看出其交集为原点, 只有原点的空间是一个子空间.
如果不是例子中特定的过原点的直线和平面,则其交集并不一定为原点, 那么其交集则未必能够形成空间.

推广开来,任意两子空间的交集会是子空间么?
答案是肯定的.这是因为对于子空间S和T来说,其包含的向量均满足数乘和加法. 那么对于同时属于这两个子空间的向量集来说, 也一定是满足数乘和加法的.

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如下,列向量均为四维空间R^4中的向量,所以A的列空间是R^4的子空间,记作C(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的列空间有多大? 它是否等同于整个四维空间R^4? 还是四维空间的一个子空间? 这就需要进行求解.

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

Does Ax=b have a solution for every b ?

由上述问题衍生出的另一个问题是, 什么样的b使方程组有解?

Which b allow this system to be solved ?

对于例子中的A,可以看出,其共有四个方程组,但是只有三个未知数.
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

只有当b是A中各列的线性组合时,Ax=b才有解.

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

回到A, 这三个列向量线性无关么? 如果用这三列进行线性组合, 是否每一列都对组合有贡献?线性组合最终得到的结果会是三维空间么? 换句话说,能否去掉某列,列空间不变?

例子中我们可以看出,列三是列一和列二的和, 我们将列一,列二称为主列(pivot column),列三处在前两列组成的平面上.

所以这里矩阵的列空间可以描述为四维空间中的二维子空间.

---

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
零空间关注的是x,可以得出x属于R^3,而列空间属于R^4.

无论什么矩阵,其零空间必然包含0.

通过求解,可以看出线性组合c＝\begin{bmatrix}1\\1\\-1\end{bmatrix}可以满足Ax=0, 其表现为R^3中过原点的一条直线.

同样,可以很简单的得到:

The solutions to Ax=0 always give a subspace.

这是因为零空间中的向量满足加法和数乘的封闭性(这个比较简单,就不赘述了).

求解非零b的解又是什么情况呢? 假设存在如下关系:
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

如果有解,那么它们是否构成子空间? 答案是否定的, 原因是因为解中不包含0.
例子中满足条件的解有\begin{bmatrix}1\\0\\0\end{bmatrix}和\begin{bmatrix}0\\-1\\1\end{bmatrix}(当然不止这两个).解有很多个,但它们构成的是一个不穿过原点的直线. 所以这些解并不能构成空间.

构建子空间的方法:

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.
置换矩阵P,是用来完成行互换的矩阵.
对于可逆矩阵A,我们需要求解Ax=b.求解过程中,如果遇到0出现在主元位置上,则需要将其移走,从而得到非零主元,这就需要用到行互换.

之前章节中提到的A=LU分解中,是在没有行互换的假设下进行的.
那么如果存在行互换,该分解又该用什么样的形式表现?
解决方法是PA=LU. 该描述概括了包含行互换的消元,即将A=LU.

置换矩阵是行重新排列的单位矩阵.
Permutations P is the identity matrix with reordered rows.

对于n维矩阵,其共有n!=n(n-1)\cdots(3)(2)(1)个置换矩阵,并且对每个P,均有P^{-1}P^T,也可以写成P^TP=I

---

Transpose – 转置矩阵

假设有矩阵\begin{bmatrix}1&3\\2&3\\4&1\end{bmatrix},那么其转置矩阵将是\begin{bmatrix}1&2&4\\3&3&1\end{bmatrix}.

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

---

Symmetric Matrix – 对称矩阵

对称矩阵,也就是说对于矩阵A,其转置等于其自身A^T=A.
对于任意矩阵R,R^TR都是对称的.
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}

加法和数乘共需满足8条运算规则.

举一个不是向量空间的例子: 对于二维空间中的第一象限, 将其看做一个空间, 那么这个空间是一个向量空间么?
通过简单的数乘,可以将第一象限中的向量转换为其他象限中的向量,所以第一象限组成的空间对于实数的数乘并不封闭,因此它并不是一个向量空间.

向量空间必须对数乘和加法两种运算是封闭的.
A vector space has to be closed under multiplication and addition of vectors. In other words, linear combinations.

再举一个空间例子,使其是R^2的一部分,但是满足加法和数乘的封闭性,那么该直线是R^2的子空间么? 例如,一条过原点的直线?

并非R^2中所有的直线均是子空间. 可以简单的查验, 对于不过原点的直线,无法满足简单的加法A-A=0.

也就是说,0点必须在直线上,否则不能构成子空间.

对于R^2来说,R^2的子空间有哪些?
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} 仅含零向量的空间
同理,R^3的子空间有:
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}
观察A中的各列向量,各列均属于R^3.
如果用这些列来构造R^3的子空间, 那么除了这些之外,还需要什么才能构成子空间?

所有的列向量的线性组合构成一个子空间.
All these linear combinations form a subspace.

这样形成的空间被称为列空间(column space), 记作C(A)

Schedule

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

---

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

假设 A , B 均可逆,那么 AB 的逆是什么?

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

这就像是穿袜子,穿鞋子,所以脱下来也得先脱鞋子再脱袜子.

对于某可逆方阵来说,其转置矩阵的逆是?

对于 AA^{-1}=I 同时进行转置,得到 (A^{-1})^T(A)^T=I .

从而得知对于可逆方阵 A来 说,其转置矩阵 A^T 的逆是 (A^{-1})^T .

注意, 这里提到的是方阵, A^{T} 也是方阵, 故 A^{T} 的左逆和右逆相同.

所以才可以说其转置矩阵 A^T 的逆是 (A^{-1})^T .

为什么对于 AA^{-1} 的转置是 (A^{-1})^T(A)^T ?

假设 A 为 m\times n 矩阵, B 为 n\times p 矩阵,两者均可逆,

则进一步设 AB=C ,其中 C_{ij}=\sum_{k=1}^nA_{ik}B_{kj}.

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

因为 B^T_{ik} = B_{ki}, A^T_{kj} = A_{jk}, 所以 D_{ij}=\sum_{k=1}^nB^T_{ik}A^T_{kj} = \sum_{k=1}^nA_{jk}B_{ki} = (AB)^T

从而实现证明 (AB)^T=B^TA^T

---

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

对于主元全部非0的可逆矩阵 A ,经过消元后得到 U , 那么对于 A=LU 如何求解 L ?

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}

对于想求解的 L ,可以从 A=LU 得知, L=E^{-1} ,所以 L=\begin{bmatrix}1&0\\4&1\end{bmatrix}.

这里 U 表示的是上三角(Upper triangular)矩阵,而 L 代表的是下三角(Lower triangular)矩阵.

有时候会将主元单独列出来组合一个矩阵,从而形成 A=LDU 的形式. 这里D指的是对角矩阵(Diagonal Matrix).

\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}

对于 E_{32}E_{31}E_{21}A=U (no row exchanges)的情况下, 如果想得到 A=LU 中的 L ,则可以得出 L=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}

对于3维矩阵来说,假设存在如下的变换使得 EA=U ,同时 E_{31}=I ,那么:

\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)

对于 A=LU ,如果不存在行互换,消元乘数(即消元步骤中需要乘以并减去的倍数)可以直接写入 L 中.

If no row exchanges, multipliers go directly into L.

对于大小为 n \times n 的矩阵 A 的消元,其总步骤数共有多少? 消元的总步骤数是否正比于 n 或 n^2 或 n^3 ?

假设 n=100 , 并且矩阵 A 中没有0(如果有很多0的话操作会快很多), 将一次操作定义为针对一个元素的一次乘法和加法.

第一行不变,将其他行的首个元素系数消除,将进行大约100^2次操作(如果第一行也发生变化的话就正好是100^2次,准确的数字应该是100*99),

同样对第二行进行消元,第二行不变,将第二主元下所有其他系数消除,则进行大约99^2次操作,

依次进行下去,最终总操作数为 Count=n^2+(n-1)^2+\cdots+1^2= \frac{1}{3}n^3

同时,对于右侧的常数向量 b ,总共需要进行 n^2 次操作.

---

Transposes and Permutations – 转置和置换

对于3维矩阵来说,其置换矩阵有限,如下列举(即互换单位阵各行的所有可能情况),共有 6P ,并且 P^{-1}=P^T :

\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 – 矩阵乘法

点乘法

矩阵乘法的Standard Rule是点乘法,将对应矩阵的行与列相乘,得到结果矩阵中的对应位置的元素.

对于 m \times n 的矩阵 A , 将其与 n \times p 的矩阵 B 相乘,得到 m \times p 的结果矩阵 C=AB .

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 – 列角度

对于矩阵乘法 A*B=C (其中 A 为 m \times n 的矩阵, B 为 n \times p 的矩阵, C 为 m \times p 的矩阵).

可以将 A 考虑成 n 个单独的列向量,从而将矩阵乘法看做是根据 B 每列对 A 各列进行线性组合,从而得到结果中对应的 p 列,即:

Columns of C are combinations of columns of A.

Tips :

这里其实可以转换下思路, 因为对于矩阵乘法 A*B=C , C 的大小是 m \times p, 而 A 的大小为 m \times n, 所以是 A 中的 m 被保留给了 C.

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

Row Way – 行角度

同理,对于矩阵乘法 A*B=C (其中 A 为 m \times n 的矩阵, B 为 n \times p 的矩阵, C 为 m \times p 的矩阵).

可以将 B 考虑成 n 个单独的行向量,从而将矩阵乘法看做是 A 中每行与 B 相乘,从而得到结果中对应的 m 行,即:

Rows of C are combinations of rows of B.

Columns times Rows – 列与行相乘

之前的值,行与列相乘得到的是一个数,那么列与行相乘呢?

对于 m \times n 的矩阵 A 和 n \times p 的矩阵 B , 假设 A 中的一列与 B 中的一行相乘,如下所示:

\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)}

矩阵相乘, A 中含有 n 列,与 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}

在上述的例子中 \begin{bmatrix} 2\\3\\4 \end{bmatrix}*\begin{bmatrix}1&6\end{bmatrix}=\begin{bmatrix}2&12\\3&18\\4&24\end{bmatrix} , 可以将结果矩阵的行空间和列空间均看做直线.

由此可以引出 Block Multiplication 的概念.

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 (证明很简单,在等式两边各乘以求中一个逆即可).

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

存在逆矩阵的矩阵被称为可逆的(invertible)或非奇异的(non-singular).

Singular Matrix – 奇异矩阵

奇异矩阵即非可逆矩阵.

举个例子: A = \begin{bmatrix} 1 & 3 \\ 2 & 6 \end{bmatrix} 可以看出 A 的 行列式(determinant) 为0.

假设 A 乘以某矩阵得到单位阵,那么结果中的列将会是 A 中的列的线性组合.

如果 A 中的列向量是共线的,则由 A 中的列向量线性组合生成的结果矩阵中的列将无法组成单位阵.

这样的线性组合无法组成单位阵,因为 A 中的列向量是共线的.

如果存在非零向量 x ,使得 Ax=0 ,那么可以说 A 不可逆.

证明: 假设逆存在,则同时满足 Ax = 0 \And A^{-1}A = I , 从而得出 A^{-1}Ax = Ix = x =0 , 而 x \neq 0 , 与假设相悖, 从而假设不成立.

对于例子中的矩阵 A ,可以找到向量 x = \begin{bmatrix} 3 \\ -1 \end{bmatrix} ,从而使得 Ax=0 ,所以 A 不可逆.

求逆

假设有如下的矩阵,需要对其求逆,则需满足:

\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]

从而得出 A|I \rightarrow I|A^{-1}

简化形式可得 E[A | I] = [I | A^{-1}] .

这里,因为 EA=I ,所以 EI = E =A^{-1} .

Introduction

课程代码 : MIT 18.06
课程配套教材 : Introduction to Linear Algebra
课程在线网址 : web.mit.edu/18.06
在线网址里有习题和matlab代码等资源.

---

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

方程式组和矩阵之间存在天然的联系. 即方程式组可以用矩阵的形式很优雅的表达出来.
举一个简单的方程式组的例子 : \begin{cases} 2x-y=0 \\\\ -x+y=3 \end{cases}

可以将未知变量的系数看作矩阵的元素,从而将原始方程式组转换为矩阵的形式表达出来, 如下所示 :
\begin{bmatrix}2 & -1 \\\\ -1 & 2 \end{bmatrix} * \begin{bmatrix}x \\\\ y \end{bmatrix} = \begin{bmatrix} 0 \\\\ 3 \end{bmatrix}
这里,我们将 \(\begin{bmatrix}2 & -1 \\ -1 & 2 \end{bmatrix} \) 看作是矩阵 \(A\) , 将 \( \begin{bmatrix}x \\ y \end{bmatrix}\) 看作是向量(Vector) \(X\) , 那么结果 \(\begin{bmatrix} 0 \\ 3 \end{bmatrix}\) 就是向量 \(b\) , 从而得出 \(A*X=b\) .

矩阵 \(A\) ,也被称为 系数矩阵(coefficient matrix).

所以, 正如老师所说,

A matrix is just a rectangular array of numbers.

---

Row Picture

Row Picture, 也就是从行的角度来考虑矩阵内在的含义.
以上面的方程式组为例,
对于方程式(1) \(2x-y=0\) 可以通过假设 \(x=0\) 和 \(x=1\) 分别得出y的对应值为 \(y=0\)和\(y=2\) . 即可以以 \((0,0)\) 和 \((1,2)\) 为线上两点确认方程式(1)在 \(x,y\) 平面上的直线.
同理可得方程式(2)在平面上所代表的线.
通过图像可以看出, 两条线条交于一点 \((1,2)\) .

---

Column Picture

从列的角度来看,上述方程式组可以看做 列的线性组合(linear combination of columns) .
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

同理可以得出对应的矩阵 \(A\) 和向量 \(b\) : \(A=\begin{bmatrix}2&-1&0\\-1&2&-1\\0&-3&4\end{bmatrix}\) \(b=\begin{bmatrix}0\\-1\\4\end{bmatrix} \)
同样,从column picture的角度来看上述方程式组,得出:
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}
可以得出一个解为\(x=0,y=0,z=1\)

对于上述方程式组,如果\(b\)的值变为\(\begin{bmatrix}1\\1\\-3\end{bmatrix}\), 则可以得出一个解为\(x=1,y=1,z=0\)

以此类推,得出一个问题:

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

即, 是否对于任意的 \(b\) , \(Ax=b\) 都有解?

对于上述方程式组,如果三个列向量均处在同一平面内, 则无法通过线性组合方式生成不在这个平面内的向量, 那么对于空间内其他不属于此平面的向量就无解.

这种情况被称为奇异(singular case),该矩阵非可逆(not invertible),不是对于所有的 \(b\) 都有解.

即 : 奇异不可逆.

---

Matrix Form – 矩阵形式

矩阵乘以向量的形式(multiply a matrix by a vector) 表达为 \(Ax=b\) .
e.g.
\begin{bmatrix}2&5\\\\1&3\end{bmatrix}*\begin{bmatrix}1\\\\2\end{bmatrix}

可以将其看作 1个列1 和 2个列 2 相加:
\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\) .