线性代数——矩阵

引入

矩阵

一般用圆括号或方括号表示矩阵，形如：

\(A = \begin{pmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{m1} & \cdots & a_{mn} \end{pmatrix}\)

矩阵表示线性方程组

例如，将线性方程组：

\( \left\{\begin{matrix} 7x_1+8x_2+9x_3=13 \\ 4x_1+5x_2+6x_3=12 \\ x_1+2x_2+3x_3=11 \end{matrix}\right. \)

写成矩阵乘法的形式（将系数抽出来）：

\( \begin{pmatrix} 7 & 8 & 9 \\ 4 & 5 & 6 \\ 1 & 2 & 3 \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}=\begin{pmatrix} 13 \\ 12 \\ 11 \end{pmatrix} \)

简记为：\(Ax = b\)，其中系数矩阵 \(A = \begin{pmatrix} 7 & 8 & 9 \\ 4 & 5 & 6 \\ 1 & 2 & 3 \end{pmatrix}\)；未知量 \(x = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}\)；常数项 \(b = \begin{pmatrix} 13 \\ 12 \\ 11 \end{pmatrix}\)；

即未知数列向量 \(x\)，左乘一个矩阵 \(A\)，得到列向量 \(b\)。

运算

矩阵的线性运算

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

例如：\(3 \times \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} = \begin{pmatrix} 3 \times 1 & 3 \times 2 \\ 3 \times 3 & 3 \times 4 \end{pmatrix} = \begin{pmatrix} 3 & 6 \\ 9 & 12 \end{pmatrix}\)

矩阵的转置

矩阵的转置，就是在矩阵的右上角写上转置「\(\text{T}\)」记号，表示将矩阵的行与列互换。

例如：\(\begin{pmatrix} 1 & 2 & 3 \\ 3 & 4 & 5 \end{pmatrix}^\text{T}=\begin{pmatrix} 1 & 3 \\ 2 & 4 \\ 3 & 5 \end{pmatrix}\)

向量内积

对应相乘再相加。

例如：\(\begin{pmatrix} 1 & 2 & 3 \end{pmatrix} \times \begin{pmatrix} 4 & 5 & 6 \end{pmatrix} = 1 \times 4 + 2 \times 5 + 3 \times 6 = 52\).

矩阵乘法

1. 算法
   设 \(A\) 为 \(n \times m\) 的矩阵，\(B\) 为 \(m \times r\) 的矩阵，即前一矩阵列数等于后一矩阵行数；
   设矩阵 \(C = A \times B\)，则 \(\displaystyle C_{i, j} = \sum_{k = 1}^m A_{i, k} B_{k, j}\)。

   乘积矩阵中第 \(i\) 行第 \(j\) 列的数恰好是乘数矩阵 \(A\) 第 \(i\) 个行向量与乘数矩阵 \(B\) 第 \(j\) 个列向量的内积，口诀为左行右列。

2. 性质
   矩阵乘法满足结合律，不满足一般的交换律；利用结合律，矩阵乘法可以利用快速幂的思想来优化。

   由于线性递推式可以表示成矩阵乘法的形式，也通常用矩阵快速幂来求线性递推数列的某一项。

演示网站：https://rainppr.gitee.io/matrixmultiplication.xyz/.

矩阵乘法的特殊化——矩阵乘向量

将向量调转，先相乘再相加。

例如：\(\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix}\begin{pmatrix} 3 \\ 6 \\ 9 \end{pmatrix}=\begin{pmatrix} 1 \times 3 + 2 \times 6 + 3 \times 9 \\ 4 \times 3 + 5 \times 6 + 6 \times 9 \end{pmatrix}=\begin{pmatrix} 42 \\ 96 \end{pmatrix}\)

矩阵乘法的特殊化——单位矩阵 I

单位矩阵 \(I\)：一个方阵（行数 \(=\) 列数），只有主对角线（左上、右左下）元素为 \(1\)，其他都为 \(0\)。

单位矩阵乘任何矩阵都得该矩阵（就像 \(1\) 一样），即 \(IA = AI = A\)。

举例：\(\begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 5 & 6 & 7 \\ 7 & 8 & 9 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 5 & 6 & 7 \\ 7 & 8 & 9 & 0 \end{pmatrix}\)

矩阵乘法优化线性递推

讲解与例题分析

斐波那契数列

在斐波那契数列当中，\(f_1 = f_2 = 1\)，\(f_i = f_{i - 1} + f_{i - 2}\)，求 \(f_n\)。

而分析式子可以知道，求 \(f_k\) 仅与 \(f_{k - 1}\) 和 \(f_{k - 2}\) 有关；
所以我们设矩阵 \(F_i = \begin{bmatrix} f_{i - 1} & f_{i - 2} \end{bmatrix}\)。

设矩阵 \(\text{Base}\)，使得 \(F_{i - 1} \times \text{Base} = F_i\)，接下来考虑 \(\text{Base}\) 是什么；
带入可得 \(\begin{bmatrix} f_{i - 2} & f_{i - 3} \end{bmatrix} \times \text{Base} = \begin{bmatrix} f_{i - 1} & f_{i - 2} \end{bmatrix}\)。

即 \(\begin{bmatrix} f_{i - 2} & f_{i - 3} \end{bmatrix} \times \text{Base} = \begin{bmatrix} f_{i - 2} + f_{i - 3} & f_{i - 2} \end{bmatrix}\)；
根据矩阵乘法的规则可知 \(\text{Base}\) 的第 \(1\) 列应为 \(\begin{bmatrix} 1 & 1 \end{bmatrix}^\text{T}\)，第 \(2\) 列应为 \(\begin{bmatrix} 1 & 0 \end{bmatrix}^\text{T}\)。

所以求得 \(\text{Base} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\)。

然后考虑 \(f_i\) 的值应该是多少；
根据前面的公式可以知道 \(f_i = F_{n + 1}\) 的第一个数，所以就是求这个数。

根据 \(f_1 = f_2 = 1\)，可以知道 \(F_3 = \begin{bmatrix} f_2 & f_1 \end{bmatrix} = \begin{bmatrix} 1 & 1 \end{bmatrix}\)，我们将这个作为边界值；
然后有 \(F_4 = F_3 \times \text{Base}\)，\(F_5 = F_4 \times \text{Base} = F_3 \times \text{Base} \times \text{Base}\)。

因为矩阵乘法有结合律，所以 \(F_{n + 1} = F_3 \times \text{Base}^{n - 2} = \begin{bmatrix} 1 & 1 \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n - 2}\)。

因为矩阵没有交换律，所以 \(F_3\)（前）和 \(\text{Base}^{n - 2}\)（后）一定不能写反了！

例题１

\(\left\{\begin{array}{l} f_1 = f_2 = 0 \\ f_i = f_{i - 1} + f_{i - 2} + 1 \end{array}\right.\)

例题２

\(\left\{\begin{array}{l} f_1 = 0 \text{，} f_2 = 1 \\ f_i = f_{i - 1} + f_{i - 2} + i \end{array}\right.\)

例题３（来自 OI-Wiki）

\(\left\{\begin{array}{l} f_{1} = f_{2} = 0 \\ f_{n} = 7f_{n-1}+6f_{n-2}+5n+4\times 3^n \end{array}\right.\)

例题４

\(\left\{\begin{array}{l} f_1 = f_2 = 0 \text{，} f_3 = 1 \\ f_i = 3f_{i - 1} + 2f_{i - 2} + f_{i - 3} + 5i + 7 \end{array}\right.\)

例题５

洛谷 P1939 矩阵加速（数列）：https://www.luogu.com.cn/problem/P1939

考虑这道题 \(\text{Base}\) 该如何设置。

时间复杂度

矩阵乘法 \(O(k^3)\) 其中 \(k\) 为矩阵的长（或宽）；
快速幂 \(O(\log n)\)；

所以［矩阵乘法优化线性递推］的时间复杂度为 \(O(k^3 \log n)\)。

代码实现

const int N = 110;			// 矩阵的最大大小
const int MOD = 1e9 + 7;	// 取模

struct matrix
{
    int n, m, a[N][N];

    // 初始矩阵
    matrix() { memset(a, 0, sizeof a); }
    matrix(int _n, int _m) { n = _n, m = _m, memset(a, 0, sizeof a); }

    // 单位矩阵
    matrix(int _n)
    {
        n = m = _n;
        for (int i = 1; i <= n; ++i)
            a[i][i] = 1;
    }

    // 定义矩阵
    matrix(int _n, int _m, const int t[N][N])
    {
        n = _n, m = _m;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                a[i][j] = t[i][j];
    }

    // 矩阵乘法
    matrix operator*(const matrix &b) const
    {
        matrix res;
        res.n = n, res.m = b.m;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= b.m; ++j)
                for (int k = 1; k <= m; ++k)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j] % MOD) % MOD;
        return res;
    }
};

// 矩阵快速幂
matrix pow(const int &n, matrix a, int k)
{
    matrix res(n);
    while (k)
    {
        if (k & 1)
            res = res * a;
        k >>= 1, a = a * a;
    }
    return res;
}

资料来源

• 矩阵左乘和右乘的区别
• 矩阵 - OI Wiki
• Matrix Multiplication

热门相关：豪门蜜爱：独宠天后小萌妻   网游三国之城市攻略   宠物小精灵之庭树   我是仙凡   网游三国之城市攻略