矩阵 (Matrix)

Created at 2022-01-20 22:16:21
Updated at 2023-10-30

请阅读这篇文章作为前置知识.

矩阵是矩形的数表, 横为行, 竖为列, 对于一个 $n$ 行 $m$ 列的矩阵, 我们表示为 $n \times m$ 矩阵, 读作 “n by m matrix”. 特别地, $n \times n$ 的矩阵被称为 $n$ 阶方阵.

矩阵 $A$ 的第 $i$ 行第 $j$ 列的元素可以表示为 $A_{i, j}$. 对于方阵 $A$, 所有形如 $A_{i, i}$ 的元素构成了 $A$ 的主对角线 (main diagonal).

根据前面我们介绍的向量的定义, 我们发现矩阵本身也是向量的一种, 具有相加和数乘运算且结果仍在同一个向量空间内. 对于仅一行的矩阵, 称为行向量, 仅一列的矩阵, 称为列向量.

定义矩阵的子矩阵为这个矩阵去掉一些行或列得到的矩阵.

矩阵乘法

相对于向量本身具有的线性运算, 矩阵还有一个重要运算: 矩阵乘法.

对于 $m \times n$ 矩阵 $A$, $n \times p$ 矩阵 $B$, 定义矩阵乘法运算为:

$[AB]_{i,j} = \sum_{r = 1}^n A_{i,r}B_{r,j}$

$AB$ 是一个 $m$ 行 $p$ 列的矩阵, 矩阵乘法不满足交换律, 满足分配律和结合律.

矩阵乘法的单位矩阵 $I_n$ 是一个 $n$ 阶方阵, 主对角线全为 $1$, 其余部分为 $0$. 满足对于任意有 $n$ 列的矩阵 $A$, $AI = A$, 对于任意有 $n$ 行的矩阵 $B$, $IB = B$.

矩阵与线性映射

我们之前提到线性映射是函数, 将一个向量空间内的向量映射到另一个向量空间中. 结合矩阵乘法, 我们发现矩阵恰恰是一种线性映射.

当我们用一个 $1 \times n$ 的行向量 $A$ 乘一个 $n \times m$ 的矩阵 $B$ 时, 我们可以得到一个 $1 \times m$ 的行向量 $C$.

$C_i = \sum_{j = 1}^n A_jB_{j, i}$

因此矩阵 $B$ 就是线性映射 $f(A) = A \times B = C$.

结合矩阵也是向量的特征, 我们推广到一般情况, 线性映射也是向量, 具备线性运算, 可以构成向量空间.

逆矩阵

一个矩阵的乘法逆元是它的逆矩阵 (Inverse Matrix), 只有方阵存在逆矩阵, 定义为 $A^{-1}A = I$.

我们把 $A$ 和 $I$ 并排放在一起, 组成 $n$ 行, $2n$ 列的矩阵. 用高斯消元把第 $i$ 行除第 $i$ 项和后 $n$ 项以外的项变成 $0$. 然后第 $i$ 行乘以相应的倍数把第 $i$ 项变成 $1$. 只要得到的左边 $n$ 列是 $I$, 那么右边 $n$ 列就是 $A^{-1}$.

求逆矩阵的过程就是高斯消元的过程, 复杂度 $O(n^3)$. 下面是模板题代码:

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

const unsigned long long Mod(1000000007);
unsigned long long a[405][805];
unsigned A, B, C, D, t, m, n;
unsigned Cnt(0), Ans(0), Tmp(0);
unsigned long long Pow(unsigned long long x, unsigned y) {
  unsigned long long Rt(1);
  while (y) { if (y & 1) Rt = Rt * x % Mod; x = x * x % Mod, y >>= 1; }
  return Rt;
}
signed main() {
  m = ((n = RD()) << 1);
  for (unsigned i(1); i <= n; ++i) for (unsigned j(1); j <= n; ++j) a[i][j] = RD();
  for (unsigned i(1); i <= n; ++i) for (unsigned j(n + 1); j <= m; ++j) a[i][j] = 0;
  for (unsigned i(1); i <= n; ++i) a[i][n + i] = 1;
  for (unsigned i(1); i <= n; ++i) {
    unsigned No(i);
    while ((!a[No][i]) && (No <= n)) ++No;
    if (No > n) { printf("No Solution\n");return 0; }
    if (No ^ i) for (unsigned j(i); j <= m; ++j) swap(a[No][j], a[i][j]);
    for (unsigned j(i + 1); j <= n; ++j) {
      unsigned long long Tms(a[j][i] * (Mod - Pow(a[i][i], Mod - 2)) % Mod);
      for (unsigned k(i); k <= m; ++k) a[j][k] = (a[j][k] + a[i][k] * Tms) % Mod;
    }
  }
  for (unsigned i(n); i; --i) {
    if (!a[i][i]) { printf("No Solution\n");return 0; }
    unsigned long long Chg(Pow(a[i][i], Mod - 2));
    if (Chg != 1) for (unsigned j(i); j <= m; ++j) a[i][j] = a[i][j] * Chg % Mod;
    for (unsigned j(i - 1); j; --j) {
      for (unsigned k(n + 1); k <= m; ++k) a[j][k] = (a[j][k] + a[i][k] * (Mod - a[j][i])) % Mod;
      a[j][i] = 0;
    }
  }
  for (unsigned i(1); i <= n; ++i) { for (unsigned j(n + 1); j <= m; ++j) printf("%llu ", a[i][j]); putchar(0x0A); }
  return Wild_Donkey;
}

转置

对于 $n \times m$ 矩阵 $A$, 它的转置 (transposition) 矩阵 $A^{T}$ 是一个 $m \times n$ 矩阵, 定义为:

$(A^T)_{i, j} = A_{j, i}$

容易理解, 矩阵转置对于矩阵的线性运算具有结合律和分配律.

秩

矩阵的秩 (Rank) 定义为最多找出多少行使得它们两两线性无关. 一个矩阵的秩等于它转置矩阵的秩. 把一个矩阵高斯消元后不全为 $0$ 的行的数量就是这个矩阵的秩.