矩阵学习笔记

数学 学习笔记

---

定义

矩阵的定义

矩阵是一个按照长方阵列排列的复数或实数集合
例如：

$$\begin{bmatrix} 1&2\\ 3&4\\ 5&6 \end{bmatrix}$$

矩阵的运算

1. 矩阵的加法
   必须相同大小的矩阵才能进行加法
   $$\begin{gather*} \begin{bmatrix} 1&2\\ 3&4\\ 5&6 \end{bmatrix} +\begin{bmatrix} 5&4\\ 3&2\\ 1&0 \end{bmatrix} =\begin{bmatrix} 6&6\\ 6&6\\ 6&6 \end{bmatrix} \end{gather*}$$
2. 矩阵的减法
   必须相同大小的矩阵才能进行加法
   $$\begin{gather*} \begin{bmatrix} 6&5\\ 4&3\\ 2&5 \end{bmatrix} -\begin{bmatrix} 5&4\\ 3&2\\ 1&0 \end{bmatrix} =\begin{bmatrix} 1&1\\ 1&1\\ 1&1 \end{bmatrix} \end{gather*}$$
3. 矩阵的数乘
   $$\begin{gather*} 6\times \begin{bmatrix} 1&1\\ 1&1\\ 1&1 \end{bmatrix} =\begin{bmatrix} 6&6\\ 6&6\\ 6&6 \end{bmatrix} \end{gather*}$$
4. 矩阵的乘法
   只有第一个矩阵的列数=第二个矩阵的行数才能进行乘法
   $$若A\times B=C，且A的大小为n\times m，B的大小为m\times k，那么C的大小为n\times k$$
   $$\begin{gather*} \begin{bmatrix} 1&2\\ 3&4\\ 5&6 \end{bmatrix} \times \begin{bmatrix} 8&9&10&11\\ 12&13&14&15 \end{bmatrix} =\begin{bmatrix} 32&35&38&41\\ 72&79&86&93\\ 112&123&134&145\\ \end{bmatrix} \end{gather*}$$
5. 矩阵的乘方（快速幂）
   $$A^2=A\times A,A^n=A\times A\cdot\cdot\cdot\times A(n个A)$$
   矩阵的乘方可以用快速幂在O(log n)内求出结果

单位矩阵

在矩阵的乘法中，有一种矩阵起着特殊的作用，如同数的乘法中的1，这种矩阵被称为单位矩阵。
单位矩阵是个方阵，从左上角到右下角的对角线（称为主对角线）上的元素均为1。除此以外全都为0。

矩阵的性质

$$如果A\times B=C，则C_{i,j}=\sum_{k=1}^n A_{i,k}\cdot B_{k,j}$$
1. 矩阵的加法满足交换律 $$A+B=B+A$$
2. 矩阵的加法满足结合律 $$(A+B)+C=A+(B+C)$$
3. 矩阵的数乘满足结合律 $$\lambda(\mu A)=\mu(\lambda A)$$
4. 矩阵的数乘满足分配律 $$(\lambda+\mu)A=\lambda A+\mu A,\lambda(A+B)=\lambda A+\lambda B$$
5. 矩阵的乘法不满足交换律 $$A\times B\neq B\times A$$
6. 矩阵的乘法满足结合律 $$A\times (B\times C)=(A\times B)\times C$$
7. 矩阵的乘法满足分配律 $$(A+B)\times C=A\times C+B\times C$$

dp的矩阵加速

例1：斐波那契数列

• 题意
  求斐波那契数列的第$n$项，即$f(n) (n<2^{63})$，且$f(n)=f(n-1)+f(n-2)$

• 暴力做法：时间$O(n)$，空间$O(n)$
  开f数组爆算斐波那契数列

• 滚动数组做法：时间$O(n)$，空间$O(1)$
  直接用$a,b,c$三个变量滚动使用，每次让$c=a+b$，然后$a=b,b=c$，这样就可以用$O(n)$的时间求出答案
• 矩阵加速做法：时间$O(\log n)$，空间$O(能过)$
  我们观察原式$f(n)=f(n-1)+f(n-2)$
  然后尝试构造矩阵，使：
  $$\begin{gather*} \begin{bmatrix} f[n-1]&f[n] \end{bmatrix} \times \begin{bmatrix} p&q\\ r&s \end{bmatrix} =\begin{bmatrix} f[n]&f[n+1] \end{bmatrix} \end{gather*}$$
  中间的矩阵就是我们初始的矩阵
  根据上面一式我们可以推出
  $$\begin{gather*} f[n-1]\times p+f[n]*r=f[n]\\\\ f[n-1]*q+f[n]*s=f[n+1] \end{gather*}$$
  解得该式的一组解为$p=0,q=1,r=1,s=1$，即初始矩阵为
  $$\begin{bmatrix} 0&1\\ 1&1 \end{bmatrix}$$
  于是，我们的答案就是这个矩阵的$n+1$次方（因为初始矩阵相当于$[0,1]$，所以它要乘$n+1$次）的第一行第一列

例2：【模板】矩阵加速（数列）

• 题意
  给定数组a[]，且a[1]=a[2]=a[3]=1，a[i]=a[i-1]+a[i-3]，求a[n]

• 矩阵加速1
  我们需要的矩阵为：
  

  $$\begin{gather*} \begin{bmatrix} a[n-3]&a[n-2]&a[n-1] \end{bmatrix} \times \begin{bmatrix} i&j&k\\ p&q&r\\ x&y&z \end{bmatrix} =\begin{bmatrix} a[n-2]&a[n-1]&a[n] \end{bmatrix} \end{gather*}$$
  然后推出：
  $$\begin{gather*} a[n-3]\times i+a[n-2]\times p+a[n-1]\times x=a[n-2]\\\\ a[n-3]\times j+a[n-2]\times q+a[n-1]\times y=a[n-1]\\\\ a[n-3]\times k+a[n-2]\times r+a[n-1]\times z=a[n] \end{gather*}$$
  解得该式的一组解为 $$i=0,j=1,k=0\\p=0,q=0,r=1\\x=1,y=0,z=1$$ ，即初始矩阵为
  $$\begin{bmatrix} 0&1&0\\ 0&0&1\\ 1&0&1 \end{bmatrix}$$
  然后直接矩阵快速幂O(log n)求解，答案为
  $$\begin{gather*} \begin{bmatrix} 1&1&1 \end{bmatrix} \times \begin{bmatrix} 0&1&0\\ 0&0&1\\ 1&0&1 \end{bmatrix}^{n-3} \end{gather*}$$ 的第一行第三列

#include<stdio.h>
const long long mod=1000000007;
long long i,j,k,m,n,T;
struct matrix{
    int len,wid;
    long long mt[105][105];
}ans;
matrix mul(matrix a,matrix b){
    matrix res;
    res.len=a.len,res.wid=b.wid;
    for(int u=1;u<=a.len;u++)
        for(int v=1;v<=b.wid;v++)
            res.mt[u][v]=0;
    for(int u=1;u<=a.len;u++)
        for(int v=1;v<=b.wid;v++)
            for(int w=1;w<=a.wid;w++)
                res.mt[u][v]+=(a.mt[u][w]*b.mt[w][v])%mod,res.mt[u][v]%=mod;
    return res;
}
long long calc(long long b){
    matrix a,res;
    a.len=a.wid=3;
    a.mt[1][1]=a.mt[1][3]=a.mt[2][1]=a.mt[2][2]=a.mt[3][2]=0;
    a.mt[1][2]=a.mt[2][3]=a.mt[3][1]=a.mt[3][3]=1;
    res.len=1,res.wid=3;
    res.mt[1][1]=res.mt[1][2]=res.mt[1][3]=1;
    while(b){
        if(b&1)
            res=mul(res,a);
        a=mul(a,a),b>>=1;
    }
    return res.mt[1][3];
}
int main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld",&n);
        if(n<=3){
            puts("1");
            continue;
        }
        printf("%lld\n",calc(n-3));
    }
    return 0;
}

• 矩阵加速2
  我们需要的矩阵为：
  $$\begin{gather*} \begin{bmatrix} a[n-1]&a[n-2]&a[n-3] \end{bmatrix} \times \begin{bmatrix} i&j&k\\ p&q&r\\ x&y&z \end{bmatrix} =\begin{bmatrix} a[n]&a[n-1]&a[n-2] \end{bmatrix} \end{gather*}$$
  然后推出：
  $$\begin{gather*} a[n-1]\times i+a[n-2]\times p+a[n-3]\times x=a[n]\\\\ a[n-1]\times j+a[n-2]\times q+a[n-3]\times y=a[n-1]\\\\ a[n-1]\times k+a[n-2]\times r+a[n-3]\times z=a[n-2] \end{gather*}$$
  解得该式的一组解为 $$i=1,j=0,k=1\\p=1,q=0,r=0\\x=0,y=1,z=0$$ ，即初始矩阵为
  $$\begin{bmatrix} 1&0&1\\ 1&0&0\\ 0&1&0 \end{bmatrix}$$
  然后直接矩阵快速幂O(log n)求解，答案为
  $$\begin{gather*} \begin{bmatrix} 1&1&1 \end{bmatrix} \times \begin{bmatrix} 1&0&1\\ 1&0&0\\ 0&1&0 \end{bmatrix}^{n-3} \end{gather*}$$
  的第一行第一列

#include<stdio.h>
const long long mod=1000000007;
long long i,j,k,m,n,T;
struct matrix{
    int len,wid;
    long long mt[105][105];
}ans;
matrix mul(matrix a,matrix b){
    matrix res;
    res.len=a.len,res.wid=b.wid;
    for(int u=1;u<=a.len;u++)
        for(int v=1;v<=b.wid;v++)
            res.mt[u][v]=0;
    for(int u=1;u<=a.len;u++)
        for(int v=1;v<=b.wid;v++)
            for(int w=1;w<=a.wid;w++)
                res.mt[u][v]+=(a.mt[u][w]*b.mt[w][v])%mod,res.mt[u][v]%=mod;
    return res;
}
long long calc(long long b){
    matrix a,res;
    a.len=a.wid=3;
    a.mt[1][2]=a.mt[2][2]=a.mt[2][3]=a.mt[3][1]=a.mt[3][3]=0;
    a.mt[1][1]=a.mt[1][3]=a.mt[2][1]=a.mt[3][2]=1;
    res.len=1,res.wid=3;
    res.mt[1][1]=res.mt[1][2]=res.mt[1][3]=1;
    while(b){
        if(b&1)
            res=mul(res,a);
        a=mul(a,a),b>>=1;
    }
    return res.mt[1][1];
}
int main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld",&n);
        if(n<=3){
            puts("1");
            continue;
        }
        printf("%lld\n",calc(n-3));
    }
    return 0;
}

• 矩阵加速3
  我们需要的矩阵为：
  $$\begin{gather*} \begin{bmatrix} a[n-3]&a[n-4]&a[n-5] \end{bmatrix} \times \begin{bmatrix} i&j&k\\ p&q&r\\ x&y&z \end{bmatrix} =\begin{bmatrix} a[n]&a[n-1]&a[n-2] \end{bmatrix} \end{gather*}$$
  然后推出：
  $$\begin{gather*} a[n-3]\times i+a[n-4]\times p+a[n-5]\times x=a[n]\\\\ a[n-3]\times j+a[n-4]\times q+a[n-5]\times y=a[n-1]\\\\ a[n-3]\times k+a[n-4]\times r+a[n-5]\times z=a[n-2] \end{gather*}$$
  解得该式的一组解为 $$i=2,j=1,k=1\\p=1,q=1,r=1\\x=1,y=0,z=1$$ ，即初始矩阵为
  $$\begin{bmatrix} 2&1&1\\ 1&1&1\\ 1&0&1 \end{bmatrix}$$
  然后直接矩阵快速幂O(log n)求解，答案为
  $$\begin{gather*} \begin{bmatrix} 1&1&1 \end{bmatrix} \times \begin{bmatrix} 2&1&1\\ 1&1&1\\ 1&0&1 \end{bmatrix}^{\frac{n-1}{3}} \end{gather*}$$
  的第一行第n%3+1列

#include<stdio.h>
const long long mod=1000000007;
long long i,j,k,m,n,T;
struct matrix{
    int len,wid;
    long long mt[105][105];
}ans;
matrix mul(matrix a,matrix b){
    matrix res;
    res.len=a.len,res.wid=b.wid;
    for(int u=1;u<=a.len;u++)
        for(int v=1;v<=b.wid;v++)
            res.mt[u][v]=0;
    for(int u=1;u<=a.len;u++)
        for(int v=1;v<=b.wid;v++)
            for(int w=1;w<=a.wid;w++)
                res.mt[u][v]+=(a.mt[u][w]*b.mt[w][v])%mod,res.mt[u][v]%=mod;
    return res;
}
long long calc(long long n){
    long long b=(n-1)/3;
    matrix a,res;
    a.len=a.wid=3;
    a.mt[3][2]=0;
    a.mt[1][2]=a.mt[1][3]=a.mt[2][1]=a.mt[2][2]=a.mt[2][3]=a.mt[3][1]=a.mt[3][3]=1;
    a.mt[1][1]=2;
    res.len=1,res.wid=3;
    res.mt[1][1]=res.mt[1][2]=res.mt[1][3]=1;
    while(b){
        if(b&1)
            res=mul(res,a);
        a=mul(a,a),b>>=1;
    }
    return res.mt[1][n%3+1];
}
int main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld",&n);
        if(n<=3){
            puts("1");
            continue;
        }
        printf("%lld\n",calc(n));
    }
    return 0;
}

题单

LOJ

• 矩阵乘法

洛谷

• 【模板】快速幂||取余运算
• 【模板】矩阵快速幂
• 【模板】矩阵加速（数列）
• 斐波那契数列
• [TJOI2017]可乐
• 帕秋莉的手环

POJ

• Matrix Power Series
• DNA Sequence
• Fibonacci
• Scout YYF I
• Cow Relays

HDU

• Another kind of Fibonacci
• 233 Matrix
• How many ways??
• Evaluation
• The Boss on Mars
• Arc of Dream

ZOJ

• Mistwald
• Calculate the Function