矩陣乘法
矩陣乘法是一種高效的算法可以把一些一維遞推最佳化到log（ n )，還可以求路徑方案等，所以更是是一種套用性極強的算法。矩陣，是線性代數中的基本概念之一。一個m×n的矩陣就是m×n個數排成m行n列的一個數陣。由於它把許多數據緊湊的集中到了一起，所以有時候可以簡便地表示一些複雜的模型。矩陣乘法看起來很奇怪，但實際上非常有用，套用也十分廣泛。
基本定義
只有當矩陣A的列數與矩陣B的行數相等時A×B才有意義。一個m×n的矩陣a（m,n)左乘一個n×p的矩陣b（n,p)，會得到一個m×p的矩陣c（m,p)，滿足
矩陣乘法滿足結合律，但不滿足交換律
一般的矩乘要結合快速冪才有效果。（基本上所有矩陣乘法都要用到快速冪的）
在計算機中，一個矩陣實際上就是一個二維數組。一個n行m列的矩陣與一個m行p列的矩陣可以相乘，得到的結果是一個n行p列的矩陣，其中的第i行第j列位置上的數為第一個矩陣第i行上的m個數與第二個矩陣第j列上的m個數對應相乘後所得的m個乘積之和。比如，下面的算式表示一個2行2列的矩陣乘以2行3列的矩陣，其結果是一個2行3列的矩陣。其中，結果矩陣的那個4（結果矩陣中第二（i）行第二（j)列）=
2（第一個矩陣第二(i)行第一列）*2（第二個矩陣中第一行第二(j)列）
+
0（第一個矩陣第二(i)行第二列）*1（第二個矩陣中第二行第二(j)列）：
[1]矩陣乘法的c語言程式：
#include<stdio.h>
float main()
{
float a[100][100],b[100][100],c[100][100];//定義三個數組，分別存儲矩陣A,B,C
int m1,n1,m2,n2,i1,j1,i2,j2,i3,j3,i4,j4,k;
float s[100][100]={0};//賦值使數組s元素初值全部為零
printf("請輸入矩陣A行數m1,列數n1:");//輸入矩陣A行數，列數
scanf("%d,%d",&m1,&n1);
printf("請輸入矩陣B行數m2,列數n2:");//輸入矩陣B行數，列數
scanf("%d,%d",&m2,&n2);
printf("\n\n");//如果不可以相乘，下面將出現判斷，在此換行，便於觀看
if(n1!=m2)
printf("不可以相乘！！！");//判斷是否可以相乘
printf("\n\n");
if((m1>100)||(n1>100))
printf("數目過多！！！");//控制矩陣A元素數量在數組容納範圍內
else
{
for(i1=1;i1<=m1;i1++)
{
for(j1=1;j1<=n1;j1++)
{
printf("a[%d][%d]=:",i1,j1);
scanf("%f",&a[i1][j1]);//輸入矩陣A元素
}
}
}
printf("\n");//分隔開A,B的元素輸入，便於觀看
if((m2>100)||(n2>100))
printf("數目過多！！！");
else
{
for(i2=1;i2<=m2;i2++)
{
for(j2=1;j2<=n2;j2++)
{
printf("b[%d][%d]=:",i2,j2);
scanf("%f",&b[i2][j2]);//輸入矩陣B元素
}
}
}
printf("矩陣A:\n");//輸出矩陣A，便於觀看，檢驗
for(i3=1;i3<=m1;i3++)
{
for(j3=1;j3<=n1;j3++)
{
printf("%f ",a[i3][j3]);
if(j3==n1)
printf("\n");
}
}
printf("\n");//與矩陣B的輸出結果隔開，便於觀看
printf("矩陣B:\n");//輸出矩陣A，便於觀看，檢驗
for(i4=1;i4<=m2;i4++)
{
for(j4=1;j4<=n2;j4++)
{
printf("%f ",b[i4][j4]);
if(j4==n2)
printf("\n");
}
}
printf("\n")；
printf("矩陣C=A*B:\n");
for(i4=1;i4<=m1;i4++)
{
for(j4=1;j4<=n2;j4++)
{
for(k=1;k<=n1;k++)
{
s[i4][j4]=s[i4][j4]+a[i4][k]*b[k][j4];//定義矩陣乘法，相乘時，有一個指標是一樣的，都用k
}
c[i4][j4]=s[i4][j4];//定義矩陣乘法
printf("%f ",c[i4][j4]);
if(j4==n2)
printf("\n");//控制在列指標到達N時換行
}
}
return 0;
}
程式運行結果示例：一般矩乘的代碼：function mul( a , b : Tmatrix ) : Tmatrix;
var
i,j,k : longint;
c : Tmatrix;
begin
fillchar( c , sizeof( c ) , 0 );
for k:=0 to n do
for i:=0 to m do
for j:=0 to p do
begin
inc( c[ i , j ] , a[ i , k ]*b[ k , j ] );
if c[ i , j ] > ra then c[ i , j ]:=c[ i , j ] mod ra;
end;
mul:=c;
end;
這裡我們不介紹其它有關矩陣的知識，只介紹矩陣乘法和相關性質。
不要以為數學中的矩陣也是黑色螢幕上不斷變化的綠色字元。在數學中，一個矩陣說穿了就是一個二維數組。一個n行m列的矩陣可以乘以一個m行p列的矩陣，得到的結果是一個n行p列的矩陣，其中的第i行第j列位置上的數等於前一個矩陣第i行上的m個數與後一個矩陣第j列上的m個數對應相乘後所有m個乘積的和。比如一下的例子中，算式所表示的是一個2行2列的矩陣與一個2行3列的矩陣相乘，所得的結果是一個2行3列的矩陣。所得矩陣中第2行第2列的“4”是2*2+0*1的和：右面的算式則是一個1 x 3的矩陣乘以3 x 2的矩陣，得到一個1 x 2的矩陣：
矩陣乘法的兩個重要性質： 一，矩陣乘法不滿足交換律；二，矩陣乘法滿足結合律。為什麼矩陣乘法不滿足交換律呢？因為交換後兩個矩陣有可能不能相乘。為什麼它又滿足結合律呢？假設你有三個矩陣A、B、C，那么(AB)C和A(BC)的結果的第i行第j列上的數都等於所有A(ik)*B(kl)*C(lj)的和（枚舉所有的k和l）。
2了解矩陣
