MIT18.06 Linear Algebra

前言

MIT 18.06 Linear Algebra 公开课，由Gilbert Strang教授主讲，b站视频地址，共35讲。

讲座内容

Lecture 1: The Geometry of Linear Equations

从线性方程组出发，逐步引出线性代数。

Lecture 2: Elimination with Matrices

介绍“消元法”求解线性方程组，引出逆矩阵。

Lecture 3: Multiplication and Inverse Matrices

1. 矩阵乘法$A_{m\times n}{B}_{n\times p}=C_{m\times p}$的5种表示：

   • $C_{ij}=\sum _{k=1}^n{A}_{ik}{B}_{kj}$
   • $C$的列向量是$A$的列向量的线性组合
   • $C$的行向量是$B$行向量的线性组合
   • sum of （ $A$的一列 $\times$ $B$的一行 ）
   • 块矩阵乘法

2. 方阵的可逆性

   • 可逆 $⟺$ 非奇异（non-singular）

• 高斯-若尔当（Gauss-Jordan）消元
  • 消元矩阵E（elimination matrix）
  • 将矩阵$A$后边加上单位阵$I$一起做变换，将得到$E[AI]=[I?]$，根据块矩阵乘法，$EA=I$
  • $(AB{)}^{-1}=B^{-1}{A}^{-1}$

Lecture 4: Factorization into A = LU

1. $AB,A^T$的逆
2. 消元矩阵（elimination matrix）的乘积，以这种总的思路审视高斯消元
   • $A=LU$, $L:$ 下三角矩阵，$U:$上三角矩阵（先考虑在消元时，不需要row exchanges的情况，即不需要调整主元的位置，没有0在主元位置）
   • $E_{32}{E}_{31}{E}_{21}A=U$
     • $A=E_{21}^{-1}{E}_{31}^{-1}{E}_{32}^{-1}U$
     • $LU$包含了$A$的所有信息，求解的复杂度在$O(n^3)$
   • 允许row exchanges，需要使用置换矩阵$P$（Permuations，将单位阵的行交换后得到）
     • $P^{-1}=P^T$
     • $4\times 4$的置换矩阵有24种

Lecture 5: Transposes, Permuations, Spaces ${\mathbb{R}}^n$

1. 置换矩阵
2. 转置
3. 向量空间，子空间
   • 零向量非常重要

Lecture 6: Column Spae and Nullspace

子空间的交集仍是子空间。

1. 列空间
   • $A$的列空间是$A$的所有列的线性组合，记作$C(A)$
   • $Ax=b$有解，当且仅当$b$在$A$的列空间中
2. 零空间
   • $Ax=0$的所有解

Lecture 7: Solving Ax=0 Pivot Variables, Special Solutions

介绍求解$Ax=0$的具体算法。

目标是零空间不会改变 ，在消元过程中，解是不会变的，所以零空间不会改变。

主元（pivot variables）的数量就是秩。

• $Ax=0$，在消元过程中，形成阶梯形式矩阵，判断主元（pivot variables）和自由变量（free variables），自由变量任意取值（001,100,010这样取值）确定特解（special solutions），特解的线性组合都是所有解
• 简化行阶梯形式（reduced row echelon form）
  • 主元的上下都是0
  • Matlab中的rref函数
  • 零空间 $[-F;I]$

Lecture 8: Solving Ax=b Row Reduced Form $R$

求解$Ax=b$。

1. 增广矩阵$[Ab]$;

2. 探讨可解性（solvability）

   • 如果$A$各行的线性组合得到零行，那么$b$中的元素同样组合必然等于0
     • 言下之意是$b$对可解性有约束
   • 第一步，先求特解$x_{particular}$
     • 先设所有自由变量为0，求出一个特解
   • 第二步，求零空间nullspace
   • 第三步，完整解为：
     • $x_{complete}=x_{particular}+x_{nullspace}$

3. $Ax=b$解的情况与秩$r$有关，记简化行阶梯形式为$R$，$F$代表其中的自由变量对应的列

   • $r=m=n$
     • $R=I$
     • 1个解
   • $r=n<m$
     • $R=[I;0]$
     • 0或1个解
   • $r=m<n$
     • $R=[IF]$（这样的表述不够准确，$I$和$F$实际上可能交叉出现）
     • 无穷多解
   • $r<m,r<n$
     • $R=[IF;00]$
     • 要么无解，要么无穷多解

矩阵的秩决定了方程组解的数目。

Lecture 9: Independence, Basis, and Dimension

1. 线性无关性（Linear Independence）
   • $c_1{x}_1+\cdots +c_n{x}_n\ne 0$ （$c_i$不全为0）
   • 如果零空间$N(A)$存在非零向量，那么各列线性相关
   • 关注不为0的线性组合
2. 生成一个空间（Spanning a space）
   • 由一组向量生成空间，意味着这个空间由这组向量的线性组合构成
   • 关注所有线性组合
3. “基”和“维数”（Basis and dimension）
   • 生成空间时，最关心这样的向量组：既能生成空间，本身又是线性无关的
     • 引出了“基”的概念
     • 向量的个数足够多但又不会太多
     • 关注一组线性无关的向量，并张成空间
   • 重要性质：对于给定空间，空间中任意基的基向量个数是相等的
   • 基向量的个数被称为维数
     • 对同一个空间来说，所有基的向量个数是一样的

Lecture 10: The Four Fundamental Subspaces

介绍4个基本子空间，需要回答两个基本问题：

• “基”是什么
• “维数”是多少

1. 列空间$C(A)$

   • ${\mathbb{R}}^m$的子空间

   • $dimC(A)=r$

   • 基就是主列（pivot columns）

     • 注意，简化行阶梯形式$R$, $C(R)\ne C(A)$
       • “行变换”不会对行空间有影响，行空间就是$R$的前$r$行

2. 零空间$N(A)$

   • ${\mathbb{R}}^n$的子空间
   • $dimN(A)=n-r$
   • 基就是$Ax=0$特解组成的矩阵（special solutions）

3. 行空间$C(A^T)$

   • ${\mathbb{R}}^n$的子空间

   • $dimC(A^T)=r$

   • 将$A$进行行变换得到$R$

     • “行变换”不会对行空间有影响，行空间就是$R$的前$r$行

4. $A^T$的零空间$N(A^T)$（也被称为左零空间）

   • ${\mathbb{R}}^m$的子空间
   • $dimN(A^T)=m-r$
   • 相当于$A^{T}y=0⟹y^{T}A=0$
     • 高斯-若尔当消元 $E[A_{m\times x}{I}_{m\times m}]⟶[R_{m\times n}{E}_{m\times m}]$, 初等行变换
     • 通过$E$来求基，$R$中的最后几行为0的话，正好是$y^{T}A$，$y$中向量将$A$的行向量组合为0

Lecture 11 Matrix Spaces Rank 1 - Small World Graphs

介绍由矩阵构成的“向量空间”，（满足向量空间的8大定律的元素都可以构成向量空间）。

比如$M$空间是所有$3\times 3$的矩阵，它的子空间有：

• 对称阵${}_{3\times 3}$
• 上三角矩阵${}_{3\times 3}$

举一个来自微分方程的例子，$\frac{d^{2}y}{d{x}^2}+y=0$的所有解：

• 即$y^{\prime \prime }+y=0$
• 特解：$y=\cos x,\sin x$ （特解还有其它的）
• 完整解：$y=c_1\cos x+c_2\sin x$
• $\cos x,\sin x$就是一组基

回到矩阵上，矩阵的最为关键的数字就是秩（rank），比如：

• $$A=\left[\begin{array}{ccc}1& 4& 5\\ 2& 8& 10\end{array}\right]=\left[\begin{array}{c}1\\ 2\end{array}\right]\left[\begin{array}{ccc}1& 4& 5\end{array}\right]=\overrightarrow{u}{\overrightarrow{v}}^T$$
• 秩为1 的矩阵就像“积木”，搭建任何矩阵
• 例1: 所有秩4矩阵不能构成子空间
• 例2: 将朋友关系建模为矩阵，“六度分离猜想”（number six degrees of seperation）

Lecture 12 Graphs,Networks,Incidence Matrices

主要介绍线性代数的应用：

• 表示图结构
• 关联矩阵（Incidence Matrices）
  • 表示电路图，从节点出来用$-1$表示，进入节点用$1$表示，其它用0，节点$x$表示电势，$Ax$可以看作是节点间的电势差。
  • 四个基本子空间对应了物理应用中的定律
  • 主列（线性无关）对应的子图是个树
  • 维度公式$dimN(A^T)=m-r$可以推出欧拉公式：
    • #nodes - #edges + #loops = 1
• 基尔霍夫电流定律（Kirchoff's Current Law, KCL）

Lecture 13 Quiz 1 Review

习题课。

Lecture 14 Orthogonal Vectors and Subspaces

向量的正交，子空间的正交，基的正交。

矩阵$A$的4个基本子空间：行空间(row space)，零空间(nullspace)，列空间(column space)，$A^T$的零空间，关系如下：

• 正交向量，若$\overrightarrow{x}$和$\overrightarrow{y}$正交，则${\overrightarrow{x}}^T\overrightarrow{y}=0$。

• 零向量与任意向量都正交。

• 子空间$S$与子空间$T$正交的意思是：

  • $S$中的每个向量都和$T$中的每个向量正交
  • 两个正交的子空间的交集一定不会是非零向量

• nullspace and row space are orthogonal complements (正交补) in ${\mathbb{R}}^n$

  • 表示零空间包含所有垂直于行空间的向量

• 目前为止讨论了以及即将讨论以下内容：

  • 一，线性代数的基本定理
    • 四个基本子空间的关系
    • 维数
  • 二，正交性
  • 三，基（正交基）

• 本章核心内容

  • $Ax=b$无解时怎么求？(下一章具体介绍)
    • 无解意味着$b$不在$A$的列空间中
    • 当$A$矩阵，$m>n$时，右侧取值大部分情况都无解，（消元后，A的最后几行是0，对b的约束更多）
    • $A^{T}A$矩阵
      • 因为$Ax=0⟹A^{T}Ax=0$，所以$N(A^{T}A)=N(A)$
      • 当且仅当$A$的零空间只有零向量时，$A^{T}A$是可逆的
        • $N(A)=0⟹N(A^{T}A)=0⟹N(A^{T}A)=n-r=0⟹A^{T}A$的秩为$n$

Lecture 15 Projections onto Subspaces

这一章主要介绍投影（Projection）和最小二乘法（Least Squares）。

• 投影矩阵

  

  • 把$b$投影到$a$上，记$a$上离$b$最近的点为$p$
    • $p=xa$ (倍数)
    • $a^T(b-xa)=0$
    • $x=\frac{a^{T}b}{a^{T}a}$
    • $p=a\frac{a^{T}b}{a^{T}a}$
    • 记$p=Pb$，那么$P=\frac{a{a}^T}{a^{T}a}$，$P$称为投影矩阵（projection matrix）
      • $a{a}^T$秩为1
  • 投影矩阵的2个性质
    • 对称：$P^T=P$
    • 如果投影2次，结果和1次一样：$P^2=P$
  • 推广到高维情况
    • 动机，为什么要投影？
      • $Ax=b$也许无解，只能求解最接近的那个可解问题
        • $Ax$总是在$A$的列空间中，$b$不一定在（比如方程有噪声）
        • 微调$b$，把$b$变成列空间中最接近它的那一个
        • 将原问题换作求解$A\hat{x}=p$（有解的），$p$是$b$在列空间上的投影
          • $\hat{x}$不是原来的解，但是是最接近解的
    • $b$有两种情况
      • 一是在列空间中，那么投影就是它自己，投影后不改变原始解
      • 二是不在列空间中，原始方程无解，误差向量$e=b-p$，$e$垂直于超平面
    • 假设$A=[a_1{a}_2]$
      • $p=A\hat{x}$，找到$\hat{x}$
      • 关键在于$e=b-p=b-A\hat{x}$垂直于平面，得：
        • $a_1^T(b-A\hat{x})=0,a_2^T(b-A\hat{x})=0⟹$
        • $A^T(b-A\hat{x})=0$
        • 从上式可得，$e$在$N(A^T)$中，而$N(A^T)$与$A$的列空间$C(A)$是正交的，可得 $e\perp C(A)$
        • 从上面式子可得，非常重要的式子： $$A^{T}A\hat{x}=A^{T}b$$
        • 关于上面这个式子的三个问题：
          • $\hat{x}$是什么
            • $\hat{x}=(A^{T}A{)}^{-1}{A}^{T}b$
          • 投影是什么
            • $p=A\hat{x}=A(A^{T}A{)}^{-1}{A}^{T}b$
          • 投影矩阵是什么
            • $P=A(A^{T}A{)}^{-1}{A}^T$ (需要注意的是，括号不能随便打开，因为$A$不一定可逆)
            • 满足两个性质：
              • 对称
              • $P^2=P$
    • 应用（最小二乘法）

Lecture 16 Projection Matrices and Least Squares

投影、最小二乘法和最佳拟合曲线。

• 回顾投影矩阵

  

  • $P=A(A^{T}A{)}^{-1}{A}^T$
  • $e=b-p=b-Pb=(I-P)b$
    • 所以$I-P$是把$b$投影到$N(A^T)$上的投影矩阵

• 最小二乘法例子

  • 用$y=C+Dt$拟合3个点$(1,1),(2,2),(3,2)$
  • 从投影矩阵角度考虑
    • $A^{T}A\hat{x}=A^{T}b$
    • 求解$\hat{x}$
  • 从最小化均方误差
    • Minimize $||Ax-b|{|}^2=||e|{|}^2$
    • 微分方程求偏导
  • 二者最后得到的正规方程组相同

• 以上推导一直假设$A^{T}A$是可逆的，下面证明当$A$各列线性无关时，$A^{T}A$一定可逆：

  • $A^{T}A$要可逆的话，$N(A^{T}A)$一定只有零向量，即$A^{T}Ax=0$只有零解，
  • 根据$A^{T}Ax=0$，那么有$x^T{A}^{T}Ax=0$，那么有$(Ax{)}^T(Ax)=0$，（$a^{T}a$是长度）,
  • 那么$Ax$一定是零向量，
  • 利用假设，$A$各列线性无关，可推出$x=0$

• 互相垂直的各列一定线性无关

  • 互相垂直的单位向量被称为标准正交向量组（orthonormal vectors）

Lecture 17 Orthogonal Matrices and Gram Schmidt

关于正交性的最后一讲，标准正交基，正交阵（orthogonal matrices），Gram-Schmidt方法。

• 当$Q$是方阵时，才称为正交矩阵
  • $q_i,q_j$表示标准正交向量
  • $Q^{T}Q=I$，$Q^T=Q^{-1}$
  • 比如置换矩阵（permutation matrix）
• $Q$是有标准正交向量的矩阵
  • 投影矩阵为$P=Q(Q^{T}Q{)}^{-1}{Q}^T=Q{Q}^T$
  • 满足投影矩阵的2个性质
    • 对称性
    • $Q^2=Q$
  • 正规方程$A^{T}A\hat{x}=A^{T}b$，对于正交矩阵来说，即$Q^{T}Q\hat{x}=Q^{T}b$
    • $\hat{x}=Q^{T}b$
      • ${\hat{x}}_i=q_i^{T}b$
• Gram-Schmidt 格拉姆-施密特正交化法
  • 对于线性无关的向量$a,b$
  • 第一步，求出正交向量组$A,B$
    • $A=a$
    • $B=b-p=b-\frac{A^{T}b}{A^{T}A}A$ ( 减去$b$在$a$上的投影)
  • 第二步，标准化$q_1=\frac{A}{||A||},q_2=\frac{B}{||B||}$
  • 泛化到3个向量$a,b,c$
  • 第一步，求正交向量组$A,B,C$
    • $A=a$
    • $B=b-\frac{A^{T}b}{A^{T}A}A$
    • $C=c-\frac{A^{T}c}{A^{T}A}A-\frac{B^{T}c}{B^{T}B}B$
• 换个角度看Gram-Schmidt正交化方法
  • 以前的消元法相当于$A=LU$
  • Gram-Schmidt相当于$A=QR$
    • $R$是上三角矩阵，因为后面构造的$q$向量垂直于先前的向量
• 总结
  • $A$的各列线性无关，Gram-Schmidt构造一组标准正交列的矩阵$Q$
    • $A$和$Q$通过上三角矩阵$R$联系：$A=QR$

Lecture 18 Properties of Determinants

方阵的行列式及其10条性质，由1，2，3条性质可推其它。

1. 单位阵行列式为1，$detI=1$ 。
2. 交换行会使行列式正负号相反。
   • 由1，2可得置换矩阵的行列式。
3. 对于某一行，线性（Linear for each row）
   • (a): $$\left|\begin{array}{cc}t\cdot a& t\cdot b\\ c& d\end{array}\right|=t\left|\begin{array}{cc}a& b\\ c& d\end{array}\right|$$
   • (b): $$\left|\begin{array}{cc}a+a^{\prime }& b+b^{\prime }\\ c& d\end{array}\right|=\left|\begin{array}{cc}a& b\\ c& d\end{array}\right|+\left|\begin{array}{cc}{a}^{\prime }& b^{\prime }\\ c& d\end{array}\right|$$
4. 两行相等会使行列式为0。
   • 用性质2可证，交换两行，符号交换但相等
5. 从行$k$减去行$i$的$l$倍，行列式不变
   • $$\begin{array}{rl}\left|\begin{array}{cc}a& b\\ c-la& d-lb\end{array}\right|& \stackrel{\mathrm{性}\mathrm{质}3}{=}\left|\begin{array}{cc}a& b\\ c& d\end{array}\right|+\left|\begin{array}{cc}a& b\\ -la& -lb\end{array}\right|\\ & \stackrel{\mathrm{性}\mathrm{质}3}{=}\left|\begin{array}{cc}a& b\\ c& d\end{array}\right|-l\left|\begin{array}{cc}a& b\\ a& b\end{array}\right|\\ & \stackrel{\mathrm{性}\mathrm{质}4}{=}\left|\begin{array}{cc}a& b\\ c& d\end{array}\right|-0\end{array}$$
6. 若有一行为0，则$detA=0$.
7. 上三角矩阵$u$
   • $$detu=\left|\begin{array}{ccc}{d}_1& ...& ...\\ 0& \ddots & ...\\ 0& 0& d_n\end{array}\right|=d_1\cdot d_2\cdot \cdots d_n$$
8. 当且仅当$A$是奇异（singular）的，行列式为0.
   • 求行列式方法，先求上三角，再求对角，（和消元法一样）
9. $detAB=(detA)(detB)$
   • $det{A}^{-1}=\frac{1}{detA}$
   • $det{A}^2=(detA{)}^2$
   • $det2A=2^{n}detA$
10. $det{A}^T=detA$

Lecture 19 Determinant Formulas and Cofactors

介绍求$detA$的公式，代数余子式(Cofactor formula)，Tridiagonal matrices（除三条对角线上，其它为0）。

利用行列式的基本性质1-3，可以将原行列式化为各行各列仅有一个元素的方阵的行列式之和。

Big Formula:

• $$detA=\sum _{n!}\pm a_{1\alpha }{a}_{2\beta }{a}_{3\gamma }\cdots a_{n\omega }$$，其中$(\alpha ,\beta ,\gamma ,\dots ,\omega )$是$(1,\dots ,n)$的一个排列，正负号待定。

代数余子式（cofactors）：

• 作用是把n阶行列式化简为n-1阶行列式。
• cofactor of $a_{ij}=C_{ij}=\pm$ 把第$i$行和第$j$列去掉的$n-1$阶矩阵，
  • $i+j$为偶，符号为正
  • $i+j$为奇，符号为负
• $detA=a_{11}{C}_{11}+a_{12}{C}_{12}+\cdots +a_{1n}{C}_{1n}$

Lecture 20 Cramer's Rule, Inverse Matrix, and Volume

关于行列式的最后一课，行列式的应用。

• 逆矩阵$A^{-1}=\frac{1}{detA}{C}^T$
  • $C$是由代数余子式组成的矩阵，$C^T$一般称作伴随矩阵
• 克莱姆法则 （Carmer's Rule）
  • $x=A^{-1}=\frac{1}{detA}{C}^{T}b$
  • $x_1=\frac{det{B}_1}{detA},x_2=\frac{det{B}_2}{detA},\dots$
    • $B_i$是将$A$中的第$i$列用$b$替代而得到的矩阵。
  • 克莱姆法则一般不用来解方程，计算太复杂，Matlab中用消元法解方程。
• 行列式的应用
  • 行列式的绝对值等于一个箱子的体积，正负号表示左手系还是右手系。
  • 如果三角形的顶点不在原点，三个顶点坐标为$(x_1,y_1),(x_2,y_2),(x_3,y_3)$，面积为：
    • $$\left|\begin{array}{ccc}{x}_1& y_1& 1\\ x_2& y_2& 1\\ x_3& y_3& 1\end{array}\right|$$
    • 具体推导过程，对上面的矩阵消元，想当于使三角形回到原点

Lecture 21 Eigenvalues and Eigenvectors

方阵特征值和特征向量。

• 特征向量
  • $Ax$平行于$x$的特征向量
    • $Ax=\lambda x$
    • 如果$A$是奇异的（可以把非零向量变成0），$\lambda =0$是特征值。
• 先看投影矩阵$P$
  • 任何平面上的向量就是特征向量，$\lambda =1$，因为$Px=x$
  • 任何垂直于平面的向量，$\lambda =0$，因为$Px=0$
• 性质
  • 特征值的和是矩阵$A$的对角线元素之和($a_{11}+a_{22}+\cdots +a_{nn}$)
• 如何求解特征值
  • 重写为$(A-\lambda I)x=0$，$\lambda$未知，$x$未知
    • 除了零向量，要有非零$x$的话，$A-\lambda I$必须是奇异的 $⟹$ $det(A-\lambda I)=0$
    • 称为“特征方程（characteristic equation）”or 特征值方程“eigenvalue equation”
    • $\lambda$值可能重复
• if $Ax=\lambda x$, then $(A+3I)x=Ax+3x=\lambda x+3x=(\lambda +3)x$
  • 特征值加3，特征向量不变
• 旋转矩阵会有复数解
  • 反对称矩阵会出现复数解

Lecture 22 Diagonalizing a matrix and Powers of A

特征值的第二讲。

• 对角化一个矩阵：$S^{-1}AS=\mathrm{\Lambda }$，
  • $S$由$A$的特征向量组成
    • 可逆$⟹$$n$个线性无关的特征向量
  • 假设$A$有$n$个线性无关的向量，把它们作为$S$的列向量可得：
    • $$\begin{array}{rl}AS& =A[x_1{x}_2\dots x_n]\\ & =[{\lambda }_1{x}_1\dots {\lambda }_n{x}_n]\\ & =[x_1\dots x_n]\left[\begin{array}{c}{\lambda }_1\dots 0\\ 0\dots {\lambda }_n\end{array}\right]\\ & =S\mathrm{\Lambda }\end{array}$$
    • $\mathrm{\Lambda }$是对角矩阵：特征值矩阵
  • 特征值和特征向量提供了理解矩阵幂的一种好方法
    • 假设$Ax=\lambda x$，有$A^{2}x=\lambda Ax={\lambda }^{2}x$
    • $A^2=S\mathrm{\Lambda }{S}^{-1}S\mathrm{\Lambda }{S}^{-1}=S{\mathrm{\Lambda }}^2{S}^{-1}$
    • $A^k=S{\mathrm{\Lambda }}^k{S}^{-1}$
  • 定理
    • 如果所有$|{\lambda }_i|<1$，那么当$k\to \mathrm{\infty }$时，$A^k\to 0$
    • 以上这些推导的前提条件是$n$个线性无关的特征向量
  • 哪些矩阵可对角化呢？
    • 如果$A$矩阵的所有特征值$\lambda$是不同的（没有重根），那么$A$肯定有$n$个线性无关的特征向量。
      • 充分但不必要
    • 如果$A$的特征值有重复，A可能有，也可能没有 $n$个线性无关的特征向量。
• Powers of A
  • ${\mu }_{k+1}=A{\mu }_k$
  • 一阶差分方程${\mu }_{k+1}=A{\mu }_k$，给定起始值${\mu }_0$。求解：
    • 把${\mu }_0$写成特征向量的线性组合后再处理
      • ${\mu }_0=c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n$
      • $\begin{array}{rl}{A}^{100}{\mu }_0& =c_1{\lambda }_1^{100}{x}_1+c_2{\lambda }_2^{100}{x}_2+\cdots +c_n{\lambda }_n^{100}{x}_n\\ & =S{\mathrm{\Lambda }}^{100}c\end{array}$
    • 斐波那契数列例子
      • $0,1,1,2,3,4,8,13,\dots ,F_{100},\dots$
      • 不禁要问
        • 这个数列的“增长速度如何”？
          • 增长速度由特征值决定
      • $F_{k+2}=F_{k+1}+F_k$，二阶差分方程
        • 写成一阶：$${\mu }_k=\left[\begin{array}{c}{F}_{k+1}\\ F_k\end{array}\right]$$
        • 方程组为：
          • $$\{\begin{array}{l}{F}_{k+2}=F_{k+1}+F_k\\ F_{k+1}=F_{k+1}\end{array}$$
        • 可得
          • $$\begin{array}{rl}{\mu }_{k+1}& =\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]{\mu }_k\\ & =\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}{F}_{k+1}\\ F_k\end{array}\right]\end{array}$$
          • 系数矩阵是对称阵，可知
            • 特征值是实数
            • 特征向量一定正交
          • 求系数矩阵的特征值和特征向量
            • $det(A-\lambda I)=0⟹{\lambda }_1=\frac{1+\sqrt{5}}{2},{\lambda }_2=\frac{1-\sqrt{5}}{2}$
            • 特征向量：$$x_1=\left[\begin{array}{c}{\lambda }_1\\ 1\end{array}\right],x_2=\left[\begin{array}{c}{\lambda }_2\\ 1\end{array}\right]$$
          • 然后把$${\mu }_0=\left[\begin{array}{c}{F}_1\\ F_0\end{array}\right]=c_1{x}_1+c_2{x}_2$$
            • $c_1=\frac{1}{\sqrt{5}},c_2=-\frac{1}{\sqrt{5}}$
        • 特征值决定增长的趋势，发散至无穷还是收敛于0

Lecture 23 Differential Equations and exp(At)

微分方程$\frac{du}{dt}=Au$和矩阵的指数$e^{At}$。

• 微分方程
  • 例子
    • $u(0)=[10{]}^T$
    • $\frac{d{u}_1}{dt}=-u_1+2u_2$
    • $\frac{d{u}_2}{dt}=u_1-2u_2$
    • 系数矩阵$A=\left[\begin{array}{cc}-1& 2\\ 1& -2\end{array}\right]$
      • 奇异的
      • $\lambda =0,-3$
      • $x_1=\left[\begin{array}{c}2\\ 1\end{array}\right],x_2=\left[\begin{array}{c}1\\ -1\end{array}\right]$
    • 解的形式是$u_t=c_1{e}^{{}_{1}t}{x}_1+c_2{e}^{{}_{2}t}{x}_2$
    • 首先根据$u_0$确定$c_1=\frac{1}{3},c_2=\frac{1}{3}$
    • 然后得到$u(t)=\frac{1}{3}\left[\begin{array}{c}2\\ 1\end{array}\right]+\frac{1}{3}{e}^{-3t}\left[\begin{array}{c}1\\ -1\end{array}\right]$
    • 可以看出稳态是$u(\mathrm{\infty })=\left[\begin{array}{c}2\\ 1\end{array}\right]$
    • 什么情况下才有稳态？
      • 1. 稳定性 stability，需要$e^{\lambda t}\to 0$，即$Re\lambda <0$ （$Re\lambda$表示$\lambda$的实数部分）
      • 2. steady state需要${\lambda }_1=0,$其它$Re\lambda <0$
      • 3. 无法收钱，if 任一$Re\lambda >0$
    • $2\times 2$矩阵的有稳态的条件是
      • trace ${\lambda }_1+{\lambda }_2<0$
      • $det={\lambda }_1\cdot {\lambda }_2>0$
    • 回到原来的方程组$\frac{du}{dt}=Au$
      • 矩阵$A$表明$u_1,u_2$耦合，关键是特征向量如何解耦。
      • 设$u=Sv$，$S$由特征向量组成，
      • $S\frac{dv}{dt}=ASv⟹\frac{dv}{dt}=S^{-1}ASv=\mathrm{\Lambda }v$
        • 关键在于以特征向量为基，将$u$表示为$Sv$
        • $⟹v(t)=e^{\mathrm{\Lambda }t}v(0)$
        • $u(t)=S{e}^{\mathrm{\Lambda }t}{S}^{-1}u(0)=e^{At}u(0)$
      • 矩阵指数（Matrix exponentials）
        • $e^{At}=I+At+\frac{(At{)}^2}{2}+\frac{(At{)}^3}{6}+\cdots +\frac{(At{)}^n}{n!}+\dots$
          • 类似于$e^x=\sum _0^{\mathrm{\infty }}\frac{x^n}{n!}$
        • $(I-At{)}^{-1}=I+At+(At{)}^2+(At{)}^3+\dots$
          • 要求$At$的特征值都小于1
          • 类似于$\frac{1}{1-x}=\sum _0^{\mathrm{\infty }}{x}^n$
        • 证明$e^{At}$等于$S{e}^{\mathrm{\Lambda }t}{S}^{-1}$
          • $\begin{array}{rl}{e}^{At}& =I+At+\frac{(At{)}^2}{2}+\cdots +\frac{(At{)}^n}{n!}+\dots \\ & =I+S\mathrm{\Lambda }{S}^{-1}t+\frac{S{\mathrm{\Lambda }}^2{S}^{-1}{t}^2}{2}+\dots \\ & =S{S}^{-1}+S\mathrm{\Lambda }{S}^{-1}t+\frac{S{\mathrm{\Lambda }}^2{S}^{-1}{t}^2}{2}+\dots \\ & =S{e}^{\mathrm{\Lambda }t}{S}^{-1}\end{array}$
        • $$e^{\mathrm{\Lambda }t}=\left[\begin{array}{ccc}{e}^{{\lambda }_{1}t}& \dots & 0\\ ⋮& \ddots & ⋮\\ 0& \dots & e^{{\lambda }_{n}t}\end{array}\right]$$
          • 如果所有特征值的实部为负（$Re{\lambda }_i<0$），对角线的指数收敛于0。
      • 
      • 只有1个方程：$y^{\prime \prime }+b{y}^{\prime }+ky=0$，二阶微分方程
        • 把1个二阶微分方程化为一阶方程组
        • 令$u=\left[\begin{array}{c}{y}^{\prime }\\ y\end{array}\right]$,
        • $$u^{\prime }=\left[\begin{array}{c}{y}^{\prime \prime }\\ y^{\prime }\end{array}\right]=\left[\begin{array}{cc}-b& -k\\ 1& 0\end{array}\right]\left[\begin{array}{c}{y}^{\prime }\\ y\end{array}\right]$$
        • 同理五阶的微分方程也可以化为一阶方程组，对应矩阵为：
          • $$\left[\begin{array}{ccccc}\dots & \dots & \dots & \dots & \dots \\ 1& & & & \\ & 1& & & \\ & & 1& & \\ & & & 1& 0\end{array}\right]$$

Lecture 24 Markov Matrices, Fourier Series

主要内容包括：马尔可夫矩阵和它的稳态，Fourier Series Projections，特征值的应用。

• Markov Matrices （马尔可夫矩阵）
  • $$\left[\begin{array}{ccc}.1& .01& .3\\ .2& .99& .3\\ .7& 0& .4\end{array}\right]$$
  • 满足以下条件:
    • 所有元素$\ge 0$
    • 每一列加起来为1 $⟹\lambda =1$是特征值
    • 它的幂也是马尔可夫矩阵
  • 稳态和特征值1及其特征向量关联在一起
  • 稳态的关键在于
    • $\lambda =1$是特征值
    • 所有其它特征值$|{\lambda }_i|<1$
    • ${\mu }_k=A^k{\mu }_0=c_1{\lambda }_1^k{x}_1+c_2{\lambda }_2^k+\dots$， 当满足上面两个条件时，这个式子趋近于$c_1{x}_1$
  • 证明：每一列的和为1，那么1是特征值
    • 思路：如果$A-1\cdot I$是奇异的，那么1是特征值
    • 由于$A-1\cdot I$每一列和为0，相当于要证：每一列和为0时，矩阵是奇异的
    • 方法
      • 1. 求行列式$\to$ 太复杂
        2. 奇异的，意味着
           1. 列向量线性相关
           2. 行向量线性相关（正好有$1\cdot ro{w}_1+1\ast ro{w}_2+...=0$）
    • 以3阶矩阵为例，说明$(1,1,1)$在$n(A^T)$（转置的零空间，左零空间）中
      • then，$x_1$（$\lambda =1$对应的特征向量）在$n(A-I)$中
    • $A$和$A^T$的特征值是一样的
      • $det(A-\lambda I)=0$
      • 利用$det(A)=det(A^T)$
      • $(A-I)=0$
      • $(A-I{)}^T=0$
      • $det(A^T-\lambda I)=0$
  • 应用，马尔科夫矩阵，
    • 两个地方的人口迁移问题
• 傅立叶级数
  • 回归带有标准正交基的投影问题
    • 标准正交基：$q_1,\dots ,q_n$
    • $v=x_1{q}_1+x_2{q}_2+\cdots +x_n{q}_n$
    • 基向量的系数很容易求出：$q_1^{T}v=x_1{q}_1^T{q}_1+0+\cdots +0=x_1\cdot 1$
  • Fourier series可以把任何周期函数或周期信号分解成一个（可能由无穷个元素组成的）简单振荡函数的集合（PERIODIC Function，周期函数）
  • 已知函数$f(x)=a_0\cdot 1+a_1\cos x+b_1\sin x+a_2\cos 2x+b_2\sin 2x+\dots$
    • 无穷维，关键性质是正交
    • “正交”
      • 向量的正交是$y^{T}x=0$
      • 函数的正交（对于函数$f,g$）是$f^{T}g={\int }_0^{2\pi }f(x)g(x)=0$
    • 怎么计算$a_1$
      • ${\int }_0^{2\pi }f(x)\cos xdx=0+a_1{\int }_0^{2\pi }(\cos x{)}^{2}dx+0+\dots$

Lecture 25 Review for Quiz 2

习题课，包括以下内容：

• 投影，最小二乘，Gram-Schmidt正交化
• 行列式的性质，代数余子式
• 特征值，对角化，矩阵的幂

Lecture 26 Symmetric Matrices and Positive Definiteness

本讲是关于对称矩阵的知识，$A=A^T$，意味着：特征值是实数，特征向量互相垂直

• 根据矩阵的对角化：$A=S\mathrm{\Lambda }{S}^{-1}$，$S$由特征向量构成，$\mathrm{\Lambda }$由特征值构成
  • 对称矩阵$A=Q\mathrm{\Lambda }{Q}^{-1}=Q\mathrm{\Lambda }{Q}^T$，$Q$是标准正交向量
  • 为什么对称阵的特征值是实数？
    • 先回归共轭：$\overline{a+ib}=a-ib$
    • $Ax=\lambda x$ （1.）总可以得到$\overline{A}\overline{x}=\overline{\lambda }\overline{x}$ （2.）
      • $A$为实矩阵时
        • $\overline{A}=A$
        • 转置2. 可得$\overline{x}{A}^T={\overline{x}}^T\overline{\lambda }$
        • 由于对称，$\overline{x}A={\overline{x}}^T\overline{\lambda }$ (3.)
        • 1.左乘${\overline{x}}^T$，${\overline{x}}^{T}Ax=\lambda {\overline{x}}^{T}x$
        • 3.右乘$x$,，${\overline{x}}^{T}Ax={\overline{x}}^T\overline{\lambda }x$
        • 由上面两个式子可得，$\lambda {\overline{x}}^{T}x=\overline{\lambda }{\overline{x}}^{T}x⟹\lambda =\overline{\lambda }$, 所以$\lambda$是实数
      • A为复矩阵时
        • 转置2.可得，${\overline{x}}^T{\overline{A}}^T={\overline{x}}^T\overline{\lambda }$ (4.)
        • 1.左乘${\overline{x}}^T$，${\overline{x}}^{T}Ax=\lambda {\overline{x}}^{T}x$
        • 4.右乘$x$,，${\overline{x}}^T{\overline{A}}^{T}x={\overline{x}}^T\overline{\lambda }x$
        • 所以，当且仅当$A={\overline{A}}^T$时，才有$\lambda$是实数
        • 定义新的符号：$A^H\triangleq {\overline{A}}^T$，表示共轭转置
  • 对称阵可以分解为$A=Q\mathrm{\Lambda }{Q}^T={\lambda }_1{q}_1{q}_1^T+{\lambda }_2{q}_2{q}_2^T+\dots$
    • $q_i{q}_i^T$是投影矩阵
    • 每个对称阵都是一些互相垂直的投影矩阵的组合，（理解谱定理的另一种方法）
  • 上面知道了对称阵的特征值是实数了，下面分析一下特征值的正负
    • 对于对称阵来说，主元的符号与特征值的符号相同
      • 正主元的个数等于正特征值的个数
    • 什么是正定矩阵（positive definite matrix）（对称的）
      • 所有的特征值是正的
      • 所有的主元是正的
      • 所有的子行列式是正的（从左上角开始，$1\times 1,2\times 2...$, 即顺序主子式都大于0）
      • 微分方程需要根据特征值的正负判断稳定性