算法笔记——矩阵乘法

矩阵乘法的概述

一个矩阵有n行m列，一个矩阵有x行y列。当m == x的时候， 才可以进行矩阵运算。

算法比较难记，生成的矩阵共n行y列。

拿第一个矩阵的i行每一个元素与第二个矩阵j列的每一个数对应， 生成的矩阵i，j位置的值为这些对应的值的积的和。

 

矩阵乘法的作用

每增加一个维度，世界便会增加无限的美感——517教练

矩阵乘法可以解决无数出乎意料的递推式（当要推的值实在太大的时候）

比如例题 斐波那契数列 递推式 f[n] = f[n-1] + f[n-2];

我们构造矩阵 1. 一行两列放两个递推的值 f[x], f[x-1]

矩阵 2 两行两列 全是常数 

1 1           我们把这两个矩阵相乘， 就会出现一个1行2列的矩阵，我们发现它的值就是f[x+1], f[x];

1 0 

矩阵乘法和乘法一样， 满足分配率与结合率，因此，矩阵乘法是满足快速幂的运算的。

我们就可以对2号全是常数的矩阵求其的n次幂， 可以在logn的时间内求出斐波那契数列的值。

我们可以构造一个全是常数的矩阵来满足线性加减的递推式，也可以用各种神奇的操作完成其他的运算：

例题：已知A为一个矩阵 求 A+A×A＋A^3+.......A^k的值

我们对其矩阵外再套一个矩阵，　设计矩阵：

A A    × A Ａ =  A ^ A + A,  A ^ A 

1  0　　1  0       1                 0

我们对这个矩阵自乘ｋ次，即是上述表达式的值