线性代数2 矩阵

任意 nn 维向量 (a0,a1,a2,...,an−1)(a_0, a_1, a_2,...,a_{n - 1}), (b0,b1,b2,...,bn−1)(b_0, b_1, b_2,...,b_{n - 1}), 其点乘定义为 ∏i=0n−1ai+∏i=0n−1bi\prod_{i = 0}^{n - 1} a_i + \prod_{i = 0}^{n - 1} b_i.

Matrix Multiplication

对于 mm 行 nn 列的矩阵 AA, nn 行 oo 列的矩阵 BB, 定义矩阵乘法运算为:

[AB]i,j=∑k=1nAi,kBk,j[AB]_{i,j} = \sum_{k = 1}^n A_{i,k}B_{k,j}

ABAB 是一个 mm 行 oo 列的矩阵, 矩阵乘法不满足交换律, 满足分配律和结合律.

矩阵乘法的单位矩阵 InI_n 是一个 n∗nn * n 的矩阵, 其左上右下对角线为 11, 其余部分为 00. 满足对于任意有 nn 列的矩阵 AA, AI=AAI = A, 对于任意有 nn 行的矩阵 BB, IB=BIB = B.

Inverse Matrix

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

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

求逆矩阵的过程就是高斯消元的过程, 复杂度 O(n3)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;
}

Rank

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