线性代数 ​

向量的线性无关：
	定义：任何一个向量都不能被其他的向量通过初等变换表示出来
	结论：若有n个元，那么必须有恰n个线性无关的方程，才能解出n个元的值	
解方程组：
	做法：
		法一：高斯消元法：上三角+回代
		法二：高斯-约旦消元法：直接成对角
	本质：
		将每一个元都只保留在一个方程中
		将其他出现的元都消去
		所以，其实每次随便找一个没有被选过的元处理即可
		并不一定是变成对角矩阵
	特别的，在模p意义下的消元：
		如果p是质数，可以直接取逆元
		如果p不是质数（一般做法)：
			类似辗转相除法处理
			复杂度利用势能分析可以得到是O(n^3+n^2logP)
行列式：
	定义：
		对于一个n阶方阵A，对于所有长度为n的排列p，(-1)^(p的逆序对数)*a[1][p1]*a[2][p2]*...*a[n][pn] 的和就是其行列式，记为det(A)
	性质：
		上三角矩阵的行列式为其对角线乘积
		交换矩阵的两行，行列式*=-1
		有两行相同的矩阵的行列式=0
		一行*=k，那么行列式*=k
		矩阵的一行加上另一行，矩阵的行列式不变
		行列式=0等价于矩阵有两个行向量线性相关
	求解：
		利用高斯消元法将矩阵变成上三角矩阵求其对角线乘积即可
矩阵求逆：
	矩阵的逆：矩阵A*B=E，那么B是A的逆
	处理：
		将一个单位矩阵放在A左边然后做高斯-约旦消元使A变成单位矩阵（而不是对角矩阵）
		此时，右边的矩阵就是A的逆
	proof：
		考虑对于B的一个列向量{x1,x2,...,xn}
		对于A的每一行，我们可以得到一个方程（因为最终得到是单位矩阵）
		一个朴素的做法是对于每一列都做一次消元，复杂度O(n^4)
		但是注意到，我们每次消元都只有=右边的列向量改变了
		而消元的本质是将左边的矩阵变成单位矩阵，所以可以一起消
	扩展：
		显然，对于任意的A,C，我们都有办法找到A*B=C（在B存在的情况下）
		因为我们的做法和单位矩阵没有任何联系
fun fact：
	以下等价：
		矩阵中存在两向量线性相关
		行列式=0
		高斯消元消出空向量
		矩阵没有逆
		方程组无解或有无数解
矩阵树定理：
	无向图：
		度数矩阵-邻接矩阵
		随便去掉第k行k列后求值
	有向图：
		外向树：入度矩阵-邻接矩阵
		内向树：出度矩阵-邻接矩阵
		若k为根，则去掉第k行第k列求值

向量的线性无关：
	定义：任何一个向量都不能被其他的向量通过初等变换表示出来
	结论：若有n个元，那么必须有恰n个线性无关的方程，才能解出n个元的值	
解方程组：
	做法：
		法一：高斯消元法：上三角+回代
		法二：高斯-约旦消元法：直接成对角
	本质：
		将每一个元都只保留在一个方程中
		将其他出现的元都消去
		所以，其实每次随便找一个没有被选过的元处理即可
		并不一定是变成对角矩阵
	特别的，在模p意义下的消元：
		如果p是质数，可以直接取逆元
		如果p不是质数（一般做法)：
			类似辗转相除法处理
			复杂度利用势能分析可以得到是O(n^3+n^2logP)
行列式：
	定义：
		对于一个n阶方阵A，对于所有长度为n的排列p，(-1)^(p的逆序对数)*a[1][p1]*a[2][p2]*...*a[n][pn] 的和就是其行列式，记为det(A)
	性质：
		上三角矩阵的行列式为其对角线乘积
		交换矩阵的两行，行列式*=-1
		有两行相同的矩阵的行列式=0
		一行*=k，那么行列式*=k
		矩阵的一行加上另一行，矩阵的行列式不变
		行列式=0等价于矩阵有两个行向量线性相关
	求解：
		利用高斯消元法将矩阵变成上三角矩阵求其对角线乘积即可
矩阵求逆：
	矩阵的逆：矩阵A*B=E，那么B是A的逆
	处理：
		将一个单位矩阵放在A左边然后做高斯-约旦消元使A变成单位矩阵（而不是对角矩阵）
		此时，右边的矩阵就是A的逆
	proof：
		考虑对于B的一个列向量{x1,x2,...,xn}
		对于A的每一行，我们可以得到一个方程（因为最终得到是单位矩阵）
		一个朴素的做法是对于每一列都做一次消元，复杂度O(n^4)
		但是注意到，我们每次消元都只有=右边的列向量改变了
		而消元的本质是将左边的矩阵变成单位矩阵，所以可以一起消
	扩展：
		显然，对于任意的A,C，我们都有办法找到A*B=C（在B存在的情况下）
		因为我们的做法和单位矩阵没有任何联系
fun fact：
	以下等价：
		矩阵中存在两向量线性相关
		行列式=0
		高斯消元消出空向量
		矩阵没有逆
		方程组无解或有无数解
矩阵树定理：
	无向图：
		度数矩阵-邻接矩阵
		随便去掉第k行k列后求值
	有向图：
		外向树：入度矩阵-邻接矩阵
		内向树：出度矩阵-邻接矩阵
		若k为根，则去掉第k行第k列求值