【笔记】数论之线性代数

向量和矩阵

向量

可以理解成是一个一维数组

矩阵

可以理解成是一个二维数组

向量的运算

加法： $(x_1,x_2,x_3,...,x_n)+(y_1,y_2,y_3,...,y_n) = (x_1+y_1,x_2+y_2,...,x_n+y_n)$
减法： $(x_1,x_2,x_3,...,x_n)-(y_1,y_2,y_3,...,y_n) = (x_1-y_1,x_2-y_2,...,x_n-y_n)$
向量与数相乘： $k \times (x_1,x_2,x_3,...x_n) = (k \times x_1,k \times x_2,...,k \times x_n)$

线性相关

给定若干个向量 $V_1,V_2,V_3,...,V_m$

如果有一组非全0系数 $x_1,x_2,x_3,...,x_m$ 使得 $x_1 \times V_1 + x_2 \times V_2 + ... + x_m \times V_m$ 为全0向量

则成这m个向量为线性相关

线性相关其实是用来检查线性方程组的，如果线性相关，则说明有方程组是可以被其它方程组表示出来的，那么就会有方程没用活方程无解

那怎样解决线性方程组问题呢，往下看

高斯消元

其实很简单，就是我们初一学的加减消元法

算法步骤：选择一个变量 $k$ 作为主元，并选择一个 $k$ 的系数不为0的方程，用这个方程，把其他方程的 $k$ 消掉，最后只剩下这个方程的 $k$ ，直接求解

再往前带入，去求每一个变量的值

例：洛谷 P3389

代码如下：

#include<bits/stdc++.h>

using namespace std;

const int N = 110;
const double M = 1e-8;
double a[N][N],b[N];

int main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            cin >> a[i][j];
        }
        cin >> b[i];
    }
    for(int i = 1;i <= n;i++){
        int mxi = i;
        for(int j = i+1;j <= n;j++){
            if(fabs(a[mxi][i]) < fabs(a[j][i])){
                mxi = j;
            }
        }
        if(fabs(a[mxi][i]) < M){
            cout << "No Solution";
            return 0;
        }
        if(mxi != i){
            swap(a[i],a[mxi]);
            swap(b[i],b[mxi]);
        }
        for(int j = 1;j <= n;j++){
            if(i == j){
                continue;
            }
            double w = a[j][i]/a[i][i];
            for(int k = i;k <= n;k++){
                a[j][k] -= a[i][k]*w;
            }
            b[j] -= b[i]*w;
        }
    }
    for(int i = 1;i <= n;i++){
        printf("%.2lf\n",b[i]/a[i][i]);
    }
    return 0;
}

基

对于一组向量： $V_1,V_2,V_3,...,V_m$ ，基指的是找到最多的一个线性无关的子集，即子集之外的所有元素都能被子集内的向量表示出来

线性基

给定 $n$ 个正整数 $a_1,a_2,a_3,...,a_n$

要求从中选出一个子集，子集内所有数的异或和为 $x$

例：洛谷 P3812

代码如下：

#include<bits/stdc++.h>

using namespace std;

long long s[50];

int main(){
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++){
		long long x;
		cin >> x;
		for(int j = 49;j >= 0;j--){
			if(x>>j&1){
				if(!s[j]){
					s[j] = x;
					break;
				}
				x ^= s[j];
			}
		}
	}
	long long ans = 0;
	for(int i = 49;i >= 0;i--){
		ans = max(ans,ans^s[i]);
	}
	cout << ans;
	return 0;
}

矩阵的运算

加法：令 $C_{1...n,1...m} = A_{1...n,1...m}+B_{1...n,1...m}$ ，则 $C_{i,j} = A_{i,j}+B_{i,j}$
减法：令 $C_{1...n,1...m} = A_{1...n,1...m}-B_{1...n,1...m}$ ，则 $C_{i,j} = A_{i,j}-B_{i,j}$
乘法：令 $C_{1...n,1...m} = A_{1..n,1...k} \times B_{1...k,1...m}$ ，则 $C_{i,j} = \sum^k_{x=1}A_{i,x} \times B_{x,j}$

单位矩阵

主对角线：所有横坐标和纵坐标相等的元素，即所有 $A_{i,i}$ 构成的元素成为主对角线

对于一个 $n \times n$ 的方阵，主对角线所有元素为1，其他所有元素为0，就叫做单位矩阵

上三角矩阵

主对角线下方所有数都是0的矩阵则称为上三角矩阵

其实，上三角矩阵是可以和高斯消元扯上关系的

把系数矩阵消成上三角矩阵，如果消元完成后，主对角线出现了0，则说明有方程是没用的

行列式

定义行列式：消元成上三角矩阵后对角线的数的乘积

查看对角线是否有0等价于行列式是否为0

对于行列式有以下性质：

矩阵转置，行列式不变
交换两行，行列式取反
把一行乘一个系数加到另一行，行列式不变
把一行所有数成 $k$ ，行列式乘 $k$

矩阵乘法的运算定律

结合律： $A \times B \times C = A \times (B \times C)$
分配律： $(A+B) \times C = A \times C + B \times C$
矩阵乘法不满足交换律！

由于矩阵乘法满足结合律所以可以使用矩阵快速幂

KV熵的Blog