矩阵

矩阵的基本概念

矩阵的定义

　　由 \(m \times n\) 个数 \(a_{ij}\) 排成的 \(m\) 行 \(n\) 列的数表称为 \(m\) 行 \(n\) 列的矩阵，简称 \(m \times n\) 矩阵。记作：

\[A=\begin{bmatrix} {a_{11}}&{a_{12}}&{\cdots}&{a_{1n}}\\ {a_{21}}&{a_{22}}&{\cdots}&{a_{2n}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {a_{m1}}&{a_{m2}}&{\cdots}&{a_{mn}}\\ \end{bmatrix} \]

　　这 \(m\times n\) 个数称为矩阵 \(A\) 的元素，简称为元，数 \(a_{ij}\) 位于矩阵 \(A\) 的第 \(i\) 行第 \(j\) 列。上面的矩阵还可以简记为：\(A = A_{m\times n} = (a_{ij})_{m\times n} = (a_{ij})\)。

几种特殊的矩阵

  1. 行数和列数都等于 \(n\) 的矩阵 \(A\)， 称为 \(n\) 阶方阵（也叫 \(n\) 阶矩阵）。

    \[A=\begin{pmatrix} {a_{11}}&{a_{12}}&{\cdots}&{a_{1n}}\\ {a_{21}}&{a_{22}}&{\cdots}&{a_{2n}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {a_{n1}}&{a_{n2}}&{\cdots}&{a_{nn}}\\ \end{pmatrix} \]

  2. 只有一行的矩阵称为行矩阵（或行向量）。

    \[A = (a_1,a_2,\cdots,a_n) \]

  3. 只有一列的矩阵称为列矩阵（或列向量）。

    \[A=\begin{pmatrix} {a_{1}}\\ {a_{2}}\\ {\vdots}\\ {a_{n}}\\ \end{pmatrix} \]

  4. 矩阵 \(A\) 和 \(B\) 的行数列数分别相同，称为同型矩阵。

  5. 元素全为 \(0\) 的矩阵称为零矩阵，记做 \(0\)。注意：不同阶数的零矩阵是不相同的。

    \[\begin{pmatrix} 0&0&{\cdots}&0\\ 0&0&{\cdots}&0\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ 0&0&{\cdots}&0\\ \end{pmatrix} \neq \begin{pmatrix} 0, 0, 0 \end{pmatrix} \]

  6. 主对角线（左上到右下）的元素都为 \(1\)，其他元素都为 \(0\) 的 \(n\) 阶方阵称为单位矩阵。

    \[E_n=I_n=\begin{pmatrix} 1&0&{\cdots}&0\\ 0&1&{\cdots}&0\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ 0&0&{\cdots}&1\\ \end{pmatrix} \]

    　　同时单位矩阵也可以简单地记为一个对角线矩阵：$$E_n=I_n=diag(1,1,\cdots,1)$$。

    　　对于不同矩阵他们的单位矩阵大小是不同的，对于 \(n\times m\) 的矩阵，它的单位矩阵大小为 \(m\times m\) ，对于 $ m\times n$ 的矩阵，它的单位矩阵大小为 \(n \times n\) 。也就是说单位矩阵都是正方形的，这是因为只有正方形的矩阵能保证结果和前一个矩阵形状相同

  7. 对角矩阵(diagonal matrix)是一个主对角线主)之外的元素皆为 \(0\) 的方阵。

    \[A=\begin{pmatrix} \lambda_1&0&{\cdots}&0\\ 0&\lambda_2&{\cdots}&0\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ 0&0&{\cdots}&\lambda_n\\ \end{pmatrix} \]

    其中 \(\lambda_1,\lambda_2, \cdots,\lambda_n\) 不全为 \(0\)，也可记作：\(A= diag(\lambda_1,\lambda_2, \cdots,\lambda_n)\)

  8. 如果两个同型矩阵的对应元素相等，则两个矩阵相等。

线性变换矩阵

　　线性变换矩阵 \(\text{(matrix of a linear transformation)}\)一种特殊矩阵。指该矩阵可以通过线性变换得到。

　　\(n\) 个变量 \(x_1,x_2,…,x_n\) 与 \(m\) 个变量 \(y_1,y_2,…,y_m\) 之间的关系式：

\[\begin{cases} y_1=a_{11}x_1 + a_{12}x_2+\cdots+a_{1n}x_n\\ y_1=a_{21}x_1+a_{21}x_2+\cdots+a_{2n}x_n\\ \vdots\\ y_m = a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n \end{cases} \]

　　表示从变量$ x_1,x_2,…,x_n$ 到变量 \(y_1,y_2,…,y_m\) 的线性变换，其中 \(a_{ij}\) 为常数。

　　我们把系数取出，写成矩阵的形式，其系数矩阵为：

\[A=\begin{pmatrix} {a_{11}}&{a_{12}}&{\cdots}&{a_{1n}}\\ {a_{21}}&{a_{22}}&{\cdots}&{a_{2n}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {a_{m1}}&{a_{m2}}&{\cdots}&{a_{mn}}\\ \end{pmatrix} \]

　　可以看出线性变换与矩阵之间存在一一对应的关系。

矩阵运算

1. 矩阵加减法

　　设有两个 \(m×n\) 的矩阵 $A=(a_{ij}) $ 和矩阵 \(B=(b_{ij})\)，那么 \(A\) 和 \(B\) 的和记为 \(A+B\)，规定：

\[A \pm B=\begin{pmatrix} {a_{11}\pm b_{11}}&{a_{12}\pm b_{12}}&{\cdots}&{a_{1n}\pm b_{1n}}\\ {a_{21}\pm b_{21}}&{a_{22}\pm b_{22}}&{\cdots}&{a_{2n}\pm b_{2n}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {a_{m1}\pm b_{m1}}&{a_{m2}\pm b_{m2}}&{\cdots}&{a_{mn}\pm b_{mn}}\\ \end{pmatrix} \]

　　注意：两个同型矩阵才可以做加法。

矩阵的加减法满足的运算定律：

交换律 \(A+B=B+A\)

结合律 \((A+B)+c=A+(B+C)\) 。

2.矩阵乘法

　　设 \(A=(a_{ij})\) 是一个 \(m×s\) 矩阵， \(B=(b_{ij})\) 是一个 \(s×n\) 矩阵，那么 \(A\) 和 \(B\) 的乘积 \(C=(c_{ij})\) 是一个 \(m×n\) 矩阵，其中:

\[c_{ij}=a_{i1}b_{1j}+a_{i2}b_{2j}+\cdots a_{is}b_{sj} =\sum_{k=1}^{s} a_{ik}b_{kj}\\ A=\begin{pmatrix} a_{11}&a_{12}&a_{13}\\ a_{21}&a_{22}&a_{23}\\ \end{pmatrix}, B=\begin{pmatrix} b_{11}&b_{12}\\ b_{21}&b_{22}\\ b_{31}&b_{32}\\ \end{pmatrix}\\ C=AB\begin{pmatrix} a_{11}b_{11} + a_{12}b_{21}+a_{13}b_{31}&a_{11}b_{12}+a_{12}b_{22}+a_{13}b_{32}\\ a_{21}b_{11} +a_{22}b_{21}+a_{23}b_{31}&a_{21}b_{12}+a_{22}b_{22}+a_{23}b_{32}\\ \end{pmatrix} \]

矩阵乘法满足的运算定律：

结合律： \((AB)C=A(BC)\)

左分配律：(A+B)C=AC+BC

右分配律：C(A+B)=CA+CB

数乘： k(AB)=(kA)B=A(kB)

转置： \((AB)^T=B^T A^T\)

　　设 \(A\) 为 \(m×n\) 阶矩阵（即 \(m\) 行 \(n\) 列），第 \(i\) 行 \(j\) 列的元素是 \(a(i,j)\)，即：把 \(m×n\) 矩阵 \(A\) 的行换成同序数的列得到一个 \(n×m\) 矩阵，此矩阵叫做 \(A\) 的转置矩阵，记做 \(A^T\) 。例如：

\[A=\begin{pmatrix} 1&2&0\\ 3&-1&4\\ \end{pmatrix}\\ A^T=\begin{pmatrix} 1&3\\ 2&-1\\ 0&4 \end{pmatrix} \]

转置的基本性质、

  1. \((A^T)^T = A\)
  2. \((A+B)^T=A^T+B^T\)
  3. \((kA)^T=kA^T\)
  4. \((AB)^T=B^TA^T\)

注意：矩阵乘法一般不满足交换律

矩阵乘法代码
#include
const int maxn = 100 + 5;
using namespace std;
int a[maxn][maxn], b[maxn][maxn], c[maxn][maxn];
int main(){
    int m,n,k;
    scanf("%d%d%d", &m, &n, &k);
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            scanf("%d", &a[i][j]);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= k; ++j)
            scanf("%d", &b[i][j]);
    for(int i = 1; i <= m; ++i)//枚举a的行数m
        for(int j = 1; j <= k; ++j)//枚举b的列数k
            for(int kk = 1; kk <= n; ++kk)//枚举a的列(b的行)
                c[i][j] += a[i][kk]*b[kk][j];
    return 0;
}

Fibonacci 数列

时间限制：1 s 内存限制：128 MB 文件：

题目描述

　　斐波拉切数列，\(f_0,f_1,\cdots,f_n\) ，满足：\(f_0=0,f_1=1,f_n=f_{n-2}+f_{n-1}(n>=2)\) ，请求出 \(f_n\) 的值，由于答案可能会很大，只需输出答案模 \(10000\) 的结果。

输入格式

　　输入包含多组数据，第一行为一个正整数 \(T\)，表示有T组输入。

　　每组输入为一个正整数 \(n\) ，表示求斐波拉切数列第 \(n\) 的值模 \(10000\) 的结果。

输出格式

　　对每组输入输出一个答案。

样例输入

4
0
9
999999999
1000000000

样例输出

0
34
626
6875

样例解释

数据范围与提示

　　对 \(100\%\) 的数据满足：\(1\le T\le 100, 0\le n \le 10^9\) 。

分析

　　\(\text{O(log(n))}\) 的递推很容想到，但 \(n\) 高达 \(10^9\) 显然在线性时间效率上显然会超时，构造矩阵$$A=\begin{bmatrix}1&1\1&0 \end{bmatrix}$$，列矩阵 $$B_n=\begin{bmatrix} f_n\f_{n-1}\end{bmatrix}$$ ，则有：

\[A*B_1=\begin{bmatrix} 1&1\\1&0 \end{bmatrix}* \begin{bmatrix} f_1\\f_0 \end{bmatrix}= \begin{bmatrix} f_0+f_1\\f_1 \end{bmatrix}= \begin{bmatrix} f_2\\f_1 \end{bmatrix}=B_2\\ A*B_2=\begin{bmatrix} 1&1\\1&0 \end{bmatrix}* \begin{bmatrix} f_2\\f_1 \end{bmatrix}= \begin{bmatrix} f_1+f_2\\f_2 \end{bmatrix}= \begin{bmatrix} f_3\\f_2 \end{bmatrix}=B_3\\ \vdots\\ A*B_{n-1}=\begin{bmatrix} 1&1\\1&0 \end{bmatrix}* \begin{bmatrix} f_{n-1}\\f_{n-2} \end{bmatrix}= \begin{bmatrix} f_{n-2}+f_{n-1}\\f_{n-1} \end{bmatrix}= \begin{bmatrix} f_n\\f_{n-1} \end{bmatrix}=B_n\\ \Rightarrow B_n=A^{n-1}*B_1=A^{n-1}*\begin{bmatrix}1\\0\end{bmatrix} \]

　　因为 \(A*A^{n-1}\) 的第一行第二列答案和 \(A^{n-1} * B_1\) 的第一行第一列答案一样， 所以只需求出 \(A^n\) 即可，答案为矩阵第一行第二列。现在关键是如何快速求出 \(A^n\) ，其实矩阵快速幂跟普通快速幂思想是一样的，不同的地方答案初始化为对角线为 \(1\)，其他为 \(0\) 的单位矩阵，普通乘法改为矩阵乘法即可，具体操作见代码实现。

代码实现：

#include
using namespace std;
const int maxn = 2, Mod = 10000;
void Matrix(int a[][2], int b[][2]){//矩阵乘法
    int c[maxn][maxn] = {0};
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            for(int k = 0; k < 2; ++k)
                c[i][j] =(c[i][j] + a[i][k] * b[k][j]) % Mod;
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            a[i][j] = c[i][j];
}
//A为转移矩阵，res初始为基础矩阵存储答案
int Pow(int A[][2], int n, int res[][2]){//矩阵快速幂
    for(; n; n >>= 1){
        if(n & 1) Matrix(res, A);
        Matrix(A, A);
    }
    return res[0][1];
}
int main(){
    int N;scanf("%d", &N);
    while(N--){
        int n; scanf("%d", &n);
        //A为转移矩阵,res存储 A^n%10000的结果，初始为基础矩阵
        int A[maxn][maxn] = {1, 1, 1, 0}, res[maxn][maxn]={1, 0, 0, 1};
        printf("%d\n", Pow(A, n, res));
    }
}

矩阵加速

题目描述

　　已知一个数列 \(f\)，它满足：

\[f_x= \begin{cases} 1 & x \in\{1,2,3\}\\ f_{x-1}+f_{x-3} & x \geq 4 \end{cases} \]

　　求 \(f\) 数列的第 \(n\) 项对 \(10^9+7\) 取余的值。

输入格式

　　第一行一个整数 \(T\)，表示询问个数。

　　以下 \(T\) 行，每行一个正整数 \(n\)。

输出格式

　　每行输出一个非负整数表示答案。

样例 1 输入

3
6
8
10

样例 1 输出

4
9
19

数据范围

  • 对于 \(30\%\) 的数据 \(n \leq 100\)；
  • 对于 \(60\%\) 的数据 \(n \leq2 \times 10^7\)；
  • 对于 \(100\%\) 的数据 \(1 \leq T \leq 100\)，\(1 \leq n \leq 2 \times 10^9\)。

分析

　　跟上一题类似，首先我们要构造出初始矩阵、目标矩阵和转移矩阵，首先初始矩阵矩阵显然为 $$B_3=\begin{bmatrix}f_3\f_2\f_1 \end{bmatrix}=\begin{bmatrix}1\1\1 \end{bmatrix}$$ ，根据初始矩阵我们构造出目标矩阵 $$B_n=\begin{bmatrix}f_n\f_{n-1}\f_{n-2} \end{bmatrix}$$，那如何构造出转移矩阵呢？显然目标矩阵需要从上一个矩阵 $$B_{n-1}=\begin{bmatrix}f_{n-1}\f_{n-2}\f_{n-3} \end{bmatrix}$$ 推导而来，即：$$\begin{bmatrix}f_n\f_{n-1}\f_{n-2} \end{bmatrix}=A*\begin{bmatrix}f_{n-1}\f_{n-2}\f_{n-3} \end{bmatrix}$$ 根据递推式，当 \(n>=4\) 时，显然有：

\[\begin{align} f_n &= f_{n-1} * 1 + f_{n-2}*0 + f_{n-3}*1\\ f_{n-1} &= f_{n-1}*1 + f_{n-2}*0 + f_{n-3}*0\\ f_{n-2} &= f_{n-1}*0 + f_{n-2}*1 + f_{n-3}*0\\ \end{align}\\ \therefore A = \begin{bmatrix} 1 & 0 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{bmatrix} \]

　　很容易推出：

\[\begin{align} B_4 &= A * B_3\\ B_5 &= A * B_4\\ \vdots\\ B_n &= A * B_{n-1}\\ \therefore B_n &= A^{n - 3} * B_3 \end{align} \]

代码实现

#include
using namespace std;
typedef long long ll;
const int Mod = 1e9 + 7;
void Matrix(ll a[][3], ll b[][3]){
    ll c[3][3] = {0};
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            for(int k = 0; k < 3; k++)
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % Mod;
    for(int i = 0; i < 3; ++i)
        for(int j = 0; j < 3; ++j)
            a[i][j] = c[i][j];
}
void Pow(ll a[][3], int n, ll res[][3]){
    for(; n; n >>= 1){
        if(n & 1) Matrix(res, a);
        Matrix(a, a);
    }
}
void Sol(){
    int T; scanf("%d", &T);
    while(T--){
        int n; scanf("%d", &n);
        if(n <= 3){
            printf("1\n"); continue;
        }
        ll res[3][3] = {1, 0, 0, 0, 1, 0, 0, 0, 1},
            A[3][3] = {1, 0, 1, 1, 0, 0, 0, 1, 0};
        Pow(A, n - 3, res);
        ll ans = (res[0][0] + res[0][1] + res[0][2]) % Mod;
        printf("%lld\n", ans); 
    }
}
int main(){
    Sol();
    return 0;
}

斐波那契前 n 项和

题目描述

　　大家都知道 Fibonacci 数列吧，\(f_1=1,f_2=1,f_3=2,f_4=3,…,f_n=f_{n?1}+f_{n?2}\)。

现在问题很简单，输入 \(n\) 和 \(m\)，求 \(f_n\) 的前 \(n\) 项和 \(S_n\ mod\ m\)。

输入格式

　　共一行，包含两个整数 \(n\) 和 \(m\) 。

输出格式

　　输出前 \(n\) 项和 $ S_n\ mod\ m$ 的值。

样例 1 输入

5 1000

样例 1 输出

12

数据范围

　　对 \(100\%\) 数据满足： \(1≤n≤2\times 10^9,1≤ m ≤10^9+10\) 。

方一：分析

　　我们先来推推公式：

\[\begin{align} &f_n = f_{n-1} + f_{n-2} =S_n -S_{n-1} \tag 1\\ &f_{n-1} =S_{n-1} - S_{n-2} \tag2 \\ &f_{n-2} = S_{n-2} - S_{n-3} \tag3\\ (1)(2)(3)\ \Rightarrow\ &S_n = 2 * S_{n-1} - S_{n-3}\\ \end{align} \]

结论：对于数列 \(\{f_n\}\)，若 \(f_i = a_1 f_{i-1} + a_2 f_{i-2}+\dots + a_i f_0\)，那么存在如下结果：

\[\begin{bmatrix} a_1 & a_2 &\dots &a_{i-1} &a_i\\ 1 & 0 &\dots & 0 &0\\ 0 & 1 &\dots & 0 &0\\ \vdots &\vdots &\vdots &\vdots &\vdots\\ 0 & 0 &\dots & 1 &0\\ \end{bmatrix}^n \begin{bmatrix} f_{i-1}\\ f_{i-2}\\ \vdots\\ f_1\\ f_0\\ \end{bmatrix} =\begin{bmatrix} f_{n+i-1}\\ f_{n+i-2}\\ \vdots\\ f_{n+1}\\ f_n\\ \end{bmatrix} \]

证明：

　　当 \(n = 1\) 时

\[\begin{bmatrix} a_1 & a_2 &\dots &a_{i-1} &a_i\\ 1 & 0 &\dots & 0 &0\\ 0 & 1 &\dots & 0 &0\\ \vdots &\vdots &\vdots &\vdots &\vdots\\ 0 & 0 &\dots & 1 &0\\ \end{bmatrix} \begin{bmatrix} f_{i-1}\\ f_{i-2}\\ \vdots\\ f_1\\ f_0\\ \end{bmatrix} =\begin{bmatrix} f_{i}\\ f_{i-1}\\ \vdots\\ f_{2}\\ f_1\\ \end{bmatrix} \]

　　显然成立，假设 \(n = k\) 结论也成立，两边同时乘以相同矩阵可得：

\[\begin{bmatrix} a_1 & a_2 &\dots &a_{i-1} &a_i\\ 1 & 0 &\dots & 0 &0\\ 0 & 1 &\dots & 0 &0\\ \vdots &\vdots &\vdots &\vdots &\vdots\\ 0 & 0 &\dots & 1 &0\\ \end{bmatrix}^{k+1} \begin{bmatrix} f_{i-1}\\ f_{i-2}\\ \vdots\\ f_1\\ f_0\\ \end{bmatrix} = \begin{bmatrix} a_1 & a_2 &\dots &a_{i-1} &a_i\\ 1 & 0 &\dots & 0 &0\\ 0 & 1 &\dots & 0 &0\\ \vdots &\vdots &\vdots &\vdots &\vdots\\ 0 & 0 &\dots & 1 &0\\ \end{bmatrix} \begin{bmatrix} f_{k+i-1}\\ f_{k+i-2}\\ \vdots\\ f_{k+1}\\ f_k\\ \end{bmatrix} = \begin{bmatrix} f_{n+k}\\ f_{n+k-1}\\ \vdots\\ f_{n+2}\\ f_{n+1}\\ \end{bmatrix} \]

所以 \(n = k + 1\) 时也成立。得证。

　　由上述结论我们很容易构造出转移矩阵 $$A=\begin{bmatrix}2&0&-1\1&0&0\0&1&0 \end{bmatrix}$$，初始矩阵为 $$S=\begin{bmatrix} S_2\S_1\S_0\end{bmatrix}=\begin{bmatrix}2\1\0 \end{bmatrix}$$ 。

方二：分析

显然有：\(S(n)=f(n+2)-f(2)\)

证明：

\[\begin{align} \notag &f(3)=f(1)+f(2)\iff f(1)=f(3)-f(2)\\\notag &f(2)=f(4)-f(3)\\\notag &f(3)=f(5)-f(4)\\\notag &f(n)=f(n+2)-f(n+1)\\\notag &前面的式子进行累加可得：\\\notag &S(n)=f(n+2)-f(2) \end{align} \]

数论芝士梳理矩阵

相关

1084: [SCOI2005]最大子矩阵

数据结构/PTA-邻接矩阵存储图的深度优先遍历/图

Numpy | 矩阵库(Matrix)

「笔记」数论知识整理

矩阵快速幂(Matrix_Fast_Power)

opencv-meanstddev计算矩阵的均值和标准偏差

动态规划之矩阵连乘

【 2019北京集训测试赛（十）】 子矩阵 二分

邻接矩阵存储创建有向图

【数论】【差分】Row GCD

【前缀和】最大子矩阵

Python代码阅读（第41篇）：矩阵转置

标签