西北工业大学NOJ平台：行列式值

发表于

前言

计算行列式的值是线性代数中非常重要的一个知识点，由于个人能力限制，我一直都没有完成这道题目。好在有一位已经自学了线性代数的同学帮忙，我完成了这道题目。本篇文章不只会展示题解，也会同时解释清楚行列式的值的计算方法，并介绍行列式的部分实际应用。

前置知识

逆序对数

对于一个数列{a1, a2, a3 ... an}来说，其中的子数对(ai, aj)若其满足i < j且ai > aj，则称其为一个逆序对，一个数列的逆序对数为其包含逆序对的总数，记作t(a1, a2 ... an)。

举个例子，对于{4, 8, 2, 10, 7}来说，其满足条件的逆序对为(4, 2),(8, 2),(8, 7),(10, 7)，故其逆序对数为4。

计算一组随机数据的逆序对数最快的算法是仿照归并排序的分治法，复杂度为O(NlogN)。

行列式的值

行列式是一个N阶方阵A，第i行第j列的元素记作a(i, j)，的其值D是由该方阵确定的一个值，记作det(A)。

方阵

现说明其值的计算方法如下：

  1. 数列B为{1, 2, 3 ... N}，N为方阵大小。
  2. 对数列B的所有元素进行排列，一共有A(N, N)种排列方式，A(N, N)指的是排列数；
  3. 记其中一种排列方式为C，则其对应的数列为{c1, c2, c3 ... cN}，现计算表达式a(1, c1) * a(2, c2) * a(3, c3) ... * a(N, cN) * (-1 ^ t(c1, c2, c3 ... cN))的值。
  4. 将所有排列方案的表达式值相加，将该值记作det(A)，这就是行列式的值。

手算行列式

三角形行列式的值为其对角线乘积

三角形行列式的值为其对角线乘积

行列式的倍乘性质

将行列式的某一行（或某一列）中所有元素同乘以一个常数k，则行列式的值对应也乘上k倍。

行列式的倍乘性质

行列式的累加性质

将行列式某一行（或某一列）的所有元素都乘上k后，
再加到另一行（或另一列）的对应元素上，行列式值不变。

行列式的累加性质

计算示例

计算示例

如上方所示，通过以上性质，将行列式化为三角形，并直接计算对角线元素乘积。

行列式的应用

一个最常见的应用是计算N元线性方程组的解，下图展示了解三元方程的过程，更高元的方程组同理：
解方程组

这里就不对结论做证明了，感兴趣的朋友可以自己证明试试。

题面描述

题面描述

题解：定义法计算和手算法计算

定义法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
using namespace std;

vector<vector<long long>> matrix;
long long result = 0;
int width;

// 计算这个数的逆序对数
int countReversePairs(int index, vector<bool> visList) {
    int result = 0;
    for (int i = index + 1; i < visList.size(); i++) {
        result += visList[i] ? 1 : 0;
    }
    return result;
}

// 逐个组合计算乘积值并累加
void countMatrix(int currRow, int currReverseCnt, long long currMult, vector<bool> visList) {
    if (currRow < width) {
        for (int i = 0; i < visList.size(); i++) {
            if (!visList[i]) {
                vector<bool> newList(visList);
                newList[i] = true;
                countMatrix(currRow + 1, currReverseCnt + countReversePairs(i, visList), currMult * matrix[currRow][i], newList);
            }
        }
    }
    else {
        result += currMult * (currReverseCnt & 1 ? -1 : 1);
    }
}

int main() {
    cin >> width;
    matrix.resize(width, vector<long long>());
    for (int i = 0; i < width; i++) {
        matrix[i].resize(width, 0);
        for (int j = 0; j < width; j++) {
            long long curr; cin >> curr;
            matrix[i][j] = curr;
        }
    }
    // 初始化矩阵
    vector<bool> visList;
    visList.resize(width, false);
    countMatrix(0, 0, 1, visList);
    // 计算结果
    cout << result;
    return 0;
}

运用countMatrix()的递归操作，在过程中记录列的访问情况visList，来遍历所有的可能组合，最后计算表达式并累加。

计算逆序对数是在递归的过程中完成的，当有新元素添加时，计算该元素前面比它大的数的个数，并累加。

手算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int main() {
	int n, count = 0;
	cin >> n;
	double result = 1;
	vector<vector<double>>juzhen(n, vector<double>(n));
	//初始化
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> juzhen[i][j];
		}
	}
	//调整
	for (int i = n-1; i>=0; i--) {
		for (int j =n-1; j>=0; j--) {
			if (!juzhen[i][i] && juzhen[j][i]) {
				for (int k = 0; k < n; k++) {
					int tem = juzhen[i][k];
					juzhen[i][k] = juzhen[j][k];
					juzhen[j][k] = tem;
				}
				count++;
				continue;
			}
		}
	}
	//计算
	for (int k = 0; k < n; k++) {
		for (int i = n - 1; i > k; i--) {
			for (int j = n - 1; j >= k; j--) {
				if (!juzhen[k][k]) { continue; }
				juzhen[i][j] -= juzhen[i][k] * juzhen[k][j] / juzhen[k][k];
			}
		}
	}
	//打印
	for (int i = 0; i < n; i++) {
		result *= juzhen[i][i];
	}
	cout << result * pow(-1, count) << endl;
	return 0;
}

其中，手算法的过程由那位热心同学提供。

主要是以将矩阵转化为三角形的思路，另外他的算法在对角线上有0时会出现问题，所以他在对角线上有0时将其交换到了其它行来保障程序稳定运行。

后记

这篇文章介绍了行列式是什么，其值的两个计算方法和它的一个常见应用，并给出了NOJ上行列式值题目的题解。

在此感谢那位热心同学，学习的过程离不开合作和交流，只有积极沟通才能更好地促进思想的进步。
交流

另外，本篇文章引用了：

不得不说知乎上的很多数学内容还是相当可以的。