0x35 高斯消元与线性空间

高斯消元

高斯消元是一种求解线性方程组的方法。所谓线性方程组，是由 $M$ 个 $N$ 元一次方程共同构成的。线性方程组的所有系数可以写成一个 $M$ 行 $N$ 列的“系数矩阵”，再加上每个方程等号右侧的常数，可以写成一个 $M$ 行 $N + 1$ 列的“增广矩阵”，例如：

求解这种方程组的步骤可以概括成对“增广矩阵”的三类操作：

1. 用一个非零的数乘某一行。

2. 把其中一行的若干倍加到另一行上。

3. 交换两行的位置。

我们把这三类操作称为矩阵的“初等行变换”。同理，我们也可以定义矩阵的“初等列变换”。用若干次初等行变换求解上面的方程组，过程如下：

最后得到的矩阵被称为“阶梯形矩阵”，它的系数矩阵部分被称为“上三角矩阵”，名字来源于其形状。这个矩阵表达的信息是：

因此，我们已经知道了最后一个未知量的值，从下往上依次代回方程组，即可得到每个未知量的解。事实上，该矩阵也可以进一步化简：

最后得到的矩阵被称为“简化阶梯形矩阵”，它的系数矩阵部分是一个“对角矩阵”，名字来源于其形状。该矩阵已经直接给出了方程组的解。

通过初等行变换把增广矩阵变为简化阶梯形矩阵的线性方程组求解算法就是高斯消元算法。高斯消元算法的思想就是，对每个未知量 $x_{i}$ ，找到一个 $x_{i}$ 的系数非零，但 $x_{1} \sim x_{i-1}$ 的系数都是零的方程，然后用初等行变换把其他方程的 $x_{i}$ 的系数全部消成零。

上面给出的例子是一种比较理想的情况。事实上，在高斯消元的过程中，可能会遇到各种各样的特殊情形，需要我们分情况讨论。

首先，在高斯消元过程中，可能出现 $0 = d$ 这样的方程，其中 $d$ 是一个非零常数。这表明某些方程之间存在矛盾，方程组无解。

其次，有可能找不到一个 $x_{i}$ 的系数非零，但 $x_{1} \sim x_{i-1}$ 的系数都是零的方程。这是我们要重点讨论的情况，例如：

在上例中，找不到 $x_{2}$ 的系数非零，但 $x_{1}$ 的系数为零的方程。方程组的解可以写作：

$x_{2}$ 取任何值，都可以计算出一个对应的 $x_{1}$ ，并且满足原方程组。换言之，方程组有无穷多个解。我们把 $x_{1}, x_{3}$ 这样的未知量称为“主元”，把 $x_{2}$ 这样的未知量称为“自由元”。

仔细分析可以发现，对于每个主元，整个简化阶梯形矩阵中有且仅有一个位置 $(i,j)$ ，满足该主元的系数非零。第 $j$ 列的其他位置都是零，第 $i$ 行的第 $1\sim j - 1$ 列都是零。

综上所述，在高斯消元完成后，若存在系数全为零、常数不为零的行，则方程组无解。若系数不全为零的行恰好有 $n$ 个，则说明主元有 $n$ 个，方程组有唯一解。若系数不全为零的行有 $k < n$ 个，则说明主元有 $k$ 个，自由元有 $n - k$ 个，方程组有无穷多个解。

【例题】球形空间产生器 BZOJ1013

有一个球形空间产生器能够在 $n$ 维空间 $(1 \leq n \leq 10)$ 中产生一个坚硬的球体。现在，你被困在了这个 $n$ 维球体中，你只知道球面上 $n + 1$ 个点的坐标，你需要以最快的速度确定这个 $n$ 维球体的球心坐标，以便于摧毁这个球形空间产生器。数据保证有解，答案精确到小数点后3位。

一个球体上的所有点到球心的距离相等，因此只需求出一个点 $(x_{1}, x_{2}, \dots, x_{n})$ ，使得：

其中 $C$ 为常数， $i \in [1, n + 1]$ ，球面上第 $i$ 个点的坐标为 $(a_{i,1}, a_{i,2}, \dots, a_{i,n})$ 。该方程组由 $n + 1$ 个 $n$ 元二次方程构成，不是线性方程组。但是我们可以通过相邻两个方程作差，把它变成 $n$ 个 $n$ 元一次方程，同时消去常数 $C$ ：

把变量放在左边，常数放在右边：

这就是一个线性方程组了。题目保证方程组有唯一解，我们直接对下面的增广矩阵进行高斯消元，变为简化阶梯形矩阵，即可得到每个 $x_{j}$ 的值。

double a[20][20], b[20], c[20][20];  
int n;  
int main() {  
cin >> n;  
for (int i = 1; i <= n + 1; i++)  
    for (int j = 1; j <= n; j++) scanf("%lf", &a[i][j]);  
// c: 系数矩阵，b: 常数，二者一起构成增广矩阵  
for (int i = 1; i <= n; i++)  
    for (int j = 1; j <= n; j++) {  
        c[i][j] = 2 * (a[i][j] - a[i + 1][j]);  
        b[i] += a[i][j] * a[i][j] - a[i + 1][j] * a[i + 1][j];  
    }  
// 高斯消元（数据保证有唯一解）  
for (int i = 1; i <= n; i++) {  
    // 找到x[i]的系数不为0的一个方程  
    for (int j = i; j <= n; j++) {  
        if (fabs(c[j][i]) > 1e-8) {  
            for (int k = 1; k <= n; k++) swap(c[i][k], c[j][k]);  
                swap(b[i], b[j]);  
        }  
    }

// 消去其他方程的  $x[i]$  的系数  
for (int j = 1; j <= n; j++) {  
    if (i == j) continue;  
    double rate = c[j][i] / c[i][i];  
    for (int k = i; k <= n; k++) c[j][k] -= c[i][k] * rate;  
    b[j] -= b[i] * rate;  
}  
}  
for (int i = 1; i < n; i++) printf("%.3f", b[i] / c[i][i]);  
printf("%.3f\n", b[n] / c[n][n]);

【例题】开关问题 FOJ1830

有 $N$ 个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。

你的目标是经过若干次开关操作后使得最后 $N$ 个开关达到一个特定的状态。对于任意一个开关，最多只能进行一次开关操作。你的任务是，计算有多少种可以达到指定状态的方法（不计开关操作的顺序）。

输入数据的第一行是一个数 $N(0 < N < 29)$ ；第二行有 $N$ 个0或者1的数字，表示 $N$ 个开关的初始状态；第三行有 $N$ 个0或者1的数字，表示 $N$ 个开关的目标状态。接下来每行两个数 $i, j$ ，表示如果操作第 $i$ 个开关，第 $j$ 个开关的状态也会变化。

设 $x_{i}$ 表示第 $i$ 个开关的操作情况， $x_{i} = 1$ 表示按了这个开关， $x_{i} = 0$ 表示没有按。再统计 $a_{i,j}$ 表示第 $i$ 个开关和第 $j$ 个开关的联系情况， $a_{i,j} = 1$ 表示按下 $j$ 会影响 $i$ 的状态， $a_{i,j} = 0$ 表示不会影响，特别地，令 $a_{i,i} = 1$ 。

一个开关最后的状态 $dst_{i}$ ，取决于它最初的状态 $src_{i}$ ，以及所有与它有联系的开关的操作情况执行异或运算得到的结果。可列出异或方程组：

异或其实就是不进位加法，我们仍然可以写出增广矩阵，矩阵中的每个值要么是0，要么是1。然后，在执行高斯消元的过程中，把加、减法替换成异或，且不需要执行乘法。最终我们可以得到该异或方程组对应的简化阶梯形矩阵。若存在形如 $0 = 1$ 的方程，则方程组无解。否则，因为自由元可以取0或1，所以方程组解的数量就是 $2^{cnt}$ ，

其中 $cnt$ 为自由元的个数。

在程序编写中，为了简便、高效，可以把增广矩阵的每一行进行状态压缩，用一个int类型的整数表示 $n + 1$ 位二进制数，其中第0位为增广矩阵最后一列的常数，第 $1\sim n$ 位分别为增广矩阵第 $1\sim n$ 列的系数。

int a[100], n, t, ans;  
int main() {  
cin >> t;  
while (t--) {  
cin >> n;  
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);  
for (int i = 1, j; i <= n; i++) {  
    scanf("%d", &j);  
    a[i] ^= j;  
    a[i] |= 1 << i; // a[i][i] = 1;  
}  
int x, y;  
while (~scanf("%d%d", &x, &y) && x && y) {  
    a[y] |= 1 << x; // a[y][x] = 1;  
}  
ans = 1;  
for (int i = 1; i <= n; i++) {  
    // 找到最大的一个 a[i]，即主元位数最高的 a[i]  
    for (int j = i + 1; j <= n; j++)  
        if (a[j] > a[i]) swap(a[i], a[j]);  
    // 消元完毕，有 i-1 个主元，n-i+1 个自由元  
    if (a[i] == 0) { ans = 1 << (n - i + 1); break;}  
// 出现 0=1 的方程，无解  
if (a[i] == 1) { ans = 0; break;}  
// a[i]最高位的 1 作为主元，消去其他方程该位的系数  
for (int k = n; k; k--)  
    if (a[i] >> k & 1) {  
        for (int j = 1; j <= n; j++)  
            if (i != j && (a[j] >> k & 1)) a[j] ^= a[i];  
        break;  
    }  
}  
if (ans == 0) puts("Oh, it's impossible~!!");

elsecout<<ans<<endl; }

线性空间

线性空间是一个关于以下两个运算封闭的向量集合：

1. 向量加法 $a + b$ ，其中 $a, b$ 均为向量。

2. 标量乘法 $k * a$ ，也称数乘运算，其中 $a$ 是向量， $k$ 是常数（标量）。

给定若干个向量 $a_1, a_2, \dots, a_k$ ，若向量 $b$ 能由 $a_1, a_2, \dots, a_k$ 经过向量加法和标量乘法运算得出，则称向量 $b$ 能被向量 $a_1, a_2, \dots, a_k$ 表出。显然， $a_1, a_2, \dots, a_k$ 能表出的所有向量构成一个线性空间， $a_1, a_2, \dots, a_k$ 被称为这个线性空间的生成子集。

任意选出线性空间中的若干个向量，如果其中存在一个向量能被其他向量表出，则称这些向量线性相关，否则称这些向量线性无关。

线性无关的生成子集被称为线性空间的基底，简称基。基的另一种定义是线性空间的极大线性无关子集。一个线性空间的所有基包含的向量个数都相等，这个数被称为线性空间的维数。

例如，平面直角坐标系中的所有向量构成一个二维线性空间，它的一个基就是单位向量集合 $\{(0,1),(1,0)\}$ 。平面直角坐标系的 $x$ 轴上的所有向量构成一个一维线性空间，它的一个基就是 $\{(1,0)\}$ 。

对于一个 $n$ 行 $m$ 列的矩阵，我们可以把它的每一行看作一个长度为 $m$ 的向量，称为“行向量”。矩阵的 $n$ 个行向量能够表出的所有向量构成一个线性空间，这个线性空间的维数被称为矩阵的“行秩”。类似地，我们可以定义列向量和列秩。实际上，矩阵的行秩一定等于列秩，它们都被称为矩阵的秩。

把这个 $n * m$ 的矩阵看作“系数矩阵”进行高斯消元（增广矩阵的最后一列全看作零），得到一个简化阶梯形矩阵。显然，简化阶梯形矩阵的所有非零行向量线性无关。因为初等行变换就是行向量之间进行的向量加法与标量乘法运算，所以高斯消元不改变矩阵的行向量表出的线性空间。于是，简化阶梯形矩阵的所有非零行向量就是该线性空间的一个基，非零行向量的个数就是矩阵的秩。

【例题】装备购买 BZOJ4004

脸哥最近在玩一款神奇的游戏，这个游戏里有 $n$ 件装备，每件装备有 $m$ 个属性，用向量 $z[i] = (a_{i,1}, a_{i,2}, \dots, a_{i,m})$ 表示，每件装备需要花费 $c_i$ 。现在脸哥想买一些装备，但是脸哥很穷，所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。对于脸哥来说，如果一件装备的属性能用购买的其他装备组合出（也就是说脸哥可以利用手上的这

些装备组合出这件装备的效果), 那么这件装备就没有买的必要了。严格的定义是, 如果脸哥买了 $z[i_1], z[i_2], \dots, z[i_p]$ 这 $p$ 件装备, 并且不存在实数 $b_1, b_2, \dots, b_p$ 使得 $z[k] = b_1z[i_1] + b_2z[i_2] + \dots + b_pz[i_p]$ , 那么脸哥就会买 $z[k]$ , 否则 $z[k]$ 对脸哥就是有用的。脸哥想要在买下最多数量的装备的前提下花最少的钱, 你能帮他算一下吗? $1 \leq n, m \leq 500, 0 \leq a_{i,j} \leq 1000$ 。

把 $n$ 件装备看作 $n$ 个长度为 $m$ 的向量，根据题意，购买的装备对应的向量应该是线性无关的。要买下最多数量的装备，就是求这 $n$ 个向量表出的线性空间的基。

把 $a_{i,j}(1 \leq i \leq n, 1 \leq j \leq m)$ 看作系数矩阵，则每个装备 $z_i$ 都是一个行向量。用高斯消元求出该矩阵的秩，就得到了能买下的装备的最多数量。

本题还要求花最少的钱。我们只需要在高斯消元的过程中，使用贪心策略，对于每个主元 $x_{i}$ ，在前 $i - 1$ 列为0、第 $i$ 列不为0的行向量中，选择价格最低的一个，消去其他行中第 $i$ 列的值。

该贪心策略可用反证法证明。假设花费价钱最少的基底是 $z[i_1], z[i_2], \dots, z[i_p]$ ，其中不包含价格最低的行向量 $z[k]$ 。因为基底是极大线性无关子集，所以 $z[k]$ 能被 $z[i_1], z[i_2], \dots, z[i_p]$ 表出，不妨设 $z[k] = b_1z[i_1] + b_2z[i_2] + \dots + b_pz[i_p]$ 。

移项变换可得 $z[i_p] = (z[k] - b_1z[i_1] - \dots -b_{p - 1}z[i_{p - 1}]) / b_p$ ，即 $z[i_p]$ 能被 $z[k]$ 和 $z[i_1],z[i_2],\dots ,z[i_{p - 1}]$ 表出。故 $z[k],z[i_1],z[i_2],\dots ,z[i_{p - 1}]$ 能与 $z[i_1],z[i_2],\dots ,z[i_p]$ 表出相同的线性空间，是一个总价格更低的基底，与假设矛盾。实现细节请参阅配套光盘中的程序。

线性空间的概念可以进一步推广，不仅限于向量、向量加法和标量乘法。例如“异或空间”就是一个很常见的形式。异或空间是一个关于异或运算封闭的非负整数集合。可以在异或空间中用类似的方法定义“表出”“线性无关”“基底”等。

若整数 $b$ 能由整数 $a_1, a_2, \dots, a_k$ 经异或运算得出，则称 $b$ 能被 $a_1, a_2, \dots, a_k$ 表出。 $a_1, a_2, \dots, a_k$ 能表出的所有整数构成一个异或空间， $a_1, a_2, \dots, a_k$ 被称为这个异或空间的生成子集。

任意选出异或空间中的若干个整数，如果其中存在一个整数能被其他整数表出，则称这些整数线性相关，否则称这些整数线性无关。异或空间的基就是异或空间中一个线性无关的生成子集，或者定义为异或空间的极大线性无关子集。

给定 $n$ 个 $0 \sim 2^{m} - 1$ 之间的整数 $a_{1}, a_{2}, \dots, a_{n}$ , 如何求出这 $n$ 个整数表出的异或空间的基? 我们可以把它们看作 $m$ 位二进制数, 写成一个 $n$ 行 $m$ 列的 01 矩阵, 矩阵中第 $i$ 行从左到右依次是 $a_{i}$ 的第 $m - 1, m - 2, \dots, 1, 0$ 位 (二进制数的最低位称为第 0 位)。把矩阵作为系数矩阵, 用高斯消元求解异或方程组的方法, 将其转化为简化阶梯形矩阵。简化阶梯形矩阵的每一行也是一个整数, 所有非零整数一起构成异或空

间的基。

【例题】XOR HDOJ3949

有 $n$ 个整数 $a_1, a_2, \dots, a_n$ 和 $m$ 个询问，每个询问给出一个整数 $k$ ，求从 $a_1, a_2, \dots, a_n$ 中选出若干个数执行异或运算能够得到的整数集合中（去掉重复的数），第 $k$ 小的整数是多少。 $1 \leq n, m \leq 10000, 1 \leq a_i, k \leq 10^{18}$ 。

用高斯消元求出 $a_1, a_2, \dots, a_n$ 构成的异或空间的基。不妨设这个基由整数 $b_1, b_2, \dots, b_t$ 构成，其中 $b_1 > b_2 > \dots > b_t$ 。从基底中选取若干个整数，显然有 $2^t$ 种取法，因此 $t$ 维异或空间中共有 $2^t$ 个整数，与这 $2^t$ 种取法一一对应。

在上面的高斯消元过程中，共有 $t$ 个主元，分别是 $b_{1}, b_{2}, \dots, b_{t}$ 的最高位。设它们的最高位分别是第 $c_{1}, c_{2}, \dots, c_{t}$ 位，显然 $c_{1} > c_{2} > \dots > c_{t}$ 。

我们之前提到过，在简化阶梯形矩阵中，对于每个主元，有且仅有一个位置 $(i,j)$ 满足该主元的系数非零。第 $j$ 列的其他位置都是0，第 $i$ 行的第 $1\sim j - 1$ 列都是0。也就是说，在 $b_{1}, b_{2}, \dots, b_{t}$ 中，有且仅有 $b_{i}$ 的第 $c_{i}$ 位是1，其他数的第 $c_{i}$ 位都是0。

例如整数5,12,2,7,9写成的01矩阵，以及高斯消元得到的简化阶梯形矩阵如下：

异或空间的基是9,5,2，最高位的1分别在第3位、第2位、第1位，自由元是第0位。可以看到，只有9的第3位是1，5和2的第3位都是0，即满足“主元所在位为1”的整数是唯一的。

因为基底 $b_{1}, b_{2}, \cdots, b_{t}$ 能与 $a_{1}, a_{2}, \cdots, a_{n}$ 表出相同的异或空间，所以异或空间中第 $k$ 小的整数，就是从 $b_{1}, b_{2}, \cdots, b_{t}$ 中选出若干个数做异或运算，能表出的第 $k$ 小的整数。而第 $c_{1}$ 位是 1 的只有 $b_{1}$ ，所以选取 $b_{1}$ 一定比不选 $b_{1}$ 得到的数更大。同理，在选了 $b_{1}$ 之后，选取 $b_{2}$ 一定比不选 $b_{2}$ 得到的数更大。异或空间中最大的数就是 $b_{1}, b_{2}, \cdots, b_{t}$ 全部异或起来得到的数。

综上所述，我们把询问中给出的 $k - 1$ 进行二进制分解（减掉1是为了把最小的数定义为第0小，题目中是第1小），如果 $k - 1$ 的第 $j$ $(0\leq j < t)$ 位等于1，就选取 $b_{t - j}$ ，最后把所有选出的 $b$ 异或起来，就得到了答案。特别地，若 $k > 2^t$ ，则无解。

值得注意的一点边界情况是，异或空间中第 $k$ 小的整数与题目中所求的第 $k$ 小的整数稍有不同。题目不允许 $a_{i}$ xor $a_{i}$ 这样的运算，而异或空间中允许。造成的差

别是异或空间一定包含整数0，但从 $a_1, a_2, \dots, a_n$ 选出几个不同的数异或，可能得不到0。实际上，我们检查简化阶梯形矩阵中是否存在“零行”，即可判断能否得到0。若不能得到0，就把 $k$ 而不是 $k - 1$ 进行二进制分解（相当于在统计顺序时跳过“0”这个数）。

unsigned long long a[10010];  
int n, m, t, T;  
int main() {  
cin >> T;  
for (int C = 1; C <= T; C++) {  
cin >> n;  
for (int i = 1; i <= n; i++) scanf("%I64u", &a[i]);  
bool zero = 0;  
t = n;  
for (int i = 1; i <= n; i++) {  
for (int j = i + 1; j <= n; j++)  
if (a[j] > a[i]) swap(a[i], a[j]);  
if (a[i] == 0) {  
zero = 1, t = i - 1;  
break;  
}  
for (int k = 63; k >= 0; k--)  
if (a[i] >> k & 1) {  
for (int j = 1; j <= n; j++)  
if (i != j && (a[j] >> k & 1)) a[j] ^= a[i];  
break;  
}  
}  
cin >> m;  
printf("Case %d:\\n", C);  
while (m--){  
unsigned long long k, ans = 0;  
scanf("%I64u", &k);  
if (zero) k--;  
if (k >= 11lu << t) puts("-1");  
else {  
for (int i = t - 1; i >= 0; i--)  
if (k >> i & 1) ans ^= a[t - i];

printf("%I64u\n",ans); } 1 1

本题中讨论的“异或空间”是一个“去重异或集合”，它包含 $2^{t}$ 个互不相等的整数。我们还可以进一步关注包含 $2^{n}$ 个整数（可能相等）的“不去重异或集合”的形态。

一定能从 $a_1, a_2, \dots, a_n$ 中找出 $t$ 个线性无关的整数，构成异或空间的一个基。不在基底中的整数还有 $n - t$ 个，从这 $n - t$ 个整数中选出若干个，显然有 $2^{n - t}$ 种选法。

对于任意一种选法，设选取的整数异或起来得到 $x$ ，把基底能表出的 $2^{t}$ 个互不相等的整数与 $x$ 分别异或，又得到 $2^{t}$ 个整数。因为当 $y \neq z$ 时，必然有 $x \text{ XOR } y \neq x \text{ XOR } z$ ，所以刚刚得到的 $2^{t}$ 个整数也互不相等。换言之，每种取法与基底相组合，恰好遍历“去重异或集合”一次。

综上所述，“不去重异或集合”就是“去重异或集合”中的 $2^{t}$ 个整数各重复 $2^{n - t}$ 次形成的。