去**的线性代数

粘一段 oi-wiki 上对线代的描述：

线性代数源于人们的观察。人们发现，很多对象都拥有相似的性质，比如：

• 力可以被分解、合成。

• 对于任意的 \(k,x_0，k \sin (x-x_0)\) 可以分解成 \(k_1\sin x + k_2\cos x\)。

这些性质与所描述对象的 缩放、分解、叠加 等有关。线性代数把这些性质从具体对象中抽象出来，作为一个独立的学科来研究。

由此可见，线代是一个历史悠久，用处很大的数学分支。

这里略过一些线代中的基础定义。

先从线代最初的作用：解方程说起。假设我们有如下的一个方程组：

如果我们用矩阵和向量来描述方程组中的参数和未知数，可以得到：

\(A\times \vec x=\vec b\)，其中 \(\vec x\) 和 \(\vec b\) 是两个列向量，分别存储了所有的 \(x\) 和 \(b\)。

考虑只记录 \(A\) 和 \(\vec b\)，我们考虑平时消元的过程：依次处理所有的未知数 \(x_i\)，找到一个含有 \(x_i\) 的方程，将这个方程的若干倍加到其他的方程上从而消去其他方程中的 \(x_i\) 项，直到所有方程都呈现 \(ax=b\) 的形式。我们称其为 高斯-约旦消元（如果每次只消去后面的方程中的 \(x_i\)，解出一个 \(x\) 后再依次回代的叫高斯消元）。

其中将方程的若干倍加到其他方程上的一步是整个算法变化最多的一步：

• 如果方程组在实数域内就直接用实数除法。
• 如果方程组定义在模质数意义下就用逆元。
• 如果方程组定义在模任意自然数意义下考虑对于两个方程辗转相除，将某一个方程的这一项消到 0。
• 如果方程定义在模 2 意义下考虑用 bitset 优化此过程。

一般情况下复杂度为 \(O(n^3)\)。处理特殊矩阵时会有更优秀的复杂度。

我们都知道如果一组向量无法相互表示那它们就是线性无关的，而一组向量的极大线性无关子集就成为这组向量的线性基。

考虑如何求解线性基，每次插入一个向量时从它的最高位开始考虑，如果现在它的最高位 \(p\) 没有对应的向量 \(b_p\)，就将其插入，否则用 \(b_p\) 将给向量的 \(p\) 位置给消去。当向量被消为 0 时就表明现在线性基中的向量可以表示该向量，无法插入。

我们称一个向量组的线性基的大小为该向量组的秩，或是维数。

对于一个矩阵，如果我们将其看为将若干个行向量堆叠在一起，这这些行向量的秩称为矩阵的行秩。同样的定义有矩阵的列秩。同时我们有对于任意矩阵，行秩等于列秩，证明略。

行秩和列秩统称为矩阵的秩，记为 \(\operatorname{rank} A\)。

对于一个方阵 \(A_{n,n}\)，定义方阵的行列式 \(\det A=\sum\limits_{p_{1,n}}(-1)^{\sigma(p)}\prod\limits_{i=1}^nA_{i,p_i}\)，其中 \(\sigma(p)\) 表示排列 \(p\) 的逆序对数。

或者行列式还可以由 Laplace 展开式计算： \(\det A=\sum_{i=1}^n(-1)^{1+i}A_{1,i}\times \det M_{1,i}\)，其中 \(M_{i,j}\) 表示原方阵 \(A\) 中删去第 \(i\) 行和第 \(j\) 列后剩余的子矩阵，称为余子阵，\(\det M_{i,j}\) 被称为余子式。

这告诉我们一个三角矩阵的行列式值等于其对角线上所有元素的乘积。

矩阵的行列式有如下几条重要的性质：

• 如果将矩阵 \(A\) 的某一行或某一列整体乘上一个常数 \(c\)，则 \(\det A'=c\cdot\det A\)。
• 如果矩阵 \(A\) 和矩阵 \(B,C\) 满足 \(A\) 的某一行或某一列是 \(B\) 和 \(C\) 对应的行或列的和，矩阵中的其他位置分别相等，则有 \(\det A=\det B+\det C\)。
• 交换矩阵 \(A\) 的某两行或某两列的位置，矩阵的行列式值取反。

结合之前的三角矩阵行列式值，我们可以回想高斯消元的过程，发现消元的结果就是一个三角矩阵，也就是我们可以在 \(O(n^3)\) 的复杂度内求出行列式的值。

同时，如果一个矩阵的行列式值不为 0，一个充要条件是该矩阵满秩。证明显然。

Cauchy-binet formula，柯西比内公式的内容如下：对于两个矩阵 \(U_{n\times m}\) 和 \(V_{m\times n}\)，其乘积的行列式 \(\det (U\times V)=\sum\limits_{S=\binom{[m]}n}\det U_{[n],S}\times \det V_{S,[n]}\)。表示对于 1 到 \(m\) 中每一个大小为 \(n\) 的子集，然后将 \(U,V\) 中对应的 \(n\) 阶子矩阵的行列式的乘积求和。

显然如果 \(n>m\) 积的行列式为 0（因为两矩阵乘积的秩不超过这两个矩阵的秩，所有乘积矩阵明显不是满秩的）。

该公式可以算一些神秘的组合意义题。鬼知道能不能用上。

Matrix Determinant Lemma，矩阵行列式引理表示为：

证明如下：

考虑块矩阵乘法，\(\begin{pmatrix}I_n&\\V&I_m\end{pmatrix}\begin{pmatrix}I_n+UV&U\\&I_m\end{pmatrix}\begin{pmatrix}I_n&\\-V&I_m\end{pmatrix}=\begin{pmatrix}I_n&U\\&I_m+VU\end{pmatrix}\)

由于上式所有矩阵都是三角矩阵，因此有 \(1\times|I_n+UV|\times1=|I_m+VU|\)。

另外此引理还有推广形式：对于一个 \(n\) 阶可逆方阵 \(A\)，有 \(|A+UV|=|A|\cdot|I_n+(A^{-1}U)V|=|A|\cdot|I_m+VA^{-1}U|\)。