OI中的线代学习笔记

排列和逆序对

定义

以任意一种顺序将相异的 $n$ 个数重排，每个顺序都称作一个排列。
在排列 $a_1 a_2 .. a_n$ 中，如果每有一个二元组 $(i, j)$ 满足 $i < j$ 且 $a_i > a_j$ ，则称 $a_i, a_j$ 组成了一个逆序对。
排列 $a_1 a_2 ... a_n$ 的逆序数表示为 $\tau(a_1 a_2 ... a_n)$ 。
定义：如果一个排列的逆序数为偶数，则称此排列为偶排列，否则称为奇排列。
定义：在一个排列中，对换其中某两个数，其余的数不动，得到另一个排列，这种操作称为一个对换。

定理

对换改变排列的奇偶性。

证明：
对于排列 $a_i a_{i+1} ... a_{j-1} a_j$ 将 $a_i$ 与 $a_{i+1}$ 对换时，逆序对一定增加或者减少一个，所以将 $a_i$ 与 $a_j$ 调换可以视作：将 $a_i$ 逐位对换到 $a_j$ 的位置，易得到排列变为 $a_{i+1} ... a_{j-1} a_j a_i$ 所需要的操作数为 $j - i$ ；再将 $a_j$ 逐位对换到 $a_i$ 原先的位置，由于 $a_j$ 移动的位置显然比 $a_i$ 移动的位置少一个，易得到排列变为 $a_j a_{i+1} ... a_{j-1} a_i$ 所需要的操作数为 $j - i - 1$ 。由于每次相邻的元素对换均会改变排列的奇偶性，而相邻元素总对换数为 $2j -2i -1$ ，这显然是个奇数，所以对换会改变排列的奇偶性。

在全部 $n$ 阶排列中，奇偶排列各占一半。

证明；
对于任意一个排列，通过对换可以改变排列的奇偶性，也就是实现奇排列与偶排列的双射，所以奇偶排列数量一样，各占一半。

定理：任意一个排列可以经过一系列对换操作变成自然排列，并且所做对换操作次数的奇偶性与这个排列的奇偶性相同。

行列式

定义

N阶行列式是由 $N^2$ 个数 $a_{ij}(i, j = 1, 2, ... , n)$ 通过下式确定的一个数

$\left | \begin{array}{cccc} a_{1 1} & a_{1 2} & ... & a_{1 n} \\ a_{2 1} & a_{2 2} & ... & a_{2 n} \\ ... & ... & ... & ... \\ a_{n 1} & a_{n 2} & .. & a_{n n} \end{array} \right | = \Sigma_{j_1j_2...j_n}sgn(j_1j_2...j_n)a_{1j_1}a_{2j_2}...a_{nj_n}$

也称为行列式的完全展开式。

其中 $\Sigma_{j_1j_2...j_n}$ 表示枚举 1 到 n 的每一种排列对后面的式子进行求和， $sgn$ 函数是符号函数。

$a_{1j_1}a_{1j_2}...a_{nj_n}$ 表示从每行取出一个数乘起来，由于排列 $j_1j_2...j_n$ 是没有重复的，所以这里也是从每一行每一列取一个数乘起来。

$sgn(j_1j_2...j_n) = (-1)^{\tau(j_1j_2...j_n)} = \begin{cases} 1 \quad \ \ & j_1j_2...j_n是偶排列 \\ -1 \quad \ \ & j_1j_2...j_n是奇排列 \end{cases}$

引理

行列互换，值不变。
用一个数乘行列式的某行等于这个数乘此行列式。
如果行列式中某一行是两组数之和，则这个行列式等于两个行列式之和，这两个行列式分别以这两组数为该行，而其余各行与原行列式对应各行相同。
对换行列式中两行的位置，行列式反号。
如果行列式中有两行成比例，则行列式等于0。
把一行的某个倍数加到另一行，行列式的值不变。

矩阵

定义

由 $mn$ 个数排成 $m$ 行 $n$ 列矩形的数表

$\begin{bmatrix} a_{1 1} && a_{1 2} && \cdots && a_{1 n} \\ a_{2 1} && a_{2 2} && \cdots && a_{2 n} \\ \vdots && \vdots && \ddots && \vdots \\ a_{m 1} && a_{m 2} && \cdots && a_{m n} \end{bmatrix}$