Skip to content

矩阵

矩阵基础

矩阵的定义

矩阵（\(\text{matrix}\)）是一个按照行与列排列出的元素表。

元素通常是来自于某个数系或代数结构的，例如实数域 \(\mathbb{R}\)，整数环 \(\mathbb{Z}\) 或模 \(MOD\) 的整数环 \(\mathbb{Z}_{MOD}\)。

我们记一个矩阵 \(A\) 为：

\[ A= \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,m}\\ a_{2,1} & a_{2,2} & \cdots & a_{2,m}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n,1} & a_{n,2} & \cdots & a_{n,m} \end{pmatrix}. \]
  • \(A\) 有 \(n\) 行 \(m\) 列，称为一个 \(n\times m\) 矩阵，记作 \(A\in F^{n\times m}\)（\(F\) 是元素集合）。
  • 第 \(i\) 行第 \(j\) 列元素记为 \(A_{i,j}\) 或 \(a_{i,j}\)。

行向量和列向量

当矩阵只有一行或一列时，它们是向量的矩阵表示：

  • 行向量：\(1\times m\)，例如 \(\begin{pmatrix}x_1 & x_2 & \cdots & x_m\end{pmatrix}\)。
  • 列向量：\(n\times 1\)，例如 \(\begin{pmatrix}x_1\\x_2\\\vdots\\x_n\end{pmatrix}\)。

常见特殊矩阵

  • 方阵（\(\text{square matrix}\)）：\(n\times n\)。
  • 零矩阵（\(\text{zero matrix}\)）：全为 \(0\)，记作 \(0\)。
  • 单位矩阵（\(\text{identity matrix}\)）：\(I_n\)，满足主对角线为 \(1\)，其余为 \(0\)：
\[ I_n= \begin{pmatrix} 1&0&\cdots&0\\ 0&1&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&1 \end{pmatrix}. \]
  • 对角矩阵：仅主对角线可能非零。
  • 上（下）三角矩阵：主对角线下方（上方）为零。
  • 稀疏矩阵（\(\text{sparse matrix}\)）：大部分元素为零。

矩阵与线性映射

一个 \(n\times m\) 矩阵可以视为从 \(F^m\) 到 \(F^n\) 的线性变换。

若 \(\mathbf{x}\in F^m\) 是列向量，则 \(A\mathbf{x}\in F^n\)，并且

\[ (A\mathbf{x})_i=\sum_{j=1}^{m}A_{i,j}x_j. \]

矩阵乘法的定义正是为了让「变换的复合」能用矩阵表示：若先做 \(B\)，再做 \(A\)，则复合变换用 \(AB\) 表示，并满足

\[ A(B\mathbf{x})=(AB)\mathbf{x}. \]

矩阵乘法

矩阵乘法的维度匹配

若 \(A\in F^{n\times m}\)，\(B\in F^{m\times p}\)，则 \(AB\) 有定义， 且 \(AB\in F^{n\times p}\)。

维度匹配条件是：

\[ \mathrm{cols}(A)=\mathrm{rows}(B). \]

标准矩阵乘法定义

设 \(A\in F^{n\times m}\)，\(B\in F^{m\times p}\)。定义 \(C=AB\) 为 \(n\times p\) 矩阵，且

\[ C_{i,j}=\sum_{k=1}^{m}A_{i,k}B_{k,j}. \]

也就是大家常说的「左行右列」。

矩阵乘法性质

  • 结合律：
\[ (AB)C=A(BC). \]

这也是我们可以用「快速幂」来计算矩阵乘法的根本依据。

  • 分配律：
\[ A(B+C)=AB+AC,\qquad (A+B)C=AC+BC. \]
  • 一般不满足交换律：
\[ AB\neq BA\quad (\text{通常成立}). \]

单位矩阵满足：

\[ AI_n=I_nA=A\quad (\text{维度匹配时}). \]

复杂度与快速幂

朴素矩阵乘法复杂度

朴素矩阵乘法的复杂度是很好分析的， 对 \(n\times n\) 方阵，朴素乘法时间复杂度为：\(O(n^3)\)。

值得一提的是学术界存在复杂度小于 \(O(n^3)\) 的矩阵乘法计算方式， 只不过这些计算方式实现起来十分复杂而且常数很大， 在算法竞赛领域我们通常来说只使用朴素的 \(O(n^3)\) 计算方式。

矩阵的幂运算

对方阵 \(A\in F^{n\times n}\)，定义：

\[ A^0=I_n,\qquad A^{t+1}=A^tA. \]

矩阵快速幂

矩阵快速幂本质上和常规的快速幂并无较大的差别， 唯一的差别在于我们把普通的整数之间的乘法换成了矩阵的乘法。

快速幂需要 \(O(\log k)\) 次矩阵乘法，因此复杂度为：\(O(n^3\log k)\)。

矩阵乘法与路径问题

标准乘法

\[ (AB)_{i,j}=\sum_{k}A_{i,k}B_{k,j} \]

是具有「拼接」结构的，我们可以去枚举 \(k\)，把 \(i\to k\) 的信息和 \(k\to j\) 的信息合成 \(i\to j\) 的信息， 再对所有的 \(k\) 进行聚合，这样一来就能得到全局的 \(i\to j\) 的信息。

给定有向图 \(G\)（点集 \(\{1,\dots,n\}\)），定义邻接矩阵 \(A\in\{0,1\}^{n\times n}\)：

\[ A_{i,j}= \begin{cases} 1,& \text{若存在有向边 } i\to j,\\ 0,& \text{否则}. \end{cases} \]

对任意 \(k\ge 1\)，成立：

\[ (A^k)_{i,j}=\{\text{从 } i \text{ 到 } j \text{ 的长度恰为 } k \text{ 的路径数量}\}. \]

核心原因是因为：

\[ (A^2)_{i,j}=\sum_{t=1}^{n}A_{i,t}A_{t,j}. \]

矩阵乘法与传递闭包

把运算替换为布尔逻辑：

  • “加法”替换为 \(\lor\)；
  • “乘法”替换为 \(\land\)。

定义布尔矩阵乘法：

\[ (AB)_{i,j}=\bigvee_{k=1}^{n}\left(A_{i,k}\land B_{k,j}\right). \]

此时

\[ (A^k)_{i,j}=1 \]

表示存在至少一条长度恰为 \(k\) 的路径可以从 \(i\) 走到 \(j\)。

定义传递闭包：

\[ A^*=I_n\lor A\lor A^2\lor A^3\lor\cdots, \]

于是

\[ (A^*)_{i,j}=1\iff i \text{ 可达 } j. \]

min-plus 矩阵乘法

\[ \oplus=\min,\qquad \otimes=+. \]

在该体系下的矩阵乘法：

\[ (AB)_{i,j}=\min_{k}\left(A_{i,k}+B_{k,j}\right). \]

我们令带权邻接矩阵 \(W\in(\mathbb{R}\cup\{+\infty\})^{n\times n}\)：

\[ W_{i,j}= \begin{cases} w(i,j),& \text{若存在边 } i\to j \text{ 且边权为 } w(i,j),\\ +\infty,& \text{否则}, \end{cases} \qquad W_{i,i}=0. \]

则在 \(\text{min-plus}\) 意义下：

\[ (W^t)_{i,j}=\min\{\text{从 } i \text{ 到 } j \text{ 恰好走 } t \text{ 条边的路径代价}\}. \]

闭包：

\[ W^*=I_n\oplus W\oplus W^2\oplus W^3\oplus\cdots. \]