【笔记】矩阵

矩阵笔记

矩阵

前置知识

定义

基本概念：由 $n \times m$ 个数排成 $m$ 行 $n$ 列的矩形的数表，称为一个 $m \times n$ 的矩阵，记作 $A$。其中 $a_{i,j}$ 表示第 $i$ 行第 $j$ 列的元素。

0 矩阵

对于每个矩阵中的元素 $a_{i,j}$ 都为 0，这个矩阵因此也可表示为 $0_{n,m}$

单位矩阵

单位矩阵必须保证 $n = m$，否则就不是单位矩阵，单位矩阵只有对角线上的数为 1，其余的数都为 0。

举个例子：

\[\begin{bmatrix}

1 & 0 & 0 & 0 \\

0 & 1 & 0 & 0 \\

0 & 0 & 1 & 0 \\

0 & 0 & 0 & 1 \\

\end{bmatrix}

这就是个单位矩阵，可以表示为 $I_{n}$，单位矩阵的作用相当于我们运算中的 1。用它来乘以任意数都为本身。

其他的一些矩阵

好像一般用不到？

对角矩阵，纯量矩阵，上三角矩阵，下三角矩阵，对称矩阵，反对称矩阵。

矩阵运算

加减法运算

对于相加和相减的两个矩阵，必须保证两个矩阵大小相同才能做矩阵加减法运算。

加减法运算的两个矩阵直接对应位置相加或者相减就可以了。

\(\begin{bmatrix}

a_{1,1} & \cdots & a_{1,m} \\

\vdots & \ddots & \vdots \\

a_{n,1} & \cdots & a_{n,m} \\

\end{bmatrix}\) + \(\begin{bmatrix}

b_{1,1} & \cdots & b_{1,m} \\

b_{n,1} & \cdots & b_{n,m} \\

\end{bmatrix}\) = \(\begin{bmatrix}

a_{1,1} + b_{1,1} & \cdots & a_{1,m} + b_{1,m} \\

a_{n,1} + b_{n,1} & \cdots & a_{n,m} + b_{n,m}\\

\end{bmatrix}\)

是不是很好理解 /cy

矩阵的加减法满足交换律和结合律。

数乘运算

$k \times$ \(\begin{bmatrix}

k \times a_{1,1} & \cdots & k \times a_{1,m} \\

k \times a_{n,1} & \cdots & k \times a_{n,m} \\

矩阵乘法

定义：矩阵的乘法

如果要使用矩阵乘法，两个矩阵必须是其中的一个矩阵的行数等与另一个矩阵的列数，即 $A_{n,q}$ 与 $B_{q,m}$ 可以进行矩阵乘法，得出的矩阵的行数是第一个矩阵的行数，矩阵的列数是第二个矩阵的列数。

我们设 $A = (a_{i,j})_{m \times r},B = (b_{i,j})_{r \times n}$，则矩阵 $C = (c_{i,j})_{m,n}$，其中 $c_{i,j} = a_{i,1}b_{1,j} + a_{i,2} b_{2,j} + \cdots + a_{i,r} b_{r,j}$。

记作 $C = A * B$。

举个例子 :

我们设一个 $A_{2,2}$，一个 $B_{2,3}$，我们将会的到一个 $C_{2,3}$ 的矩阵。

$\begin{bmatrix}

1 & 2 \

3 & 4 \

\end{bmatrix} \times $$\begin{bmatrix}

1 & 2 & 3 \

4 & 5 & 6 \

\end{bmatrix} =$ \(\begin{bmatrix}

9 & 12 & 15 \\

19 & 26 & 33 \\

$C_{i,j} = \sum$ 第一个矩阵的第 $i$ 行的每个数与第二个矩阵的第 $j$ 列每个数相乘(一一对应)。

矩阵乘法的性质

$0_{n,m} A_{m,k} = 0,A_{k,m} 0_{m,n} = 0$。
$I_{n,m} A_{m,k} = A,A_{k,m} I_{m,n} = A$。
$A(BC) = (AB)C$
$A(B + C) = AB + BC$，左分配率律
$(B + C) A = B A + C A$，右分配率律

注意左右两分配率矩阵相乘的顺序不能颠倒。

矩阵乘法没有交换律！！！

但是有三种特殊情况，交不交换无所谓。

$O A = A O = 0$

$I A = A I = A$

$A A = A A = A ^ 2$

下面给出一个矩阵乘法的代码。

$\text{problem}$ ： Link

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int Maxk = 110;
int n,m,p;
struct Matrix {
  int n1,m1;
  int z[Maxk][Maxk];
  Matrix (){
    n1 = m1 = 0;
    memset(z,0,sizeof z);
  }
} A , B ; 
inline int read()
{
	int s = 0, f = 0;char ch = getchar();
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}
Matrix operator * (const Matrix &m1,const Matrix &m2)
{
  Matrix m3;
  m3.n1 = m1.n1;
  m3.m1 = m2.m1;
  for(int i = 1;i <= m3.n1;i ++) 
    for(int k = 1;k <= m1.m1;k ++) 
      for(int j = 1;j <= m2.m1;j ++)
        m3.z[i][j] += m1.z[i][k] * m2.z[k][j];
  return m3;  
} 
signed main()
{
  n = read(),m = read();
  for(int i = 1;i <= n;i ++) 
    for(int j = 1;j <= m;j ++) 
      A.z[i][j] = read();
  p = read();
  for(int i = 1;i <= m;i ++) 
    for(int j = 1;j <= p;j ++)
      B.z[i][j] = read();
  A.n1 = n,A.m1 = m;
  B.n1 = m,B.m1 = p;
  Matrix Ans = A * B;
  for(int i = 1;i <= n;i ++) {
    for(int j = 1;j <= p;j ++)  {
      cout << Ans.z[i][j] << " ";
    }
    cout << '\n';
  }
  return 0;
}

矩阵快速幂

矩阵快速幂就是把快速幂和矩阵乘法结合起来，没有什么很难的，我们只需要像快速幂那样先初始化一个单位矩阵，之后按照快速幂的形式不断相乘即可。

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int mod = 1e9 + 7; 
const int Maxk = 110;
int n,m;
struct Matrix {
  int n1,m1;
  int z[Maxk][Maxk];
  Matrix (){
    n1 = m1 = 0;
    memset(z,0,sizeof z);
  }
} A , E ; 
inline int read()
{
	int s = 0, f = 0;char ch = getchar();
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}
Matrix operator * (const Matrix &m1,const Matrix &m2)
{
  Matrix m3;
  m3.n1 = m1.n1;
  m3.m1 = m2.m1;
  for(int i = 1;i <= m3.n1;i ++) 
    for(int k = 1;k <= m1.m1;k ++) 
      for(int j = 1;j <= m2.m1;j ++) {
        m3.z[i][j] = m3.z[i][j] + m1.z[i][k] * m2.z[k][j];
        if(m3.z[i][j] >= mod) m3.z[i][j] %= mod;
      }
  return m3;  
} 
signed main()
{
  n = read(),m = read();
  for(int i = 1;i <= n;i ++) 
    for(int j = 1;j <= n;j ++) 
      A.z[i][j] = read();
  A.n1 = n,A.m1 = n;
  for(int i = 1;i <= n;i ++) E.z[i][i] = 1;//初始化单位矩阵
  E.n1 = n,E.m1 = n;
  while(m) {//按照快速幂的方法来乘
    if(m & 1) E = E * A;
    A = A * A;
    m >>= 1; 
  }
  for(int i = 1;i <= n;i ++) {
    for(int j = 1;j <= n;j ++) {
      cout << E.z[i][j] << " ";
    } 
    cout << "\n"; 
  } 
  return 0;
}

矩阵乘法应用 & 矩阵加速

因为矩阵加减法太简单了，所以基本没有什么题目来考矩阵加减法。

斐波那契数列加速求解

$\text{problem}$ : Link

首先我们知道 $f_{i} = f_{i - 1} + f_{i - 2}$。

很多这种递推式都可用矩阵来加速，我们只要找到一个矩阵，保证这个矩阵在不变的情况下就可以来求出下一项，我们就可以矩阵加速求解。

我们定义 $A$ 矩阵为

f_{n} & f_{n - 1}

\end{bmatrix}\]

我们要求的 $C$ 矩阵为

f_{n + 1} & f_{n}

我们要找一个 $B$ 矩阵，保证在 $B$ 矩阵不变的情况下就可以进行矩阵加速。

如何来找这个矩阵？

首先，我们的 $C$ 矩阵有一行两列，所以可以得出，我们的 $B$ 矩阵是两行两列，设 $B$ 矩阵为 :

a & b \\

c & d \\

根据矩阵乘法，显然可以得到：

\[\begin{aligned}

f_{n + 1} &= a \times f_{n} + c \times f_{n - 1} \\

f_{n} &= b \times f_n + d \times f_{n - 1} \\

\end{aligned}\]

所以我们很容易的到 $b = 1,d = 0$，之后在根据 $f_n = f_{n - 1} + f_{n - 2}$，所以 $a = 1,b = 1$。

我们的 $B$ 矩阵就可以得出了 :

1 & 1 \\

1 & 0 \\

之后我们直接套一个快速幂就可以解决了。

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int mod = 1e9 + 7; 
const int Maxk = 110;
int n,m;
struct Matrix {
  int n1,m1;
  int z[3][3];
  Matrix (){
    n1 = m1 = 0;
    memset(z,0,sizeof z);
  }
} A ,B,E ; 
inline int read()
{
	int s = 0, f = 0;char ch = getchar();
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}
Matrix operator * (const Matrix &m1,const Matrix &m2)
{
  Matrix m3;
  m3.n1 = m1.n1;
  m3.m1 = m2.m1;
  for(int i = 1;i <= m3.n1;i ++) 
    for(int k = 1;k <= m1.m1;k ++) 
      for(int j = 1;j <= m2.m1;j ++) {
        m3.z[i][j] = m3.z[i][j] + m1.z[i][k] * m2.z[k][j];
        if(m3.z[i][j] >= mod) m3.z[i][j] %= mod;
      }
  return m3;  
} 
signed main()
{
  n = read();
  if(n == 1 || n == 0) {
    cout << 1 << endl;
    return 0;
  }
  A.z[1][1] = 1,A.z[1][2] = 0;
  A.n1 = 1,A.m1 = 2;
  B.z[1][1] = 1,B.z[1][2] = 1;
  B.z[2][1] = 1,B.z[2][2] = 0;
  B.n1 = 2,B.m1 = 2;
  for(int i = 1;i <= 2;i ++) E.z[i][i] = 1;//初始化单位矩阵
  E.n1 = 2,E.m1 = 2;
  m = n - 1;
  while(m) {
    if(m & 1) E = E * B;
    B = B * B;
    m >>= 1; 
  }
  A = A * E;
  cout << A.z[1][1] % mod;
  return 0;
}

斐波那契数列求和

似乎和前面差不多，也是推式子。

我们用 $S_i$ 代表从第 $1$ 项到第 $i$ 项的和，显然 $A$ 矩阵和 $C$ 矩阵一样设就行了，上面是 $A$，下面是 $C$。

f_{n} & f_{n - 1} & S_n

f_{n + 1} & f_{n} & S_{n + 1}

明显我们要设一个 $B$ 矩阵，行列都为 3。

a & b & c\\

d & e & f \\

g & h & i \\

得出：

f_{n + 1} &= a \times f_{n} + d \times f_{n - 1} + g \times S_n \\

f_{n} &= b \times f_n + e \times f_{n - 1} + h \times S_n \\

S_{n + 1} &= c \times f_n + f \times f_{n - 1} + i \times S_n \\

所以化简一下就得到了矩阵 $B$ ：

1 & 1 & 1\\

1 & 0 & 1 \\

0 & 0 & 1 \\

其实还有一种方法：

\[S_n = f_0 + f_1 + \cdots + f_n \\ S_{n + 1} = f_0 + f_1 + \cdots + f_{n + 1}

S_n + S_{n + 1} &= f_0 + f_2 + f_3 + \cdots f_{n + 2} \\

&= S_{n + 2} - f_0 \\

&= S_{n + 2} - 1

注意如果有常数想的情况下要增加一个维度来存常数项。

S_n & S_{n - 1} & 1

S_{n + 1} & S_{n} & 1

的出的 $B$ 矩阵为：

1 & 1 & 0\\

1 & 0 & 0 \\

就不再多阐述了。

Problem

由于上课的时候没怎么听懂，先说一下题面。。

Description

$n$ 个点的图，共有 $m$ 条边，且都是单向边。

$M_{i,j}$ 表示从第 $i$ 个点到第 $j$ 个点有多少条边。

求从 1 号点走 $t$ 条边到第 $n$ 号点的方案数。

$n \leq 100,t \leq 10 ^ 9$。

Solution

咕咕咕

如果要用矩阵乘法加速 $DP$，要保证两点。

必须从 $i - 1$ 转移到 $i$。
$M$ 不会随着 $i$ 的改变而改变，即第二个矩阵无关。

【笔记】矩阵

矩阵

前置知识

矩阵运算

矩阵乘法应用 & 矩阵加速

斐波那契数列加速求解

斐波那契数列求和

Problem

Description

Solution

继续阅读

python学习——阿里云天池龙珠计划（python训练营）——task01注释运算符位运算条件语句循环语句for循环异常处理结尾

天池龙珠金融风控训练营Task04学习笔记前言学习知识点概要学习内容学习问题与解答学习思考与总结

2021-09-301、Ubuntu18.04安装Google浏览器2、待定

（Nginx）03_Nginx原理与优化一、Nginx原理二、master-workers机制三、面试题：

（Nginx）02_Nginx配置实例一、Nginx的应用：反向代理实现一：二、反向代理实例二：三、Nginx的配置实例三–负载均衡：四、Nginx的配置实例四–动静分离：Nginx在实际开发中的应用：

nginx配置示例

2022秋招面试记录与反思

《断舍离》读后感

unity中实现背景滚动

命令行和环境变量

Android记事本（附apk和源码）

现国内基金定投最好的入门书《指数基金投资指南》

【人工智能行业大师访谈1】吴恩达采访 Geoffery Hinton

线程同步，可重入锁，synchronized

对象锁和全局锁

iview后台管理模版