不会线性代数。
行列式
定义
对一个 \(n\times n\) 的矩阵 \(A\)，其 \(n\) 阶行列式写作 \(\mathrm{det}(A)\) 或 \(|A|\)，定义为
\[\mathrm{det}(A)=|A|=\sum_{p}(-1)^{\tau(p)}\prod_{i=1}^{n}a_{i,p_i} \]所有的 \(p\) 形成 \(1\) 到 \(n\) 的全排列，\(\tau(p)\) 表示排列 \(p\) 的逆序对个数。
排列的奇偶性
-
规定若 \(\tau(p)\) 为奇数，则 \(p\) 是一个奇排列，否则是一个偶排列。
-
奇排列与偶排列在 \(n(n\geq2)\) 阶排列中的出现次数相同。
-
对于排列 \(p\)，仅交换其中 \(2\) 个元素，其余不变，得到一个新的排列，该操作称为对换。
-
一次对换会改变排列的奇偶性。
-
一个排列可通过若干次对换使其元素严格递增，对换次数奇偶性与原排列奇偶性相同。
性质
线代秒了。害。
- 矩阵转置后行列式值不变。（\(A\rightarrow A^{T}:a_{i,j}\rightarrow a_{j,i}\)）
即证 \(\displaystyle \sum_{p}(-1)^{\tau(p)}\prod_{i=1}^{n}a_{i,p_i}=\sum_{p}(-1)^{\tau(p)}\prod_{i=1}^{n}a_{p_i,i}\)
则 \((-1)^{\tau(p)}=(-1)^{\tau(p')}\)，其中 \(p'_{p_i}=i\)。
后者即按权值排序后下标的逆序对数，有 \(\tau(p)=\tau(p')\)，得证。
于是所有对行满足的性质，对于列而言也满足，因为将矩阵转置后，原来的列操作等价于转置后的行操作。
- 行列式的行（列）所有元素等比例变化，则行列式等比例变化。
列上同理。这是显然的。
- 将行列式某行（列）的值拆为两部分，行列式求和后与原行列式值相等。
这个也是简单的。
- 交换行列式两行（列），行列式值反号。
相当于交换原排列的两位置，\(\tau(p)\) 奇偶性改变，易知行列式值反号。
- 若行列式两行（列）成比例，则行列式值为 \(0\)。
先将比例提出，交换两行（列），行列式值不变且反号，可知行列式值为 \(0\)。
- 将矩阵的一行（列）的值全部乘一个常数加到另一行（列）上，行列式值不变。
这个也是简单的。
行列式求值
- 模数为质数
观察上三角方针 \(A=\begin{vmatrix} a_{1,1}&a_{1,2}&\cdots&a_{1,n} \\ 0&a_{2,2}&\cdots&a_{2,n} \\ \vdots&\vdots&\ddots&\vdots \\ 0&0&\cdots&a_{n,n} \end{vmatrix}\)，容易发现 \(\displaystyle \mathrm{det}(A)=\prod_{i=1}^{n}a_{i,i}\)，只需将原行列式变成一个与其值相同的上三角方针即可。
利用行列式的性质，高斯消元即可。时间复杂度 \(O(n^3)\)。
- 一般情况
此时不能直接算 \(\dfrac{a_{j,i}}{a_{i,i}}\) 了。
考虑辗转相除，每次将第 \(j\) 行消去即 \(a_{j,i}\leftarrow a_{j,i}\bmod a_{i,i}\) 后交换两行（变号），直至 \(a_{j,i}=0\)。
在辗转相除过程中可以做到取模。
辗转相除是 \(O(\log V)\) 的，于是时间复杂度 \(O(n^3+n^2\log V)\)。
标签：ddots,tau,Matrix,定理,Tree,vmatrix,cdots,行列式,vdots From： https://www.cnblogs.com/SError0819/p/18004412