线性代数

Uh-oh.

也就是说，只要多写写公式你的水平自然会提升。——离散小波变换°

矩阵和线性方程组

矩阵是什么。嘴巴嘴巴嘴巴

一个线性方程组可以被描述成 $A\boldsymbol x=\boldsymbol b$ 的形式。

可以利用高斯约旦消元法解，时间复杂度是 $O(n^3)$。

线性空间

定义线性空间 $V$ 是域 $F$ 上的一个子空间，元素 $\alpha$ 和 $\beta$ 满足：

• $\alpha+\beta\in V$，有 $e$，$\mathrm{inv}$，交换律，结合律。
• 乘法：
  • $1\cdot \alpha=\alpha$。
  • $c_1\cdot c_2\alpha=(c_1c_2)\alpha,c(\alpha+\beta)=c\alpha+c\beta,(c_1+c_2)\alpha=c_1\alpha+c_2\alpha$
  • 为什么没写交换律。因为可能没有交换律。

线性组合：若存在一组 $c_1,c_2,\dots,c_n$ 满足 $\beta=\sum\limits_{i=1}^nc_i\alpha_i$，则称 $\beta$ 是 $\alpha_i$ 的线性组合。

线性不相关：一组元素 $\alpha_1,\alpha_2,\dots,\alpha_n$ 每个元素都不能表示成其他元素的线性组合。或者另一个定义是方程 $\boldsymbol c\boldsymbol {\alpha}=\boldsymbol 0$ 的唯一解是 $\boldsymbol c=\boldsymbol 0$。

基：张成 $V$ 的一组线性不相关向量 $(\alpha_1,\alpha_2,\dots,\alpha_n)$。并且记 $\dim(V)=n$。

“张成” $V$ 的定义：要求 $\forall\boldsymbol\beta\in V$，都有一组 $\boldsymbol c=(c_1,c_2,\dots,c_n)$ 使得 $\boldsymbol c\boldsymbol {\alpha}=\boldsymbol \beta$。

线性变换

标准定义

称一个函数 $T:V\rightarrow W$ 为 $V$ 到 $W$ 的线性变换当且仅当这东西有线性性。

即，$c\cdot T(\boldsymbol\alpha)+\boldsymbol \beta=T(c\boldsymbol\alpha+\boldsymbol\beta)$。

事实上这个映射可以写成矩阵的形式，就是说 $n$ 维空间到 $m$ 维空间就乘上一个 $n\times m$ 的矩阵。

设 $\mathcal B_1=(\boldsymbol\alpha_1,\boldsymbol\alpha_2,\dots,\boldsymbol\alpha_n)$ 为 $V$ 的一组基，$\mathcal B_2=(\boldsymbol\beta_1,\boldsymbol\beta_2,\dots,\boldsymbol\beta_m)$ 为 $W$ 的一组基。

那么 $T$ 的结果可以完全被 $(T\boldsymbol\alpha_i),i\in[1,n]$ 表示，而每个 $T\boldsymbol\alpha_i$ 又可以被 $\mathcal B_2$ 唯一表示。不妨设

$$T\boldsymbol\alpha_i=\sum_{j=1}^mA_{ij}\boldsymbol\beta_j$$

那么就称 $A_{ij}$ 为 $T$ 的矩阵表示。容易发现 $A$ 是 $n\times m$ 的矩阵。

线性变换是可以复合的，就像函数复合一样。而对于同一组基，复合的结果就是将两个矩阵乘起来。

行列式

针对矩阵的运算，称 $\det(A)$ 为矩阵 $A$ 的行列式。记作：

$$\det(A)= \begin{vmatrix} a_{11}&a_{12}&\cdots&a_{1n}\\ a_{21}&a_{22}&\cdots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}&a_{n2}&\cdots&a_{nn} \end{vmatrix} =\sum_{\substack{p_1,p_2,\cdots,p_n\\\{p_i\}\text{ is a permutation}}}(-1)^{\pi(p_1,p_2,\cdots,p_n)}\prod_{i=1}^na_{ip_i}$$

（后面这是什么鬼？）

定义 $\pi(p_1,p_2,\dots,p_n)$ 为 $(p_1,p_2,\dots,p_n)$ 的逆序对数。

特别的：

$$\begin{vmatrix} a&b\\ c&d \end{vmatrix} =ad-bc,\\ \begin{vmatrix} a_1&a_2&a_3\\ b_1&b_2&b_3\\ c_1&c_2&c_3 \end{vmatrix} =(a_1b_2c_3+a_2b_3c_1+a_3b_1c_2)-(a_1b_3c_2+a_2b_1c_3+a_3b_2c_1)$$

（这两个比较小，可以记住）

范德蒙矩阵行列式和循环矩阵行列式

$$\begin{vmatrix} 1&1&\cdots&1\\ x_1&x_2&\cdots&x_n\\ x_1^2&x_2^2&\cdots&x_n^2\\ \vdots&\vdots&\ddots&\vdots\\ x_1^n&x_2^n&\cdots&x_n^n \end{vmatrix} =\prod_{1\le j<i\le n}(x_i-x_j)$$ $$\begin{vmatrix} a_1&a_2&\cdots&a_n\\ a_n&a_{1}&\cdots&a_{n-1}\\ a_{n-1}&a_{n}&\cdots&a_{n-2}\\ \vdots&\vdots&\ddots&\vdots\\ a_2&a_3&\cdots&a_1 \end{vmatrix} =\prod_{i=1}^nf(\omega_i)$$

其中 $f(x)=\sum\limits_{i=0}^{n-1}a_{i+1}x^i$，$\omega_i^n=1,\omega_i\in\mathbf C$。

特征值、特征向量、特征多项式

这里只考虑方阵的情况，即 $A$ 是 $n$ 个向量向 $n$ 个向量的线性变换。

如果向量 $\boldsymbol x$ 满足 $A\boldsymbol x=\lambda\boldsymbol x$，则称 $\boldsymbol x$ 为 $A$ 的特征向量而 $\lambda$ 为 $A$ 的特征值。

注意到 $\lambda$ 实际上描述了一个方程 $(A-\lambda I)\boldsymbol x=\boldsymbol 0$，这样的方程的解 $\boldsymbol x$ 构成了一个线性空间，称这个空间为 $\lambda$ 对应的特征向量空间。

同时当 $\lambda=0$ 时这个空间为零空间（其实就是 $A\boldsymbol x=\boldsymbol b$ 的解向量空间），其维度记作 $\operatorname{null}(A)$。有性质

$$\operatorname{null}(A)+\operatorname{rank}(A)=\dim(A)$$

其中 $\operatorname{rank}(A)$ 称为矩阵的秩。

（大概就是矩阵对应的那个方程组有多少个线性不相关的方程）

如何解特征值

我们发现 $\det(A-\lambda I)=0$。因此我们将 $\det(A-\lambda I)$ 看做关于 $\lambda$ 的 $n$ 次多项式，这个多项式的根就是全体特征值。这个多项式也被称为特征多项式。

Matrix-Tree 定理

定义一个图的基尔霍夫矩阵为 $K=D-A$，其中 $D$ 是度数矩阵，$A$ 是邻接矩阵。

任意去掉 $i$ 行 $j$ 列，剩余矩阵的 $\det$ 就是生成树的个数。