8.15.5 ACM-ICPC 线性代数 矩阵

8.15.5 ACM-ICPC 线性代数 矩阵

引言

线性代数在计算机科学和编程竞赛中扮演着重要角色，尤其是矩阵的应用。矩阵不仅仅是一个数学概念，它在图像处理、图形学、机器学习、数据分析等领域中都有广泛的应用。在ACM-ICPC中，掌握矩阵相关的知识和技巧是解决许多复杂问题的关键。

矩阵的基本概念

矩阵是一个由行和列组成的二维数组，其中每个元素可以是一个数字、变量或表达式。常见的矩阵类型包括：

• 零矩阵：所有元素都是零的矩阵。
• 对角矩阵：只有对角线上的元素非零，其他元素都是零。
• 单位矩阵：对角线上全是1，其他位置全是0。
• 转置矩阵：将矩阵的行和列互换得到的矩阵。

矩阵的运算

矩阵加法

两个相同大小的矩阵可以进行加法运算，结果是相应位置元素的和。

矩阵乘法

矩阵乘法是一个复杂但非常重要的运算。两个矩阵相乘的条件是第一个矩阵的列数等于第二个矩阵的行数。

矩阵的转置

矩阵的转置是将矩阵的行变成列，列变成行。

矩阵在ACM-ICPC中的应用

在编程竞赛中，矩阵常用于以下场景：

• 图的表示：邻接矩阵表示图中的顶点和边的关系。
• 动态规划：一些复杂的动态规划问题可以用矩阵来简化计算。
• 线性变换：在图形学中，矩阵用于描述和计算图形的变换（如旋转、缩放和平移）。

实例分析

示例1：矩阵快速幂

矩阵快速幂用于解决多次矩阵相乘的问题，提高计算效率。例如计算矩阵的N次幂可以通过快速幂算法来实现。

#include <iostream>
#include <vector>
 
using namespace std;
 
typedef vector<vector<long long>> Matrix;
 
Matrix multiply(Matrix& A, Matrix& B) {
    int n = A.size();
    Matrix C(n, vector<long long>(n, 0));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            for (int k = 0; k < n; ++k)
                C[i][j] += A[i][k] * B[k][j];
    return C;
}
 
Matrix matrix_pow(Matrix A, int p) {
    int n = A.size();
    Matrix result(n, vector<long long>(n, 0));
    for (int i = 0; i < n; ++i)
        result[i][i] = 1;
    while (p) {
        if (p & 1)
            result = multiply(result, A);
        A = multiply(A, A);
        p >>= 1;
    }
    return result;
}
 
int main() {
    Matrix A = {{1, 1}, {1, 0}};
    int n = 5;
    Matrix result = matrix_pow(A, n);
    for (auto row : result) {
        for (auto elem : row)
            cout << elem << " ";
        cout << endl;
    }
    return 0;
}

示例2：使用邻接矩阵求最短路径

邻接矩阵可以用来存储图，并通过Floyd-Warshall算法求所有点对之间的最短路径。

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int INF = 1e9;
typedef vector<vector<int>> Graph;
 
void floyd_warshall(Graph& graph) {
    int n = graph.size();
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (graph[i][k] < INF && graph[k][j] < INF)
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
}
 
int main() {
    int n = 4;
    Graph graph = {
        {0, 3, INF, 7},
        {8, 0, 2, INF},
        {5, INF, 0, 1},
        {2, INF, INF, 0}
    };
 
    floyd_warshall(graph);
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            if (graph[i][j] == INF)
                cout << "INF ";
            else
                cout << graph[i][j] << " ";
        cout << endl;
    }
 
    return 0;
}

结论

矩阵在ACM-ICPC和实际应用中有着广泛的用途。掌握矩阵的基本概念和运算，并理解其在各种算法中的应用，可以大大提高解决复杂问题的能力。通过不断练习和应用，可以更好地掌握线性代数中的矩阵知识，为编程竞赛和实际编程打下坚实的基础。

---

8.15.5 ACM-ICPC 线性代数 矩阵

引言

本文介绍线性代数中一个非常重要的内容——矩阵（Matrix），主要讲解矩阵的性质、运算，以及矩阵乘法的一些应用。

向量与矩阵

在线性代数中，向量分为列向量和行向量。需要注意的是，在中国台湾地区关于「列」与「行」的翻译，恰好与中国大陆地区相反。本篇博客 按照中国大陆地区的习惯，采用列（column）与行（row）的翻译。

线性代数的主要研究对象是列向量，约定使用粗体小写字母表示列向量。在用到大量向量与矩阵的线性代数中，不引起混淆的情况下，在手写时，字母上方的向量记号可以省略不写。向量也是特殊的矩阵。如果想要表示行向量，需要在粗体小写字母右上方写转置记号。行向量在线性代数中一般表示方程。

矩阵的引入

矩阵的引入来自于线性方程组。与向量类似，矩阵体现了一种对数据「打包处理」的思想。例如，将线性方程组：

一般用圆括号或方括号表示矩阵。将上述系数抽出来，写成矩阵乘法的形式：

简记为：

即未知数列向量 xxx，左乘一个矩阵 AAA，得到列向量 bbb。这个式子可以认为是线性代数的基本形式。

矩阵的定义

对于矩阵 AAA，主对角线是指 Ai,iA_{i,i}Ai,i​ 的元素。一般用 III 来表示单位矩阵，就是主对角线上为 1，其余位置为 0。

同型矩阵

两个矩阵，行数与列数对应相同，称为同型矩阵。

方阵

行数等于列数的矩阵称为方阵。方阵是一种特殊的矩阵。对于「n 阶矩阵」的习惯表述，实际上讲的是 n 阶方阵。阶数相同的方阵为同型矩阵。

主对角线

方阵中行数等于列数的元素构成主对角线。

对称矩阵

如果方阵的元素关于主对角线对称，即对于任意的 iii 和 jjj，i 行 j 列的元素与 j 行 i 列的元素相等，则将方阵称为对称矩阵。

对角矩阵

主对角线之外的元素均为 0 的方阵称为对角矩阵，一般记作：

式中的 λ1,⋯ ,λn\lambda_1,\cdots,\lambda_nλ1​,⋯,λn​ 是主对角线上的元素。对角矩阵是对称矩阵。如果对角矩阵的元素均为 1，称为单位矩阵，记为 III。只要乘法可以进行，无论形状，任何矩阵乘单位矩阵仍然保持不变。

三角矩阵

如果方阵主对角线左下方的元素均为 0，称为上三角矩阵。如果方阵主对角线右上方的元素均为 0，称为下三角矩阵。两个上（下）三角矩阵的乘积仍然是上（下）三角矩阵。如果对角线元素均非 0，则上（下）三角矩阵可逆，逆也是上（下）三角矩阵。

单位三角矩阵

如果上三角矩阵 AAA 的对角线全为 1，则称 AAA 是单位上三角矩阵。如果下三角矩阵 AAA 的对角线全为 1，则称 AAA 是单位下三角矩阵。两个单位上（下）三角矩阵的乘积仍然是单位上（下）三角矩阵，单位上（下）三角矩阵的逆也是单位上（下）三角矩阵。

矩阵的运算

矩阵的线性运算

矩阵的线性运算分为加减法与数乘，它们均为逐个元素进行。只有同型矩阵之间可以对应相加减。

矩阵的转置

矩阵的转置，就是在矩阵的右上角写上转置「T」记号，表示将矩阵的行与列互换。对称矩阵转置前后保持不变。

矩阵乘法

矩阵的乘法是向量内积的推广。矩阵相乘只有在第一个矩阵的列数和第二个矩阵的行数相同时才有意义。

设 AAA 为 P×MP \times MP×M 的矩阵，BBB 为 M×QM \times QM×Q 的矩阵，设矩阵 CCC 为矩阵 AAA 与 BBB 的乘积，其中矩阵 CCC 中的第 iii 行第 jjj 列元素可以表示为：

在矩阵乘法中，结果 CCC 矩阵的第 iii 行第 jjj 列的数，就是由矩阵 AAA 第 iii 行 MMM 个数与矩阵 BBB 第 jjj 列 MMM 个数分别相乘再相加得到的。这里的相乘再相加，就是向量的内积。乘积矩阵中第 iii 行第 jjj 列的数恰好是乘数矩阵 AAA 第 iii 个行向量与乘数矩阵 BBB 第 jjj 个列向量的内积，口诀为「左行右列」。

线性代数研究的向量多为列向量，根据这样的对矩阵乘法的定义方法，经常研究对列向量左乘一个矩阵的左乘运算，同时也可以在这里看出「打包处理」的思想，同时处理很多个向量内积。矩阵乘法满足结合律，不满足一般的交换律。利用结合律，矩阵乘法可以利用快速幂的思想来优化。

矩阵乘法的优化

首先对于比较小的矩阵，可以考虑直接手动展开循环以减小常数。可以重新排列循环以提高空间局部性，这样的优化不会改变矩阵乘法的时间复杂度，但是会在得到常数级别的提升。

mat operator*(const mat& T) const {
  mat res;
  for (int i = 0; i < sz; ++i)
    for (int j = 0; j < sz; ++j)
      for (int k = 0; k < sz; ++k) {
        res.a[i][j] += mul(a[i][k], T.a[k][j]);
        res.a[i][j] %= MOD;
      }
  return res;
}

mat operator*(const mat& T) const {
  mat res;
  int r;
  for (int i = 0; i < sz; ++i)
    for (int k = 0; k < sz; ++k) {
      r = a[i][k];
      for (int j = 0; j < sz; ++j)
        res.a[i][j] += T.a[k][j] * r, res.a[i][j] %= MOD;
    }
  return res;
}

方阵的逆

方阵 AAA 的逆矩阵 PPP 是使得 A×P=IA \times P = IA×P=I 的矩阵。逆矩阵不一定存在。如果存在，可以使用高斯消元进行求解。

方阵的行列式

行列式是方阵的一种运算。

参考代码

一般来说，可以用一个二维数组来模拟矩阵。

struct mat {
  LL a[sz][sz];
 
  mat() { memset(a, 0, sizeof a); }
 
  mat operator-(const mat& T) const {
    mat res;
    for (int i = 0; i < sz; ++i)
      for (int j = 0; j < sz; ++j) {
        res.a[i][j] = (a[i][j] - T.a[i][j]) % MOD;
      }
    return res;
  }
 
  mat operator+(const mat& T) const {
    mat res;
    for (int i = 0; i < sz; ++i)
      for (int j = 0; j < sz; ++j) {
        res.a[i][j] = (a[i][j] + T.a[i][j]) % MOD;
      }
    return res;
  }
 
  mat operator*(const mat& T) const {
    mat res;
    int r;
    for (int i = 0; i < sz; ++i)
      for (int k = 0; k < sz; ++k) {
        r = a[i][k];
        for (int j = 0; j < sz; ++j)
          res.a[i][j] += T.a[k][j] * r, res.a[i][j] %= MOD;
      }
    return res;
  }
 
  mat operator^(LL x) const {
    mat res, bas;
    for (int i = 0; i < sz; ++i) res.a[i][i] = 1;
    for (int i = 0; i < sz; ++i)
      for (int j = 0; j < sz; ++j) bas.a[i][j] = a[i][j] % MOD;
    while (x) {
      if (x & 1) res = res * bas;
      bas = bas * bas;
      x >>= 1;
    }
    return res;
  }
};

矩阵乘法的应用

矩阵加速递推

以斐波那契数列（Fibonacci Sequence）为例。在斐波那契数列当中，F1=F2=1F_1 = F_2 = 1F1​=F2​=1，Fi=Fi−1+Fi−2(i≥3)F_i = F_{i - 1} + F_{i - 2}(i \geq 3)Fi​=Fi−1​+Fi−2​(i≥3)。如果有一道题目让你求斐波那契数列第 nnn 项的值，最简单的方法莫过于直接递推了。但是如果 nnn 的范围达到了 101810^{18}1018 级别，递推就不行了，此时我们可以考虑矩阵加速递推。

根据斐波那契数列递推公式的矩阵形式:

定义初始矩阵

那么，FnF_nFn​ 就等于 ans⋅basen−2\text{ans} \cdot \text{base}^{n-2}ans⋅basen−2 这个矩阵的第一行第一列元素，也就是

的第一行第一列元素。

注意

矩阵乘法不满足交换律，所以一定不能写成

的第一行第一列元素。另外，对于 n≤2n \leq 2n≤2 的情况，直接输出 1 即可，不需要执行矩阵快速幂。

为什么要乘上 base\text{base}base 矩阵的 n−2n-2n−2 次方而不是 nnn 次方呢？因为 F1,F2F_1, F_2F1​,F2​ 是不需要进行矩阵乘法就能求的。也就是说，如果只进行一次乘法，就已经求出 F3F_3F3​ 了。如果还不是很理解为什么幂是 n−2n-2n−2，建议手算一下。

下面是求斐波那契数列第 nnn 项对 109+710^9+7109+7 取模的示例代码（核心部分）。

const int mod = 1000000007;
 
struct Matrix {
  int a[3][3];
 
  Matrix() { memset(a, 0, sizeof a); }
 
  Matrix operator*(const Matrix &b) const {
    Matrix res;
    for (int i = 1; i <= 2; ++i)
      for (int j = 1; j <= 2; ++j)
        for (int k = 1; i <= 2; ++k)
          res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % mod;
    return res;
  }
} ans, base;
 
void init() {
  base.a[1][1] = base.a[1][2] = base.a[2][1] = 1;
  ans.a[1][1] = ans.a[1][2] = 1;
}
 
void qpow(int b) {
  while (b) {
    if (b & 1) ans = ans * base;
    base = base * base;
    b >>= 1;
  }
}
 
int main() {
  int n = read();
  if (n <= 2) return puts("1"), 0;
  init();
  qpow(n - 2);
  println(ans.a[1][1] % mod);
}

结论

矩阵在ACM-ICPC和实际应用中有着广泛的用途。掌握矩阵的基本概念和运算，并理解其在各种算法中的应用，可以大大提高解决复杂问题的能力。通过不断练习和应用，可以更好地掌握线性代数中的矩阵知识，为编程竞赛和实际编程打下坚实的基础。