矩阵 是一种用于简化运算的工具,很神奇的。
(未完待续)
矩阵的定义
矩阵其实就是一对数字的有机组合,是一种方便我们简化计算的工具(尽管矩阵的形式并不是很简便)。
矩阵运算
矩阵加法
只有行数和列数都相等的矩阵才能相加,矩阵的加法运算法则用公式表示为:
$$\text{C} _ {i,j}=\text{A} _ {i,j}+\text{B} _ {i,j}$$
值得注意的是,矩阵加法运算的单位元是一个各项都为零的矩阵。
矩阵乘法
对于一个 $n$ 行 $m$ 列的矩阵 $\text{A}$ 与一个 $m$ 行 $k$ 列的矩阵 $\text{B}$,他们的乘积为一个 $n$ 行 $k$ 列的矩阵 $\text{C}$,具体地,我们有:
$$\text{C} _ {i,j}=\sum^m _ {k=1}\text{A} _ {i,k} \text{B} _ {k,j}$$
当然,在矩阵乘法中,结果 $\text{C}$ 矩阵的第 $i$ 行第 $j$ 列的数,就是由矩阵 $\text{A}$ 第 $i$ 行 $k$ 个数与矩阵 $\text{B}$ 第 $j$ 列 $k$ 个数分别相乘再相加得到的。
性质
单位元
矩阵乘法的单位元是一条从左上到右下角的 $1$,例如 $3\times 3$ 的矩阵的乘法单位元是:
$$
\begin{bmatrix}
1&0&0\\
0&1&0\\
0&0&1
\end{bmatrix}
$$
结合律
矩阵乘法符合结合律,下面是证明。
证明略。
应用
因为矩阵乘法符合结合律,我们往往把一个矩阵视作一种操作。
首先对于比较小的矩阵,可以考虑直接手动展开循环以减小常数。
可以重新排列循环以提高空间局部性,这样的优化不会改变矩阵乘法的时间复杂度,但是会在得到常数级别的提升。这与内存的缓存机制有关。
- 慢
inline Matrix 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; }
- 快
inline 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; }
广义矩阵乘法
我们往往会到一种奇怪的矩阵乘法的定义:
$$\text{C} _ {i,j}=\max^m _ {k=1} \{\text{A} _ {i,k}+\text{B} _ {k,j}\}$$
动态 $\text{DP}$ 中往往会使用这种特殊的矩阵乘法的定义。
简单应用
未完待续
近期评论