线性代数是个有趣的东西。
过于基础的定义（例如矩阵运算等）不会提及。
I.基于行变换的线性代数
I.I.高斯消元、行变换与线性方程组
高斯消元是一切线代科技的基础。
高斯消元，是指通过以下三种变换：
- 倍加变换，即将一行的一定倍数加到另一行上
- 对换变换，即交换两行
- 倍乘变化，即将某一行中所有数同乘以某一非零数
可以证明，通过且仅通过如上三种变化，可以将任意矩阵，变换成如下形式的矩阵：
\[\begin{bmatrix}?,?,?,?,\dots,?\\0,?,?,?,\dots,?\\0,0,0,?,\dots,?\\\dots\\0,0,\dots,0,0,?\end{bmatrix} \]即，从上到下，每一行的开头都有着一定数量的 \(0\)，且该 \(0\) 的数量单调递增（当然，最后可能会有很多零行，即元素全部为 \(0\) 的行，此时并不要求零的数量单调递增）。
我们称这种矩阵为上三角矩阵，因为其非零元素仅集中于右上方的三角内。我们有时也将其称作阶梯型矩阵。
同理我们可以定义下三角矩阵，是非零元素仅集中于左下方的三角内的矩阵。
高斯消元又被称作行变换。
高斯消元可以被用于求解多元一次方程组。例如，对于一有 \(n\) 个方程，\(m\) 个变量的方程组
\[\begin{cases}a_{1,1}x_1+a_{1,2}x_2+\dots+a_{1,m}x_m=k_1\\\dots\\a_{n,1}x_1+a_{n,2}x_2+\dots+a_{n,m}x_m=k_n\end{cases} \]定义其增广矩阵 \(A\) 为
\[\begin{bmatrix}a_{1,1},a_{1,2},\dots,a_{1,m},k_1\\\dots\\a_{n,1},a_{n,2},\dots,a_{n,m},k_n\end{bmatrix} \]其是一 \(n\) 行 \(m+1\) 列矩阵。
对其行变换，则我们可以得到一上三角矩阵。则：
- 若其中有一行，前 \(m\) 个数均为 \(0\)，但最后一个数非零，此线性方程组无解。
- 若其存在至少 \(m\) 行，其中前 \(m\) 个数中存在非零的数，则此线性方程组有唯一解。
- 否则，此线性方程组解非唯一，但是我们可以求出其解的一般形式。
一增广矩阵相容，当且仅当不存在情况一。
首先，可以先感性理解一下为何行变换可以用来求解线性方程组：这是因为明显高斯消元的三种操作对于一个线性方程来说仍然成立。
则如果我们发现前 \(m\) 个数均为零但最后一个数非零的行，将其还原成方程组的形式就是
\[0x_1+0x_2+0x_3+\dots+0x_m=k \]其等价于 \(0=k\)，而这显然是不可能成立的。
然后，我们接下来通过一个新的定义：简化阶梯型矩阵来证明上述二三条推论。
定义简化阶梯型矩阵是这样的矩阵：
每一行上先导的非零元素的数量递增（除了最后的零行以外）
每一非零行上第一个非零元素全是 \(1\)，且该 \(1\) 是此列上唯一非零元素。
示例如图。
\[\begin{bmatrix}1,0,?,0,0,?,\dots,0,?\\0,1,?,0,0,?,\dots,0,?\\0,0,0,1,0,?,\dots,0,?\\0,0,0,0,1,?,\dots,0,?\\0,0,0,0,0,0,\dots,0,?\\\dots\\0,0,0,0,0,0,\dots,1,?\end{bmatrix} \]可以被证明的是，一个矩阵所对应的阶梯型矩阵数量可能很多，但一个矩阵通过行化简所能得到的的简化阶梯型矩阵是唯一的。
则，第二条推论成立时所对应的矩阵，如果不考虑矩阵最下方的若干零行，一定是这样的
\[\begin{bmatrix}1,0,\dots,0,?\\0,1,\dots,0,?\\\dots\\0,0,\dots,1,?\end{bmatrix} \]将其复原成线性方程组的形式，就会发现它即为线性方程组的唯一解。
通过对阶梯型矩阵进一步化简（常被称作“Gauss-Jordan”消元），可以简单得到简化阶梯型矩阵。
定义一个矩阵的主元位置，是其所对应的简化阶梯型矩阵中所有上述 \(1\) 的位置。
定义一个矩阵的主元列，是其所有主元所在的列。
则，在一线性方程组中，其对应矩阵的所有主元列所对应的变量，被称作基本变量或主元，剩余的称作*变量或*元。
在一个线性方程组中，*元是可以任意取值的；但是，当所有*元的取值被唯一固定后，剩余主元的值也被唯一固定了。以某些*元的值来表示主元的值的式子，被称作线性方程组的通解。
可以发现，假如一个线性方程组不存在*元，则其有唯一解。
I.II.向量、向量方程、线性组合与生成空间
向量是只含一列的矩阵，即 \(n\times 1\) 的矩阵。所有有 \(n\) 行的向量集合被记作 \(\mathbb{R}^n\)。以下，用黑体 \(\mathbf{v}\) 来表示一向量。
一组向量 \(\mathbf{v}_1,\dots,\mathbf{v}_n\) 的线性组合，被定义为
\[\mathbf{u}=\sum\limits_{i=1}^nc_i\mathbf{v}_i \]该线性组合被称作以标量 \(\{c_i\}\) 为权的线性组合。
定义一组向量 \(\{\mathbf{v}_i\}\) 的生成空间，是其以任意一组 \(\{c\}\) 为权的线性组合的结果所构成的集合，可被记作 \(\text{Span}\{\mathbf{v}_i\}\)。
若要判断一向量 \(\mathbf{u}\) 是否在一个生成空间内（或者说其能否被线性组合表示出来），就等价于求解方程
\[\sum\limits_{i=1}^nc_i\mathbf{v}_i=\mathbf{u} \]是否有解。
其可由矩阵
\[[\mathbf{v}_1,\mathbf{v}_2,\dots,\mathbf{v}_n,\mathbf{u}] \]所对应的线性方程组是否有解来判定。
I.III.矩阵方程
矩阵方程指的是形如
\[A\mathbf{x}=\mathbf{b} \]的方程（当然，前提是该乘法能被定义）。
它可以被看作，\(A\) 的所有列向量以 \(\mathbf{x}\) 的元素为权的线性组合，也就是说，它等价于判定 \(\mathbf{b}\) 是否在 \(A\) 的列向量所生成的空间内，如果有则求出该线性组合的权。
I.IV.线性方程组的解
定义一线性方程组是齐次的，当且仅当其等价于矩阵方程 \(A\mathbf{x}=\mathbf{0}\)。
（该等价性可以由线性方程组与判定是否在生成空间内的等价性和生成空间与矩阵方程的等价性得到）
显然，任何齐次方程组都有平凡解 \(\mathbf{x}=\mathbf{0}\)。而其有非平凡解的充要条件是等价的矩阵方程存在*元。
一个齐次线性方程组的通解（被表示成了向量形式），可以由一些向量以其*元为权的线性组合被表示出来。也就是说，其解集是那些向量的生成空间。
可以发现，这些向量是与其对应的简化阶梯型矩阵的非主元列有很大关联的。
而一非齐次线性方程组的通解，是以*元为权的线性组合，再加上一个向量得到的。该通解被称作“参数向量形式”。
I.V.线性相关与线性无关
定义一组向量 \(\{\mathbf{v}_i\}\) 线性无关，若方程
\[\sum\limits_{i=1}^nc_i\mathbf{v}_i=\mathbf{0} \]仅有平凡解。
反之，其线性相关。
显然，一组向量组合线性无关等价于矩阵方程
\[[\mathbf{v}_1,\mathbf{v}_2,\dots,\mathbf{v}_n]\mathbf{x}=\mathbf{0} \]仅有平凡解，也即该矩阵存在*元。
可以发现，线性无关集中不存在任何向量是其它向量的线性组合。
II.基于方阵的线性代数
II.I.可逆矩阵
某个方阵 \(A\) 的逆 \(A^{-1}\) 是满足 \(AA^{-1}=I\) 的方阵。
逆矩阵的逆就是原矩阵。这意味着有 \(AA^{-1}=A^{-1}A=I\)。
一个方阵可逆，当且仅当其可被行化简成为单位矩阵 \(I\)。
此时，将行化简过程中使用的所有变换原封不动地顺次施加于单位矩阵 \(I\)，即可得到 \(A^{-1}\)。
若只需逆矩阵中某一行/列的数，只需在原矩阵中消完对应的行/列即可。复杂度可被优化到 \(n^2\)。
多个可逆方阵的积之逆，等于方阵之逆的倒序积。
II.II.行列式
通过行列式也可以判定一个方阵是否可逆。
行列式的定义是递归的。定义一个 \(1\times1\) 方阵 \(A\) 的行列式是其中唯一的元素。
否则，暂定义 \(A_{u,v}\) 为方阵 \(A\) 删去第 \(u\) 行和第 \(v\) 列后所得到的方阵。暂定义 \(a_{i,j}\) 为其第 \(i\) 行第 \(j\) 列的元素。
则其行列式 \(\det A=\sum\limits_{i=1}^n(-1)^{1+i}a_{1,i}\det A_{1,i}\)
我们也可定义 \(A\) 在位置 \((i,j)\) 的余因子 \(C_{i,j}=(-1)^{i+j}\det A_{i,j}\)
则我们可以得出 \(A\) 关于第一行的余因子展开式是
\[\det A=\sum\limits_{i=1}^na_{1,i}C_{1,i} \]可以被证明的是，方阵 \(A\) 关于任何一行和任何一列的余因子展开式均是相等的——都等于其行列式。
若按照其定义来计算行列式，我们将很容易得到此算法的复杂度是 \(O(n!)\) 的。
行列式可以通过行变换求出。
-
若对矩阵 \(A\) 施加倍加变换，则其行列式不变。
-
若对其施加对换变换，则其行列式取相反数。
-
若对其施加倍乘变换，则其行列式相应乘上扩大的倍数。
此性质可以通过所有变换所对应的矩阵的行列式简单得出。
行列式的性质之一是 \(\det A\times \det B=\det AB\)。
我们总是可以通过倍加和对换变换将一个矩阵消成上三角矩阵。可以被证明的是，一 \(n\times n\) 上三角矩阵的行列式，等于
\[\sum\limits_{i=1}^na_{i,i} \]因为一个矩阵可逆，当且仅当其可被消成单位矩阵 \(I\)，故其必恰有 \(n\) 个主元，则此主元应分布在对角线上。若对角线上元素中不全非零，则显然其不可逆。而此时其行列式也就为零。故行列式为零等价于矩阵不可逆。
上述上三角矩阵的行列式可以被 \(O(n)\) 简单计算。于是我们可以通过先将一矩阵消成上三角矩阵再求行列式来在 \(O(n^3)\) 时间内计算行列式。
计算几何中“叉积”的定义的实质是行列式。即，两个二维向量 \(\mathbf{u},\mathbf{v}\) 之叉积 \(\mathbf{u}\times\mathbf{v}\)，即是矩阵 \([\mathbf{u},\mathbf{v}]\) 之行列式。同理，三维向量乃至更高维向量的叉积也可经由行列式定义。
因为二维/三维叉积的集合意义是面积/体积，所以我们可以发现，若二维平面中由向量集合描述的图形 \(\{\mathbf{v}\}\) 经由矩阵 \(A\) 描述的线性变换得到了图形 \(\{\mathbf{u}\}\)，则其面积相应地变换了 \(|\det A|\)。
行列式也有一种表达方式是 \(|A|\)，但我个人不太欣赏，因为这很容易与绝对值符号混淆，甚至会让人产生“行列式非负”的误会。
II.III.特征值与特征向量
定义一数 \(\lambda\) 是一矩阵 \(A\) 的特征值，当且仅当方程 \(A\mathbf{x}=\lambda\mathbf{x}\) 有非平凡解。这时，称所有上述非平凡解 \(\mathbf{x}\) 都是对应于 \(\lambda\) 的特征向量。
依据定义，\(\lambda\) 是可以为零的，但 \(\mathbf{x}\) 却不能。
假如我们往后稍微跳一点的话，就会发现对应于 \(\lambda\) 的所有特征向量，加上零向量，构成一空间，称作\(A\)关于\(\lambda\)的特征空间。特征空间中除了零向量以外的所有向量都是关于\(\lambda\)的特征向量。
上述方程也可以被化成 \((A-\lambda I)\mathbf{x}=0\)。依据我们的行列式知识，此方程有非平凡解当且仅当 \(\det(A-\lambda I)=0\)。
于是，我们定义矩阵 \(A\) 的特征方程是方程\(\det(A-\lambda I)=0\)。\(\lambda\)是\(A\)的特征值，当且仅当其是特征方程的根。
若\(A\)是\(n\times n\)矩阵，则\(\det(A-\lambda I)\)会是一关于\(\lambda\)的\(n\)次多项式，称作特征多项式。这就证明了任意矩阵 \(A\) 都有 \(n\) 个特征值（不论虚实，可能重复）。若特征方程的所有根中，某一个\(\lambda\)共出现了\(k\)次，则\(k\)即为\(\lambda\)的重数。
在OI中，我们不需知道太多关于特征值的特殊用法，最多只需对于一个给定的特征值，求出其对应的特征空间或对于一个给定的特征向量，求出其对应的特征值即可。
III.基于向量空间的线性代数
III.I.向量空间
向量空间是一个向量集合，满足集合中任意向量的倍数与任意两向量的和/差仍在集合内。
零向量属于一切非空向量空间（因为它是任意向量的零倍）。
任何 \(\mathbb{R}^n\) 均是典型的向量空间。
一向量空间拥有子空间，一子空间中所有元素皆属于原向量空间，且其本身仍是合法向量空间。
另一个典型的向量空间的例子是I中提到过的 \(\text{Span}\{\mathbf{v}_i\}\)。
III.II.零空间和列空间
对于一矩阵 \(A\)，所有满足 \(A\mathbf{x}=\mathbf{0}\) 的解构成一向量空间。具体可以见I，因为那时已经提到了其通解可以被表示成某些向量的线性组合形式。
我们将这一空间记作 \(\text{Nul }A\)，中文为零空间。
明显，\(\text{Nul } A\) 的表达是隐式的——这意味着我们无法从矩阵 \(A\) 的元素直接得到生成其的任意一组向量集合。
对于一个特定的（元素全部已知的）\(A\)，可以通过高斯消元将其消成简化阶梯型矩阵，这样便可以用消元后的矩阵的非主元列——加上一点分类讨论后——的线性组合表示 \(\text{Nul }A\)。
虽然其表达是隐式的，但判断一个向量是否在零空间内却是显式的——直接计算 \(A\mathbf{x}\)，并验证其是否为 \(\mathbf{0}\) 即可。
对于一矩阵 \(A\)，其所有列向量的线性组合构成一向量空间，记作 \(\text{Col }A\)，中文为列空间。
其表达明显是显式的。但是，若判断一向量是否在列空间内却是隐式的——你需要建出增广矩阵并判断增广矩阵是否相容。
III.III.基
上文我们已经提到了线性无关的定义。这里，我们有一个新的定义：
一组向量集合 \(\{\mathbf{v}_i\}\) 是一向量空间 \(\mathbb{S}\) 的基，当且仅当 \(\{\mathbf{v}_i\}\) 线性无关且恰好生成 \(\mathbb{S}\)。
在一组线性无关的向量集合中不断添加新的向量并使其仍然线性无关，最终便会生成一组基。
而往一组生成向量空间 \(\mathbb{S}\) 的集合中不断删去向量并使其仍然生成该空间，最终也会生成一组基。
我们将会发现，\(\text{Nul }A\) 的基已经在前面提到了；而 \(\text{Col }A\) 的基即是 \(A\) 中所有主元列。
定义 \(n\) 阶标准基是一组生成 \(\mathbb{R}^n\) 的基，其为 \(n\) 阶单位矩阵 \(I_n\) 的所有列。
III.IV.坐标系
若向量集合 \(\mathcal{B}=\{\mathbf{v}_i\}\) 是向量空间 \(\mathbb{S}\) 的一组基，则对于 \(\mathbb{S}\) 中任意一个向量 \(\mathbf{u}\)，通过 \(\mathcal{B}\) 中向量的线性组合来表示 \(\mathbf{u}\) 的方法是唯一的，即
\[\mathbf{u}=\sum\limits_{i=1}^nc_i\mathbf{v}_i \]我们把向量 \([c_1,c_2,\dots,c_n]\) 称作 \(\mathbf{u}\) 相对于 \(\mathcal{B}\) 的坐标向量，或者 \([\mathbf{u}]_{\mathcal{B}}\)。
我们将会发现，若令 \(P_{\mathcal{B}}=[\mathbf{v}_1,\mathbf{v}_2,\dots,\mathbf{v}_n]\)，则有
\[\mathbf{u}=P_{\mathcal{B}}[\mathbf{u}]_{\mathcal{B}} \]以及
\[[\mathbf{u}]_{\mathcal{B}}=(P_{\mathcal{B}})^{-1}\mathbf{u} \]\(P_{\mathcal{B}}\) 被称作 \(\mathcal{B}\) 到标准基的坐标变换矩阵。因为 \(\mathcal{B}\) 线性无关，故其逆必定存在，故通过它可以实现在 \(\mathcal{B}\) 坐标和标准坐标下的互换。
两个向量空间被称作同构，当前仅当存在一个坐标变换矩阵，可以实现从一个空间到另一个空间的一对一映射。
例如，\(n\) 次多项式空间 \(\mathbb{P}_n\) 就与 \(\mathbb{R}^{n+1}\) 同构。
III.V.维数与秩
定义一个向量空间 \(\mathbb{S}\) 的维数为 \(\dim\mathbb{S}\)，其中 \(\mathbb{S}\) 的任意一组基均包含维数个元素。
同理可以得出一个推论，如果 \(\mathbb{S}\) 的某个子集中含有多于 \(\dim\mathbb{S}\) 个元素，则其线性相关。
\(\text{Nul }A\) 的维数是 \(A\) 中*元的数量，\(\text{Col }A\) 的维数是 \(A\) 中主元的数量。
因此有 \(\dim\text{Nul }A+\dim\text{Col }A=m\)，其中 \(m\) 是 \(A\) 的列数。
定义一个矩阵的秩 \(\text{rank }A=\dim\text{Col }A\)，即其列空间的维数，也即其主元列数。
III.VI.马尔可夫链
定义概率向量是各元素非负且和为 \(1\) 的向量。定义随机矩阵为各列均是概率向量的矩阵。定义马尔可夫链为一系列概率向量 \(\mathbf{x}_0,\mathbf{x}_1,\dots\)，使得存在一个随机矩阵 \(P\)，使得 \(\forall i\geq 1,\mathbf{x}_i=P\mathbf{x}_{i-1}\)。可以发现，马尔可夫链由 \(\mathbf{x}_0\) 和 \(P\) 唯一确定。
定义一马尔可夫链的稳态向量是一概率向量 \(\mathbf{q}\)，使得\(P\mathbf{q}=\mathbf{q}\)成立。
求解一马尔可夫链的稳态向量可以通过求解矩阵方程
\[(P-I)\mathbf{q}=\mathbf{0} \]来得到。可以发现，\(\mathbf{q}\) 是属于 \(\text{Nul }P-I\) 的任意向量。
我们定义一马尔可夫链收敛于一概率向量 \(\mathbf{q}\)，当且仅当\(\lim\limits_{i\rightarrow\infty}\mathbf{x}_i=\mathbf{q}\)。
INF.总结
OI中要用到的线性代数知识很少很少，了解这些已经足够了。
最后，放一些等价的说法：
若 \(A\) 是 \(n\times n\) 方阵：
-
是可逆矩阵
-
行等价于 \(n\) 阶单位矩阵
-
有 \(n\) 个主元
-
\(A\mathbf{x}=0\) 只有平凡解
-
各列线性无关
-
对 \(\forall \mathbf{b}\in\mathbb{R}^n\)，方程 \(A\mathbf{x}=\mathbf{b}\) 有唯一解
-
各列生成 \(\mathbb{R}^n\)
-
\(A^T\) 可逆
-
\(A\) 的列是 \(\mathbb{R}^n\) 之基
-
\(\text{Col }A=\mathbb{R}^n\)
-
\(\dim\text{Col }A=n\)
-
\(\text{rank }A=n\)
-
\(\text{Nul }A=\{\mathbf{0}\}\)
-
\(\dim\text{Nul }A=0\)
-
\(\det A\neq0\)