线性代数——矩阵 学习笔记

线性代数——矩阵

引入

矩阵

一般用圆括号或方括号表示矩阵,形如:

\(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}\)(后)一定不能写反了!

例题1

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

点击查看题解

\(f_i\) 仅与 \(f_{i - 1}\)\(f_{i - 2}\) 有关,同时还包括了常数 \(1\)
所以我们设 \(F_i = \begin{bmatrix} f_{i - 1} & f_{i - 2} & 1 \end{bmatrix}\)

然后设 \(\text{Base}\) 使得 \(F_{i - 1} \times \text{Base} = F_i\)
\(\begin{bmatrix} f_{i - 2} & f_{i - 3} & 1 \end{bmatrix} \times \text{Base} = \begin{bmatrix} f_{i - 1} & f_{i - 2} & 1 \end{bmatrix}\)

因为 \(f_{i - 1} = f_{i - 2} + f_{i - 3} + 1\),所以易知:

\(\text{Base} = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \end{bmatrix}\).

边界条件为 \(F_3 = \begin{bmatrix} 0 & 0 & 1\end{bmatrix}\)
所以 \(F_{n + 1} = F_3 \times \text{Base}^{n - 2}\)

即可求出 \(f_n\).

例题2

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

点击查看题解

\(f_i\) 仅与 \(f_{i - 1}\)\(f_{i - 2}\)\(i\) 有关,为实现 \(i\) 的递增,还需设置常量 \(1\)
所以我们设 \(F_i = \begin{bmatrix} f_{i - 1} & f_{i - 2} & i & 1 \end{bmatrix}\)

\(F_{i - 1} \times \text{Base} = F_i\)\(\text{Base} = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{bmatrix}\).

边界条件为 \(F_3 = \begin{bmatrix} 1 & 0 & 3 & 1 \end{bmatrix}\).

\(F_{n + 1} = F_3 \times \text{Base}^{n - 2}\);即可求出 \(f_n\)

例题3(来自 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.\)

点击查看题解

我的解法与 OI-Wiki 上的有所不同:

\(F_n = \begin{bmatrix} f_{n - 1} & f_{n - 2} & n & 3^n & 1 \end{bmatrix}\).

易知 \(\text{Base} = \begin{bmatrix} 7 & 1 & 0 & 0 & 0 \\ 6 & 0 & 0 & 0 & 0 \\ 5 & 0 & 1 & 0 & 0 \\ 4 & 0 & 0 & 3 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix}\).

边界值 \(F_3 = \begin{bmatrix} 0 & 0 & 3 & 27 & 1 \end{bmatrix}\).

\(F_{n + 1} = F_3 \times \text{Base}^{n - 2}\).

例题4

\(\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.\)

点击查看题解

增加了 \(f_{i - 3}\),但是本质是一样的。

可以设 \(F_i = \begin{bmatrix} f_{i - 1} & f_{i - 2} & f_{i - 3} & i & 1 \end{bmatrix}\)

易得 \(\text{Base} = \begin{bmatrix} 3 & 1 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 5 & 0 & 0 & 1 & 0 \\ 7 & 0 & 0 & 1 & 1 \end{bmatrix}\).

\(F_4 = \begin{bmatrix} 1 & 0 & 0 & 4 & 1 \end{bmatrix}\)

\(F_{n + 1} = F_4 \times \text{Base}^{n - 3}\)

例题5

洛谷 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;
}

资料来源

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