高斯消元
引入
高斯消元听起来非常高大上,其实就是我们初中学的加减消元、代入消元法的程序化实现罢了。
考虑一个方程组
概念
系数矩阵:上面的方程组中系数A组成的
增广矩阵:系数矩阵的最右边补上一列,表示
初等行列变换:
1. 以一个非零的数乘矩阵的某一行(列)
2. 把矩阵的某一行(列)的c倍加到另一行(列),这里c是任意数 3. 互换矩阵中两行(列)的位置
阶梯型矩阵:一个矩阵成为阶梯型矩阵,需满足两个条件:
1. 如果它既有零行,又有非零行,则零行在下,非零行在上。
2. 如果它有非零行,则每个非零行的第一个非零元素所在列号自上而下严格单调上升。
转置:把一个矩阵的行变成列,列变成行,得到的矩阵就是原矩阵的转置。记为
如图所示,这就是一个阶梯型矩阵
三角矩阵:三角矩阵分上三角矩阵和下三角矩阵两种。上三角矩阵的对角线左下方的系数全部为零,下三角矩阵的对角线右上方的系数全部为零。
算法流程
它的基本思想是通过初等行变换,把增广矩阵消成上三角矩阵,此时最后一个非零行必然是
代码 (SDOI2006 线性方程组)
改编自 ComeIntoPower,在此对他表示谢意QwQ
1 |
|
解释:
- Q: 咋判断无解和无穷多组解鸭?
- A:当消元完成后,回代之前时,方程组若出现除了常数项之外全零的行,则一定无解或无穷多组解。(常数项为0是无穷多组解,非零则无解)
- Q:代码中那个变量c的作用是啥呀?为啥不能用i代替呢?
- A:因为如果把c换成i,当存在一个自由元的时候,可能没法消出来全零行,而是直接跳过了本该消成全零行的那一行,将其放在了原来的位置,导致判断无穷解和无解的时候出偏差。(详见洛谷本题讨论的“Hack+1”篇目).
行列式
概念:
主子式:对于一个n阶矩阵A,选取它的任意i行,将行号记为
行列式:行列式是一个标量。对一个矩阵A来说,它的行列式(记作
1.
为了证明这个定理,我们需要首先证明一个引理: * 引理:一个排列的两项交换,逆序对改变量为奇数。 * 引理证明:不妨设
现在,证明这个定理就十分容易了。
证明:交换矩阵的两行,相当于交换
的两项。逆序对改变量为奇数,所以行列式变号。推论2.1:有两行相同的矩阵,行列式为
。- 证明:交换这两行,行列式变号且值不变...
- 将某一行乘上
,行列式乘上 .- 证明:你在这一行选出的每个数,都乘上了一个
。提取公因数即得。
- 证明:你在这一行选出的每个数,都乘上了一个
- 两个矩阵如果只有一行不同,则它们的行列式和等于将不同的行相加得到的新矩阵的行列式。
- 证明:从定义下手。挺显然的吧qwq.
- 推论4.1:将一行乘上
的值加到另一行上,行列式不变。- 证明:设被加的行为
,乘上 加到 上的为 。把这个新矩阵拆成两个矩阵 。其中 是原矩阵, 的 行改为 :则由性质2和3, 的行列式为 。又由性质4,新矩阵的行列式为 ,和原来相等 - 有了这个推论和性质2,我们就可以做高斯消元啦!
- 证明:设被加的行为
- 每行每列和均为0的矩阵,行列式为0.
- 证明:对原矩阵补上一列0,进行高斯消元。显然这个方程组有解——所有未知数都相等.则由高斯消元判断无穷多组解的条件可得,消出的上三角矩阵中,一定有全零行,且常数项也是0。所以该矩阵的行列式为0.因为高消之后的矩阵的行列式只是原行列式乘上±1(只在交换行的时候行列式发生变号),所以原矩阵的行列式也为0.
- 对于一个上三角矩阵,它的行列式为对角线上数的乘积。
- 证明:要在每行选取一个列不重复的数,且这些数乘积非0,则只能选对角线上的n个数。
求解
直接求解要枚举全排列,时间复杂度为
1 | inline long double determinant(long double (*A)[maxn],int n) |
矩阵树定理
概念:
- 度数矩阵:定义
为图 的度数矩阵,则 为一个 矩阵,其中 为编号为i的结点的度数. - 邻接矩阵:就是我们通常所说的邻接矩阵,记为
。 - 基尔霍夫矩阵(拉普拉斯矩阵):定义基尔霍夫矩阵
.
定理:
当邻接矩阵不带边权时(若
矩阵树定理:一个无重边、自环的图
的生成树个数,等于它的基尔霍夫矩阵任意一个n-1阶主子式的行列式的绝对值。
将邻接矩阵加上边权,得到新的邻接矩阵、度数矩阵和基尔霍夫矩阵。即:允许重边(甚至把边数扩展到
变元矩阵树定理: 1. 对生成树T定义求其边权之积的函数
2. 对于每一棵生成树,求其 函数值的和得到 : 3. 则 等于(带边权的)基尔霍夫矩阵的任意一个n-1阶主子式的行列式的绝对值. 4. 容易发现,当边权都为1的时候,它就是普通的矩阵树定理.
对于有向图来说,有:
有向图的矩阵树定理
定义去掉第i行第i列,则能求出以i为根的外向树的数量(边权积)
同样地,定义则能求内向树的数量(边权积)
(原谅我语文学得不好没法简洁地描述上述定理qwq...) ## 证明: ~~我们采用闭眼证明法...嗯!它是对的!^_^..~~
事实上博主太菜并不会证明..(留坑)
应用:
BZOJ1002: (假的)题解戳这里~
BZOJ1016:题解戳这里~
BZOJ3524:题解戳这里~
引用&鸣谢
对以上巨佬表示感谢。
v1.5.2