矩阵论大杂烩

本文内容来自浙大海院吴叶舟老师的矩阵论、MIT18.06、MIT18.065以及各种学习过程中记录的笔记。近两个月没怎么更新了，发现还是有很多地方可以改进的。欢迎交流与建议~

本文同时还提供了PDF和markdown版本，可以戳这里到度娘网盘下载，提取码2333

PDF生成使用Obsidian v1.0.0，主题Blue Topaz

立个flag，考完我要把矩阵论和优化课的内容都缝合上去（（

散装内容

矩阵的四个空间

列空间 Column Space （aka 值域 Range） \[C(A)=\left \{ y|y=Ax \right \} \] 零空间 Nullspace （aka 解空间 Solution Space） \[N(A)=\left \{ x|Ax=0 \right \} \]

行空间 Row Space \[R(A)=C(A^{\mathrm{T}} )=\left \{ y|y=A^{\mathrm{T}} x \right \} \] 左零空间 Left Nullspace \[N(A^{\mathrm{T}} )=\left \{ x|A^{\mathrm{T}} x=0 \right \} \]

列空间和左零空间互为正交补（Orthogonal Complements）
行空间与零空间互为正交补

证明：假设\(A^{\mathrm{T}} x=0\)，则\(A^{\mathrm{T}}\)的任意行向量都与\(x\)正交，从而列空间垂直于左零空间，又因为两个空间的维度相加为\(m\)，因此两个空间互为正交补；另一对同理。

伪逆 pseudo-inverse （aka Moore-Penrose逆）

顺便还有广义逆（generalized inverse）

广义逆、伪逆和左右逆是啥？有什么关系？

伪逆是一种特殊的广义逆，伪逆一定是广义逆，广义逆不一定是伪逆

Kronecker积

Kronecker积是矩阵代数中的张量积 \[ A\otimes B=\begin{bmatrix} a_{11}B &\cdots &a_{1n}B \\ \vdots &\ddots &\vdots \\ a_{m1}B &\cdots &a_{mn}B \end{bmatrix} \]

这玩意从俩\((1,1)\)型张量\(A,B\)定义了一个\((2,2)\)型张量\(A\otimes B:V^*\times V^*\times V \times V \rightarrow \mathbb{P}\)，对于向量\(y_1\in V_1, y_2\in V_2\)以及其各自对偶空间中的\(x_1^{\mathrm{T}} \in V_1^*,x_2^{\mathrm{T}} \in V_2^*\)，有

\[ x_1^{\mathrm{T}} x_2^{\mathrm{T}} A\otimes By_2y_1=x_1^{\mathrm{T}} Ay_1\cdot x^{\mathrm{T}} _2By_2 \]

Kronecker和

即

\[ A\otimes I+I\otimes A \]

似乎这玩意可以表示\(-\frac{\partial ^2u }{\partial x^2 } -\frac{\partial ^2u }{\partial y^2 }\)，不是很懂.jpg

Hadamard积

就是两个矩阵的对应元素相乘

\[A\circ B=\begin{bmatrix} a_{11}b_{11} &\cdots &a_{1n}b_{1n} \\ \vdots &\ddots &\vdots \\ a_{m1}b_{m1} &\cdots &a_{mn}b_{mn} \end{bmatrix}\]

Cartisian积与直积

若\(a\in A,b\in B\)，则集合\(A\)与\(B\)的Cartisian积为

\[ A\times B=\left\{ (a,b)|a\in A,b\in B \right\} \] Cartisian积仅仅是两个集合的东西的捆绑。直积也是上面这个式子，但集成了代数结构（如群、线性空间等），即对元素之间的运算有一定要求。

直和

列向量的直和：

\[ x_1\oplus x_2=\begin{bmatrix} x_1\\ x_2\end{bmatrix} \]

矩阵的直和： \[ A\oplus B=\begin{bmatrix} A & \\ &B \end{bmatrix} \]

Taylor展开

变量为向量，函数为标量

\[ f(x+\Delta x)=f(x)+\frac{\partial f }{\partial x } \Delta x+\frac{ 1 }{ 2 } \Delta x^{\mathrm{T}} \frac{\partial ^2f }{\partial x^{\mathrm{T}} \partial x }\Delta x+\omicron\left(\left\| \Delta x \right\|_2^2 \right) \]

或\(\exists t\in (0,1)\)

\[ f(x+\Delta x)=f(x)+\frac{\partial f(x) }{\partial x } \Delta x+\frac{ 1 }{ 2 } \Delta x^{\mathrm{T}} \frac{\partial ^2f(x+t\Delta x) }{\partial x^{\mathrm{T}} \partial x }\Delta x \]

其中\(\frac{\partial f }{\partial x }\)为梯度（的转置），\(\frac{\partial ^2f }{\partial x^{\mathrm{T}} \partial x }\)为Hessian矩阵。详见梯度与Hessian矩阵。

变量为向量，函数为向量

\[ f(x+\Delta x)=f(x)+\frac{\partial f }{\partial x } \Delta x+\omicron \left( \left\| \Delta x \right\| _2 \right) \]

其中\(\frac{\partial f }{\partial x }\)为Jacobian矩阵。

矩阵级数

\[ e^{tA}=\sum_{n=1}^{\infty}\frac{ 1 }{ n! } (tA)^n \]

\[ (I-tA)^{-1}=\sum_{n=0}^{\infty}(tA)^n \]

\[ \ln(I+A)=\sum_{ n=0 }^{ \infty } \frac{ (-1)^{n} }{ n+1 } A^n =A-\frac{ 1 }{ 2 }A^2+\frac{ 1 }{ 3 } A^3+\cdots \]

\[ \sin^{}{ A }=\sum_{ n=0 }^{ \infty } \frac{ (-1)^nA^{2n+1} }{ (2n+1)! } \]

\[ \cos^{}{ A }=\sum_{ n=0 }^{ \infty } \frac{ (-1)^nA^{2n} }{ (2n)! } \]

这几个都是定义出来的，强行使得这些函数（至少先作为符号）有意义

当然上式必须收敛才能如此定义，如\(0<x<1\)可推广到\(\forall k=1,\cdots,n \Longrightarrow 0<\lambda_k(A)<1\)

其中\(e^{tA}\)有个很骚的计算公式：

\[ e^{tA}=\mathcal{L} ^{-1}[(sI-A)^{-1} ] \]

因为

\[\frac{ 1 }{ n! }(tA)^{n} = \mathcal{L} ^{-1}[\frac{ A^{n} }{ s^{n+1} } ]\]

低秩矩阵

只要\(\mathrm{rank}(A)<\frac{ 1 }{ 2 } n\)就能称\(A\)为低秩矩阵。

当\(\mathrm{rank}(A)\ll \frac{ 1 }{ 2 } n\)，称\(A\)炒鸡低秩（efficiently low rank）。

数值秩 Numerical Rank

对于给定容差\(\varepsilon \in[0,1)\)，若第\(k\)个奇异值刚好小于第一奇异值，即：

\[ \left\{\begin{matrix} \sigma_{k+1}\le\varepsilon \sigma_1 \\ \sigma_{k}>\varepsilon \sigma_1 \end{matrix}\right. \]

则称矩阵的数值秩为\(\mathrm{rank}_\varepsilon (A)=k\)。

Rayleigh商

Rayleigh Quotient \[ R(x)=\frac{ x^{\mathrm{T}} Sx }{ x^{\mathrm{T}} x } \]

其中\(S\)实对称。

（话说这玩意不就是2诱导范数里被优化的那坨吗）

则\(R(x)\)的最大值为\(\lambda_1(S)\)，当且仅当\(x\)取对应的特征向量；\(R(x)\)的最大值为\(\lambda_n(S)\)，当且仅当\(x\)取对应的特征向量。其他的特征向量都为鞍点（Saddle Point）。

线性空间

线性空间的定义

在数域\((F,+,\cdot)\)与集合\(V\)上定义两个封闭运算加法\(\oplus:V\times V\rightarrow V\)与数乘\(\circ:F\times V\rightarrow V\)，即

\[ \forall \alpha \in V,\forall \beta\in V\Longrightarrow \alpha \oplus\beta\in V \]

\[ \forall \alpha \in V,\forall\lambda \in F\Longrightarrow \lambda \circ\alpha \in V \]

且如果满足以下8条公理：

加法零元：\(\forall \alpha \in V,\exists !\ 0\in V\Longrightarrow \alpha \oplus0=\alpha\)
加法逆元：\(\forall \alpha\in V,\exists!\ \beta \in V \Longrightarrow \alpha \oplus\beta=0\)（则\(\beta\)记为\(-\alpha\)）
加法交换律：\(\forall \alpha \in V,\forall \beta\in V\Longrightarrow \alpha \oplus\beta=\beta \oplus\alpha\)
加法结合律：\(\forall \alpha \in V, \forall \beta\in V\Longrightarrow (\alpha \oplus \beta)\oplus\gamma=\alpha \oplus(\beta\oplus\gamma)\)
数乘单位：\(\forall \alpha \in V,\exists ! \ 1\in F\Longrightarrow 1\circ \alpha =\alpha\)
数乘结合律：\(\forall \lambda \in F,\forall \mu \in F\Longrightarrow \lambda \circ(\mu \circ \alpha )=(\lambda \cdot\mu)\circ \alpha\)
基域分配律：\(\forall \lambda,\mu \in V,\forall \alpha \in F\Longrightarrow (\lambda +\mu)\circ \alpha =\lambda \circ \alpha \oplus \mu \circ \alpha\)
线性空间分配律：\(\forall \lambda \in F,\forall \alpha ,\beta \in V\Longrightarrow \lambda\circ (\alpha\oplus\beta) =\lambda \circ \alpha \oplus \lambda \circ \beta\)

则称代数系统\((V,\oplus,\circ,F)\)为一个线性空间。其中\(F\)为基域，本课主要讨论\(F=\mathbb{R}\)与\(F=\mathbb{C}\)。

有理数的扩域\(\mathbb{Q} (\sqrt{p})=\left\{ y|y=a+b\sqrt{p};a,b\in\mathbb{Q} \right\}\)

各种层次的运算：

加法\((\cdot)\oplus(\cdot)\)（如加法\((\cdot)+(\cdot)\)与乘法\((\cdot)\cdot(\cdot)\)）

数乘\((\cdot)\circ(\cdot)\)

映射\(f:(\cdot)\rightarrow (\cdot)\)

内积\((\cdot,\cdot)\)

范数\(\left\| \cdot \right\|\)

线性空间的性质

若\(\oplus\)或\(\circ\)不封闭，则不满足8条公理

若数域\(F\)为\(\mathbb{C}\)或其子域（如\(\mathbb{R} ,\mathbb{Q}\)等），则若\(\oplus\)与\(\circ\)均封闭，则\((V,\oplus,\circ,F)\)一定为线性空间

一些举例

若\(V=\mathbb{R} ,F=\mathbb{C}\)，则对数乘不封闭，从而\(V\)不是线性空间

矩阵\(A\)的列空间\(C(A)\)与零空间\(N(A)\)均为线性空间

线性空间的同构

两个线性空间\((V,\oplus,\circ,F)\)与\((W,\otimes,\bullet ,F)\)是同构的：

如果\(V,W\)之间存在双射\(f:V\rightarrow W\)（即“一一对应关系”）使得对于\(\forall \alpha ,\beta\in V,\forall \lambda \in F\)有：

\(f(\alpha\oplus\beta)=f(\alpha)\otimes f(\beta)\)
\(f(\lambda \circ \alpha )=\lambda \bullet f(\alpha )\)

一个三元一次方程集合 \[ \{ ax+by+cz=d|a,b,c,d\in \mathbb{R}\} \] 的一组基是

\[ x=0,y=0,z=0,1=0 \]

除了线性空间这样的代数系统外，还有群、环、域等代数系统，其中群\((G,\cdot)\)只需满足封闭性、结合律、幺元与逆即可（简称封结幺逆）

线性变换

线性变换\(T\)的原则：

\(T(v+w)=T(v)+T(w)\)
\(T(C\cdot v)=C\cdot T(v)\)

投影变换
旋转变换
实际上，与矩阵相乘的任意变换\(T(v)=Av\)都是线性变换

Jordan标准型

流程化计算Jordan分解 - 知乎

内积空间

Gram-Schmidt正交化

对于矩阵\(A=[a_1,\cdots,a_n]\)，选择：

\[ \left\{\begin{matrix} \beta_1=a_1 &,q_1=\frac{ \beta_1 }{ \left\| \beta_1 \right\| } \\ \beta_2=a_2-(a^{\mathrm{T}} _2q_1)q_1 &,q_2=\frac{ \beta_2 }{ \left\| \beta_2 \right\| } \\ \vdots \\ \beta_n=a_n-(a_n^{\mathrm{T}} q_1)q_1-\cdots-(a_n^{\mathrm{T}} q_{n-1})q_{n-1}&,q_n=\frac{ \beta_n }{ \left\| \beta_n \right\| } \end{matrix}\right. \]

改进版：列主元Gram-Schmidt正交化

对于求\(q_k\)，比较

\[ \left\{\begin{matrix} a_k-(a_k^{\mathrm{T}} q_1)q_1-\cdots-(a_k^{\mathrm{T}} q_{k-1})q_{k-1} \\ a_{k+1}-(a_{k+1}^{\mathrm{T}} q_1)q_1-\cdots-(a_{k+1}^{\mathrm{T}} q_{k-1})q_{k-1} \\ \vdots \\ a_n-(a_n^{\mathrm{T}} q_1)q_1-\cdots-(a_n^{\mathrm{T}} q_{k-1})q_{k-1} \end{matrix}\right. \] 选择最大的一个做归一化 \[q_k=\frac{ (\cdot) }{ \left\| \cdot \right\| }\]

赋范线性空间

向量范数

\(\ell_2\)范数 \[ \left \| x \right \|_{2} = \sqrt{\sum_{ k=1 }^{ n } |x_k|^{2} }=\sqrt{x^{\mathrm{T}} x} \] \(\ell_1\)范数 \[ \left \| x \right \|_{1} = \sum_{ k=1 }^{ n } |x_k| \] \(\ell_{+\infty}\)范数 \[ \left \| x \right \|_{+\infty} = \max |x_k| \]

\(\ell_0\)范数（实际上不是范数，真正的范数要求是凸的） \[ \left \| x \right \|_{0} = \sum_{ k=1 }^{ n } |\mathrm{sgn}(x_k)| \]

\(\ell_p\)范数 \[ \left \| x \right \|_{p} = \left( \sum_{ k=1 }^{ n } |x_k|^{p} \right)^\frac{ 1 }{ p } \]

矩阵范数

元素形式范数 Entrywise Norm

\[ \left\| A \right\| _{E_p}=\left( \sum_{ i=1 }^{ m } \sum_{ j=1 }^{ n } |a_{ij}|^p \right) ^\frac{ 1 }{ p } \]

\(p=1\)：和范数 \[ \left\| A \right\|_{E_1}=\sum_{ i=1 }^{ m } \sum_{ j=1 }^{ n } |a_{ij}| \]

\(p=2\)：Frobenius范数（aka Euclidean范数或 Schur范数或 Hilbert-Schmidt范数） \[ \left \| A \right \| _{E_2} =\left \| A \right \| _{F} = \sqrt{\sum_{ k=1 }^{ m } \sum_{ l=1 }^{ n } |a_{ij}|^2 }=\sqrt{\sum_{ k=1 }^{ r } \sigma_k^2 }=\sqrt{\mathrm{tr} \left( AA^{\mathrm{T}} \right) } \]

\(p=\infty\)：最大范数 \[ \left \| A \right \| _{E_\infty} =\max_{i,j}{|a_{ij}|} \]

诱导范数 Induced Norm

\[ \left\| A \right\|_{m,n}=\max_{x\in\mathbb{R} ^n,\left\| x \right\|_n=1 }{\left\| Ax \right\| _m }=\max_{x\in\mathbb{R} ^n,x\ne 0}\frac{ \left\| Ax \right\| _m }{ \left\| x \right\|_n } \] 当\(m=n\)时，称为\(\ell_p\)范数（aka Minkowski范数）

诱导范数是算子范数的一个特例

\(p=1\)：\(\ell_1\)范数

\[ \left\| A \right\| _{\ell_1}=\left\| A \right\| _{1,1} =\max_{1\le j\le n}{\sum_{ i=1 }^{ m }|a_{ij}| } \]

\(p=2\)：\(\ell_2\)范数（aka 谱范数 Spectral Norm）

\[ \left\| A \right\| _{\ell_2}=\left\| A \right\| _{2,2} =\max_{x\in \mathbb{R} ,x\ne 0}{ \frac{ \left\| Ax \right\|_2 }{ \left\| x \right\|_2 } }=\sigma_1 \]

\(p=\infty\)：\(\ell_\infty\)范数

\[ \left\| A \right\| _{\ell_\infty}=\left\| A \right\| _{\infty,\infty} =\max_{1\le i\le m}{\sum_{ j=1 }^{ n }|a_{ij}| } \]

Schatten范数

令 \[ \sigma=\begin{pmatrix} \sigma_1,\cdots,\sigma_{\min{\left\{ m,n \right\} }} \end{pmatrix}^{\mathrm{T}} \] 则Schatten-\(p\)范数为 \[ \left\| A \right\|_{S_p} =\left\| \sigma \right\|_p \]

\(p=1\)：核范数（Nuclear Norm） \[ \left\| A \right\|_{S_1}=\left\| A \right\|_*=\sum_{ i }\sigma_i=\mathrm{tr}\left( \left( A^{\mathrm{T}} A \right)^\frac{ 1 }{ 2 } \right) \]

\(p=\infty\)：\(\ell_2\)范数（aka 谱范数 Spectral Norm）

\[ \left\| A \right\| _{\ell_2}=\left\| A \right\| _{2,2} =\max_{x\in \mathbb{R} ,x\ne 0}{ \frac{ \left\| Ax \right\|_2 }{ \left\| x \right\|_2 } }=\sigma_1 \]

强行定义的零范数

和向量的0范数类似，定义矩阵的零范数为\(\left\| A \right\|_0 =\mathrm{rank}(A)\)

显然这并不是范数，只不过叫范数而已。猫猫虫是虫吗？是的

算子范数

上节诱导范数就是算子范数的一种特例。

条件数

就是矩阵\(A\)的范数和\(A^{-1}\)的范数的比，若取\(\ell_2\)范数，则条件数为

\[ \mathrm{cond_2}(A)=\frac{\|A\|_2}{\|A^{-1}\|_2}=\frac{\sigma_1}{\sigma_n} \]

条件数越大，表示矩阵越病态，在一些数值计算时误差越大。

矩阵分解方法

LU分解

\[A=LU\] 或

\[PA=LU\]

用于消元

拓展方法：

LDU分解
UD分解

QR分解

\[A=QR\]

本质是Gram-Schmidt正交化

对于线性无关的向量组\(\begin{bmatrix} a_1 &\cdots &a_n \end{bmatrix}\)，Gram-Schmidt正交化得到单位正交向量组\(Q=\begin{bmatrix} q_1 &\cdots &q_n \end{bmatrix}\)

其中 \(R\) 为上三角矩阵，且

\[ R=\begin{bmatrix} a_1^{\mathrm{T}} q_1 & \cdots & a_n^{\mathrm{T}} q_1 \\ \vdots & \ddots & \vdots \\ a_1^{\mathrm{T}} q_n & \cdots & a_n^{\mathrm{T}} q_n \end{bmatrix} \]

正交分解/特征值分解

\[S=Q\Lambda Q^{\mathrm{T}}=\sum_{k=1}^{n}\lambda_kq_kq_k^{\mathrm{T}} \]

其中 \(S\) 为对称矩阵

特征值矩阵的用法

求解\(v_{k+1}=Av_k\)
求解\(\frac{\mathrm{d}}{\mathrm{d}t}v=Av\)

对于非对称矩阵 \(A\)

\[A=X\Lambda X^{-1}\]

Jordan分解

流程化计算Jordan分解 - 知乎

奇异值分解 Singular Value Decomposition

\[A=U\Sigma V^{\mathrm{T}} \]

原理

魔改特征向量定义， \[ \sigma_iu_i=Av_i\] 不妨令\(u_1,\cdots,u_r\)和\(v_1,\cdots,v_r\)分别为列空间和行空间的一组单位正交向量，组合得到 \[\begin{bmatrix} \sigma_1u_1 & \cdots & \sigma_r u_r \end{bmatrix}=A\begin{bmatrix} v_1 & \cdots & v_r \end{bmatrix} \] 或 \[ \begin{bmatrix} u_1 & \cdots & u_r \end{bmatrix}\begin{bmatrix} \sigma_1 & & \\ & \ddots & \\ & & \sigma_r \end{bmatrix}=A\begin{bmatrix} v_1 & \cdots & v_r \end{bmatrix} \] 注意到列空间和左零空间、行空间和零空间互为正交补，即可以选择一组单位正交向量\(u_{r+1},\cdots,u_m\)和\(v_{r+1},\cdots,v_n\)，扩充到上式形成两个正交矩阵： \[ \begin{bmatrix} u_1 & \cdots & u_r & u_{r+1} & \cdots u_m \end{bmatrix}\begin{bmatrix} \sigma_1 & & &\\ & \ddots & &\\ & & \sigma_r&\\ & & &O_{m-r,n-r}\\ \end{bmatrix}=A\begin{bmatrix} v_1 & \cdots & v_r & v_{r+1} & \cdots & v_n \end{bmatrix} \]

右乘\(V^{-1} =V^{\mathrm{T}}\)得到

\[ A=U\Sigma V^{\mathrm{T}} \]

且一般会令\(\sigma_1>\cdots>\sigma_r>0\)

其中\(\sigma_k(A)=\lambda_{[k]}(A^{\mathrm{H}} A)\)，其中\((\cdot)_{[k]}\)表示由大到小排序第\(k\)个（第k序列数）。

特别地，当\(A\)为对称阵时，\(\sigma_k(A)=\left| \lambda(A) \right|_{[k]}\)。

三个矩阵的直观意义

应用：主成分分析

\[ A=U\Sigma V^{\mathrm{T}} =\sum_{ k=1 }^{ n } \sigma_ku_kv_k^{\mathrm{T}} \] 其中最主要的成分即\(\sigma_1u_1v_1^{\mathrm{T}}\)

极分解 Polar Decomposition

\[ A=SQ \]

其中 \(S=U\Sigma U^{\mathrm{T}}\) 为对称矩阵， \(Q=UV^{\mathrm{T}}\) 为正交矩阵。

与\(z=r\cdot e^{i\theta }\)有异曲同工之妙

Ax=b求解方法

A可逆

方法1

若条件数\(\mathrm{cond}(A)=\frac{ \sigma_1 }{ \sigma_n }\)比较阳间，且阶数较小，则直接求逆：\(x=A^{-1} b\)

方法2

若条件数比较阴间，用\(QR\)分解或列主元\(QR\)分解再计算

方法3

若\(A\)维数很高，用迭代方法计算

方法4

若\(A\)维数很高且稀疏，用\(x_k\)代替\(x\)，其中\(x_k\)为Krylov子空间\(\mathcal{K}_k =\mathrm{span}\left\{ b,Ab,\cdots,A^{k-1}b \right\}\)中对\(Ax=b\)的最优解。

Krylov子空间\(\mathcal{K}_k\)的基经过正交单位化后称为Krylov-Arnoldi子空间。

若\(A\)为对称矩阵，则Krylov-Arnoldi子空间称为Krylov-Lanczos子空间。

方法5

若\(A\)维数高得离谱，将\(A\)视为样本矩阵，用随机线性代数解决

A不可逆，A列满秩

令 \[L=\left\| Ax-b \right\|_2^2=x^{\mathrm{T}} A^{\mathrm{T}} Ax-2b^{\mathrm{T}} Ax+b^{\mathrm{T}} b\]

方法1

伪逆 \[ \hat{x}=A^\dagger b \]

方法2

令偏导\(\frac{ \partial L }{ \partial x }\)为0

方法3

将A列向量正交化，然后做Householder变换

方法4

引入罚函数/正则项，令\(A=U\Sigma V^{\mathrm{T}}\)，如：

岭回归

\[ \min{\left( \left\| Ax-b \right\|^2 +\delta^2 \left\| x \right\|^2_2 \right) } \] 从而

\[ (A^{\mathrm{T}} A+\delta ^2 I)x_\delta =A^{\mathrm{T}} b \]

LASSO回归

\[ \min{\left( \left\| Ax-b \right\|^2 +\delta^2 \left\| x \right\|_1 \right) } \]

特征值的计算问题

矩阵阶数大于4时，不存在特征值的公式。

一种迭代法

利用QR分解进行迭代：

分解\(A=A_0=Q_0R_0\)，令\(A_1=R_0Q_0\)，即\(A_1=R_0A_0R_0^{-1}\)。如此递推，有

\[ A_{n+1}=R_nA_nR_n^{-1} \]

则

\[ \Lambda=\lim_{n\rightarrow \infty}{\mathrm{diag}(A_n)} \] ### 改进方法1：加速引入偏移\(A_0-sI=Q_0R_0\)，则迭代式为

\[ A_{n+1}-sI=R_n(A_n-sI)R_n^{-1} \]

改进方法2：MATLAB采用的算法

LAPACK和LINPACK用到了这个算法

步骤：

用相似变换将\(A\)变换到Hessenberg矩阵
用改进方法1

特殊矩阵

初等矩阵

三种初等矩阵

交换 \(k\) 与 \(l\) 行/列：\(E_{k,l}\)
乘 \(t\) 到第 \(k\) 行/列：\(E_{k}(t)\)
将第 \(k\) 列的 \(t\) 倍加到第 \(l\) 列（或将第 \(l\) 行的 \(t\) 倍加到第 \(k\) 行）：\(E_{k,l}(t)\)

三种初等矩阵的逆

\(E^{-1}_{k,l}=E_{k,l}\)
\(E_{k}(t)^{-1}=E_{k}(\frac{ 1 }{ t } )\)
\(E_{k,l}(t)^{-1}=E_{k,l}(-t)\)

对称矩阵

\[A=A^{\mathrm{T}} \]

性质：

若\(A\in \mathbb{R}^{n\times n}\)，则所有特征值\(\lambda \in \mathbb{R}\)
特征向量可以被选为互相正交的

正交矩阵 Orthogonal Matrix

\[ A^{\mathrm{T}} A=AA^{\mathrm{T}} =I \]

酉矩阵 Unitary Matrix

复数域则称酉矩阵：

\[ A^{\mathrm{H}} A=AA^{\mathrm{H}} =I \]

正规矩阵 Normal Matrix

\[ A^{\mathrm{H}} A=AA^{\mathrm{H}} \] 三种特殊正规矩阵：

对称矩阵\(S=S^{\mathrm{T}}\)；有\(\mathcal{Im} (\lambda)=0\)，特征向量相互正交；
正交矩阵\(Q^{\mathrm{T}} =Q^{-1}\)；有\(\left| \lambda \right| =1\)，特征向量相互正交；
反对称矩阵\(M^{\mathrm{T}} =-M\)；有\(\mathcal{Re} (\lambda)=0\)，特征向量相互正交。

正定矩阵 Positive Definite Matrix

正定矩阵首先必须是对称的。

对于不对称矩阵\(A\)，可以将其分解为反对称矩阵\(W\)与对称矩阵\(S\)的和，而反对称矩阵\(W\)的二次型 \(x^{\mathrm{T}} Wx\) 恒为0，因此可以通过对称矩阵\(S\)反映矩阵\(A\)的正定性(ref)

找到\(W,S\)使\(A=W+S\)：

\[ W=\frac{ 1 }{ 2 } \left( A-A^{\mathrm{T}} \right),\ S=\frac{ 1 }{ 2 } \left( A+A^{\mathrm{T}} \right) \]

半正定(Positive Semidefinite)矩阵：\(A\succeq 0\)

检验方法

矩阵正定，即\(A\succ 0\)，如果：

所有特征值\(>0\)
所有顺序主子式\(>0\)
矩阵消元时所有主元\(>0\)
\(\forall x,x^{\mathrm{T}} Ax>0\)

性质

\[\forall A\in \mathbb{R}^{m\times n},\ \ A^{\mathrm{T}} A\succeq 0\]

\[A\succ0,B\succ0\Longrightarrow A+B\succ0\]

投影矩阵

到向量 \(a\) 上的1维投影：

\[P=\frac{ aa^{\mathrm{T}} }{ a^{\mathrm{T}} a } \]

到矩阵 \(A\) 的列空间 \(C(A)\) 的高维投影（\(A\)列满秩）：

\[P=A(A^{\mathrm{T}} A)^{-1} A^{\mathrm{T}} \]

这玩意实际上就是\(AA^\dagger\)
用于近似求解对于不在列空间中的 \(b\) 的线性方程组\(Ax=b\)

投影到\(C(A^{\mathrm{T}} )\)的矩阵（\(A\)行满秩）：

\[ P=A^\dagger A=A^{\mathrm{T}} (AA^{\mathrm{T}} )^{-1} A \]

性质

\[\det{P}=0\] \[P^{\mathrm{T}} =P\] \[P^2=P\]

轮换矩阵 Shift Matrix

\[ P=\begin{bmatrix} & 1 & & \\ & & \ddots & \\ & & & 1\\ 1 & & & \end{bmatrix} \] 左乘P相当于把所有行都向上平移，并把多出来的第一行丢到最后一行去；右乘P相当于把所有列都向右平移，并把多出来的最后一列丢到第一列去。

这玩意有如下性质：

\[ P^2=\begin{bmatrix} & & 1 && \\ & & & \ddots& \\ & & & &1\\ 1 & & &&\\ &1& & & \end{bmatrix} \]

反反复复，直到

\[ P^n=I \]

Householder矩阵

用于镜像变换

若镜像变换的对称超平面的法线向量为\(u\)，则Householder矩阵为

\[ H=I-2uu^{\mathrm{T}} \]

性质

正交矩阵：\(H^{-1} =H^{\mathrm{T}}\)
对称矩阵：\(H^{\mathrm{T}} =H\)
对合矩阵：\(H^2=I\)

Hadamard矩阵

（其实h不发音，阿达马矩阵）

特殊的正交阵，由+1和-1组成

只能是\(2, 4, 16, 64, \cdots\)维矩阵

可以由Kronecker积定义递推：

\[H_n=H_1 \otimes H_{n-1}\]

其中

\[H_1=\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}\]

Markov矩阵

性质：

所有元素\(\ge0\)
任意列的求和均为1（确保1为一个特征值）
从而其他任意特征值均有\(|\lambda|<1\)

假设\(\lambda_k=1\)，则对于\(u_k=A^ku_0\)有

\[ \lim_{k\rightarrow\infty}u_k=c_k x_k \]

其中 \(x_k\) 为 \(\lambda_k\) 对应的特征向量，\(c_k\) 为 \(u_0\) 在 \(x_k\) 方向上的系数

Fourier矩阵

\[ F_n=\frac{ 1 }{ \sqrt{n} } \begin{bmatrix} 1 & 1 & 1 & \cdots & 1\\ 1 & \omega^{1} & \omega^{2} & \cdots & \omega^{n-1}\\ 1 & \omega^{2} & \omega^{4} & \cdots & \omega^{2(n-1)}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)^2} \end{bmatrix} \]

其中\(\omega =e^{i\frac{ 2\pi }{ n } }\)

一种递推关系：

\[ F_{2n}=\begin{bmatrix} 1 & & & & 1 & & & \\ & 1 & & & & \omega & & \\ & & \ddots & & & & \ddots & \\ & & & 1 & & & &\omega^{n-1} \\ 1 & & & & -1 & & & \\ & 1 & & & & -\omega & & \\ & & \ddots & & & & \ddots & \\ & & & 1 & & & &-\omega^{n-1} \end{bmatrix}\begin{bmatrix} F_n & \\ & F_n \end{bmatrix}\begin{bmatrix} 1 & 0 & & & & & & & &\\ & & 1 & 0 & & & & & &\\ & & & & 1 & 0 & & & &\\ & & & & & &\ddots & \ddots & & \\ & & & & & & & & 1 &0\\ 0 & 1 & & & & & & & & \\ & & 0 & 1 & & & & & & \\ & & & & 0 & 1 & & & &\\ & & & & & & \ddots & \ddots & &\\ & & & & & & & & 0 & 1 \end{bmatrix} \]

Haar矩阵

\[ H_8=\begin{bmatrix} 1 & 1 & 1 & & 1 & & & \\ 1 & 1 & 1 & & -1 & & & \\ 1 & 1 & -1 & & & 1 & & \\ 1 & 1 & -1 & & & -1 & & \\ 1 & -1 & & 1 & & & 1 & \\ 1 & -1 & & 1 & & & -1 & \\ 1 & -1 & & -1 & & & & 1 \\ 1 & -1 & & -1 & & & & -1 \end{bmatrix} \]

每列为Haar小波变换的基，可用于图像压缩

在图像压缩上，性能（计算速度、最少需要的基底数）较优

Schur补

对于 \[ M=\begin{bmatrix} A & B\\ D & C \end{bmatrix} \]

则\(A\)的Schur补为\(M/A=C-DA^{-1}B\)，\(C\)的Schur补为\(M/C=A-BC^{-1} D\)

\(M\succ 0\)与下面两个命题等价：

\(A\)及其Schur补正定：\(A\succ 0,M/A\succ0\)
\(C\)及其Schur补正定：\(C\succ 0,M/C\succ0\)

基于这个定理，可以有如下骚操作：（在鲁棒控制中出现过，证明时滞鲁棒控制器的Lyapunov函数导数负定时连用4次这玩意）

要使得\(\lambda A^{\mathrm{T}} A+P\prec 0\)，只需要

\[ \begin{pmatrix} P & A^{\mathrm{T}} \\ A & -\frac{ 1 }{ \lambda } I \end{pmatrix}\prec 0 \] 即可

还有在证明里经常用的《打洞技巧》：

就是用det为1的矩阵，把原矩阵操作出一个分块后的三角矩阵。

Hessenberg矩阵

下面部分，除了第一副对角线外都为0：

\[ H=\begin{bmatrix} \times & \times & \times & \times & \times\\ \times & \ddots & \ddots & \ddots & \times\\ & \ddots & \ddots & \ddots & \times\\ & & \ddots & \ddots & \times\\ & & & \times & \times \end{bmatrix} \]

~~生化危机8直呼内行（~~

三对角阵 Tridiagonal Matrix

\[ \begin{bmatrix} \times & \times & & & \\ \times & \ddots & \ddots & & \\ & \ddots & \ddots & \ddots & \\ & & \ddots & \ddots & \times\\ & & & \times & \times \end{bmatrix} \] 也可以看作对称的Hessenberg矩阵

双对角阵 Bidiagonal Matrix

\[ \begin{bmatrix} \times & & & & \\ \times & \ddots & & & \\ & \ddots & \ddots & & \\ & & \ddots & \ddots & \\ & & & \times & \times \end{bmatrix} \]

Hilbert矩阵

Hilbert矩阵是一类典型的病态矩阵（aka 低-数值秩矩阵） \[ H_{i,j}=\frac{ 1 }{ i+j-1 } \]

1000阶的Hilber矩阵的秩为\(\mathrm{rank}(H_{1000})=1000\)，但其在容差\(\varepsilon =10^{-15}\)下的数值秩为\(\mathrm{rank}_{10^{-15}}(H_{1000})=28\)

Vandermonde矩阵

Vandermonde矩阵也是一类典型的病态矩阵，因为随着阶数的增大，数值的差异也会爆炸式增大 \[ \begin{bmatrix} 1 & x_1 & x_1^2& \cdots & x_1^{n-1}\\ 1 & x_2 & x_2^2& \cdots & x_2^{n-1}\\ \vdots & \vdots & \ddots & \vdots&\\ 1 & x_m & x_m^2 & \cdots & x_m^{n-1} \end{bmatrix} \]

梯度与Hessian矩阵

这俩都是针对以向量为变量的标量函数描述的

梯度

\[ \nabla f^{\mathrm{T}} =\frac{\partial f }{\partial x }= \begin{bmatrix} \frac{\partial f }{\partial x_1 } & \cdots & \frac{\partial f }{\partial x_n } \end{bmatrix} \]

Hessian矩阵

\[ H=\frac{\partial ^2f }{\partial x^{\mathrm{T}} \partial x } =\begin{bmatrix} \frac{\partial^2 f }{\partial x_1 \partial x_1 } & \cdots & \frac{\partial^2 f }{\partial x_n \partial x_1 }\\ \vdots & \ddots & \vdots\\ \frac{\partial^2 f }{\partial x_1 \partial x_n } & \cdots & \frac{\partial^2 f }{\partial x_n \partial x_n } \end{bmatrix} \]

Jacobian矩阵

\(f\)是从向量到向量的函数

\[ \frac{\partial f }{\partial x } = \begin{bmatrix} \frac{\partial f_1 }{\partial x_1 } & \cdots & \frac{\partial f_1 }{\partial x_n }\\ \vdots & \ddots & \vdots\\ \frac{\partial f_m }{\partial x_1 } & \cdots & \frac{\partial f_m }{\partial x_n } \end{bmatrix} \]

时变矩阵A(t)及其导数

逆矩阵的导数用\(\frac{ \mathrm{d}A }{ \mathrm{d}t }\)表示：

特征值的导数用\(\frac{ \mathrm{d}A }{ \mathrm{d}t }\)表示：

矩阵的二次幂的导数用\(\frac{ \mathrm{d}A }{ \mathrm{d}t }\)表示： \[ \frac{ \mathrm{d}A^2 }{ \mathrm{d}t } =A\frac{ \mathrm{d}A }{ \mathrm{d}t }+\frac{ \mathrm{d}A }{ \mathrm{d}t } A \]

奇异值的导数用\(\frac{ \mathrm{d}A }{ \mathrm{d}t }\)表示：

\[ \frac{ \mathrm{d}\sigma }{ \mathrm{d}t } =u^{\mathrm{T}} \frac{ \mathrm{d}A}{ \mathrm{d}t}v \]

其他一些奇奇怪怪的东西详见The Matrix Cookbook

循环矩阵 Circulant Matrix (aka 循环卷积矩阵 Cyclic Convolution Matrix)

\[ C_n=\sum_{ k=0 }^{ n-1 } c_kP^k \] 其中\(P\)为轮换矩阵。其实循环矩阵是一种特殊的Toeplitz矩阵。

反正就是每个对角线上的元素相同，比如

\[ C_4=\begin{bmatrix} 2 & 5 & 1 &0 \\ 0 &2 &5 &1 \\ 1 & 0 &2 &5\\ 5 & 1 &0 &2 \end{bmatrix} \]

对于卷积运算：

\[ (3,1,2)*(4,6,1) \] 可以借助

\[ (3+x+2x^2)(4+6x+x^2)=12+22x+17x^2+13x^3+2x^4 \] 来得到

\[ (3,1,2)*(4,6,1)=(12,22,17,13,2) \] 循环卷积则将结果大小降回原大小（二者最大的元素数）：

\[ (3,1,2)\circledast (4,6,1)=(12+13,22+2,17)=(25,24,17) \]

该操作可以使用循环矩阵来描述：

\[ c\circledast v=Cv \]

Toeplitz矩阵

Toeplitz矩阵 aka Linear Shift Invariant, Linear Time Invariant, Convolution Matrix, Constant Diagonal Matrix

在滤波器使用较多，如池化层。

\[ T=\begin{bmatrix} t_0 &t_1 &t_2 & \cdots &t_{n-1} \\ t_{-1} & t_0 & t_1 & \ddots & \vdots\\ t_{-2} & t_{-1} & t_0 & \ddots &t_2 \\ \vdots & \ddots & \ddots & \ddots & t_1\\ t_{-(m-1)} & \cdots & t_{-2} & t_{-1} &t_0 \end{bmatrix} \] 在MATLAB中，可以用toeplitz(col,row)生成，其中col为第一个列向量的数组，row为第一个行向量的数组。

Toeplitz矩阵可以用于表示卷积，即\(Tv=t*v\)。写了个MATLAB实现如下。

% convolution p1 and p2 via Toeplitz Matrix
% input#1: n-th polymonial 1 in an array
% input#2: m-th polymonial 2 in an array
% output#1: (m+n)-th polynomial in an column array
function res = conv_toeplitz(p1,p2)
% ensure theyre column vectors
if size(p1,1) == 1
	p1 = p1.';
end
if size(p2,1) == 1
	p2 = p2.';
end
% derive Toeplitz Matrix
m = length(p2) - 1;
p1_conv = toeplitz([p1;zeros(m,1)], [p1(1);zeros(m,1)]);
% do the convolution
res = p1_conv * p2;
end

注意，这样写是支持符号运算的，比如要求一个优化问题：

\[\min \| (1,2,-1)*(a_1,a_2)-(1,2,3,4)\| _2\] 可以直接这样求解：

>> syms a [2 1]
>> f = conv_toeplitz([1 2 -1].',a) - [1 2 3 4].';
>> solve(gradient(f.'*f))

ans = 

  包含以下字段的 struct:

    a1: 1/3
    a2: 2/3

方程

Sylvester方程

对于正规矩阵（Normal Matrices）\(A,B\)，即\(A^{\mathrm{H}} A=AA^{\mathrm{H}} ,B^{\mathrm{H}} B=BB^{\mathrm{H}}\)且\(\forall i,j\Longrightarrow \lambda_i(A)\ne \lambda_j(B)\)，满足下式

\[AX-XB=C\]

Sylvester方程以及下面的Lyapunov方程在控制理论里经常用到。

Lyapunov方程

若\(B=-A^{\mathrm{H}}\)，则方程

\[ AX+XA^{\mathrm{H}} =C \]

为Lyapunov方程。

Lyapunov微分方程的一个特例

\[ \dot{X}=A^{\mathrm{T}} X+XA \]

若\(X(0)\in \mathcal{S}^n_{++}\)，则\(X(t)=e^{tA^{\mathrm{T}} }X(0)e^{tA}\)。

其中\(\mathcal{S}^n_{++}\)表示\(n\)阶正定对称矩阵空间。

这玩意在Lyapunov稳定性的判据中的证明有用到。也与线性时变系统的求解有关。

应用

对于一个线性时不变系统\(\dot{x}=Ax\)而言，若系统是渐进稳定的，则

\[ \forall Q\in \mathcal{S}^n_{++} ,\ \exists!\ P\in \mathcal{S}^n_{++} \Longrightarrow A^{\mathrm{T}} P+PA=-Q \]

对于一个线性时变系统\(\dot{x}=A(t)x\)而言，若系统是渐进稳定的，则

\[ \forall Q(t)\in \mathcal{S}^n_{++} ,\ \exists!\ P(t)\in \mathcal{S}^n_{++} \Longrightarrow A^{\mathrm{T}} P+PA=-Q-\dot{P} \]

其中要求\(Q(t),P(t)\)是一致正定的，即其正定性与\(t\)无关

Riccati矩阵方程

Riccati矩阵微分方程

对于给定\(Q,P(t)\in \mathcal{S}^n_{+},R\in \mathcal{S}^m_{++}\)

\[ -\dot{P}(t)=A^{\mathrm{T}} P(t)+P(t)A+Q-P(t)BR^{-1} B^{\mathrm{T}} P(t) \]

这玩意的一个应用就是最优控制中的线性二次型调节器（Linear Quadratic Regulator）：

给定\(\dot{x}=Ax+Bu\)，其中\(x(t_0)=x_0\)，对于给定\(S,Q\in \mathcal{S}^n_{+},R\in \mathcal{S}^m_{++}\)，求最优控制\(u^*(t)\)使得 \[ \min J=\frac{ 1 }{ 2 }x^{\mathrm{T}}(t_2)Sx(t_2)+\frac{ 1 }{ 2 }\int_{t_1}^{t_2}x^{\mathrm{T}} (t)Qx(t)\mathrm{d}t+\frac{ 1 }{ 2 }\int_{t_1}^{t_2}u^{\mathrm{T}} (t)Ru(t)\mathrm{d}t \] 直观理解为，第一项为终值误差，第二项为误差的累计，第三项为控制能量。

若解得\(P(t)\)，则\(u^*(t)=R^{-1} B^{\mathrm{T}} P(t)x(t)\)

且此时

\[ \dot{x}^*(t)=(A-BR^{-1} B^{\mathrm{T}} P(t))x^*(t) \]

\[ J^*=\frac{ 1 }{ 2 }x^{\mathrm{T}} (t_0)P(t_0)x(t_0) \]

Riccati矩阵代数方程

对于给定\(Q,P\in \mathcal{S}^n_{+},R\in \mathcal{S}^m_{++}\)， \[ PA+A^{\mathrm{T}} P+Q-PBR^{-1} B^{\mathrm{T}} P=0 \]

应用为无限时间LQR：

给定\(\dot{x}=Ax+Bu\)，其中\(x(t_0)=x_0\)，对于给定\(Q\in \mathcal{S}^n_{+},R\in \mathcal{S}^m_{++}\)，求最优控制\(u^*(t)\)使得Riccati矩阵代数方程成立。

若解得\(P\)，则\(u^*(t)=R^{-1} B^{\mathrm{T}} Px(t)\)

且此时

\[ \dot{x}^*(t)=(A-BR^{-1} B^{\mathrm{T}} P)x^*(t) \]

\[ J^*=\frac{ 1 }{ 2 }x^{\mathrm{T}} (t_0)Px(t_0) \]

MATLAB有函数可以用于求解：ICARE。

Euler方程

\[ \frac{ \partial L }{ \partial x } -\frac{ \mathrm{d} }{ \mathrm{d}t }\frac{ \mathrm{d}L }{ \mathrm{d}\dot{x} } =0 \] 在Lagrange力学中，令Lagrange函数为动能与广义力势能的差\(\mathcal{L}=\mathcal{K}-\mathcal{P}\)，\(x\)为广义坐标\(q_j,j=1,\cdots,s\)，方程称为Euler-Lagrange方程（的特殊形式）。注意此式仅在理想体系（约束力不做功）且保守体系（机械能守恒）且\(\frac{\partial \mathcal{P} }{\partial \dot{q}_j }=0\)时成立。

这玩意是这样推导的：

假设一个优化泛函为

\[ J[x(t)]=\int_{t_1}^{t_2}L\left[ x(t),\dot{x}(t),t \right] \mathrm{d}t \] 其中\(L\)二阶可微，\(x\)的端点固定，即\(x(t_1)=x_1,x(t_2)=x_2\)，从而\(\delta x(t_1)=0,\delta x(t_2)=0\)

令\(\delta J=0\)，则

\[ \int_{t_1}^{t_2}\left( \frac{\partial L }{\partial x } \delta x - \frac{\partial L }{\partial \dot{x} } \delta \dot{x} \right)\mathrm{d}t=0 \] 分部积分，得 \[ \frac{\partial L }{\partial \dot{x} } \left( \delta x(t_2)-\delta x(t_1) \right) +\int_{t_1}^{t_2}\left( \frac{\partial L }{\partial x } -\frac{\mathrm{d} }{\mathrm{d} t} \frac{\partial L }{\partial \dot{x} } \right)\delta x \mathrm{d}t=0 \] 从而 \[ \int_{t_1}^{t_2}\left( \frac{\partial L }{\partial x } -\frac{\mathrm{d} }{\mathrm{d} t} \frac{\partial L }{\partial \dot{x} } \right)\delta x \mathrm{d}t=0 \] 引理：若\(F(t)\)在\([t_1,t_2]\)上连续，且对\(\forall \eta(t)\)有\(\int_{t_1}^{t_2}F(t)\eta(t)\mathrm{d}t=0\)，则\(F(t)=0\)。因此 \[ \frac{\partial L }{\partial x } -\frac{\mathrm{d} }{\mathrm{d} t} \frac{\partial L }{\partial \dot{x} } =0 \]

如果条件中，\(x_1,x_2\)不固定，则可以用横截条件平替：

\[ \frac{\partial L }{\partial \dot{x} }|_{t_1}=0,\frac{\partial L }{\partial \dot{x} }|_{t_2}=0 \]

~~话说这玩意和线代有半毛钱关系吗，这不是泛函吗（写完才发现（（~~

正交Procrustes问题

\[ \underset{ \Omega }{\mathrm{min}}\ {\left\| \Omega A-B \right\|_\mathrm{F} } \]

\[ \mathrm{s.t.}\ \ \Omega ^{\mathrm{T}} \Omega =I \]

其解为 \[ R=\underset{ \Omega }{\mathrm{argmin}}\ { \left\| \Omega A-B \right\|_\mathrm{F} }=UV^{\mathrm{T}} \]

其中\(U,V\)来自矩阵\(BA^{\mathrm{T}}\)的奇异值分解\(BA^{\mathrm{T}} =U\Sigma V^{\mathrm{T}}\)

证明：

定理与归纳

六度空间理论 Number Six Degrees of Separation

可以用图论建模，从而用矩阵表示图。

据说又是个猜想，不是很懂.jpg

Eckart-Young定理

\[ \min \left \| A-B \right \| = \left \| A-A_k \right \| \]

其中 \[ A_k=\sum_{ k=1 }^{ \mathrm{rank}(B) } u_k\sigma_k v_k^{\mathrm{T}} \] \(A_k\)也是对\(A\)的低阶近似

对\(\ell_2\)范数、Frobenius范数成立

Kalley-Hamilton定理

对于任意方阵\(A\in \mathbb{R}^{n\times n}\)，矩阵的e指数均可表示为

\[ e^{At}=c_0(t)I+c_1(t)A+\cdots+a_{n-1}(t)A^{n-1} \]

该定理可通过特征多项式证明：

\[ \mathrm{det}\left( \lambda I-A \right)=p_0+p_1\lambda +\cdots+p_{n-1}\lambda^{n-1}+\lambda^n =0 \] 从而有（我也不知道具体咋来的，可以致电Kalley或Hamilton咨询）

\[ A^n+p_{n-1}A^{n-1}+\cdots+a_1A+a_0I=0 \] 方程乘个\(A\)可以得到\(A^{n+1}\)的线性组合

反复如此操作，\(A\)的任意幂都可以表示为\(I,A,\cdots,A^{n-1}\)的线性组合。

矩阵反演公式 Matrix Inversion Formula

用\(I\)做扰动（perturbation），对秩1矩阵有 \[ \left( I-uv^{\mathrm{T}} \right)^{-1} =I+\frac{ uv^{\mathrm{T}} }{ 1-v^{\mathrm{T}} u } \]

用\(I\)做扰动（perturbation），对\(\mathrm{rank}(U^{\mathrm{T}} V)=k\)有 \[ (I-UV^{\mathrm{T}} )^{-1} =I+U(I_k-V^{\mathrm{T}} U)^{-1} V^{\mathrm{T}} \]

Sherman-Morrison-Woodbury公式

用可逆矩阵\(A\)做扰动，对\(\mathrm{rank}(U^{\mathrm{T}} V)=k\)有 \[ \left( A-UV^{\mathrm{T}} \right)^{-1} =A^{-1} +A^{-1} U(I_k-V^{\mathrm{T}}A^{-1} U) ^{-1} V^{\mathrm{T}} A^{-1} \] 证明方法：级数展开再展回去（话说那岂不是得限定\(A\)的最大奇异值小于1）

应用1

已知\(A,b,w\)使得\(Aw=b\)，求\((A-uv^{\mathrm{T}} )x=b\)的解：

先求解\(Az=u\)，可以通过\(A[w,z]=[b,u]\)求解；

再代入 \[ x=w+\frac{ wv^{\mathrm{T}} z }{ 1-v^{\mathrm{T}} z } \]

应用2：递归最小二乘

已知\(\hat{x}\)使得标准方程（normal equation） \[ A^{\mathrm{T}} A\hat{x}=A^{\mathrm{T}} b \] 成立

现测得新数据\(v^{\mathrm{T}} ,b_{\mathrm{new}}\)满足 \[ \begin{bmatrix} A \\ v^{\mathrm{T}}\\ \end{bmatrix}x=\begin{bmatrix} b \\ b_{\mathrm{new}}\\ \end{bmatrix} \] 于是就愉快地得到了新标准方程 \[ \begin{bmatrix} A^{\mathrm{T}} & v\\ \end{bmatrix}\begin{bmatrix} A \\ v^{\mathrm{T}}\\ \end{bmatrix}\hat{x}_{\mathrm{new}}=\begin{bmatrix} A^{\mathrm{T}} & v\\ \end{bmatrix}\begin{bmatrix} b \\ b_{\mathrm{new}}\\ \end{bmatrix} \] 这玩意如果再引入：

协方差矩阵（实现“加权”）
状态空间方程（实现“动态”）

那就是Kalman滤波了

状态空间方程（State Space Equations）是用于描述这样一个系统的线性方程组：对于输入u，输出y，状态变量x，有： \[ \left\{\begin{matrix} \dot{x}=Ax+Bu \\ y=Cx+Du \end{matrix}\right. \]

交错理论 Interlacing Theorem

设实对称矩阵\(S\)的特征值为\(\lambda_1\ge \cdots\ge \lambda_n\)，矩阵\((S+uu^{\mathrm{T}} )\)的特征值为\(\gamma_1\ge \cdots \gamma_n\)，则

\[ \gamma_1\ge \lambda_1\ge\gamma_2\ge\lambda _2\ge\cdots\gamma_n\ge \lambda_n \]

Weyl不等式

\[ \lambda _{i+j-1}(S_1+S_2)\le \lambda_i(S_1)+\lambda_j(S_2) \]

世界是平滑的 World is Smooth

大多矩阵都是低-数值秩矩阵

世界是Sylvester的 World is Sylvester

大多矩阵满足Sylvester方程，从而是低-数值秩矩阵

二次规划的拉格朗日乘子法的矩阵表示

\[ \min{\frac{ 1 }{ 2 } x^{\mathrm{T}} Sx },\ \ \ \ \mathrm{s.t.}\ Ax=b \] 其中\(S\succ 0\)

则拉格朗日函数（Lagrangium）为

\[ L(x;\lambda)=\frac{ 1 }{ 2 } x^{\mathrm{T}} Sx-\lambda^{\mathrm{T}} (Ax-b) \] 令偏导数为0：

\[ \left\{\begin{matrix} \frac{\partial L }{\partial x } = Sx-A^{\mathrm{T}} \lambda \\ \frac{\partial L }{\partial \lambda } = -Ax+b \end{matrix}\right. \]

从而矩阵表达为

\[ \begin{bmatrix} S & A^{\mathrm{T}} \\ A &O \end{bmatrix}\begin{bmatrix} x \\ -\lambda \end{bmatrix}=\begin{bmatrix} 0 \\ b \end{bmatrix} \]

线性规划与对偶

\[ \min{f=c^{\mathrm{T}} x},\ \ \ \ \mathrm{s.t.}\ \left\{\begin{matrix} Ax=b \\ x\succeq 0 \end{matrix}\right. \] 目前主流的两种解法：

单纯形法（Simplex Method），由Dantzig提出，从角点入手
内点法（Interior Points Method），由Karmarkar提出，从内部点入手

该问题的对偶问题为

\[ \max{b^{\mathrm{T}} y}\ \ \ \ \mathrm{s.t.}\ A^{\mathrm{T}} y\preceq 0 \] 弱对偶：\(b^{\mathrm{T}} y\le c^{\mathrm{T}} x\)

对偶（强对偶）：\(b^{\mathrm{T}} \underset{ y }{\mathrm{argmax}}\ { \{b^{\mathrm{T}} y \}}=c^{\mathrm{T}} \underset{ x }{\mathrm{argmin}}\ { \{c^{\mathrm{T}} x \}}\)