MIT线性代数公开课学习笔记第26~30课二十六、对称矩阵及正定性二十七、复数矩阵和快速傅里叶变换二十七、正定矩阵和最小值二十九、相似矩阵与Jordan标准型三十、奇异值分解

二十六、对称矩阵及正定性

实对称矩阵

实对称矩阵是所有元素均为实数的对称矩阵。具有以下性质：

• 1、所有特征值均为实数

• 2、所有特征向量均为实向量

• 3、不同特征值对应的特征向量之间是正交的

• 4、具有n个线性无关的特征向量

• 5、任意实对称阵A都可以用正交阵(P)对角化：(A=QLambda Q^{-1}=QLambda Q^T)

分析第一条性质

下面证明第1条性质：
因为(A)为实对称阵，从而(bar A=A,A^T=A)
[Ax=lambda x]

两边同取共轭：

[bar A bar x=bar lambda bar x ]

两边同时转置：

[bar x^Tbar {A^T} =bar lambda bar x^T ]

[bar x^T A =bar lambda bar x^T ]

两边同时右乘(x)

[bar x^T Ax =bar lambda bar x^T x ]

[lambda bar x^T x =bar lambda bar x^T x ]

其中，(|x|^2=bar x^T x)，又特征向量模长不为0，从而左右同时除去(bar x^T x)便可得到：

[barlambda=lambda]

分析第五条性质

国内线代教材已指出，可通过求出A的每个特征值的特征向量，并对每个特征值的(n-r(lambda_iI-A))个线性无关的特征向量施密特正交单位化后，得到n个相互正交的单位特征向量，将它们按列排列，即可得到正交阵P=((q_1,cdots,q_n))，(q_i)对应于(Lambda)中第i个主对角元，其值为特征向量(q_i)对应的特征值

[A=QLambda Q^T=(q_1,cdots,q_n)mathrm{diag}(lambda_1,cdots,lambda_n)(q_1,cdots,q_n)^T ]

[A=(q_1,cdots,q_n)(lambda_1q_1,cdots,lambda_nq_n)^T=sum_{i=1}^n lambda_iq_iq_i^T]

正定矩阵

定义：正定矩阵是特殊的实对称矩阵，其所有特征值均大于0。(xneq 0)时，对应的二次型(x^TAx)恒大于0

判断实对称阵是否正定的办法：

• 1、求出所有特征值，判断是否都大于0

• 2、n个K阶顺序主子式均大于0

• 3、通过倍加操作将A化为阶梯型矩阵U后，判断U的所有主元(必须有n个主元)是否全部大于0。更一般地，大于0的主元个数=大于0的特征值个数，小于的主元个数=小于0的特征值个数，

二十七、复数矩阵和快速傅里叶变换

复数向量的内积与模长

对于n维复数列向量(x,yin mathbb{C}^n)，其内积被定义为：

[xcdot y=bar x^T y]

定义(bar x^T=x^H)(hermitian)，则：

[xcdot y=x^Hy]

相应地，n维复数列向量(xin mathbb{C}^n)的模长被定义为：

[|x|=sqrt{x·x}=sqrt{x^Hx}]

复数矩阵、埃尔米特矩阵与酉矩阵

由复数构成的矩阵称为复数矩阵

类似之前的定义，也有

[bar A^T=A^H ]

对于复数方阵(Ain mathbb{C^{ntimes n}})，若：

[A^H=A ]

则称A为埃尔米特矩阵(Hermitian Matrix)，可见，埃尔米特矩阵中，与对角线对称的(a_{i,j}=bar a_{j,i})

若方阵(A)有(A^HA=I)，则称其为酉矩阵，对应于实矩阵里的正交矩阵。类似正交矩阵，在酉矩阵中，任意两个列向量是正交的，(alpha^Hbeta=0)，同样地，任意两个行向量也是正交的

快速傅里叶变换

傅里叶矩阵

[F_n=begin{pmatrix}1 & 1 & 1 & cdots & 1\ 1 & w & w^2 & cdots & w^{n-1}\ 1 & w^2 & w^4 & cdots & w^{2(n-1)}\ vdots & vdots & vdots & ddots & vdots\ 1 & w^{n-1} & w^{2(n-1)} & cdots & w^{(n-1)^2} end{pmatrix}_{n times n}]

其中，((F_n)_{i,j}=w^{ij})，注意傅里叶矩阵的下标是从0开始的，即i,j=0,...,n-1

({1,w,cdots,w^{n-1}})为n阶单位根，(w^n=1,w=e^{ifrac {2pi} n }=cos(frac {2pi} n)+isin(frac {2pi} n))(欧拉公式)

傅里叶矩阵是酉矩阵，(F_n^HF_n=I)

给出n维列向量x，x的离散傅里叶变换(DFT)可表示为(F_nx)，离散傅里叶逆变换为(F_n^{-1}x)

正常情况下，这个乘法过程时间复杂度为(O(n^2))

矩阵分解实现快速傅里叶变换

令(D_n=mathrm{diag}(1,w,cdots,w^{n-1}))，则：

[F_{2n}= begin{pmatrix}I & D_n\I & -D_nend{pmatrix} begin{pmatrix}F_n & 0\0 & F_nend{pmatrix}P_{2n}]

其中P为奇偶置换阵，将奇数列(行)排在前面，然后将偶数列(行)排在后面。例如：

[P_4=begin{pmatrix} 1 &&&\ &&1&\ &1&&\ &&&1 end{pmatrix}]

则

[F_{2n}x= begin{pmatrix}I & D_n\I & -D_nend{pmatrix} begin{pmatrix}F_n & 0\0 & F_nend{pmatrix}P_{2n}x]

设(P_{2n}x=(alpha^T,beta^T)^T),其中(alpha,betain mathbb{R}^n)

[F_{2n}x= begin{pmatrix}I & D_n\I & -D_nend{pmatrix} begin{pmatrix}F_n & 0\0 & F_nend{pmatrix}(P_{2n}x)]

[=begin{pmatrix}I & D_n\I & -D_nend{pmatrix} begin{pmatrix}F_n & 0\0 & F_nend{pmatrix}begin{pmatrix}alpha\ betaend{pmatrix}]

[=begin{pmatrix}I & D_n\I & -D_nend{pmatrix} begin{pmatrix}F_nalpha & 0\0 & F_nbetaend{pmatrix}]

求解(begin{pmatrix}I & D_n\I & -D_nend{pmatrix} begin{pmatrix}F_nalpha & 0\0 & F_nbetaend{pmatrix})时，计算量最大的是计算(F_nalpha,F_nbeta)，这两个计算完成后，其余的n阶矩阵乘法都是在(O(n))时间内完成(因为I和D都是对角阵)

FFT的关键是用这种矩阵分解的方法，递归下去计算(F_{n}alpha,F_{n}beta)

设计算(F_nx)的时间复杂度是(f(n))，则

[f(2n)=f(n)+n]

[f(2n)=n+frac n 2+frac n 4+cdots +1= O(nlogn)]

二十七、正定矩阵和最小值

正定矩阵的定义和判定方法，在国内教材中都有，这里不再赘述

正定二次型的几何意义

对于二次型(f(x_1,x_2)=x^TAx)而言，若A正定，则所有点((x_1,x_2,f(x_1,x_2)))在直角坐标系中构成了一个开口向上，过原点的碗型(表明当(x_1,x_2)不同时为0时，二次型取值一定大于0)。

若在这个碗型，z轴为1处作一个平行于xoy面的平面，可以截得一个椭圆：(ax_1^2+bx_1x_2+cx_2^2=1)

Hessian矩阵与极小值判定

定义n元函数f的Hessian矩阵为

当(H(f))正定时，(f(x))在该点取得极小值

正定二次型与主轴定理

对于正定二次型(x^TAx)，(x^TAx=1)是一个椭圆形(x为三维向量则是椭球体)，(A)的n个线性无关的特征向量代表该几何图形(椭圆、椭球...)的n条主轴的方向，每个特征向量对应的特征值是该主轴的长度

通过将二次型化为标准型(x^T(P^TAP)x=1)可以使得该几何图形通过正交变换P，使得所有主轴与各个坐标系平行

将二次型先化为标准形，再化为规范形(x^T(P^TAP)x=1)，则可以使得该几何图形通过线性变换P，变为标准的圆(球体,...)

二十九、相似矩阵与Jordan标准型

相似矩阵

对于方阵A,B，若存在可逆阵(P)使得(P^{-1}AP=B)，则(Asim B)

注意，若方阵A,B中有一个不可对角化，则A,B有完全相同的特征值也不能得到A和B相似。

只有当A,B有完全相同的特征值，都可对角化为相同的(Lambda)时，才能说A,B相似

Jordan标准型

设n阶方阵A有K个线性无关的特征向量(x_1,cdots,x_K)，对应的特征值为(lambda_1,cdots,lambda_K)，则一定存在可逆阵(P)使得

[P^{-1}AP= begin{pmatrix} J_1&&\ &J_2&\ &&ddots\ &&&J_K end{pmatrix}=J]

J称为A的Jordan标准型，其中(J_i)是一个Jordan块，为方阵，对应于K个线性无关的特征向量里的第i个，其中的(lambda_i)是该特征向量对应的特征值:

[J_i=begin{pmatrix} lambda_1&1&\ &lambda_2&1\ &&ddots&ddots\ &&&lambda_{r_i} end{pmatrix}]

当K=n时，每个Jordan块都是一阶的，J就是对角阵了

若J中对应(lambda_i)的Jordan块有t个，则(dim V_{lambda_i}=t)

三十、奇异值分解

任意m*n矩阵A都可以通过奇异值分解(singularly valueable decomposition,SVD)被分解为：

[A=USigma V^T]

其中，U是m阶正交阵，V是n阶正交阵，(U=(u_1,cdots,u_m)),(V=(v_1,cdots,v_n))，(Sigma)是(mtimes n)对角阵

((u_1,cdots,u_m)),((v_1,cdots,v_n))都是标准正交基，A矩阵可以让n维空间(C(v_1,cdots,v_n))投射到r(A)维空间中，即，将一组标准正交基((v_1,cdots,v_n))投射到((Av_1,cdots,Av_n))，而(dim (AV)= r(A))

当(ineq j)时，(v_icdot v_j=v_i^Tv_j=0)，若(v_i)为(A^TA)的单位化的特征向量，则

[v_i^TA^TAv_j=v_i^Tlambda_jv_j=lambda_jv_i^Tv_j=0]

从而，

[Av_icdot Av_j=(Av_i)^TAv_j=v_i^TA^TAv_j=0]

表明新基是正交基，再将投射后的新的正交基单位化：

[u_i=frac {Av_i}{|Av_i|}=frac {Av_i}{sqrt{v_i^TA^TAv_i}}=frac {Av_i}{sqrt{lambda_iv_i^Tv_i}}=frac {Av_i}{sqrt {lambda_i}}]

所以(Av_i=sigma_i u_i,sigma_i=sqrt {lambda_i})，用矩阵表示：

[AV=U Sigma ]

当(r(A)<n)时，对A的(v_1,cdots,v_{r(A)})，用A的零空间的n-r(A)个基(v_{r(A)+1},cdots,v_n)扩充成n个正交基

计算过程

[(A^TA)_{ntimes n}=VSigma^TU^TUSigma V^T=VSigma^TSigma V^T]

(r(A^TA)=r(A))。

对n阶对角阵(A^TA)用正交阵对角化，便可得到(V=(v_1,cdots,v_n))，约定，(v_1,cdots,v_{r(A)})对应的特征值非零，对角阵(Lambda=Sigma^TSigma=mathrm{diag}(lambda_1,cdots,lambda_{r(A)},0,cdots,0))

从而(lambda_i=sigma_i^2,sigma_i=sqrt {lambda_i})被称为奇异值，由于(Lambda)有r(A)个非零元素，因此奇异值有r(A)个

[Sigma= begin{pmatrix} sigma_1\ & ddots\ && sigma_{r(A)}\ &&& 0 end{pmatrix}_{mtimes n}]

[(AA^T)_{mtimes m}=USigma V^TVSigma^T U^T=USigma Sigma^T U^T]

对(AA^T)用正交阵对角化，得到(U=(u_1,cdots,u_m))，这里(Lambda=SigmaSigma^T=mathrm{diag}(lambda_1,cdots,lambda_{r(A)},0,cdots,0))

当(lambda_ineq 0)时(u_i)对应的(lambda_i)应该与(v_i)对应的(lambda_i)一致

SVD分解

[A=USigma V^T=(u_1,cdots,u_m) begin{pmatrix} sigma_1\ & ddots\ && sigma_{r(A)}\ &&& 0 end{pmatrix}_{mtimes n} begin{pmatrix} v_1^T\ vdots\ v_n^T end{pmatrix} ]
[ =(u_1,cdots,u_m) begin{pmatrix} sigma_1v_1^T\ vdots\ sigma_{r(A)}v_{r(A)}^T\ 0\ vdots\ 0 end{pmatrix} ]

[ =sum_{i=1}^{r(A)}sigma_iu_iv_i^T ]

从而将矩阵分解成了r(A)个秩1矩阵之和，每个秩1矩阵可以用一个奇异值(sigma_i)、两个向量(u_i,v_i)表示。若这里保留奇异值最大的前k个(sigma_i,u_i,v_i)，则可以进一步压缩这个矩阵