【详解】矩阵乘法

2024-07-04 08:12| 来源: 网络整理| 查看: 265

矩阵乘法 1. 矩阵的定义

一个 m × n m\times n m×n 的矩阵就是 m m m 行 n n n 列的数字阵列，如 2 × 3 2\times 3 2×3 的矩阵： [ 1 5 3 2 8 10 ] \left[ \begin{matrix} 1&5&3\\2&8&10\end{matrix} \right] [1258310]

实际上，矩阵类似二维数组。

2. 矩阵的运算（1）矩阵的加法和减法

矩阵的加法和减法就是将两个矩阵对应位置上的数相加减。因此，相加减的两个矩阵A，B的行列必须相同。

（2）矩阵乘法

A ， B ， C A，B，C A，B，C 是三个矩阵，若 A × B = C A\times B=C A×B=C，需要满足：

A A A 的列数必须和 B B B 的行数相等；设 A A A 是一个 n × r n\times r n×r 的矩阵， B B B 是一个 r × m r\times m r×m 的矩阵，则矩阵 A A A 乘矩阵 B B B 的乘积 C C C 是一个 n × m n\times m n×m 的矩阵； C ( i , j ) = A ( i , 1 ) × B ( 1 , j ) + A ( i , 2 ) × B ( 2 , j ) + . . . A ( r , 1 ) × B ( r , j ) C_{(i,j)}=A_{(i,1)}\times B_{(1,j)}+A_{(i,2)}\times B_{(2,j)}+...A_{(r,1)}\times B_{(r,j)} C(i,j)=A(i,1)×B(1,j)+A(i,2)×B(2,j)+...A(r,1)×B(r,j)

矩阵 C C C 的第 i i i 行第 j j j 列元素 = = = 矩阵 A A A 的第 i i i 行元素与矩阵 B B B的第 j j j 列对应元素乘积之和。

例如： A = [ a b c d e f ] A=\left[ \begin{matrix} a&b\\c&d\\e&f\end{matrix} \right] A=⎣⎡acebdf⎦⎤， B = [ g h i j k l ] B=\left[ \begin{matrix} g&h&i\\j&k&l\end{matrix} \right] B=[gjhkil]，求 C = A × B C=A\times B C=A×B 。

A × B = [ a × g + b × j a × h + b × k a × i + b × l c × g + d × j c × h + d × k c × i + d × l e × g + f × j e × h + f × k e × i + f × l ] A\times B=\left[ \begin{matrix} a\times g+b\times j&a\times h+b\times k&a\times i+b\times l\\c\times g+d\times j&c\times h+d\times k&c\times i+d\times l\\e\times g+f\times j&e\times h+f\times k&e\times i+f\times l\end{matrix} \right] A×B=⎣⎡a×g+b×jc×g+d×je×g+f×ja×h+b×kc×h+d×ke×h+f×ka×i+b×lc×i+d×le×i+f×l⎦⎤

可以发现 A × B A\times B A×B 和 B × A B\times A B×A 将得到两种不同的结果，因此矩阵不满足乘法交换律。

（3）方阵次幂

如果矩阵的行和列相同，称矩阵为方阵。若 A A A 是一个方阵，方阵的幂是指，将 A A A 连乘 n n n 次， A n A^n An 。

若不是方阵则无法进行乘幂运算。

矩阵乘法不满足交换律，但是满足结合律，因此可以用快速幂的思想来求解方程次幂。

3. 矩阵乘法的应用

在信息学竞赛中考矩阵乘法不是为了考基本运算，而是利用矩阵乘法的特性，配合快速幂求解递推式的第 n n n 项，以及一些图论的构造转化。

【例1】 ( P O J 3070 ) (POJ \ 3070) (POJ 3070) F i b o n a c c i Fibonacci Fibonacci 第 n n n 项

【问题描述】

F i b o n a c c i Fibonacci Fibonacci 数列满足， f 0 = 0 f_0=0 f0=0 ， f 1 = 1 f_1=1 f1=1 ， f n = f n − 1 + f n − 2 （ n ≥ 2 ） f_n=f_{n-1}+f_{n-2}（n\geq 2） fn=fn−1+fn−2（n≥2）。给定整数 n （ 0 ≤ n ≤ 1 0 9 ） n（0\leq n \leq 10^9） n（0≤n≤109），输出 f n f_n fn 。

【输入格式】

有多组测试数据，每组测试输出包含一个数 n n n ，当 n n n 为 − 1 -1 −1 时结束。

【输出格式】

对于每组数据，输出 f n m o d 10000 f_n \ mod \ 10000 fn mod 10000 的值。

【样例输入】

0 9 999999999 1000000000 -1

【样例输出】

0 34 626 6875

看似一个简单的题目，但是当看到数据规模时，显然并不简单。这个时候，矩阵乘法就派上用场了。

可以知道：

f i = 1 × f i − 1 + 1 × f i − 2 （ 1 ） f_i=1\times f_{i-1}+1\times f_{i-2} \ \ \ （1） fi=1×fi−1+1×fi−2 （1）

f i − 1 = 1 × f i − 1 + 0 × f i − 2 （ 2 ） f_{i-1}=1\times f_{i-1}+0\times f_{i-2} \ \ \ （2） fi−1=1×fi−1+0×fi−2 （2）

将上式（ 1 ）（ 2 ）（1）（2）（1）（2）转化为矩阵运算：

[ f i f i − 1 ] = [ f i − 1 f i − 2 ] × [ 1 1 1 0 ] \left[ \begin{matrix} f_i&f_{i-1}\end{matrix} \right]=\left[ \begin{matrix} f_{i-1}&f_{i-2}\end{matrix} \right]\times\left[ \begin{matrix} 1&1\\1&0\end{matrix} \right] [fifi−1]=[fi−1fi−2]×[1110]

同理，可以将 [ f i − 1 f i − 2 ] \left[ \begin{matrix} f_{i-1}&f_{i-2}\end{matrix} \right] [fi−1fi−2] 也进行转化：

[ f i f i − 1 ] = [ f i − 1 f i − 2 ] × [ 1 1 1 0 ] = [ f i − 2 f i − 3 ] × [ 1 1 1 0 ] × [ 1 1 1 0 ] \left[ \begin{matrix} f_i&f_{i-1}\end{matrix} \right]=\left[ \begin{matrix} f_{i-1}&f_{i-2}\end{matrix} \right]\times\left[ \begin{matrix} 1&1\\1&0\end{matrix} \right]=\left[ \begin{matrix} f_{i-2}&f_{i-3}\end{matrix} \right]\times\left[ \begin{matrix} 1&1\\1&0\end{matrix} \right]\times\left[ \begin{matrix} 1&1\\1&0\end{matrix} \right] [fifi−1]=[fi−1fi−2]×[1110]=[fi−2fi−3]×[1110]×[1110]

所以，最后可得：

[ f n f n − 1 ] = [ f 1 f 0 ] × [ 1 1 1 0 ] n − 1 \left[ \begin{matrix} f_n&f_{n-1}\end{matrix} \right]=\left[ \begin{matrix} f_1&f_0\end{matrix} \right]\times\left[ \begin{matrix} 1&1\\1&0\end{matrix} \right]^{n-1} [fnfn−1]=[f1f0]×[1110]n−1

可以通过快速幂的方法求解矩阵 [ 1 1 1 0 ] n − 1 \left[ \begin{matrix} 1&1\\1&0\end{matrix} \right]^{n-1} [1110]n−1 ，因此求解 f n f_n fn 可以在 O ( 2 3 × log ⁡ N ) O(2^3\times \log N) O(23×logN) 的时间求得。

对于 2 × 2 2\times 2 2×2 的任意方阵，乘以方阵 [ 1 0 0 1 ] \left[ \begin{matrix} 1&0\\0&1\end{matrix} \right] [1001] 都不变，因此可以设置初始值。

可以推导出，对于 m × m m\times m m×m 的任意方阵，乘以 m × m m\times m m×m 大小的方阵 [ 1 0 . . . 0 0 1 . . . 0 . . . . . . . . . . . . 0 0 . . . 1 ] \left[ \begin{matrix} 1&0&...&0\\0&1&...&0\\...&...&...&...\\0&0&...&1\end{matrix} \right] ⎣⎢⎢⎡10...001...0............00...1⎦⎥⎥⎤ 都不变，即对角线为 1 1 1 ，其余位置均为 0 0 0 。

【参考程序】

#include #define M 10000 using namespace std; struct node { int mat[3][3]; }; int n; node z; node matrix_mul(node x,node y) //矩阵乘法 { memset(z.mat,0,sizeof(z.mat)); for(int i=1;i 1 1 1。 1 1 1 -> 2 2 2 -> 2 2 2。 1 1 1 -> 2 2 2 -> 3 3 3。

【数据范围与约定】

对于 20 % 20\% 20% 的数据，保证 t ≤ 1000 t \leq 1000 t≤1000。

对于 100 % 100\% 100%的数据，保证 1 < t ≤ 1 0 6 1 < t \leq 10^6 12->1 1−>2−>1 ，a[1][3]*a[3][1]=1 表示路径 1 − > 3 − > 1 1->3->1 1−>3−>1 ，a[1][4]+a[4][1]=0 表示的路径 1 − > 4 − > 1 1->4->1 1−>4−>1 不存在。

同理 a[1][2]=a[1][1]*a[1][2]+a[1][2]*a[2][2]+a[1][3]*a[3][2]+a[1][4]*a[4][2]=1 ，起点为 1 1 1 ，终点为 2 2 2 ，经过 2 2 2 步，共有 1 1 1 种方案。其中 a[1][3]*a[3][2]=1 表示路径 1 − > 3 − > 2 1->3->2 1−>3−>2 。

同理可以得到a[1][3]=1,a[1][4]=1 。

因此，可以发现，邻接矩阵 A t A^t At 第 i i i 行第 j j j 列的数字 a[i][j] 表示的就是起点为 i i i 终点为 j j j ，经过 t t t 步的方案数。

对于自爆的情况，可以添加一个结点 0 0 0 ，所有点都指向 0 0 0 ，到达 0 0 0 就表示自爆。

对于停留在原地，给每个结点添加一个自环，即 a[i][i]=1 。

因此最后答案 a n s = ∑ i = 1 n a [ 1 ] [ i ] ans=\sum_{i=1}^na[1][i] ans=∑i=1na[1][i] 。

【参考程序】

#include using namespace std; const int N=50; int n,m,t; struct node //矩阵 { int mat[N][N]; }s,a; node matrix_mul(node x,node y) //矩阵乘法 { node z; memset(z.mat,0,sizeof(z.mat)); for(int i=0;i

【本文地址】

公司简介

联系我们