「算法笔记」矩阵

矩阵是一个非常有用的工具,经常可以用于几何与代数之间的转化,以此来优化算法。


定义

在数学中,矩阵是一个按照长方阵列排列的复数或实数集合。一个 $n\times m$ 的矩阵一般这样表示:

$$ A_{nm}=\begin{bmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1m} \\ a_{21} & a_{22} & a_{23} & \cdots & a_{2m} \\ a_{31} & a_{32} & a_{33} & \cdots & a_{3m} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & a_{n3} & \cdots & a_{nm} \\ \end{bmatrix} $$

如果一个矩阵的行数和列数都等于 $n$,那么称这个矩阵为 $n​$ 阶矩阵


运算

加法减法

同型矩阵之间可以进行加减法,运算法则为:

$$ C_{ij}=A_{ij}\pm B_{ij} $$

乘法

一个 $n\times m$ 的矩阵 $A$ 可以和一个 $m\times p$ 的矩阵 $B$ 进行乘法运算,得到一个 $n\times p$ 的矩阵 $C$,运算法则为:

$$ C_{ij}=\sum_{k=1}^m A_{ik}\times B_{kj} $$


特殊矩阵

注意:以下矩阵中,没有明确标识的位置均表示 $0$!

初等矩阵

单位矩阵

$$ P=\begin{bmatrix} 1 & & & \\ & 1 & & \\ & & 1 & \\ & & & 1 \\ \end{bmatrix} $$

特征:除了主对角线上的元素为 $1$,其他元素均为 $0$。一般我们用字母 $E$ 来表示单位矩阵。

作用:$P$ 左乘 $A$ 矩阵,所得的结果还是 $A$ 矩阵本身。所以我们可以认为 $E$ 是矩阵乘法的单位元

交换某两行

$$ P=\begin{bmatrix} 1 & & & \\ & 0 & 1 & \\ & 1 & 0 & \\ & & & 1 \\ \end{bmatrix} $$

特征:在单位矩阵的基础上,将第 $i$ 个 $1$ 向右移动一位,将第 $j$ 个 $1​$ 向左移动一位。

作用:$P$ 左乘 $A$ 矩阵,可以将 $A$ 的第 $i$ 行和第 $j​$ 行交换。

将一行的所有元素乘上 k

$$ P=\begin{bmatrix} 1 & & & \\ & 1 & & \\ & & k & \\ & & & 1 \\ \end{bmatrix} $$

特征:在单位矩阵的基础上,将第 $i$ 个 $1$ 乘上 $k$。

作用:$P$ 左乘 $A$ 矩阵,可以将 $A$ 的第 $i$ 行的所有元素乘上 $k​$。

将一行的所有元素乘上 k 加到另一行去

$$ P=\begin{bmatrix} 1 & & k & \\ & 1 & & \\ & & 1 & \\ & & & 1 \\ \end{bmatrix} $$

特征:在单位矩阵的基础上,将第 $i$ 行第 $j$ 列的位置变为 $k​$(这个位置不在对角线上)

作用:$P$ 左乘 $A$ 矩阵,可以将 $A$ 矩阵的第 $j$ 行的所有元素乘上 $k$ 加到第 $i$ 行去。

上三角矩阵

$$ P=\begin{bmatrix} 1 & 0 & 5 & 0 \\ & 4 & 7 & 0 \\ & & 9 & 7 \\ & & & 5 \\ \end{bmatrix} $$

特征:除了主对角线及以上的元素(可以为 $0$ 也可以不为 $0$)外,其他元素均为 $0$。

作用:矩阵的秩、高斯消元、求行列式等中的重要矩阵!


初等变换

定义

我们定义矩阵的三种初等行变换:

  1. 换行变换:交换某两行。
  2. 倍法变换:将某一行的所有元素乘上 $k$(其中 $k\neq 0$)。
  3. 消法变换:将某一行的所有元素乘上 $k$ 后加到另一行上去。

本质

其实这三种初等行变换和上文的特殊矩阵是有联系的:初等行变换的本质是用初等矩阵左乘矩阵 $A$。那么很显然,初等列变换的本质是用初等矩阵右乘矩阵 $A$。


矩阵的秩分为行秩和列秩。一个矩阵 $A$ 的行秩是 $A$ 的线性无关独立的横行的极大数目;类似的,列秩是 $A$ 的线性无关独立的纵列的极大数目。

对于同一个矩阵而言,其行秩总是等于列秩的。


相抵

如果矩阵 $A$ 可以通过一系列初等行变换和初等列变换变成矩阵 $B$,则称 $A$ 和 $B$ 是相抵的。


可逆

对于一个矩阵 $A$,其可逆的充要条件是 $A$ 和 $E$ 是相抵的(即 $A$ 通过若干次初等行变换可以变成 $E$),也就是说存在一个矩阵 $P$ 使得 $PA=E$,则 $P=A^{-1}$。

有关矩阵求逆的相关过程详见:「算法笔记」矩阵求逆,其中有具体讲解如何方便地求一个矩阵的逆矩阵。


行列式

行列式是一个函数,结果是一个值。矩阵 $A$ 的行列式写作 ​$\det(A)$ 或 $\vert A\vert​$。

一个矩阵的行列式求解公式为:

$$ \det(A)=\sum_{\forall P} [(-1)^{\tau(P)}\prod_{i=1}^n A_{i,P_i}] $$

其中 $\tau(P)$ 表示排列 $P$ 的逆序对数量。

阶数较小的矩阵可以手动求解行列式,比如二阶矩阵的行列式为:

$$ \det(A)=A_{11}A_{22}-A_{12}A_{21} $$

有关行列式的具体求解过程详见:「算法笔记」行列式,其中有具体讲解如何快速地求一个矩阵的行列式。


等价命题

以下这些命题均是等价的,即是彼此的充要条件!

  • 矩阵满秩。
  • 矩阵是可逆的。
  • 矩阵的行列式不为 $0$。

板子

为了方便大家使用,笔者把自己的矩阵板子放在博客里!(可能会更新)

void add(int &x, int y) {
    (x += y) >= mod && (x -= mod);
}
struct Matrix {
    int n, A[N][N];
    Matrix(int _n = 0) {
        n = _n, memset(A, 0, sizeof(A));
    }
    void operator~() {
        for (int i = 0; i < n; i++) A[i][i] = 1;
    }
    Matrix operator+(const Matrix &b) const {
        Matrix ret(n);
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            ret.A[i][j] = (A[i][j] + b.A[i][j]) % mod;
        }
        return ret;
    }
    Matrix operator-(const Matrix &b) const {
        Matrix ret(n);
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            ret.A[i][j] = (A[i][j] - b.A[i][j] + mod) % mod;
        }
        return ret;
    }
    Matrix operator*(const Matrix &b) const {
        Matrix ret(n);
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++) {
            add(ret.A[i][k], 1LL * A[i][j] * b.A[j][k] % mod);
        }
        return ret;
    }
    Matrix operator^(const long long &b) const {
        Matrix ret(n), x = *this;
        ~ret;
        for (long long p = b; p; p >>= 1, x = x * x) {
            if (p & 1) ret = ret * x;
        }
        return ret;
    }
    void print() {
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            printf("%d%c", A[i][j], " \n"[j == n - 1]);
        }
    }
};

发表评论