矩阵和行列式
矩阵
矩阵乘法
规定两个矩阵 \(A, B\) 可乘，当且仅当 \(A\)的列数 \(=\) \(B\)的行数（即\(A, B\)相容）.
设矩阵 \(C\) \(=\) \(A\times B\) ，则 \(\forall(i, j)\) ，有 \(c_{i,j}=\sum\limits_{k=1}^{N} a_{i,k}b_{k,j}\) 。可见\(C\)的行数 \(=\) \(A\)的行数，\(C\)的列数 \(=\) \(B\)的列数。
根据此定义，不难证明矩阵乘法满足结合律（但不一定满足交换律，有时交换了甚至不可乘），因此可以快速幂。
值得注意的是，定义 \(n\) 阶矩阵即 \(n\times n\) 的矩阵，对于一个 \(n\) 阶的矩阵的确有左单位元和右单位元，但不一定存在逆元，因此 \(n\) 阶矩阵的全体和矩阵乘法不能构成群。
矩阵的逆
\(n\times n\) 矩阵 \(A\) 的逆 \(A^{-1}\) （如果存在）为满足 \(AA^{-1}=I_n=A^{-1}A\) 的 \(n\times n\) 矩阵。
一个没有逆的矩阵称为不可逆的，或奇异的；
反之有逆的矩阵称为可逆的，或非奇异的。
逆操作和转置可以交换顺序。
矩阵的秩
如果存在不全为零的相关系数 \(c_1, c_2, \cdots, c_n\) 使得 \(c_1 x_1+c_2 x_2+\cdots+c_n x_n=0\) 则称向量 \(x_1,x_2,\cdots,x_n\) 是线性相关的；
反之不存在不全为0的相关系数 \(c_1, c_2, \cdots, c_n\) 使得 \(c_1 x_1+c_2 x_2+\cdots+c_n x_n=0\) 则称向量 \(x_1,x_2,\cdots,x_n\)是线性无关的。
非零 \(m\times n\) 矩阵 \(A\) 的列秩是 \(A\) 的最大线性无关列集合的大小；类似地，矩阵 \(A\) 的行秩是 \(A\) 的最大线性无关行集合的大小。有结论：A的列秩=A的行秩，所以可以简称为 \(A\) 的秩。秩的等价定义是：非零 \(m\times n\) 矩阵 \(A\) 的秩是满足如下条件的最小数值 \(r\)：存在 \(m\times r\) 矩阵 \(B\) 和 \(r\times n\) 矩阵 \(C\) ， 使得 \(A=BC\)。如果 \(n\times n\) 方阵的秩是 \(n\) ，则它是满秩的。如果 \(m\times n\) 方阵的秩是 \(n\) ，则它是列满秩的；类似地，如果 \(m\times n\) 方阵的秩是 \(m\) ，则它是行满秩的。
矩阵 \(A\) 的空向量 \(x\) 是一个满足 \(Ax=0\) 的非零向量。
矩阵的行列式
\(n\times n\) \((n>1)\) 矩阵 \(A\) 的 \(i\) 行 \(j\) 列子矩阵是一个删除 \(A\) 中 \(i\) 行 \(j\) 列后得到的 \((n-1)\times(n-1)\) 矩阵 \(A_{[i j]}\) 。
我们利用 \(n\times n\) 矩阵 \(A\) 的子矩阵递归地定义该矩阵的行列式：
\[\det(A)=\left\{\begin{array}{rcl} &a_{11} & {n=1}\\ &\sum\limits_{j=1}^{n}(-1)^{1+j}a_{1j}\det(A_{[ij]}) & {n>1}\\\end{array} \right. \]\((-1)^{i+j}\det(A_{[ij]})\) 称为元素 \(a_{ij}\) 的代数余子式。
行列式还有一种等价定义：
\[det(A)=\sum (-1)^ka_{1k_1}a_{2k_2}\cdots a_{nk_n} \]其中 \(k_1,k_2,\cdots,k_n\) 是 \(1\sim n\) 的一个排列， \(k\) 是该排列中的逆序对个数。
行列式的性质
- 如果矩阵 \(A\) 中某行（或某列）为零，则 \(\det(A)=0\)
- 当将矩阵 \(A\) 的任意一行（或列）的每个元素乘以 \(\lambda\) 后，\(A\) 的行列式乘以 \(\lambda\)
- 如果将矩阵 \(A\) 中某一行（或列）的元素加到另一行（或列）的元素上，则 \(A\) 的行列式不变
- 矩阵 \(A\) 的行列式与转置 \(A^T\) 的行列式相等
- 当交换 \(A\) 的任意两行（或两列）时，行列式改变正负号
Proof
- 在为零的行（或列）展开即证。 \(\blacksquare\)
- 对比在被乘的行（或列）的展开和原矩阵在该行（或列）的展开即证。 \(\blacksquare\)
- 考虑变换前后矩阵的行列式之差即可。 \(\blacksquare\)
- 分别按行展开和按列展开即证。\(\blacksquare\)
- 可以证明结论：考虑一个 \(1\sim n\) 的排列 \(P\) ，\(\forall i\not=j\)，交换 \(p_i,p_j\) ，则 \(P\) 中逆序对个数奇偶性改变。简单证明该结论：对数量变化产生影响的只有满足 \(min\{p_i,p_j\}<p_k<max\{p_i,p_j\}\) 且 \(i<k<j\) 的 \(p_k\) 和 \(p_i,p_j\) 产生的逆序对与 \(p_i,p_j\) 产生的逆序对 ：设满足 \(min\{p_i,p_j\}<p_k<max\{p_i,p_j\}\) 且 \(i<k<j\) 的 \(k\) 的个数为 \(x\) ，则逆序对数量改变了 \(\pm 2x\) ；而 \(p_i,p_j\) 之间由于交换使数量改变了 \(\pm 1\) ；所以共改变了 \(\pm 2x\pm 1\) 个，是一个奇数，所以总逆序对的个数奇偶性改变。根据此结论，考虑逆序对定义即证。\(\blacksquare\)
综合 性质\(2\) 性质\(3\) 有结论：如果将矩阵 \(A\) 中某一行（或列）的元素元素乘以 \(\lambda\) 加到另一行（或列）的元素上，则 \(A\) 的行列式不变。
线性递推
首先要明确如何利用矩阵乘法。矩阵乘法可以快速幂，也就是说，如果一个式子中，同一个矩阵连乘许多次，设 矩阵的行数 \(=\) 矩阵的列数 \(=\) \(n\)，就可以考虑倍增在 \(Θ(n^2\log(k))\) 的时间内完成 \(k\) 次矩阵乘法。因此，构造 状态构成的矩阵和 常数构成的矩阵，就可以快速从一个状态转移到另一个状态。
小Z和二阶线性递推数列
对于本题, 给出递推式：
\[\begin{pmatrix} f_{n}\\ f_{n-1}\end{pmatrix}=\begin{pmatrix}a & b\\ 1 & 0 \end{pmatrix}\times\begin{pmatrix}f_{n-1}\\ f_{n-2}\end{pmatrix} \]于是得到通项：
\[\begin{pmatrix} f_{n}\\ f_{n-1}\end{pmatrix}=\begin{pmatrix}a & b\\ 1 & 0 \end{pmatrix}^{n-2}\times\begin{pmatrix}f_{2}\\ f_{1}\end{pmatrix} \]而 \(\begin{pmatrix}a & b\\ 1 & 0 \end{pmatrix}^{n-2}\) 是可以快速幂的。
矩阵表达修改
大魔法师
考虑使用线段树维护区间，操作需要满足的性质有结合律和分配率，矩阵加法和乘法恰好满足。
对于每个节点，和朴素线段树相同，要记录左右端点和两个儿子（如果不是叶节点），区间和是 \(4\times1\) 的矩阵，从第一行开始分别为 \(\Sigma A_i, \Sigma B_i, \Sigma C_i, \Sigma 1\) 。懒标记是 \(4\times4\) 的矩阵, 用于暂时储存其管理区间变换的叠加（因为满足结合律和分配率）。之前提到，对于 \(n\times n\) 的矩阵上的乘法的确是有左、右单位元的。各种操作按题意模拟即可。
树上询问
定长路径统计
限长路径计数/最短路
特殊的矩阵
范德蒙德矩阵
这玩意的行列式比较特殊，所以有时会用到。
范德蒙德矩阵的行列式
设 $V(x_0, x_1, \cdots, x_{n-1})= \begin{pmatrix} 1& x_0& x_0^2& \cdots& x_0^{n-1}\ 1& x_1& x_1^2& \cdots& x_1^{n-1}\ \vdots& \vdots& \vdots& \ddots& \vdots\1& x_{n-1}& x_{n-1}^2& \cdots& x_{n-1}^{n-1}\end{pmatrix}
$
则 \(det(V(x_0, x_1, \cdots, x_{n-1}))=\prod\limits_{0\le j<k \le n-1}(x_k-x_j)\)
Proof :
对 \(n\) 归纳：
\(n\le2\) 时结论是平凡的.
假设 \(n=n_0-1\) 时成立, 考虑 \(n=n_0\)：
\(\quad\left|\begin{matrix} 1& x_0& x_0^2& \cdots& x_0^{n}\\ 1& x_1& x_1^2& \cdots& x_1^{n}\\ \vdots& \vdots& \vdots& \ddots& \vdots\\1& x_{n}& x_{n}^2& \cdots& x_{n}^{n}\end{matrix}\right|=\left|\begin{matrix} 1& x_0-x_0& x_0^2-x_0\times x_0& \cdots& x_0^{n}-x_0\times x_0^{n-1}\\ 1& x_1-x_0& x_1^2-x_0\times x_1& \cdots& x_1^{n}-x_0\times x_1^{n-1}\\ \vdots& \vdots& \vdots& \ddots& \vdots\\1& x_{n}-x_0& x_{n}^2-x_0\times x_n& \cdots& x_{n}^{n}-x_0\times x_n^{n-1}\end{matrix}\right|\)
\(=\left|\begin{matrix} 1& 0& 0& \cdots& 0\\ 1& x_1-x_0& (x_1-x_0)\times x_1& \cdots& (x_1-x_0)\times x_1^{n-1}\\ \vdots& \vdots& \vdots& \ddots& \vdots\\1& x_{n}-x_0& (x_{n}-x_0)\times x_n& \cdots& (x_{n}-x_0)\times x_n^{n-1}\end{matrix}\right|\)
\(=\left|\begin{matrix} x_1-x_0& (x_1-x_0)\times x_1& \cdots& (x_1-x_0)\times x_1^{n-1}\\ x_2-x_0& (x_2-x_0)\times x_2& \cdots& (x_2-x_0)\times x_2^{n-1}\\\vdots& \vdots& \ddots& \vdots\\x_{n}-x_0& (x_{n}-x_0)\times x_n& \cdots& (x_{n}-x_0)\times x_n^{n-1}\end{matrix}\right|\)
\(=\prod\limits_{1\le i\le n}(x_i-x_0) \times \left|\begin{matrix} 1& x_1& \cdots& x_1^{n-1}\\ 1& x_2& \cdots& x_2^{n-1}\\\vdots& \vdots& \ddots& \vdots\\1& x_n& \cdots& x_n^{n-1}\end{matrix}\right|\)
\(=\prod\limits_{0=j< k\le n}(x_k-x_0) \times \prod\limits_{1\le j<k \le n}(x_k-x_j)\)
\(=\prod\limits_{0\le j<k \le n}(x_k-x_j)\)
\(\blacksquare\)