About Jordan Form

快一个星期没更新，毕竟考试周。虽然考完高数之后我就开（被）始（退）浪（学）了。今天简单水一下Jordan Form，GS老先生说这是20年前的climax of linear algebra（现在的climax应该是svd？），但他也说了这在理解上还是有意义的。如果哪里错了或者有缺漏的地方请指出嗷

Motivation of Jordan Form

Jordan Form相关的内容在GSLA page421附近。像之前讨论过的svd一样，Jordan Form也在关注不能被对角化的矩阵。Strang老先生在18.06的视频上对Jordan Form的描述是：the nicest,most diagonal one，和the least square和pseudo-inverse 一样，Jordan Form是一个对目标的近似。Jordan Form是利用相似矩阵去获得一个最近似的diagonal matrix（实际上并不是diagonal)。当然，如果这个矩阵本身可以被对角化，那它的Jordan matrix就是Λ。

Similarity and Jordan Block

首先回顾一下如何判定一个矩阵能否被对角化，相关严谨判断在书上310页，用GM（geometric multiplicity)和AM(algebraic multiplicity)的大小关系来判断，这里简化一下：如果一个方阵A（nxn）有n个eigenvectors，那它可以被对角化。然后之前还我们证明了，如果A有n个不同的eigenvalues，那它必有n个independent eigenvectors，换句话说，如果A的eigenvectors不足n个，那它必有重复的eigenvalues。这时我们怎么得到一个diagonal或者近似diagonal呢？

• SVD
  之前我们学过可以用SVD来得到U∑V^T ,其中∑是一个diagonal，对角线上是singular value。

  我之前在想一个问题，通过svd得到的diagonal有什么意义呢，毕竟它又不能像对角化一样很快算出矩阵的幂。现在的一种理解是，因为是diagonal，所以我们可以把U∑V^T 拆成outer product的形式，也就是常说的rank-one pieces。而每个pieces对应的奇异值大小感觉有点像权重：扔掉小的奇异值对原矩阵影响不大，但是扔掉大的奇异值的pieces对原矩阵影响比较大。

  还有什么理解的话可以补充一下嗷，我觉得自己这个还是有点浅。

• Jordan Block
  首先，假设现在有一个只有一个eigenvector的矩阵A（不是1x1），那么它的每一个eigenvalue无疑都是相同的，让我们假设是λ，那么A不可能相似于一个diagonal。

  简短的说明：eigenvalue全是λ的对角矩阵就是λI，我们知道A相似于B iff A=MBM^-1 ，那么λI的相似矩阵就是M λIM^-1 = λI，也就是说，λI只和自己相似，它不可能和A相似。

  那如果我们想得到一个最近似于λI的和A相似的矩阵，其实很简单，将λI的次对角线从0改为1就可以了，这其实就是一个Jordan Block。

  最后，之前我们的假设是，一个只有一个eigenvector的矩阵A，它的eigenvalue全是λ，这是个很强的假设，有比较大的局限性，所以现在我们推广到Jordan Matrix：）

From Jordan Block to Jordan Matrix

假设一个不能被对角化的方阵A有s个eigenvector，从刚才的分析我们知道，每一个Jordan Block对应一个eigenvector。将每一个eigenvector对应的Jordan block放在对角线上，我们就得到了Jordan matrix。

值得注意的是，忽略对角线上的Jordan Block的顺序后，每个矩阵的Jordan matrix具有唯一性。

Summary

最后来总结一下，对角化和SVD和Jordan Form的区别（？）

• advantage:

  • 对角化：算矩阵的幂直接转化为λ的指数运算，快
  • SVD：适用于所有矩阵（包括非方阵）、能将矩阵拆成rank-one pieces、奇异值很稳定（误差大小不超过矩阵中的误差大小）
  • Jordan Form:适用于所有方阵，得到一个double diagonal matrix（具体应用我没怎么看到，寒假去康康leon那本书上有没有关于Jordan Form的应用）
    总的来说，SVD局限性看上去是最小的，不愧是现在的climax of linear algebra（逃

• disadvantage:

  • 对角化：只能对角化有足够eigenvector的矩阵，局限性较大

  • SVD：我也不知道有啥disadvantage，但是计算量无疑不小

  • Jordan Form:只能得到近似diagonal的结果（而且我还不知道它有什么用）

    补充1:对角化和Jordan Form都依赖于计算eigenvalue，但是书上也有说，eigenvalue是很不稳定的，矩阵上一点很小的变动或误差都能对eigenvalue的很大的改变，这也是问题之一。

    补充2：对角化和SVD都携带了eigenvalue和eigenvector的信息，但是Jordan Form就不是，你从一个矩阵的Jordan Form只能看出它的AM、GM和eigenvalue，不能得到关于矩阵的eigenvector的信息

今天暂时水这么多，是真的水（逃
有错误或有疑问的话可以跟帖回一下嗷
下一次更DFT吧，虽然clrs上讲得已经比较清楚，但是写一下比较不容易忘掉（逃

关于DFT和FFT
目前只写了关于DFT的部分，FFT的部分有点难写emmmmmmmm，内容很难写，latex也很难写：）。FFT参考了GSLA、CLRS还有Leon那本LA with applications，居然觉得讲得最清楚的是Leon 那本，补充着来看整挺好嗷。

现在算是从一个比较纯线性代数的角度的去看DFT和FFT，等算导讲到DFT和FFT的时候应该要有不同的角度去看吧。

Bintou 相同的AM和GM我觉得没啥毛病啊…AM是eigenvalue的重复个数，GM是eigenvector的个数，设c是J的唯一eigenvalue，J-cI的零空间是一维的就说明J只有一个eigenvector，A也只有一个eigenvector，所以它们GM一样。GM和AM都只是关注个数而已。

至于J-cI的零空间为什么是一维的，因为它在次对角线上有n-1个1，其他所有位置上都是0，所以它的秩是n-1，即零空间是1维的。

今天将题目整理了一下，发到Hackmd上了，如果有人要补充什么的话直接修改就好了，很方便，而且hackmd的大纲非常的舒服。以后同步更新。

DFT and FFT也放到hackmd上去了，今天更新了一部分，还没更完，希望下次更新能把它更完吧。

Latex鲨我：）