[游戏开发]【机器学习｜数学基础】Mathematics for Machine Learning系列之线性代数（2）：n阶行列式、对换

前言

Hello！小伙伴！
非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～
?
自我介绍 ?(?ˊ?ˋ)?
昵称：海轰
标签：程序猿｜C++选手｜学生
简介：因C语言结识编程，随后转入计算机专业，有幸拿过一些国奖、省奖…已保研。目前正在学习C++/Linux/Python
学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！
?
机器学习小白阶段
文章仅作为自己的学习笔记 用于知识体系建立以及复习
知其然 知其所以然！

1.3 n阶行列式

三阶行列式为：

$$\left|\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right|=a_{11}?a_{22}?a_{33}+a_{12}?a_{23}?a_{31}+a_{13}?a_{21}?a_{32}?a_{11}?a_{23}?a_{32}?a_{12}?a_{21}?a_{33}?a_{13}?a_{22}?a_{31}$$

从中我们可以发现规律：

$$\left|\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right|=\sum (?1{)}^t{a}_{1p_1}{a}_{2p_2}{a}_{3p_3}$$

其中t为排列$p_1{p}_2{p}_3$的逆序数

进而推出n阶行列式：

$$\left|\begin{array}{cccc}{a}_{11}& a_{12}& ...& a_{1n}\\ a_{21}& a_{22}& ...& a_{2n}\\ .& .& & .\\ .& .& & .\\ a_{n1}& a_{n2}& ...& a_{nn}\end{array}\right|=\sum (?1{)}^t{a}_{1p_1}{a}_{2p_2}...a_{n{p}_n}$$

特殊情况1：

$$\left|\begin{array}{ccccc}{\lambda }_1& & & & \\ & {\lambda }_2& & & \\ & & .& & \\ & & & .& \\ & & & & {\lambda }_n\end{array}\right|={\lambda }_1{\lambda }_2...{\lambda }_n$$

特殊情况2：

$$\left|\begin{array}{ccccc}& & & & {\lambda }_1\\ & & & {\lambda }_2& \\ & & .& & \\ & .& & & \\ {\lambda }_n& & & & \end{array}\right|=(?1{)}^{\frac{n(n?1)}{2}}{\lambda }_1{\lambda }_2...{\lambda }_n（其中(?1{)}^{\frac{n(n?1)}{2}}为排列n、n?1...3、2、1的逆序数）$$

1.4 对换

1.4.1 排列的对换

概念

• 对换：在排列中，将任意两个元素对调，其余的元素不动。
• 相邻对换：在排列中，相邻两个元素进行对换

定理1

内容

一个排列中任意两个元素对换，奇偶性发生改变

证明

首先证明相邻对换的情况

设排列$a_1...a_{i}ab{b}_1...b_m$

a和b对换，变成$a_1...a_{i}ba{b}_1...b_m$

显然，$a_1...a_i$、$b_1...b_m$这些元素的逆序数没有发生变化

当a<b时

• 从ab变为ba，a的逆序数+1（a前面多了一个b），b的逆序数不变

当a>b时，

• 从ab变为ba，a的逆序数不变，b的逆序数-1（b前面少了一个a）

所以

排列中发生相邻对换，奇偶性会发现变化（奇排列-> 偶排列 or 偶排列->奇排列）

再来证明一般情况

$a_1...a_{i}a{b}_1...b_{m}b{c}_1...c_n$ ,a与b发生对换，变为$a_1...a_{i}b{b}_1...b_{m}a{c}_1...c_n$

我们可以先用$b$与$b_m$进行相邻对换，变为$a_1...a_{i}a{b}_1...b{b}_m{c}_1...c_n$

再用$b$与$b_{m?1}$进行相邻对换，变为$a_1...a_{i}a{b}_1...b{b}_{m?1}{b}_m{c}_1...c_n$
.
.
.
最后$b$与$b_1$进行相邻对换，变为$a_1...a_{i}ab{b}_1...b_m{c}_1...c_n$

一共经历了m次相邻对换

和$b_m、b_{m?1}...b_2、b_1$对换，一共就是m次

然后，我们再用$a$与$b$进行相邻对换,变为$a_1...a_{i}ba{b}_1...b_m{c}_1...c_n$

再用$a$与$b_1$进行相邻对换,变为$a_1...a_{i}b{b}_{1}a...b_m{c}_1...c_n$
.
.
.
最后$a$与$b_m$进行相邻对换,变为$a_1...a_{i}b{b}_1...b_{m}a{c}_1...c_n$

一共经历了（m+1）次相邻对换

综上

一共发生了m+（m+1）=2m+1次相邻对换

从最开始的证明可以得出

2m+1次相邻对换后，排列的奇偶性还是会发生改变
（交换1次，奇偶性发生转变；交换2次，奇偶性不发生变化–>交换奇数次，奇偶性发生转变；偶数次则不会。2m+1一定是奇数 ，当m为正整数时）

推论

齐排列变成标准排列的对换次数为奇数，偶排列变成标准排列的对换次数为偶数。

说明

首先，标准排列是逆序数为0的偶排列
?
从定理1可以得知，对换一次，奇偶性发生改变
?
若是齐排列，对换一次，奇->偶，再对换一次，偶->奇…
对换奇数次，最后变为了偶排列；
对换偶数次，最后变为奇排列。
?
所以齐排列变成标准排列的对换次数一定为奇数。
偶排列变成标准排列的对换次数为偶数同理可证。

1.4.2 行列式的另一种表示方法

n阶行列式有：

$$\left|\begin{array}{cccc}{a}_{11}& a_{12}& ...& a_{1n}\\ a_{21}& a_{22}& ...& a_{2n}\\ .& .& & .\\ .& .& & .\\ a_{n1}& a_{n2}& ...& a_{nn}\end{array}\right|=\sum (?1{)}^t{a}_{1p_1}...a_{i{p}_i}...a_{j{p}_j}...a_{n{p}_n}$$

我们选择任意一项：$a_{1p_1}...a_{i{p}_i}...a_{j{p}_j}...a_{n{p}_n}$，其中1…i…j…n为自然排列，$(?1{)}^t$中的t为逆序数

然后交换$a_{i{p}_i}、a_{j{p}_j}$，得到
$a_{1p_1}...a_{j{p}_j}...a_{i{p}_i}...a_{n{p}_n}$

我们来计算奇偶性的变化

首先，我们知道只是交换来两个元素的位置，该项的值是不会发生变化的。

行标从 1…i…j…n 变为了 1…j…i…n，可以得出排列1…j…i…n的逆序数为是奇数，设为r

因为1…i…j…n逆序数为0，偶排列
根据排列任意元素对换，奇偶性改变，
1…j…i…n就变成了齐排列，那么其逆序数一定就是奇数

同样，设$p_1...p_j...p_i...pn$（列标）的逆序数为$t_1$,得到

$a_{1p_1}...a_{j{p}_j}...a_{i{p}_i}...a_{n{p}_n}$前面的正负符号为$(?1{)}^{r+t_1}$

因为

$(?1{)}^{t_1}=(?1)(?1{)}^t=?(?1{)}^t$

$p_1...p_i...p_j...pn$的逆序数为t $a_{1p_1}...a_{i{p}_i}...a_{j{p}_j}...a_{n{p}_n}$前面的系数为$(?1{)}^t$
??
对换一次变为$p_1...p_j...p_i...pn$ 奇偶性发生变化 其实就是乘以（-1）
（排列中，任意两个元素发生对换，奇偶性发生变化，其实就是乘以（-1））
?
所以$(?1)(?1{)}^{t_1}=(?1{)}^t$

又因为r为奇数，有

$（?1{）}^r=?1$

综合下面两个式子：

$$\{\begin{array}{l}(?1{)}^{t_1}=(?1)(?1{)}^t=?(?1{)}^t\\ （?1{）}^r=?1\end{array}$$

得到：

$$(?1{)}^{r+t_1}=(?1{)}^r(?1{)}^{t_1}=(?1)?(?1{)}^{t_1}=(?1)?(?(?1{)}^t)=(?1{)}^t$$

推出：

$$(?1{)}^t{a}_{1p_1}...a_{i{p}_i}...a_{j{p}_j}...a_{n{p}_n}=(?1{)}^{r+t1}{a}_{1p_1}...a_{j{p}_j}...a_{i{p}_i}...a_{n{p}_n}$$

说明

对换行列式中某一项两个元素的位置，使得行坐标、列坐标同时发生变化，但是却并不会改变该项的奇偶性。

一次交换不会改变奇偶性，那么多次交换也不会改变奇偶性

$(?1{)}^t{a}_{1p_1}{a}_{2p_2}...a_{n{p}_n}$经历若干次对换
列标排列$p_1{p}_2...p_n$一定可以变为自然排列（1 2 3… n）

设若干次变换后
列标排列变为了自然排列
行标排列设为$q_1{q}_2...q_n$，则有

$$(?1{)}^t{a}_{1p_1}{a}_{2p_2}...a_{n{p}_n}=(?1{)}^t{a}_{q_{1}1}{a}_{q_{2}2}...a_{q_{n}n}$$

对于其中任意一项 $a_{ij}$，有

$$\{\begin{array}{l}{a}_{ij}=a_{i{p}_i}\\ a_{ij}=a_{q_{j}j}\end{array}$$

得到

$$\{\begin{array}{l}j=p_i\\ i=q_j\end{array}$$

说明由$p_i$可以确定唯一对应的一个$q_j$，比如$2=p_3$ 说明 $q_2=3$ 且唯一！

那么由$p_1{p}_2...p_n$ 可以确定唯一的$q_1{q}_2...q_n$

定理2

内容

n阶行列式也可以定义为：$\sum (?1{)}^t{a}_{p_{1}1}{a}_{p_{2}2}...a_{p_{n}n}$

证明

?

首先，n阶行列式有：

$$\left|\begin{array}{cccc}{a}_{11}& a_{12}& ...& a_{1n}\\ a_{21}& a_{22}& ...& a_{2n}\\ .& .& & .\\ .& .& & .\\ a_{n1}& a_{n2}& ...& a_{nn}\end{array}\right|=\sum (?1{)}^t{a}_{1p_1}{a}_{2p_2}...a_{n{p}_n}$$

令

$$\{\begin{array}{l}D=\sum (?1{)}^t{a}_{1p_1}{a}_{2p_2}...a_{n{p}_n}\\ D_1=\sum (?1{)}^t{a}_{p_{1}1}{a}_{p_{2}2}...a_{p_{n}n}\end{array}$$

从定理1最后的讨论中可以得到：

D中任意一项$(?1{)}^t{a}_{1p_1}{a}_{2p_2}...a_{n{p}_n}$有且只有一项D1中的某一项$(?1{)}^t{a}_{q_{1}1}{a}_{q_{2}2}...a_{q_{n}n}$与之对应**（q是可以有p确定的）；**
?
同理，D1中任意一项$(?1{)}^t{a}_{p_{1}1}{a}_{p_{2}2}...a_{p_{n}n}$也有且只有D中的某一项$(?1{)}^t{a}_{1q_1}{a}_{2q_2}...a_{n{q}_n}$与之对应
?
说明，D与D1中的任意一项都可以一一对应

可以得到$D=D_1$

所以

$$\sum (?1{)}^t{a}_{1p_1}{a}_{2p_2}...a_{n{p}_n}=\sum (?1{)}^t{a}_{p_{1}1}{a}_{p_{2}2}...a_{p_{n}n}$$

结语

说明：

• 参考于 课本《线性代数》第五版 同济大学数学系编
• 配合书中概念讲解 结合了自己的一些理解及思考

文章仅作为学习笔记，记录从0到1的一个过程

希望对您有所帮助，如有错误欢迎小伙伴指正～

我是 海轰?(?ˊ?ˋ)?

如果您觉得写得可以的话，请点个赞吧

您的鼓励是海轰更新文章的动力源泉

谢谢支持 ??