行列式(Determinant)入门

行列式的概念

\(n\) 阶行列式

二阶行列式

由 \(2^2\) 个数排列成的两行两列，记作： \[ \begin{vmatrix} a_1 & a_2\\ b_1 & b_2 \end{vmatrix} = a_1b_2-a_2b_1 \] 其几何意义是平面直角坐标系 \(xoy\) 上以 \(a=(a_1, a_2) \quad b=(b_1, b_2)\) 为邻边的平行四边形的有向面积。

三阶行列式

由 \(3^3\) 个数排列成的三行三列，其几何意义为其行向量（列向量）所张成的平行六面体的有向体积。

\(n\) 阶行列式

由 \(n^n\) 个数排列成的 \(n\) 行 \(n\) 列，记作： \[ \begin{vmatrix} a_{1, 1}&a_{1, 2}&\dots&a_{1, n}\\ a_{2, 1}&a_{2, 2}&\dots&a_{2, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n, 1}&a_{n, 2}&\dots&a_{n, n}\\ \end{vmatrix}\\ 常记作\quad D\quad或\quad D=\det(a_{ij}) \] 它的值为所有不同行列 \(n\) 个元素的代数和，即：

\[ \sum_P=[(-1)^{\tau(P)}\prod_{i=1}^na_{i,p_i}] \] 其中 \(P\) 表示 \(1\) 到 \(n\) 的全排列。

行列式的性质

所有性质均可以通过定义证明其正确性。

性质一

行列式与其转置行列式相等： $$ D= \[\begin{vmatrix} a_{1, 1}&a_{1, 2}&\dots&a_{1, n}\\ a_{2, 1}&a_{2, 2}&\dots&a_{2, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n, 1}&a_{n, 2}&\dots&a_{n, n}\\ \end{vmatrix}\quad\] D^T= \[\begin{vmatrix} a_{1, 1}&a_{2, 1}&\dots&a_{n, 1}\\ a_{1, 2}&a_{2, 2}&\dots&a_{n, 2}\\ \vdots&\vdots&\ddots&\vdots\\ a_{1, n}&a_{2, n}&\dots&a_{n, n}\\ \end{vmatrix}\]

\ D=D^T\ D^T表示D的转置行列式 $$

性质二

\[ \begin{vmatrix} a_{1, 1}&a_{1, 2}&\dots&a_{1, n}\\ \vdots&\vdots&\ddots&\vdots\\ b_1+c_1&b_2+c_2&\dots&b_n+c_n\\ \vdots&\vdots&\ddots&\vdots\\ a_{n, 1}&a_{n, 2}&\dots&a_{n, n}\\ \end{vmatrix}=\begin{vmatrix} a_{1, 1}&a_{1, 2}&\dots&a_{1, n}\\ \vdots&\vdots&\ddots&\vdots\\ b_1&b_2&\dots&b_n\\ \vdots&\vdots&\ddots&\vdots\\ a_{n, 1}&a_{n, 2}&\dots&a_{n, n}\\ \end{vmatrix}+\begin{vmatrix} a_{1, 1}&a_{1, 2}&\dots&a_{1, n}\\ \vdots&\vdots&\ddots&\vdots\\ c_1&c_2&\dots&c_n\\ \vdots&\vdots&\ddots&\vdots\\ a_{n, 1}&a_{n, 2}&\dots&a_{n, n}\\ \end{vmatrix} \]

性质三

\[ \begin{vmatrix} a_{1, 1}&a_{1, 2}&\dots&a_{1, n}\\ \vdots&\vdots&\ddots&\vdots\\ ka_{i, 1}&ka_{i, 2}&\dots&ka_{i, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n, 1}&a_{n, 2}&\dots&a_{n, n}\\ \end{vmatrix}=k\begin{vmatrix} a_{1, 1}&a_{1, 2}&\dots&a_{1, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{i, 1}&a_{i, 2}&\dots&a_{i, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n, 1}&a_{n, 2}&\dots&a_{n, n}\\ \end{vmatrix} \]

特别地，当\(k = 0\) 可知如果该行列式中有一行或一列全为零，那么该行列式为零。

性质四

如果行列式中有两行（两列）完全相同，那么该行列式为零。

可以看作一个 \(n\) 维的空间少一个维度，那么它在 \(n\) 维空间中是没有体积的。

用定义来证明：

必定存在两个不同的排列 \(P\) 使得 \(\prod a_{p_i,i}\) 是相同的，只用证明 \(\tau(P)\) 的奇偶性不同即可。

对于排列\((i<j)\)： \[ P_1\ =\ \dots\quad i \quad \dots\quad j\quad \dots\\ P_2\ =\ \dots\quad j \quad \dots\quad i\quad \dots\\ \] 显然首位两端对逆序数没有影响，令中间一段有 \(a\) 个数小于 \(i\)， \(b\) 个数 大于 \(i\) 小于 \(j\)， \(c\) 个数大于 \(j\) ，那么 有： \[ \tau_{P_2}=\tau_{P_1}+((-a)+b+c)+(a+b+(-c))+1=\tau_{P_1}+2b+1 \] 所以 \(\tau_P\) 的奇偶性不同。

又因为所有的排列都可以均分为 \(\tau_p\ \& \ 1 \ =\ 1\) 和 \(\tau_P \ \& \ 1\ =\ 0\)，两组，所以行列式代数和为零。

性质五

如果行列式中有两行或两列成等比数列那么行列式为零。 \[ \begin{vmatrix} a_{1, 1}&a_{1, 2}&\dots&a_{1, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{i, 1}&a_{i, 2}&\dots&a_{i, n}\\ \vdots&\vdots&\ddots&\vdots\\ ka_{i, 1}&ka_{i, 2}&\dots&ka_{i, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n, 1}&a_{n, 2}&\dots&a_{n, n}\\ \end{vmatrix} = k\begin{vmatrix} a_{1, 1}&a_{1, 2}&\dots&a_{1, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{i, 1}&a_{i, 2}&\dots&a_{i, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{i, 1}&a_{i, 2}&\dots&a_{i, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n, 1}&a_{n, 2}&\dots&a_{n, n}\\ \end{vmatrix} = 0 \]

性质六

把一行的倍数加到另一行，行列式不变： \[ \begin{vmatrix} a_{1, 1}&a_{1, 2}&\dots&a_{1, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{i, 1}&a_{i, 2}&\dots&a_{i, n}\\ \vdots&\vdots&\ddots&\vdots\\ ka_{i, 1}+a_{j, 1}&ka_{i, 2}+a_{j,2}&\dots&ka_{i, n}+a_{j,n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n, 1}&a_{n, 2}&\dots&a_{n, n}\\ \end{vmatrix}=\begin{vmatrix} a_{1, 1}&a_{1, 2}&\dots&a_{1, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{i, 1}&a_{i, 2}&\dots&a_{i, n}\\ \vdots&\vdots&\ddots&\vdots\\ ka_{i, 1}&ka_{i, 2}&\dots&ka_{i, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n, 1}&a_{n, 2}&\dots&a_{n, n}\\ \end{vmatrix}+\begin{vmatrix} a_{1, 1}&a_{1, 2}&\dots&a_{1, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{i, 1}&a_{i, 2}&\dots&a_{i, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{j, 1}&a_{j, 2}&\dots&a_{j, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n, 1}&a_{n, 2}&\dots&a_{n, n}\\ \end{vmatrix}=\begin{vmatrix} a_{1, 1}&a_{1, 2}&\dots&a_{1, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{i, 1}&a_{i, 2}&\dots&a_{i, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{j, 1}&a_{j, 2}&\dots&a_{j, n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n, 1}&a_{n, 2}&\dots&a_{n, n}\\ \end{vmatrix} \]

性质七

对换行列式中两行的位置，行列式反号。

可以根据性质六将两行不断加减得到结果。

也可以看作交换了行的编号，即逆序数的奇偶性发生改变。

代码实现

可以通过高斯消元的方法将一个行列式转化为上三角或者下三角行列式，进而计算行列式的值。

为了保留精度，可以在消元的时候采用辗转相除法逐步消元，直到出现零为止。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 600 + 10;
const int inf = 0x3f3f3f3f;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
   
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
 
    for (; o >= '0' && o <= '9'; o = getchar()) 
        x = (x << 1) + (x << 3) + (o ^ 48);
 
    return x * t;
}

ll N, Mod;
bool flag(0);
ll D[maxn][maxn];
ll Ans(1);

int main()
{

    N = __read(), Mod = __read();
    
    for (int i = 1; i <= N; ++i) 
        for (int j = 1; j <= N; ++j)
            D[i][j] = __read() % Mod;
        
    for (int i = 1; i <= N; ++i)
    {
        int k(i), j(i);
        while (!D[j][i] && j < N) ++k, ++j;
        
        if (!D[k][i])
        {
            cout << 0 << endl;
            return 0;
        }

        if (i ^ k) 
        {
            swap (D[i], D[k]);
            flag ^= 1;
        }

        for (j = i + 1; j <= N; ++j)
        {
            if (D[i][i] < D[j][i])
            {
                swap(D[i], D[j]);
                flag ^= 1;
            }

            while (D[j][i])
            {
                int times = D[i][i] / D[j][i];
                for (k = i; k <= N; ++k) D[i][k] = (D[i][k] + (Mod - times) * D[j][k] % Mod) % Mod;
                swap(D[i], D[j]);
                flag ^= 1;
            }
        }

        Ans = (Ans * D[i][i]) % Mod;
    }

    if (flag) cout << (Mod - (Ans % Mod)) % Mod << endl;
    else cout << Ans % Mod << endl;

    // system ("pause");
}