溫州 建網(wǎng)站的公司,wordpress 添加廣告窗口,邢臺新聞最新事件,下載app安裝對角化在眾多 dp 問題中#xff0c;我們經(jīng)?？梢杂镁仃嚳焖賰邕M行優(yōu)化。更進一步地#xff0c;如果這個遞推矩陣是一個形如 #xff0c;矩陣快速冪就顯得大財小用了。因為顯然 。對于這種只有主對角線上有值的矩陣#xff0c;稱為對角矩陣#xff0c;它顯然擁有很好的性質…對角化在眾多 dp 問題中我們經(jīng)?？梢杂镁仃嚳焖賰邕M行優(yōu)化。更進一步地如果這個遞推矩陣是一個形如矩陣快速冪就顯得大財小用了。因為顯然。對于這種只有主對角線上有值的矩陣稱為對角矩陣它顯然擁有很好的性質。那么我們不禁思考如何將一個普通矩陣變?yōu)閷蔷仃嚹?。矩陣是線性變換為什么對角陣有好的性質是因為其僅僅是在各個坐標軸方向上的伸縮。對于一個普通的矩陣如果我們能通過相似變換把它換到對角陣的基下那么計算它的冪次將也非常容易。具體來說我們反過來做。如果有一個對角陣考慮先將其通過轉換坐標到矩陣的基底的意義下然后施加操作最后再回來。這與直接做的效果是一樣的。也就是?，F(xiàn)在的問題變成了如何求。兩邊同時左乘得到。我們設列向量組最終左邊乘出來的結果是右邊乘出來是。由于我們還要求可逆因此選出來的這個向量組還得線性無關。也就是說對于這個矩陣我們要找到一些向量滿足。這就引出了我們接下來的主角。特征值與特征向量如果對于矩陣存在一個 非零向量和值滿足。那么就稱是的一個特征值是的一個屬于的特征向量。意思是在的作用下只做了伸縮操作。同時這個不能為 0要不然上面的矩陣肯定就線性相關了。同時注意特征向量表示的是矩陣變換中只有伸縮變換沒有旋轉變換的方向向量特征值是這個方向的伸縮系數(shù)一個方向當然只有一個伸縮系數(shù)。所以不同特征值對應的特征向量是互相線性無關的?？紤]如何求解特征值和特征向量對上式移項得。由于不是 0這意味著發(fā)生了坍縮要等于。這個行列式是一個關于的次多項式我們考慮對其進行因式分解變成注意這里我們把重根合并起來寫了。然后就可以解出所有特征值了。如果還想求解特征向量我們把每一個特征值回代然后解出哪些向量在該線性變化下被縮到了 0。具體來說就是求出一個齊次線性方程組的基礎解系之后再求出通解?；氐缴厦嫖覀兎Q是矩陣的特征多項式是的代數(shù)重數(shù)而一個對應所有線性無關的特征向量的個數(shù)叫做幾何重數(shù)也即直觀上就是能讓幾個不同方向的向量坍縮到 0。注意到。接下來我們給出一條重磅性質一個矩陣能被相似對角化當且僅當對于每個特征值幾何重數(shù) 代數(shù)重數(shù)。為了解決上面那個問題我們進一步考慮什么情況下一個矩陣無法被相似對角化。一開始我們提到也就是說我們必須能選出個線性無關的向量來作為相似變換的矩陣。觀察發(fā)現(xiàn)這個幾何重數(shù)之和正好對應了我們能選出多少個線性無關的向量。那么稍微想一下上面那個結論就很自然了。既然有一些矩陣注定無法被對角化那么就拿他們沒辦法了嗎由于最小多項式和特征多項式的一些性質和接下來的內(nèi)容是分不開的所以我們花一些篇幅來講如何對一些沒辦法完全對角化的矩陣進行類似對角化的化簡。廣義特征向量與 Jordan 型我們延續(xù)上面對角化的思路采用相似變換的方式?，F(xiàn)在的問題是我們在中找不到足夠的線性無關的向量。那么我們能否找一些別的向量來替補呢為此我們引入廣義特征向量鏈具體來說特征向量是滿足的向量那么層級秩為的廣義特征向量是滿足并且的非零向量?，F(xiàn)在我們不是孤立地看一個廣義特征向量而是看一串有遞推關系的向量。我們從一個秩最高的廣義特征向量開始構造一條鏈。我們先選擇一個秩為的廣義特征向量。然后我們逆向生成。以此類推。這樣我們最多生成個向量因為到時再乘一個就變成 0 了也就是說。那么就是特征向量。進一步地我們發(fā)現(xiàn)上面這個遞推式。也就是說我們?nèi)绻蚩紤]整個過程相當于在正常特征向量只在本方向拉伸的基礎上混入了上一層向量的影響?，F(xiàn)在我們在的基意義下考慮的影響。由于也就是說的影響是這樣的這個特殊的矩陣被稱為特征值的階 Jordan 塊。更精確地Jordan 塊的元素滿足對角線元素均為特征值主對角線上方的次對角線元素為 1其他所有元素為 0。這個矩陣已經(jīng)近乎于對角矩陣了如果我們能通過相似變換把矩陣化為這種形式也是一種不錯的結果。下面給出步驟求出所有的特征值。對于每個特征值令有。并且我們總能找到一個最小的使得這個核稱為的廣義特征空間。這是因為核的維度隨著冪次而增長而維度是有上限的只是一個矩陣而一旦停止增長之后就不會重新恢復增長。注意我們有結論就是的代數(shù)重數(shù)?，F(xiàn)在我們開始構造這個特征值對應的 Jordan 塊。假設這個特征值對應的階 Jordan 塊有個那么要滿足為代數(shù)重數(shù)要有代數(shù)重數(shù)個向量為幾何重數(shù)也就是對應有多少個廣義特征向量鏈。觀察到因為每個的 Jordan 塊中都會包含一個的向量。因此。接著對每個 Jordan 塊找到它對應廣義特征向量鏈。具體來說先從找一個向量然后繼續(xù)在找并且我們找到的這個向量不能再之前已經(jīng)找到的向量的張成之中直到這其中找不到再去找。不難發(fā)現(xiàn)這樣的構造剛好滿足了前面的那兩個條件。合并每個特征值的特征向量空間。就像各個特征值對應的特征向量線性無關我們每個特征值的廣義特征空間也是不交的這是保證矩陣可逆的條件。我們構造矩陣對于每條鏈我們按順序把它放進也就是。最后我們有。其中是一個分塊對角矩陣其中是所有特征值的幾何重數(shù)之和每一個是一個 Jordan 塊注意這里向量鏈的放入順序要和 Jordan 塊一致?？梢则炞C此時。這個就是 Jordan 型。這個是對于任意矩陣都是存在且唯一的也是在無法對角化的情況下能被化簡到的最好的情況。Jordan 型同時給出了一種把所有矩陣劃分為如果等價類的方法如果我們不考慮 Jordan 塊之間的順序。最小多項式回到一開始我們選擇將一個矩陣變成 Jordan 型對角矩陣是特殊的 Jordan 型是因為計算他的冪將會變得非常容易。而當我們處理矩陣多項式時就避不開冪的處理。別忘了標題的后半部分線性遞推到現(xiàn)在我們?nèi)匀粵]有討論過。還是以 dp 問題為背景。假設從第個階段到第個階段有其中是一個向量表示所有階段的 dp 值是轉移矩陣。那么。如果存在一個次數(shù)為的矩陣多項式也就是 0 矩陣并且我們求出就算用暴力多項式取模搭配快速冪也只需要求這個)也就是說那么:也就是說只要遞推出前項就可以算出很大時的情況。那么問題就變成了求一個次數(shù)最小的我們也稱這樣能讓最后變成 0 的多項式叫化零多項式其中次數(shù)最小的首一多項式就叫做最小多項式。別忘了現(xiàn)在我們處理矩陣冪有了強有力的工具Jordan 型。那么對于矩陣多項式和對應的有。這是因為而。這揭示了相似變換不改變化零多項式的性質想讓化零等價于讓化零當然相似變換也不改變最小多項式。那么我們先研究如何讓一個 Jordan 塊化 0?？梢园l(fā)現(xiàn)想讓一個化零是一個次數(shù)最小的多項式。因為是一個只有主對角線上方一條斜線全是 1 的矩陣乘一次就會讓這個斜線向右上方移動一格。貌似一切都明朗了。對于一個矩陣我們找到其每個特征值然后求出它的 Jordan 型。對于每個假設其對應的 Jordan 塊中階數(shù)最大的是那么這個 Jordan 型的最小多項式也是的最小多項式就是 :進一步地由于小于等于代數(shù)重數(shù)因此也就是說特征多項式如果直接帶入的也是可以化零的這一結論也即 Cayley-Hamilton 定理。在實際應用時我們可以直接根據(jù)特征值猜最小多項式。注意我們線性遞推時只是用了化零的性質來簡化計算有些時候最小多項式不便觀察時直接用特征多項式/別的化零多項式也是可以的只要復雜度不爆也就是特征多項式的次數(shù)可以接受。一道例題GDKOI2023 馬戲團里你最忙有一個數(shù)字初始是。進行次操作第次操作從均勻隨機一個數(shù)字有的概率是有的概率是。一種方案的權值是。對每個求出的所有方案中權值乘概率之和對取模。?？紤]暴力表示做了次操作最后一位是的概率是對應的答案。轉移高維前綴和FWT可以獲得 20 pts。我們考慮時怎么做。先考慮概率此時 and 的轉移矩陣是or 的轉移矩陣是。為了推廣到更大的情況這里我們引入矩陣張量積的概念設有兩個矩陣和其中是一個的矩陣是一個的矩陣。和的張量積Kronecker積記作是一個的分塊矩陣。它的定義如下可以驗證進一步地。由于每一位的轉移情況是類似的我們驚奇地發(fā)現(xiàn)概率的轉移矩陣正好就是?？梢宰孕序炞C。那么再把加進來整個轉移就是其中。先考慮求的最小多項式。因為下三角/上三角矩陣的特征值是方便觀察的即對角線上的元素可以把算一下。而這里都是三角的并且他們對角線上的元素都是。那么和也都是三角的并且可以發(fā)現(xiàn)對角線上的元素都是。實際上這一步可以不用觀察根據(jù)這里的思路時他們的特征值集合也會相應地進行笛卡爾積考察 Jordan 型即可說明。那么的最小多項式就是的張量積冪次是可對角化的因為和都是可對角化的。但這里要求的是的最小多項式因為有一個相加貌似還是不好處理。但最后結論是的最小多項式。更嚴謹?shù)淖C明請見masterhuang大佬的題解。求出之后我們發(fā)現(xiàn)就是的一個化零多項式。這是因為所以這里的并不重要因為我們自乘一次就可以發(fā)現(xiàn)。那么我們就取作為的化零多項式這個次數(shù)是的非?？梢越邮?。然后再像上面說的那樣把也求出來。這樣我們就只需要算出前項就可以了這個直接跑 20 pts 的暴力