「OI」矩阵

矩阵 是一种用于简化运算的工具,很神奇的。

(未完待续)

矩阵的定义

矩阵其实就是一对数字的有机组合,是一种方便我们简化计算的工具(尽管矩阵的形式并不是很简便)。

矩阵运算

矩阵加法

只有行数和列数都相等的矩阵才能相加,矩阵的加法运算法则用公式表示为:

$$\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}$ 中往往会使用这种特殊的矩阵乘法的定义。

简单应用

未完待续

例题