伴隨矩陣的複雜性

我知道這是一個比編程問題更復雜的理論問題，希望我沒有寫錯在這裏寫作，如果是錯誤的地方，我會道歉，但我希望你們中的某個人有答案。作爲一個複雜性理論問題，它甚至與程序設計相關。伴隨矩陣的複雜性

我正在研究線性循環序列，並且我讀到爲了獲得它彈出的序列的第n個值，您需要獲得伴隨矩陣的某些功能，我想知道是否有已知的算法來獲得這種矩陣的權力的快捷方式..

我不能給編碼的例子，但我會盡力給你一些更多的解釋：

齊次線性週期性第k個序列order：
s（n + k）= a（k-1）s（n + k-1）+ a（k-2）s（n + k-2）+ ... + a（0）
對於n = 0,1，...，其中s（i）是序列的第i個值e和a（i）是代數場中的係數。

A爲上述序列的友矩陣，如果它是：
（0 0 0 0 ... 0（0））
（1 0 0 0 ... 0（1））
（0 1 0 0 ... 0 a（2））
（.. .. ..）
（0 0 0 0 ... 1 a（k -1））
此外理論認爲對於該序列的狀態矢量，我們有：
S（N）= S（0）甲^ N對於n = 0,1，..
就是這樣，感謝幫助。

來源

2009-04-07 luiss

快速查找矩陣冪的通常策略是diagonalise它（執行特徵向量分解）：

甲= P ^-1 d。P個

其中d是對角矩陣。然後，您可以通過計算

一個 ^ň = P ^-1 d ^ň P

其中d ^ñ 是快速計算，因爲它是一個對角矩陣，所以養的n次冪你只需分別掌握每個元素的權力。

然而，並非所有的矩陣都是可對角化的 - 我不知道你的伴隨矩陣是否會成立。無論如何，你可能會發現 this Wikipedia article 有幫助。

來源

2009-04-07 14:48:38

它並不總是對角化，只有當特徵polynoials的根源是不同的，反正沒關係，這是很好的，但我想知道是否有某種方式利用矩陣的結構，TY – luiss 2009-04-07 15:07:34

可以使用 O(log n) 矩陣產品計算矩陣 M 的 n 次方：

如果 n=0 ，返回 I
如果 n 是偶數，計算 N=M ^n/2 並返回 N*N
如果 n 是奇數，則計算 N=M ^n-1 並返回 M*N

來源

2009-04-26 12:27:02

對不起，但我無法弄清楚如何使它在O（log n）中，我認爲每個矩陣乘法仍然是O（n^2），其中n是行數（supposin一個方陣），不是嗎？ – luiss 2009-04-26 15:24:53

伴隨矩陣的複雜性

回答

相關問題