MIT线性代数笔记Unit3

Unit III: Positive Definite Matrices and Applications

26 Symmetric Matrices and Positive Definiteness（对称矩阵及正定性）

Symmetric matrices are good – their eigenvalues are real and each has a complete set of orthonormal eigenvectors. Positive definite matrices are even better.

Symmetric matrices with real entries

实对称矩阵的特征值均为实数，并且可以找出一组相互正交的特征向量，对称矩阵$A$可以被分解为$A=Q\Lambda Q^{-1}=Q\Lambda Q^T$，$Q$是正交矩阵（数学上被称为谱定理spectral theorem，物理上被称为主轴定理principal axis theorem）

关于实对称矩阵的特征值为实数的证明：实对称矩阵$A$，$Ax=\lambda x$，取共轭得到$\bar{A}\bar{x}=\bar{\lambda}\bar{x}$，由于$A$为实矩阵，则$A\bar{x}=\bar{\lambda}\bar{x}$，取转置得到$\bar{x}^TA^T=\bar{x}^T\bar{\lambda}$，由于$A$为对称矩阵，则$\bar{x}^TA=\bar{x}^T\bar{\lambda}$，右乘$x$得到$\bar{x}^TAx=\bar{x}^T\bar{\lambda}x$；对于$Ax=\lambda x$右乘$\bar{x}^T$得到$\bar{x}^TAx=\bar{x}^T\lambda x$，则$\bar{x}^T\bar{\lambda}x=\bar{x}^T\lambda x$，$x$非零，$\bar{x}^Tx=\Sigma|x_i|^2\neq0$，则$\lambda$是实数

对于复数矩阵，特征值为实数且存在一组相互正交的特征向量的充要条件为$A={\bar{A}}^T$

$A=Q\Lambda Q^T=\left[\begin{array}{cccc}q_1&q_2&\cdots&q_n\end{array}\right]\left[\begin{array}{ccc}\lambda_1\\&\lambda_2\\&&\ddots\\&&&\lambda_n\end{array}\right]\left[\begin{array}{c}q_1^T\\q_2^T\\\vdots\\q_n^T\end{array}\right]=\lambda_1q_1q_1^T+\lambda_2q_2q_2^T+\cdots+\lambda_nq_nq_n^T$，$q_kq_k^T$是一个投影到$q_k$的投影矩阵，所以对称矩阵可以表示为多个投影矩阵的加权和，这提供了一种理解谱定理的角度

特征值为实数的重要性：当特征值为实数时，可以判断其正负（这对于如微分方程组是否存在稳态等数学问题很重要），对于较大的矩阵，通过计算行列式求解特征值计算量很大，但通过消元计算主元并不困难，为正数的主元的数量与为正数的特征值的数量相等，进而也可以通过$A+bI$计算大于或小于$b$的特征值数量，这在不通过行列式求解特征值的情况下提供了很多有效的信息

Positive definite matrices

正定矩阵（positive definite matrices）的所有特征值均为正数（充要条件：所有主元均为正数；所有顺序主子式均为正数）—— 此处，主元、行列式、特征值，被联系到了一起

27 Complex Matrices; Fast Fourier Transform（复数矩阵，快速傅里叶变换）

The most important complex matrix is the Fourier matrix $F_n$, which is used for Fourier transforms. Normally, multiplication by $F_n$ would require $n^2$ multiplications. The fast Fourier transform (FFT) reduces this to roughly $n log_2 n$ multiplications, a revolutionary improvement.

Complex matrices

复数向量$z$的模长$|z|^2=\bar{z}^Tz=z^Hz$（$z$ Hermitian $z$），复数向量的内积同理 —— $y^Hx=\bar{y}^Tx$

埃尔米特矩阵（Hermitian matrices）是对称的复矩阵 —— ${\bar{A}}^T=A$（$A^H=A$）与实对称矩阵相似，特征值为实数且存在一组相互正交的特征向量

酉矩阵（Unitary matrices）是正交的复矩阵 —— ${\bar{Q}}^TQ=I$（$Q^HQ=I$）

Fast Fourier transform

傅里叶矩阵$F_n=\left[\begin{array}{ccccc}1&1&1&\cdots&1\\1&w&w^2&&w^{n-1}\\1&w^2&w^4&&w^{2(n-1)}\\\vdots&&&\ddots&\vdots\\1&w^{n-1}&w^{2(n-1)}&\cdots&w^{(n-1)^2}\end{array}\right]$，$F_{n}=F_{n}^{T}$，$(F_{n})_{jk}=w^{jk}$，$w=e^{i\cdot2\pi/n}=\cos\frac{2\pi}{n}+i\sin\frac{2\pi}{n}$，列向量相互正交（注意此处为复向量正交），与傅里叶矩阵相乘实现了对向量的离散傅里叶变换（discrete Fourier transform）

$F_n$与$F_{2n}$之间的关系（基于$w_{2n}^2=w_n$）：

• $F_{2n}=\left[\begin{array}{rr}I&D\\I&-D\end{array}\right]\left[\begin{array}{rr}F_n&0\\0&F_n\end{array}\right]P$（证明方式：暴力展开，必要时用$w_{2n}^n$来替换$-1$，用$w_{2n}^{2n}$来替换$1$）

• 置换矩阵$P=\left[\begin{array}{ccccccc}1&0&0&0&\cdots&0&0\\0&0&1&0&\cdots&0&0\\&&&\vdots&&&\\0&0&0&0&\cdots&1&0\\0&1&0&0&\cdots&0&0\\0&0&0&1&\cdots&0&0\\&&&\vdots&&&\\0&0&0&0&\cdots&0&1\end{array}\right]$实现了依次取第$0,n,1,n+1,\cdots,n-1,2n$列的效果

• 对角矩阵$D=\left[\begin{array}{rrrrrr}1&&&&\\&w&&&\\&&w^2&&\\&&&\ddots&\\&&&&w^{n-1}\end{array}\right]$，此处的$w$为$w_{2n}$，实现了矩阵行的倍缩

如此递归进行计算，将计算代价从$n^2$降到了$n log_2 n$，这就是快速傅里叶变换（FFT）

28 Positive Definite Matrices and Minima（正定矩阵，最小值）

Studying positive definite matrices brings the whole course together; we use pivots, determinants, eigenvalues and stability.

Positive definite matrices

判断一个对称矩阵$A$是否正定：

• 特征值角度：所有特征值大于0

• 行列式角度：所有顺序主子式大于0

• 主元角度：所有主元大于0

• 当$x\neq0$时，$x^TAx>0$

二次型（quadratic form）$x^TAx=ax_1^2+2bx_1x_2+cx_2^2$，判断二次型是否恒大于0 —— 配方法（配方后各项系数即为矩阵的各主元，故可以通过消元法求解配方系数）

正定矩阵对应的二次型的图像一般为抛物面（paraboloid），三维正定二次型的图像可能为椭圆体（ellipsoid），$A=Q\Lambda Q^T$，$Q$（特征向量）表明$A$图像上的三个轴向，$\Lambda$（特征值）表明各轴的长度，这提供了一种理解主轴定理的角度

29 Similar Matrices and Jordan Form（相似矩阵，Jordan型）

Camille Jordan found a way to choose a “most diagonal" representative from each family of similar matrices; this representative is said to be in Jordan normal form.

$A^TA$ is positive definite

一些关于正定矩阵的性质：

• $A$正定，则$A^{-1}$正定（$\frac{1}{\lambda_i}>0$）

• $A$和$B$正定，则$A+B$正定（$x^T(A+B)x=x^TAx+x^TBx>0$）

• $A$列满秩，则$A^TA$正定（$x^T(A^TA)x=(Ax)^T(Ax)=|Ax|^2\geq0$，$A$列满秩，则当且仅当$x=0$时才有$Ax=0$，故$A^TA$正定）

• 正定矩阵进行消元时，不需要进行行交换，因为不存在为0的主元

Similar matrices $A$ and $B = M^{−1}AM$

$A$与$B$相似（similar）—— 存在可逆矩阵$M$，$B = M^{−1}AM$

典例：当$A$存在$n$个线性无关的特征向量，则$S^{-1}AS=\Lambda$，$A$与$\Lambda$相似

$A$与$B$相似，$B = M^{−1}AM$，则$A$与$B$具有相同的特征值，$A$的特征向量为$x$，则$B$的特征向量为$M^{-1}x$（$Ax=\lambda x$，则$AMM^{-1}x=\lambda x$，左乘$M^{-1}$，$M^{-1}AMM^{-1}x=\lambda M^{-1}x$，则$y=M^{-1}x$，$By=\lambda y$）

Jordan form

Jordan型矩阵 —— 一个相似矩阵族里最接近对角矩阵的矩阵，对角元都为特征值，对角线之上可能存在1，其他位置为0

Jordan块 —— $J_i=\left[\begin{array}{ccccc}\lambda_i&1&0&\cdots&0\\0&\lambda_i&1&&0\\\vdots&&\ddots&&\vdots\\0&0&&\lambda_i&1\\0&0&\cdots&0&\lambda_i\end{array}\right]$

Jordan定理 —— 每个方阵$A$都相似于一个Jordan型矩阵$J=\left[\begin{array}{cccc}J_1&0&\cdots&0\\0&J_2&\cdots&0\\\vdots&&\ddots&\vdots\\0&0&\cdots&J_d\end{array}\right]$

• 每一个Jordan块对应一个特征向量（Jordan块的数量等于特征向量的数量）

• 如果两矩阵特征值相同且特征向量数量想同，但组成它们的Jordan块的大小不同，则它们不相似

如果$A$有$n$个不同的特征值，则它可相似对角化，Jordan型为对角矩阵$\Lambda$；如果$A$有重特征值且“缺失”特征向量，Jordan型在对角线上方有$n-d$个1（$d$为Jordan块的数量）

30 Singular Value Decomposition（奇异值分解）

The heart of the problem is to find an orthonormal basis $v_1, v_2,\cdots,v_r$ for the row space of $A$.

奇异值分解SVD（Singular Value Decomposition）：对于任意矩阵$A$，都可进行分解$A=U\Sigma V^T$，$U$和$V$是正交矩阵，$\Sigma$是对角矩阵

奇异值分解的特殊情况：对于对称矩阵，它的特征向量正交，$A=Q\Lambda Q^T$，此时$U=V=Q$

奇异值分解的理解：$v_1,v_2,\cdots,v_r$为$A$行空间的正交基，$v_{r+1},\cdots,v_n$为$A$零空间的正交基，$u_1,u_2,\cdots,u_r$为$A$列空间的正交基，$u_{r+1},\cdots,u_n$是$A$左零空间的正交基，希望实现行空间的正交基到列空间的正交基的变换 —— $Av_i=\sigma_iu_i$（当$i>r$，$\sigma_i=0$），即$A\left[\begin{array}{ccccc}v_1&v_2&\cdots&v_n\end{array}\right]=\left[\begin{array}{cccc}\sigma_1u_1&\sigma_2u_2&\cdots&\sigma_nu_n\end{array}\right]=\left[\begin{array}{cccccc}u_1&u_2&\cdots&u_n\end{array}\right]\left[\begin{array}{ccccc}\sigma_1&&&&\\&\sigma_2&&&\\&&\ddots&&\\&&&&\sigma_n\end{array}\right]$，即$AV=U\Sigma$（$A=U\Sigma V^{-1}=U\Sigma V^T$），所以奇异值分解问题的核心就是找到行空间中一组特殊的正交基

奇异值分解的求解 —— 找到符合要求的$V$和$U$：$A^TA=V\Sigma U^TU\Sigma V^T=V\Sigma^2V^T=V\left[\begin{array}{rrrr}\sigma_{1}^{2}&&&\\&\sigma_{2}^{2}&&\\&&\ddots&\\&&&\sigma_{n}^{2}\end{array}\right]V^{T}$，通过计算 $A^TA$的特征向量得到$V$；$AA^T=U\Sigma V^TV\Sigma U^T=U\Sigma^2U^T=U\left[\begin{array}{rrrr}\sigma_{1}^{2}&&&\\&\sigma_{2}^{2}&&\\&&\ddots&\\&&&\sigma_{n}^{2}\end{array}\right]U^{T}$，通过计算$AA^T$的特征向量得到$U$；$\sigma_i$即为$A^TA$或$AA^T$的特征值的平方根

31 Linear Transformations and Their Matrices（线性变换及对应矩阵）

In older linear algebra courses, linear transformations were introduced before matrices. This geometric approach to linear algebra initially avoids the need for coordinates. But eventually there must be coordinates and matrices when the need for computation arises.

Without coordinates (no matrix)

映射$T:R^2\longrightarrow R^2$，满足条件$T(v+w)=T(v)+T(w),T(cv)=cT(v)$，即为线性变换，一些线性变换：

• 投影（Projection）将向量映射到一条直线上

• 旋转45°（Rotation by 45°）将向量旋转45°

With coordinates (matrix!)

$T(v)=Av$，可以用输入空间的一组基$v_1,v_2,\cdots,v_n$来描述该线性变换，$v=c_1v_1+c_2v_2+\cdots+c_nv_n$，$T(v)=c_1T(v_1)+c_2T(v_2)+\cdots+c_nT(v_n)$，$c_i$即为坐标（coordinates），这源自于所取的基（basis）

确定矩阵$A$：$T(v)=Av$（此处$v$和$Av$分别代表了在变换前后基向量下的坐标），$A$的列，是描述输入原空间的基向量变换后得到的输出向量，关于输出空间（$A$列空间）基向量的线性组合系数，$T(v_i)=a_{1i}w_1+a_{2i}w_2+\cdots+a_{mi}w_m$，这样矩阵$A$就满足$A[input\ coords]=[output\ coords]$（$\left[\begin{array}{ccccc}T(v_1)&T(v_2)&\cdots&T(v_n)\end{array}\right]=\left[\begin{array}{ccccc}w_1&w_2&\cdots&w_n\end{array}\right]A,T(v)=\left[\begin{array}{ccccc}T(v_1)&T(v_2)&\cdots&T(v_n)\end{array}\right][input\ coords]=\left[\begin{array}{ccccc}w_1&w_2&\cdots&w_n\end{array}\right]A[input\ coords]=\left[\begin{array}{ccccc}w_1&w_2&\cdots&w_n\end{array}\right][output\ coords]$）

举例，$T=\frac{d}{dx}$，$T(c_1+c_2x+c_3x^2)=c_2+2c_3x$，$v_1=1,v_2=x,v_3=x^2$，$w_1=1,w_2=x$，$A=\left[\begin{array}{ccc}0&1&0\\0&0&2\end{array}\right]$，$T\left(\left[\begin{array}{c}c_1\\c_2\\c_3\end{array}\right]\right)=A\left[\begin{array}{c}c_1\\c_2\\c_3\end{array}\right]=\left[\begin{array}{c}c_2\\2c_3\end{array}\right]$

矩阵乘法即为线性变换的叠加

32 Change of Basis; Image Compression（基变换，图像压缩）

Lecture videos, music, and other data sources contain a lot of information; that information can be efficiently stored and transmitted only after we change the basis used to record it.

Compression of images

基变换的一个重要应用就是压缩，可以通过基变换对图像、视频、音频进行压缩从而实现更高效的存储

图片压缩的本质是基变换，利用标准基存储图片并不能很好地利用如图片中连续区域灰度值很接近等特点，故利用$\left[\begin{array}{c}1\\1\\\cdots\\1\end{array}\right]$等基向量能更好地表示这种情况

两种常用的基向量：

• 傅里叶基（Fourier basis vectors）—— 傅里叶矩阵的列向量

  $$\left[\begin{array}{c}1\\1\\1\\1\\1\\1\\1\\1\end{array}\right],\left[\begin{array}{c}1\\\omega\\\omega^2\\\omega^3\\\omega^4\\\omega^5\\\omega^6\\\omega^7\end{array}\right],\left[\begin{array}{c}1\\\omega^2\\\omega^4\\\omega^6\\\omega^8\\\omega^{10}\\\omega^{12}\\\omega^{14}\end{array}\right],\cdots,\left[\begin{array}{c}1\\\omega^7\\\omega^{14}\\\omega^{21}\\\omega^{28}\\\omega^{35}\\\omega^{42}\\\omega^{49}\end{array}\right]$$

  在JEPG中，$512\times512$的图像被划分为$8\times8$的区域（64个系数 $\rightarrow$ 64维）进行处理，使用的基就是傅里叶基，对于输入的信号$\mathrm{x}$，从标准基变换位傅里叶基（无损压缩），得到系数$c$，再对$c$进行阈值处理（消除低于某个阈值的系数，有损压缩），得到系数$\hat{c}$，利用新的系数对傅里叶基进行线性组合得到压缩后的信号$\hat{\mathbf{x}}=\sum\hat{c}_i\mathbf{v}_i$，求和项已不为64项，这即是压缩

  $$\mathrm{signal~x}\overset{\mathrm{lossless}}{\operatorname*{\longrightarrow}}\text{64 coefficients }c\overset{\mathrm{lossy~compression}}{\operatorname*{\longrightarrow}}\hat{c}\text{ (many zeros)}\longrightarrow\hat{\mathbf{x}}=\sum\hat{c}_i\mathbf{v}_i$$

  视频的压缩应存储基础图象和下一帧对当前帧的修正部分（而不应该一帧一帧进行存储，那样没有利用好视频的连续性）

• 小波（The Haar wavelet basis）—— 除了全1向量外，其他基向量的非0元素一半为1，一半为-1，各基向量正交

  $$\left[\begin{array}{r}1\\1\\1\\1\\1\\1\\1\\1\end{array}\right],\left[\begin{array}{r}1\\1\\1\\1\\-1\\-1\\-1\\-1\end{array}\right],\left[\begin{array}{r}1\\1\\-1\\-1\\0\\0\\0\\0\end{array}\right],\left[\begin{array}{r}0\\0\\0\\0\\1\\1\\-1\\-1\end{array}\right],\left[\begin{array}{r}1\\-1\\0\\0\\0\\0\\0\\0\end{array}\right],\cdots,\left[\begin{array}{r}0\\0\\0\\0\\0\\0\\1\\-1\end{array}\right]$$

  标准基下的向量$p=c_1w_1+c_2w_2+\cdots+c_nw_n=Wc$，$W$为小波基向量作为列向量组成的小波矩阵，则$c=W^{-1}p$

好的基向量应具备的条件：

• 基向量矩阵可快速求逆，如快速傅里叶变换、小波矩阵直接转置（基向量正交）

• 少量的基向量就足以实现信号的近似

Change of basis

一个线性变换$T$，在基向量$v_1,v_2,\cdots,v_n$下的变换矩阵为$A$，在基向量$w_1,w_2,\cdots,w_n$下的变换矩阵为$B$，则$A$与$B$相似，$B=M^{-1}AM$

$T(v)=WA$，$W$为基向量作为列向量的矩阵，如果选取变换的特征向量作为基向量，则$T(v_i)=\lambda_iv_i$，$A=\Lambda$，可见选取特征向量作为基更利于图片压缩，但计算特征向量的代价较大，所以实际上还是采用傅里叶基或者小波

33 Quiz 3 Review

34 Left and Right Inverses; Pseudoinverse（左右逆，伪逆）

The pseudoinverse $A^+$ of $A$ is the matrix for which $x = A^+Ax$ for all $x$ in the row space of $A$. The nullspace of $A^+$ is the nullspace of $A^T$.

Left inverse

$A$列满秩，则$A^TA$可逆，则$A_{left}^{-1}=(A^TA)^{-1}A^T$是它的左逆（left inverse），$A_{left}^{-1}A=I$

$AA_{left}^{-1}=A(A^TA)^{-1}A^T=P$，是列空间的投影矩阵

Right inverse

$A$行满秩，则$A_{right}^{-1}=A^T(AA^T)^{-1}$是它的右逆（right inverse），$AA_{right}^{-1}=I$

$A_{right}^{-1}A=A^T(AA^T)^{-1}A=P$，是行空间的投影矩阵

Pseudoinverse

$A$不满秩（$r<n,r<m$），零空间和左零空间均非零，则$A$无逆矩阵（零空间存在非零向量则$Ax=0$，没有逆矩阵能恢复这一过程，即$A^{-1}0=x$），但如果将其限制在行空间和列空间上，即仅实现行空间向量$x$到列空间向量$Ax$的一一映射（证明$x$与$Ax$的一一对应：行空间向量$x\neq y$，若$Ax=Ay$，则$A(x-y)=0$，$x-y$在$A$的零空间中，同时$x-y$在$A$的行空间中，而零空间与行空间正交，则$x-y-0$，这与$x\neq y$矛盾)，则存在其逆映射，即为$A$的伪逆（pseudoinverse）

伪逆是必需的，因为使用最小二乘法解决线性回归问题时要求$A^TA$可逆，而很多时候重复的测量数据会使$A$不满秩，则此时可以使用伪逆来解决该问题

求伪逆$A^+$：奇异值分解$A=U\Sigma V^T$，$\Sigma=\left[\begin{array}{ccccc}\sigma_1&&&&&&\\&\sigma_2&&&&&\\&&\ddots&&&&\\&&&\sigma_r&&&\\&&&&0&&\\&&&&&\ddots&\\&&&&&&0\end{array}\right]$，是一个$m\times n$的对角矩阵，$\Sigma^+=\left[\begin{array}{ccccc}\frac{1}{\sigma_1}&&&&&&\\&\frac{1}{\sigma_2}&&&&&\\&&\ddots&&&&\\&&&\frac{1}{\sigma_r}&&&\\&&&&0&&\\&&&&&\ddots&\\&&&&&&0\end{array}\right]$，是$n\times m$的对角矩阵，$\Sigma\Sigma^+$和$\Sigma^+\Sigma$分别是列空间和行空间的投影矩阵，$A$的伪逆为$A^+=V\Sigma^+U^T$

35 Final Course Review