矩阵乘法

写在最前面的话

由于自己太弱了,写这个来总结一下,方便复习。很多内容总结自维基百科(链接1链接2)和李煜东《算法竞赛进阶指南》。

适用范围

一个矩阵的列数等于另一个矩阵的行数时,它们的乘法才有意义。

运算方法

对于一个n*p的矩阵A和一个p*m的矩阵B,它们的乘积C 是一个 n*m 的矩阵。

A 矩阵和B矩阵乘积中的元素C_{[i,j]},等于A矩阵第i行的p个数和B矩阵第j列的p个数分别相乘的和。 即:

    \[C_{i,j} = \sum_{k=1}^{p} A_{i,k}*B_{k,j}\]

矩阵乘法同数的乘法一样,有结合律、分配律。但是交换因数后不一定能满足(n*p)*(p*m)的形式,即m不一定等于n,并且就算满足也不一定结果相等,所以矩阵乘法不满足乘法交换律。

纯乘法的代码实现

1.计算函数。由于自己太弱了,加上时间有限,写了一份很水的代码。

但是这里必须固定AB 的数组大小,可能vector可以解决这个问题?欢迎大佬们指教。

#include<cstdio>
int A[2][3]={
	{1,2,3},
	{4,5,6}
};
int B[3][4]={
	{1,2,3,4},
	{5,6,7,8},
	{9,10,11,12}
};
int c[2][4];
int n,m;
void mul(int a[][3],int b[][4],int n,int m,int p){
	for(int i=0;i<n;++i){//n 乘积的行数 
		for(int j=0;j<m;++j){//m 乘积的列数 
			for(int k=0;k<p;++k){//p 即共有的维 
				c[i][j]+=a[i][k]*b[k][j];
			}
			printf("c[%d][%d]=%d\n",i,j,c[i][j]);
		}
	}
}
int main(){
	mul(A,B,2,4,3);//计算A*B,并保存到c[][4]数组中 
	return 0;
}

2.有一种边读入边计算的写法:

scanf("%lld%lld%lld",&n,&p,&m);
for(long long i=1;i<=n;++i){
	for(long long j=1;j<=p;++j){
		scanf("%lld",&a[i][j]);
	}
}
for(long long i=1;i<=p;++i){
	for(long long j=1;j<=m;++j){
		scanf("%lld",&b[i][j]);
		for(long long k=1;k<=n;++k){//此处k枚举的并非是公共维
			ans[k][j]+=a[k][i]*b[i][j];
		}
	}
}

需要注意的是,这里的k的含义与上一份代码不同。由于已经枚举了公共边(即第7行枚举的i)和列数j,这里只需要枚举乘积的行数。仍然是n*m*p三维。

我也不知道自己怎么就写了这么个没用的玩意。

用途

矩阵的一个重要用途是解线性方程组。线性方程组中未知量的系数可以排成一个矩阵,加上常数项,则称为增广矩阵。另一个重要用途是表示线性变换,即是诸如
f(x)=4x 之类的线性函数的推广。

——维基百科


1.其实蒟蒻的我并不知道怎么解线性方程组,但是对于矩阵加速线性变换有一些体会。让我们考虑一种比较特殊的矩阵乘法:1*nn*n。由定义可知,它们的乘积仍然是一个1*n的矩阵。那么有什么用呢?我们可以借助快速幂的思想,利用矩阵乘法的分配律、结合律,降低时间复杂度。

例如,POJ3070 这道题要求斐波那契数列第n项modm(给定n,m)的值。我们可以设一个1*2的矩阵A来存放F_{i},F_{i+1},然后通过设立方程,求出一个2*2的矩阵B,使得A*B得到的1*2的矩阵C,满足C=[F_{i+1},F_{i+2}]。于是,我们可以把时间复杂度由O(n)降低到O(log_{2}^{n})
我们可以通过设未知数解方程,使一个矩阵满足一定的性质。例如,当我们写快速计算矩阵乘法的函数时,函数里默认的矩阵(用于存放答案)应该初始化为什么呢?(计算快速幂时将对应变量初始化为1)如果全部初始化为0,就会导致任何符合条件的矩阵与其相乘都为0。

通过解方程,可以发现,一个2*2的矩阵

    \[  \left[  \begin{matrix}    1 & 0 \\    0 & 1 \\      \end{matrix}   \right] \]

与任何一个满足x==2x*y的矩阵相乘,结果仍然等于这个x*y的矩阵。

因此,我们可以把这个矩阵初始化为如上的矩阵,其作用等同于计算快速幂时的1;

2.以后遇到再来补充。

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注