MIT线性代数笔记Unit2

Unit II: Least Squares, Determinants and Eigenvalues

14 Orthogonal Vectors and Subspaces（正交向量与子空间）

The row space of a matrix’ is orthogonal to its nullspace, and its column space is orthogonal to its left nullspace.

$$\begin{array}{cc}\text{row space}&\text{column space}\\\text{dimension }r&\text{dimension }r\\\bot&\bot\\\text{nullspace}&\text{left nullspace}N(A^T)\\\text{dimension }n-r&\text{dimension }m-r\end{array}$$

Orthogonal vectors

正交（orthogonal）是垂直（perpendicular）的另一种说法

两向量正交则点积为0，$x^Ty=0$（可由勾股定理Pythagorean theorem证明）

所有向量都与零向量正交

Orthogonal subspaces

子空间$S$与$T$正交意味着$S$中的任意向量与$T$中的任意向量均正交

仅包含零向量的子空间与其他子空间正交

行空间与零空间正交，列空间与左零空间正交（根据$Ax=0$，$y^TA=0$显然可得）

零空间包含所有与行空间正交的向量，是行空间的正交补集，反之亦然

$N(A^TA) = N(A)$

当$Ax = b$无解时，转变为通过求解$A^TA\hat{x}=A^Tb$，求解原方程的最优解

$A^TA$是一个$n$阶对称方阵，当$A$的列向量线性无关时，$A^TA$可逆

$N(A^TA) = N(A)$，$r(A^TA) = r(A)$

15 Projections onto Subspaces（子空间投影）

As we know, the equation $Ax = b$ may have no solution. The vector $Ax$ is always in the column space of $A$, and $b$ is unlikely to be in the column space. So, we project $b$ onto a vector $p$ in the column space of $A$ and solve $A\hat x = p$.

Projection matrix

对于一维的情况 —— 将向量$b$投影到向量$a$所在直线上：

由上图可知，投影向量$p$即为所求，设$p=xa$，$a$与$b-p$正交，则$a^T(b-xa)=0$，$xa^Ta=a^Tb$，$x=\frac{a^Tb}{a^Ta}$，所以$p=ax=a\frac{a^Tb}{a^Ta}$

可以将投影变换表示为矩阵形式 —— $p=Pb$，由于$p=ax=a\frac{a^Tb}{a^Ta}=\frac{aa^T}{a^Ta}b$，所以投影矩阵$P=\frac{aa^T}{a^Ta}$

投影矩阵$P$是一个秩1的对称矩阵，其列空间即为$a$所在直线，两条重要性质 —— $P^T=P$，$P^2=P$

Why project?

$Ax=b$可能无解，而$Ax$一定在$A$的列空间内，此时我们可以将$b$投影到$A$的列空间，进而求解近似解$A\hat{x}=p$

Projection in higher dimensions

在$R^3$中，将向量$b$投影到平面，该平面的基为$a_1,a_2$，则该平面为$A=\begin{bmatrix} a_1&a_2 \end{bmatrix}$的列空间

投影向量$p = \hat x_1a_1 + \hat x_2a_2 = A\hat x$，$b-p$与平面的两个基正交，则$A^T(b-A\hat x)=0$（一些联想：$b-A\hat x$在$A$的左零空间中，故正交于$A$的列空间），$A^TA\hat x=A^Tb$，$\hat x=(A^TA)^{-1}A^Tb$

$p=A\hat x=A(A^TA)^{-1}A^Tb$，所以投影矩阵$P=A(A^TA)^{-1}A^T$

两条重要性质$P^T=P$，$P^2=P$保持不变

Least Squares

给定一个点集$\{(t,b)\}$，拟合一条与点集最接近的直线$b=C+Dt$ —— 最小二乘（Least Squares）

例如，点集为$\{(1, 1), (2, 2), (3, 2)\}$，则

$\left[\begin{array}{cc}1&1\\1&2\\1&3\end{array}\right]\quad\left[\begin{array}{c}C\\D\end{array}\right]\quad=\quad\left[\begin{array}{c}1\\2\\2\end{array}\right]$

$Ax=b$，拟合直线并不经过所有点，所以方程组无解，为求最小二乘最优解，改为计算$A^TA\hat x=A^Tb$

16 Projection Matrices and Least Squares（投影矩阵，最小二乘）

By “closest” line we mean one that minimizes the error represented by the distance from the points to the line. We measure that error by adding up the squares of these distances.

Projections

$P=A(A^TA)^{-1}A^T$是将$b$投影到$A$的列空间的投影矩阵，如果$b$在$A$列空间中，则$Pb=b$；如果$b$与$A$列空间正交（在$A$左零空间$N(A^T)$中），$Pb=0$

$b$在$A$列空间上的投影矩阵为$P$，则$b$在$A$左零空间$N(A^T)$上的投影矩阵为$I-P$，$b=Pb+(I-P)b$，$b$为两个投影向量之和

Least squares

$Ax=b$无解，求解$A\hat x=p$（$A^TA\hat x=A^Tb$），$p$为$b$在$A$列空间上的投影向量，$e=b-p$为误差向量（同时也是$b$在$N(A^T)$上的投影向量），故$e$与$p$正交，同时$e$也与$A$的列空间正交

最小二乘的优化目标是最小化$||e||^2=||Ax-b||^2$

$b$中各元素对应于点集中各点的纵坐标，$p$中各元素对应于拟合直线上各点的纵坐标，$e$中各元素对应各点的残差

The matrix $A^TA$

"$A^TA$是一个$n$阶对称方阵，当$A$的列向量线性无关时，$A^TA$可逆"的证明：只需证明当$A^TAx=0$，一定有$x=0$ —— 当$A^TAx=0$，$x^TA^TAx=0$，即$(Ax)^T(Ax)=0$，则一定有$Ax=0$，由于$A$列满秩，则一定有$x=0$，证毕

只要$A$的列向量无关，就可以使用线性回归（最小二乘）求解$Ax=b$的近似解，所以重点在于确保$A$的列向量无关，一种方式是使$A$的列向量正交

17 Orthogonal Matrices and Gram-Schmidt（正交矩阵，施密特正交化）

Using an orthonormal basis or a matrix with orthonormal columns makes calculations much easier. The Gram-Schmidt process starts with any basis and produces an orthonormal basis that spans the same space as the original basis.

Orthonormal matrix

标准正交向量（orthonormal vectors）$q_1,q_2,...,q_n$ —— 单位化+相互正交，可以表示为：

$q_i^Tq_j=\left\{\begin{array}{ll}0&\text{if}\ i\neq j\\1&\text{if}\ i=j\end{array}\right.$

标准正交向量必线性无关

正交矩阵（需要是方阵）$Q=\left[\begin{array}{cccc}{q_{1}}&{...}&{q_{n}}\\\end{array}\right]$，列向量为标准正交基，$Q^TQ=I$，$Q^T=Q^{-1}$

对于$P=A(A^TA)^{-1}A^T$，如果$A$为列向量是标准正交基的矩阵$Q$，则$P=QQ^T$，如果$Q$为方阵，则$P=I$

对于$A^TA\hat x=A^Tb$，如果$A$为正交矩阵$Q$，则$Q^TQ\hat x=Q^Tb$，由于$Q^TQ=I$，所以$\hat x=Q^Tb$，$q_i^Tb$即为$x$在正交基$q_i$方向上的投影，正交矩阵大大简化了计算

Gram-Schmidt

如有3个不相关的变量$a,b,c$，设求得的正交向量为$A,B,C$，标准正交基为$q_1=\frac{A}{||A||},q_2=\frac{B}{||B||},q_3=\frac{C}{||C||}$，计算方式如下：

• $A=a$

• $B=b-\frac{A^Tb}{A^TA}A$，$b$减掉在$A$方向上的投影，得到与$A$正交的向量

• $C=c-\frac{A^Tc}{A^TA}A-\frac{B^Tc}{B^TB}B$，$c$减掉在$A,B$方向上的投影，得到与$A,B$正交的向量

消元法以矩阵运算的形式表示为$A=LU$，施密特正交化也可以用矩阵运算的形式表示出来 —— $A=QR$，$R$是一个上三角矩阵，$R=Q^TA$

18 Properties of Determinants（行列式及其性质）

The determinant encodes a lot of information about the matrix; the matrix is invertible exactly when the determinant is non-zero.

Determinants

每个方阵都有一个度量 —— 行列式（determinant）$\det A,|A|$，行列式中包含了很多该方阵的信息，包括可逆、特征值等

Properties

二阶行列式的计算 —— 对角线法则$\left|\begin{array}{cc}a&b\\c&d\end{array}\right|=ad-bc$

行列式的一系列性质：

• $\det I=1$

• 交换矩阵的两行/两列，行列式取其相反数（置换矩阵的行列式为$\pm1$）

• $\left|\begin{array}{cc}ta&tb\\c&d\end{array}\right|=t\left|\begin{array}{cc}a&b\\c&d\end{array}\right|$，$\left|\begin{array}{cc}a+a'&b+b'\\c&d\end{array}\right|=\left|\begin{array}{cc}a&b\\c&d\end{array}\right|+\left|\begin{array}{cc}a'&b'\\c&d\end{array}\right|$

• 如果矩阵中有两行/两列相等，行列式为0

• 消法变换不改变行列式

• 如果矩阵中有一行/列全为0，行列式为0

• 上/下三角矩阵的行列式为各行主元（对角元）的乘积（product of pivots）

• 奇异矩阵的行列式为0（充要）

• $\det AB=(\det A)(\det B)$，$\det A^{-1}=\frac{1}{\det A}$

• $\det A^T=\det A$（$A=LU,|A^T|=|U^TL^T|=|L^T||U^T|=|L||U|=|A|$）

19 Determinant Formulas and Cofactors（行列式公式，代数余子式）

It’s time to learn some (rather messy) formulas for computing it.

Formula for the determinant

利用性质三将行列式分解为$n!$个非零的类置换矩阵（每行每列只保留一个非零元素）之和，从而得到行列式的计算公式 —— $\det A=\sum_{n!~terms}\pm a_{1\alpha}a_{2\beta}a_{3\gamma}...a_{n\omega}$，$(\alpha,\beta,\gamma,...\omega)$是$(1, 2, 3, ..., n)$的置换，正负号由置换的次数（逆序数）决定

Cofactor formula

代数余子式（Cofactor）旨在用小的矩阵的行列式来描述（计算）一个大的矩阵的行列式

$a_{ij}$的代数余子式$C_{ij}$的绝对值等于将矩阵第$i$行和第$j$列抹去后得到的$n-1$阶矩阵的行列式，其正负取决于$i+j$的奇偶性（奇负偶正）

利用代数余子式求行列式 —— $\det A=a_{11}C_{11}+a_{12}C_{12}+\cdots+a_{1n}C_{1n}$

Tridiagonal matrix

三对角矩阵（Tridiagonal matrix）指非零元素仅位于对角线上或邻近对角线的矩阵，如$A_4=\left[\begin{array}{cccc}1&1&0&0\\1&1&1&0\\0&1&1&1\\0&0&1&1\end{array}\right]$

重要规律：$|A_n|=|A_{n-1}|-|A_{n-2}|$（利用代数余子式展开证明）

20 Cramer’s Rule, Inverse Matrix, and Volume（克莱姆法则，逆矩阵，体积）

If you know the coordinates for the corners of a box, then computing the volume of the box is as easy as calculating a determinant.

Formula for $A^{−1}$

$A^{-1}=\frac{1}{\det A}C^T$，$C$是$A$的代数余子式按下标顺序构成的矩阵，$C^T$也被称为伴随矩阵（通过$AC^{T}=(\det A)I$证明）

Cramer’s Rule for $x = A^{−1}b$

$Ax=b$，则$x=A^{-1}b=\frac{1}{\det A}C^Tb$，$x$中的每个元素可以表示为$x_i=\frac{\det B_i}{\det A}$，$B_i$为$A$矩阵第$i$列用$b$替换掉后得到的矩阵（对于代数余子式按列展开的构造），这种通过计算$n+1$个行列式来解方程组的方式，即为克莱姆法则（Cramer’s Rule）

消元法的效率更高，但克莱姆法则为解方程组提供了一种新的视角

$|\det A|$ = volume of box

$|\det A|$是各边为$A$列向量的长方体盒子的体积（证明该长方体的体积与行列式具有相同的性质，即可证得二者等价），对于二维则行列式表示面积，利用行列式的这一意义，可以简化面积/体积的计算

21 Eigenvalues and Eigenvectors（特征值，特征向量）

Once we’ve found an eigenvalue $\lambda$, we can use elimination to find the nullspace of $A-\lambda I$. The vectors in that nullspace are eigenvectors of A with eigenvalue $\lambda$.

Eigenvectors and eigenvalues

矩阵$A$可看作是一种变换（函数），作用于非零向量$x$后得到$Ax$，如果$Ax$平行于$x$，则$x$为$A$的特征向量，$Ax=\lambda x$，$\lambda$为该特征向量对应的特征值

当$\lambda=0$，$Ax=0$，特征值$0$（如果存在）对应的特征向量构成$A$的零空间；如果$A$是奇异矩阵，则$Ax=0$有非零解，则$\lambda=0$为$A$的特征值

对于一个投影矩阵$P$，一定存在对应特征值为1的特征向量，如果$P$列空间不满秩，在$P$的左零空间中，也一定存在对应特征值为0的特征向量，与$P$的列空间正交

$\det(A-\lambda I)=0$

$Ax=\lambda x$，$(A-\lambda I)x=0$，若$x\neq0$，$(A-\lambda I)$为奇异矩阵，则$|A-\lambda I|=0$，这就是$A$的特征方程，由此可以求出$A$的$n$个特征值（可能存在重根），进一步求解$(A-\lambda I)x=0$得到对应的特征向量$x$

$A$的特征值为$\lambda$，特征向量为$x$，则$A+kI$的特征值为$\lambda+k$，特征向量仍为$x$（$(A+kI)x=Ax+kx=(\lambda+k)x$）

矩阵的行列式等于特征值之积，迹（trace）等于特征值之和

22 Diagonalization and Powers of $A$（对角化，$A$的幂）

When a sequence evolves over time according to the rules of a first order system, the eigenvalues of the matrix of that system determine the long term behavior of the series. To get an exact formula for the series we find the eigenvectors of the matrix and then solve for the coefficients $c_1$, $c_2$, …

Diagonalizing a matrix $S^{-1}AS=\Lambda$

如果$A$有$n$个线性无关的特征向量$x_i$，$S=[\begin{array}{ccccc}x_{1}&x_{2}&\cdots&x_{n}\end{array}]$，则$S$为可逆的方阵，所以：

$\begin{aligned} AS=A\left[\begin{array}{ccccc}x_{1}&x_{2}&\cdots&x_{n}\\\end{array}\right]=\left[\begin{array}{ccccc}\lambda_{1}x_{1}&\lambda_{2}x_{2}&\cdots&\lambda_{n}x_{n}\end{array}\right]=S\left[\begin{array}{cccc}\lambda_1&0&\cdots&0\\0&\lambda_2&&0\\\vdots&&\ddots&\vdots\\0&\cdots&0&\lambda_n\end{array}\right]=S\Lambda \end{aligned}$ 故$S^{-1}AS=\Lambda$，$A=S\Lambda S^{-1}$，所以$A^nx=\lambda^nx$，$A^n=S\Lambda^nS^{-1}$，当$A$有$n$个线性无关的特征向量时（不同的特征值对应的特征向量一定无关，重特征值的情况需要验证），相似对角化提供了一种很好的计算矩阵幂的方式

Difference equations $u_{k+1} = Au_k$

一阶差分方程$u_{k+1} = Au_k$的解为$u_k = A^ku_0$，如果$u_0=c_1x_1+c_2x_2+...+c_nx_n=Sc$（$x_i$为$A$的特征向量），则$u_k=A^ku_0=c_1\lambda_1^kx_1+c_2\lambda_2^kx_2+...+c_n\lambda_n^kx_n=\Lambda^kSc$，$A$的特征值决定了该序列的增长速度

以斐波那契数列为例，$F_{k+2}=F_{k+1}+F_{k}$，二阶差分，可以转化为一阶差分：$u_{k}=\left[\begin{array}{c}{F_{k+1}}\\{F_{k}}\end{array}\right]$，$\begin{array}{rcl}F_{k+2}&=&F_{k+1}+F_k\\F_{k+1}&=&F_{k+1}\end{array}$，则$u_{k+1}=\left[\begin{array}{cc}{1}&{1}\\{1}&{0}\end{array}\right]u_{k}$（太妙了！！！），所以$A=\left[\begin{array}{cc}{1}&{1}\\{1}&{0}\end{array}\right]$，进一步计算$u_k=A^ku_0=\Lambda^kSc$得到斐波那契数列的通项公式 —— $F_k=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^k-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^k$

23 Differential Equations and $e^{At}$（微分方程，exp(At)）

The two “pure” terms $e^{\lambda_1t}x_1$ and $e^{\lambda_2t}x_2$ are analogous to the terms $\lambda_i^k x_i$ we saw in the solution $c_1\lambda_1^k x_2+c_2\lambda_2^k x_2+...+c_n\lambda_n^k x_n$ to the difference equation $u_{k+1} = Au_k$.

Differential equations $\frac{du}{dt}=Au$

对于微分方程组$\begin{aligned}\frac{du_1}{dt}&=-u_1+2u_2\\\frac{du_2}{dt}&=u_1-2u_2\end{aligned}$，初始条件为$u(0)=\left[\begin{array}{c}1\\0\end{array}\right]$，该微分方程可以表示为$\frac{du}{dt}=Au$，$A=\left[\begin{array}{rr}-1&2\\1&-2\end{array}\right]$，通过求解$A$的特征值$\lambda_1,\lambda_2$，以及对应的特征向量$x_1,x_2$，代入解的结构$u(t)=c_1e^{\lambda_1t}x_1+c_2e^{\lambda_2t}x_2$后，根据初始条件求得$c_1,c_2$，得到微分方程的解$u(t)=\frac13\left[\begin{array}{r}2\\1\end{array}\right]+\frac13e^{-3t}\left[\begin{array}{r}1\\-1\end{array}\right]$，故该微分方程描述的系统的稳定状态为$u(\infty)=\left[\begin{array}{c}2/3\\1/3\end{array}\right]$（$u=e^{\lambda_1t}x_1$是$\frac{du}{dt}=Au$的解的证明：$Au=e^{\lambda_1t}Ax_1=\lambda_1e^{\lambda_1t}x_1=\frac{du}{dt}$）

微分方程所描述的系统的一些性质：

• 稳定性（Stability）：当所有$Re(\lambda)<0$时，$u(t)\to0$

• 稳态（Steady state）：一个特征值为0，其他特征值实数部分均为负

• 发散（Blow up）：存在$Re(\lambda)>0$

将初始条件$u(0)=\left[\begin{array}{c}1\\0\end{array}\right]$代入求解$c_1,c_2$时，可以表示为$Sc=u(0)$，$S$是特征向量组成的矩阵，由此，设$u=Sv$，则代入$\frac{du}{dt}=Au$得到$S\frac{dv}{dt}=ASv$，则$\frac{dv}{dt}=S^{-1}ASv=\Lambda v$，即$\frac{dv_i}{dt}=\lambda_iv_i$，通过特征值和特征向量实现了$u_i$间关系的解耦（在原微分方程组中它们相互耦合），通解为$v(t)=e^{\Lambda t}v(0),u(t)=Se^{\Lambda t}S^{-1}u(0)=e^{At}u(0)$

Matrix exponential $e^{At}$

$e^{At}=I+At+\frac{(At)^2}2+\frac{(At)^3}6+\cdots$，以泰勒级数的方式展开，类似地，$(I-At)^{-1}=I+At+(At)^2+(At)^3+\cdots$

$e^{At}=I+At+\frac{(At)^2}2+\frac{(At)^3}6+\cdots=SS^{-1}+S\Lambda S^{-1}t+\frac{S\Lambda^{2}S^{-1}}2t^{2}+\frac{S\Lambda^{3}S^{-1}}6t^{3}+\cdots=Se^{\Lambda t}S^{-1}$，当$A$可以相似对角化时（存在$n$个线性无关的特征向量）成立

Second order

对于二阶线性微分方程$\begin{aligned}y''+by'+ky=0\end{aligned}$，可以采用类似一阶差分处理斐波那契数列的方式，来构造一阶线性微分方程组来求解：设$u=\left[\begin{array}{c}y'\\y\end{array}\right]$，则$u'=\left[\begin{array}{c}y''\\y'\end{array}\right]=\left[\begin{array}{cc}-b&-k\\1&0\end{array}\right]\left[\begin{array}{c}y'\\y\end{array}\right]=Au$

24 Markov Matrices; Fourier Series（马尔科可夫矩阵，傅里叶级数）

When dealing with systems of differential equations, eigenvectors with the eigenvalue $\lambda=0$ represented steady states. Here we’re dealing with powers of matrices and get a steady state when $\lambda=1$ is an eigenvalue.

Markov matrices

前景回顾：$A^T$的特征值与$A$的特征值一致（$|A-\lambda x|=0,|A^T-\lambda x|=|(A-\lambda x)^T|=0$）

形如$A=\left[\begin{array}{rrr}.1&.01&.3\\.2&.99&.3\\.7&0&.4\end{array}\right]$，所有的元素非负，且每列之和均为1的矩阵，为马尔可夫矩阵（Markov matrices），它在概率论中有重要作用，同时对幂运算封闭

对于一个微分方程组系统，特征值为0代表着稳态；而对于矩阵的幂，特征值为1代表着稳态，马尔可夫矩阵保证了一个特征值是1（$A-I$是奇异矩阵，$|A-I|=0$），其他特征值的绝对值均小于1（$u_k=A^ku_0=c_1\lambda_1^kx_1+c_2\lambda_2^kx_2+\cdot\cdot\cdot+c_n\lambda_n^kx_n$，如果$\lambda_1=1$且其他特征值的绝对值均小于1，则稳态是$c_1x_1$）

一个实际的例子，对于$u_{k+1}=Au_k$，$A$是一个马尔可夫矩阵，$u$表示各城市的人口数量，$A$中的元素则表示人口的迁移率，$a_{ij}$表示每年有多少（百分比）人从$i$城市迁移到$j$城市，这种情况下通过求解$A$的特征值1对应的特征向量即可得知稳态时城市间人口的比例

在实际的应用场景中，马尔可夫矩阵可能是要求每行之和均为1（上面的定义的转置）

Fourier series and projections

正交基$q_1,q_2,...,q_n$，向量$v$可以表示为$v=x_1q_1+x_2q_2+...+x_nq_n$，$x_i=q_i^Tv$（利用正交的性质求解 —— $q_i^Tv=x_iq_i^Tq_i=x_i$），利用矩阵表示 —— $v=Qx$，$x=Q^{-1}v=Q^Tv$

傅里叶级数（Fourier series）就是基于一组正交基，如上例所示，$f(x)=a_0+a_1\cos x+b_1\sin x+a_2\cos2x+b_2\sin2x+\cdots$，$1,\cos x,\sin x,\cos 2x,\sin 2x,\cdots$正交（函数正交 —— $f^Tg=\int_0^{2\pi}f(x)g(x)dx=0$，$2\pi$为函数周期），$a_i=\frac{1}{\pi}\int_{0}^{2\pi}f(x)\cos ixdx$（利用正交的性质求解 —— $\int_{0}^{2\pi}f(x)\cos ixdx=\int_0^{2\pi}(a_0+a_1\cos x+b_1\sin x+a_2\cos2x+\cdots)\cos ixdx=0+\int_0^{2\pi}a_i\cos^2ixdx+0+0+\cdots=a_{i}\pi$）

25 Quiz 2 Review