线性代数-矩阵

施工中，咕咕咕....

矩阵乘法

1. 矩阵乘法的定义

矩阵乘法的定义 \[ (AB)_{i,j}=\sum_{k=1}^{m}A_{i,k}B_{k,j}\quad i\in[1,n],j\in[1,p] \] 一个 \(n \times m\) 的矩阵和 \(m\times p\) 的矩阵相乘，答案为一个 \(n \times p\) 的矩阵

注意，矩阵乘法没有叉乘的定义，因为叉乘通常是指在向量空间中的一种运算

列向量可以右乘矩阵（左乘需要转置为行向量），且乘积不一定相等：\(Mv \not\Leftrightarrow v^{\top}M\)

2. 快速手算

矩阵乘法的计算方法有很多种，这里提供两种方法。

第一种是传统的逆时针旋转右侧矩阵，可以在这里看动画演示。

第二种是 Roundgod 老师告诉我们的方法，如下

例： \[ \begin{bmatrix}1&2\\3&4\\\end{bmatrix} \times \begin{bmatrix}5&6\\7&8\\\end{bmatrix} \] 第一行： \[ \begin{matrix} 1\times5 & 1 \times 6 \\ +&+ \\2\times 7&2 \times 8 \\ \downarrow & \downarrow \\ 19 & 22 \end{matrix} \] 第二行 \[ \begin{matrix} 3\times 5& 3\times 6 \\+&+ \\4 \times 7& 4\times 8 \\\downarrow&\downarrow \\43&50 \end{matrix} \]

最后的答案 \[ \begin{bmatrix}19&22\\43&50\\\end{bmatrix} \]

这个可以从矩阵快速幂的那个矩阵构造感受到原理，可以看这篇

3. 特殊矩阵

单位矩阵 \[ I=\begin{bmatrix}1&&&\\&1&&\\&&\ddots&\\&&&1\\\end{bmatrix} \] 满足对于任意矩阵 \(A\) 有 \[ AI=IA=A \]

4. 矩阵乘法的性质

矩阵乘法具有结合律 \[ (AB)C=A(BC) \] 矩阵乘法具有左右分配律 \[ (A+B)C=AC+BC \\C(A+B)=CA+CB \] 矩阵乘法不一定具有交换律 \[ AB\ne BA \]

5. 矩阵快速幂

优化递推

例： \[ f_i = 2f_{i-1}+4f_{i-2}+3f_{i-3} \] 尝试构造矩阵使得 \[ \begin{bmatrix}f_{i}\\f_{i-1}\\f_{i-2}\end{bmatrix}=M\times\begin{bmatrix}f_{i-1}\\f_{i-2}\\f_{i-3}\end{bmatrix} \] 显然 \(M\) 是一个 \(3\times 3\) 的矩阵，不难发现 \[ M=\begin{bmatrix}2&4&3\\1&0&0\\0&1&0\end{bmatrix} \] 然后我们可以用 \(M^{k-1}\) 快速计算 \(f_{k}\)

常见数据范围：\(10^{18}\)

板子题：P1962 斐波那契数列

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef vector< vector<int> > mat;
#define N (int)()
const int mod=1e9+7;
void add(int &x,int y){x+=y; if(x>=mod)x-=mod;}
// (n*m) x (m*p) = (n*p)
mat mul(mat &A,mat &B)
{
    int n=A.size(),m=A[0].size(),p=B[0].size();
    mat C(n,vector<int>(p));
    for(int k=0; k<m; k++)
        for(int i=0; i<n; i++)
            for(int j=0; j<p; j++)
                add(C[i][j],A[i][k]*B[k][j]%mod);
    return C;
}
mat qpow(mat A,int k)
{
    int n=max(A.size(),A[0].size()); 
    mat B(n,vector<int>(n));
    for(int i=0; i<n; i++) B[i][i]=1;
    while(k)
    {
        if(k&1) B=mul(B,A);
        A=mul(A,A); k>>=1;
    }
    return B;
}
void print(mat &A)
{
    int n=A.size(),m=A[0].size();
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cout << A[i][j] << " \n"[j==m-1];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    if(n<=2) cout << "1";
    else
    {
        mat A(2,vector<int>(2)),B(2,vector<int>(1));
        A[0][0]=A[0][1]=A[1][0]=1;
        B[0][0]=B[1][0]=1;
        A=qpow(A,n-2); A=mul(A,B);
        cout << A[0][0] << '\n';
    }
    return 0;
}