矩阵
向量与矩阵
向量也是特殊的矩阵，行向量可以看作是一个 \(1\times n\) 的矩阵，例如下面这样：
也可以写成由行向量转置而来的，比如上面的列向量可以这样写：
如果想要表示行向量，需要在粗体小写字母右上方写转置符号。行向量在线性代数中一般表示方程。
引入
一般使用圆括号或方括号来表示矩阵。上面的方程组写成矩阵的形式就是：
我觉得方括号更整齐好看于是就用的方括号
表示位置数列向量 \(x\) 左乘一个矩阵 \(A\)，得到列向量 \(b\)。这个式子可以认为是线性代数的基本形式。
定义
对于矩阵 \(A\)，主对角线是指 \(A_{i,i}\) 的元素。
同型矩阵
两个矩阵，行数和列数对应相同，则称为同型矩阵。
方阵
主对角线
方阵中行数等于列数的元素构成主对角线
对称矩阵
对角矩阵
主对角线之外的元素均为 \(0\) 的方阵称为对角矩阵，一般记作：
对角矩阵是对称矩阵。
三角矩阵
如果方阵主对角线左下方的元素均为 \(0\)，则称为上三角矩阵，如果方阵主对角线右上方元素均为 \(0\)，则称为下三角矩阵。
单位三角矩阵
如果上三角矩阵 \(A\) 的对角线全为 \(1\)，则称 \(A\) 是单位上三角矩阵。如果下三角矩阵 \(A\) 的对角线全为 \(1\)，则称 \(A\) 是单位下三角矩阵。
运算
矩阵的线性运算分为加减法与数乘，他们均为逐个元素进行。只有同型矩阵之间可以对应相加减。
矩阵的转置
对称矩阵转置前后保持不变。
矩阵乘法
矩阵相乘只有在第一个矩阵的列数和第二个矩阵的行数相同时才有意义。
其中矩阵 \(C\) 中的第 \(i\) 行第 \(j\) 列的元素可以表示为：
在矩阵乘法中，结果 \(C\) 矩阵的第 \(i\) 行第 \(j\) 列的数，就是由矩阵 \(A\) 第 \(i\) 行 \(M\) 个数与矩阵 \(B\) 第 \(j\) 列 \(M\) 个数分别相乘再相加得到的。这里的相乘再相加，就是向量的内积。乘积矩阵中第 \(i\) 行第 \(j\) 列的数恰好是乘数矩阵 \(A\) 第 \(i\) 个行向量与乘数矩阵 \(B\) 第 \(j\) 个列向量的内积。
矩阵乘法满足结合律但不满足一般的交换律
小优化
对于较小的矩阵，可以直接手动展开循环来减小常数。
矩阵快速幂
快速幂都会，那矩阵快速幂呢？
大致的写法分为两种：重载运算符和函数，我个人比较喜欢函数的写法。
P3390【模板】矩阵快速幂 - 洛谷
#include<bits/stdc++.h>
#define int long long
#define P 1000000007
#define endl '\n'
#define N 110
using namespace std;
struct sb{int m[N][N];}ans;
int n,k;
inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){f=ch!='-';ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return f?x:-x;}
inline sb cheng(sb a,sb b)
{
sb c;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
c.m[i][j]=0;
for(int k=1;k<=n;k++)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%P;
}
}
return c;
}
inline sb jzksm(sb x,int y)
{
sb res=x;y--;
while(y)
{
if(y&1)res=cheng(res,x);
x=cheng(x,x);
y>>=1;
}
return res;
}
signed main()
{
n=read();k=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ans.m[i][j]=read();
ans=jzksm(ans,k);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<ans.m[i][j]<<" ";
cout<<endl;
}
return 0;
}
方阵的逆
方阵 \(A\) 的逆矩阵 \(P\) 是使得 \(A\times P=I\) 的矩阵。
方阵的行列式
行列式是方阵的一种运算。
看待线性方程组的两种视角
第一种观点：按行看，观察 \(A\) 的每一行，这样一来把 \(A\) 看作方程组。于是就有了消元法解方程的过程。
例如：文章开头的例子变为：
按列看比按行看更新颖。在按列看的视角下，可以研究线性无关与线性相关。
矩阵乘法的应用
矩阵加速递推
我们在之前的题目遇见的求斐波那契数列第 \(n\) 项的值范围都是很小的，因为递归的速度太慢，如果数据范围到达了 \(10^{18}\) 那么我们递推也是一定 TLE 的，所以这个时候就需要用到我们的矩阵加速递推。
试着来推导一个矩阵 \(\text{base}\)，使 \(Fib(n-1)\times \text{base}=Fib(n)\)，也就是 \(\begin{bmatrix}F_{n-1}&F_{n-2}\end{bmatrix}\times \text{base}=\begin{bmatrix}F_{n}&F_{n-1}\end{bmatrix}\)。
综上所述，\(\text{base}=\begin{bmatrix}1&1\\1&0\end{bmatrix}\)，原式化为 \(\begin{bmatrix}F_{n-1}&F_{n-2}\end{bmatrix}\times \begin{bmatrix}1&1\\1&0\end{bmatrix}=\begin{bmatrix}F_{n}&F_{n-1}\end{bmatrix}\)。
注意矩阵乘法不满足交换律，所以不能将两个矩阵反过来，另外，对于 \(n\le 2\) 的情况，可以直接输出 \(1\)。
参考代码：
#include<bits/stdc++.h>
#define int long long
#define P 1000000007
#define N 110
using namespace std;
int n;
struct sb{int m[N][N];}ans,base;
inline sb cheng(sb a,sb b,int ok)
{
sb c;
for(int i=1;i<=ok;i++)
{
for(int j=1;j<=ok;j++)
{
c.m[i][j]=0;
for(int k=1;k<=ok;k++)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%P;
}
}
return c;
}
inline sb jzksm(sb x,int y)
{
sb res=x;y--;
while(y)
{
if(y&1)res=cheng(res,x,2);
x=cheng(x,x,2);
y>>=1;
}
return res;
}
signed main()
{
cin>>n;
if(n==1||n==2){puts("1");return 0;}
ans.m[1][1]=1;ans.m[1][2]=1;
base.m[1][1]=1;base.m[1][2]=1;
base.m[2][1]=1;base.m[2][2]=0;
base=jzksm(base,n-2);
ans.m[1][1]=(base.m[1][1]+base.m[1][2])%P;
cout<<ans.m[1][1]<<endl;
return 0;
}
大部分内容来自 OI Wiki。