※ [本文转录自 Math 看板 #1MwGVM6S ]
作者: iasm (I am Nobody) 看板: Math
标题: [线代] 如何使用复杂度低的矩阵对角化来求两矩阵相乘
时间: Wed Mar 16 15:14:28 2016
各位好，想请问有无一个general 的表示式可以让两矩阵相乘以"对角矩阵"来实现，但不
能使用传统对角化(diagonalization)的技巧?
假设有一矩阵，其为a=[a11, a12
a21, a22];
也就是a*a=[a11*a11+a12*a21 , a11*a12 +a12*a22
a21*a11+a22*a21 , a21*a12+a22*a22 ];
事实上我们可以把a*a'变成两对角矩阵，其大小皆为8*8
例如D=[ a11, 0, 0, 0, 0, 0, 0, 0
0, a12, 0, 0, 0, 0, 0, 0
0, 0, a11, 0, 0, 0, 0, 0
0, 0, 0, a12, 0, 0, 0, 0
0, 0, 0, 0, a21, 0, 0, 0
0, 0, 0, 0, 0, a22, 0, 0
0, 0, 0, 0, 0, 0, a21, 0
0, 0, 0, 0, 0, 0, 0, a22]
D'= [ a11, 0, 0, 0, 0, 0, 0, 0
0, a21, 0, 0, 0, 0, 0, 0
0, 0, a12, 0, 0, 0, 0, 0
0, 0, 0, a22, 0, 0, 0, 0
0, 0, 0, 0, a11, 0, 0, 0
0, 0, 0, 0, 0, a21, 0, 0
0, 0, 0, 0, 0, 0, a12, 0
0, 0, 0, 0, 0, 0, 0, a22]
D*D'= [ a11*a11, 0, 0, 0, 0, 0, 0, 0
0,a12*a21, 0, 0, 0, 0, 0, 0
0, 0,a11*a12, 0, 0, 0, 0, 0
0, 0, 0,a12*a22, 0, 0, 0, 0
0, 0, 0, 0,a21*a11, 0, 0, 0
0, 0, 0, 0, 0,a22*a21, 0, 0
0, 0, 0, 0, 0, 0,a21*a12, 0
0, 0, 0, 0, 0, 0, 0,a22*a22 ]
重新整理后，将每两组diagonal elements依序塞入2*2 matrix后，其结果与a*a相同，也
就是
[a11*a11+a12*a21 , a11*a12 +a12*a22
a21*a11+a22*a21 , a21*a12+a22*a22 ];
这与一般对角化的方法差别在于a=>D以及a=>D'都是O(n^2)的operation，但一般对角化是
O(N^3)
但以上这样的叙述并不是严格的证明，请问此运算有无特别的名称或是数学规纳法的表示
方式?