※ [本文轉錄自 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)
但以上這樣的敘述並不是嚴格的證明，請問此運算有無特別的名稱或是數學規納法的表示
方式?