企业官网建设流程全解析

织梦网站 防黑,招聘网站开发手册,网站开发中的paml,建筑培训网能发焊工证吗对角化在众多 dp 问题中#xff0c;我们经常可以用矩阵快速幂进行优化。更进一步地#xff0c;如果这个递推矩阵是一个形如 #xff0c;矩阵快速幂就显得大财小用了。因为显然 。对于这种只有主对角线上有值的矩阵#xff0c;称为对角矩阵#xff0c;它显然拥有很好的性质…对角化在众多 dp 问题中我们经常可以用矩阵快速幂进行优化。更进一步地如果这个递推矩阵是一个形如矩阵快速幂就显得大财小用了。因为显然。对于这种只有主对角线上有值的矩阵称为对角矩阵它显然拥有很好的性质。那么我们不禁思考如何将一个普通矩阵变为对角矩阵呢。矩阵是线性变换为什么对角阵有好的性质是因为其仅仅是在各个坐标轴方向上的伸缩。对于一个普通的矩阵如果我们能通过相似变换把它换到对角阵的基下那么计算它的幂次将也非常容易。具体来说我们反过来做。如果有一个对角阵考虑先将其通过转换坐标到矩阵的基底的意义下然后施加操作最后再回来。这与直接做的效果是一样的。也就是。现在的问题变成了如何求。两边同时左乘得到。我们设列向量组最终左边乘出来的结果是右边乘出来是。由于我们还要求可逆因此选出来的这个向量组还得线性无关。也就是说对于这个矩阵我们要找到一些向量满足。这就引出了我们接下来的主角。特征值与特征向量如果对于矩阵存在一个 非零向量和值满足。那么就称是的一个特征值是的一个属于的特征向量。意思是在的作用下只做了伸缩操作。同时这个不能为 0要不然上面的矩阵肯定就线性相关了。同时注意特征向量表示的是矩阵变换中只有伸缩变换没有旋转变换的方向向量特征值是这个方向的伸缩系数一个方向当然只有一个伸缩系数。所以不同特征值对应的特征向量是互相线性无关的。考虑如何求解特征值和特征向量对上式移项得。由于不是 0这意味着发生了坍缩要等于。这个行列式是一个关于的次多项式我们考虑对其进行因式分解变成注意这里我们把重根合并起来写了。然后就可以解出所有特征值了。如果还想求解特征向量我们把每一个特征值回代然后解出哪些向量在该线性变化下被缩到了 0。具体来说就是求出一个齐次线性方程组的基础解系之后再求出通解。回到上面我们称是矩阵的特征多项式是的代数重数而一个对应所有线性无关的特征向量的个数叫做几何重数也即直观上就是能让几个不同方向的向量坍缩到 0。注意到。接下来我们给出一条重磅性质一个矩阵能被相似对角化当且仅当对于每个特征值几何重数 代数重数。为了解决上面那个问题我们进一步考虑什么情况下一个矩阵无法被相似对角化。一开始我们提到也就是说我们必须能选出个线性无关的向量来作为相似变换的矩阵。观察发现这个几何重数之和正好对应了我们能选出多少个线性无关的向量。那么稍微想一下上面那个结论就很自然了。既然有一些矩阵注定无法被对角化那么就拿他们没办法了吗由于最小多项式和特征多项式的一些性质和接下来的内容是分不开的所以我们花一些篇幅来讲如何对一些没办法完全对角化的矩阵进行类似对角化的化简。广义特征向量与 Jordan 型我们延续上面对角化的思路采用相似变换的方式。现在的问题是我们在中找不到足够的线性无关的向量。那么我们能否找一些别的向量来替补呢为此我们引入广义特征向量链具体来说特征向量是满足的向量那么层级秩为的广义特征向量是满足并且的非零向量。现在我们不是孤立地看一个广义特征向量而是看一串有递推关系的向量。我们从一个秩最高的广义特征向量开始构造一条链。我们先选择一个秩为的广义特征向量。然后我们逆向生成。以此类推。这样我们最多生成个向量因为到时再乘一个就变成 0 了也就是说。那么就是特征向量。进一步地我们发现上面这个递推式。也就是说我们如果正向考虑整个过程相当于在正常特征向量只在本方向拉伸的基础上混入了上一层向量的影响。现在我们在的基意义下考虑的影响。由于也就是说的影响是这样的这个特殊的矩阵被称为特征值的阶 Jordan 块。更精确地Jordan 块的元素满足对角线元素均为特征值主对角线上方的次对角线元素为 1其他所有元素为 0。这个矩阵已经近乎于对角矩阵了如果我们能通过相似变换把矩阵化为这种形式也是一种不错的结果。下面给出步骤求出所有的特征值。对于每个特征值令有。并且我们总能找到一个最小的使得这个核称为的广义特征空间。这是因为核的维度随着幂次而增长而维度是有上限的只是一个矩阵而一旦停止增长之后就不会重新恢复增长。注意我们有结论就是的代数重数。现在我们开始构造这个特征值对应的 Jordan 块。假设这个特征值对应的阶 Jordan 块有个那么要满足为代数重数要有代数重数个向量为几何重数也就是对应有多少个广义特征向量链。观察到因为每个的 Jordan 块中都会包含一个的向量。因此。接着对每个 Jordan 块找到它对应广义特征向量链。具体来说先从找一个向量然后继续在找并且我们找到的这个向量不能再之前已经找到的向量的张成之中直到这其中找不到再去找。不难发现这样的构造刚好满足了前面的那两个条件。合并每个特征值的特征向量空间。就像各个特征值对应的特征向量线性无关我们每个特征值的广义特征空间也是不交的这是保证矩阵可逆的条件。我们构造矩阵对于每条链我们按顺序把它放进也就是。最后我们有。其中是一个分块对角矩阵其中是所有特征值的几何重数之和每一个是一个 Jordan 块注意这里向量链的放入顺序要和 Jordan 块一致。可以验证此时。这个就是 Jordan 型。这个是对于任意矩阵都是存在且唯一的也是在无法对角化的情况下能被化简到的最好的情况。Jordan 型同时给出了一种把所有矩阵划分为如果等价类的方法如果我们不考虑 Jordan 块之间的顺序。最小多项式回到一开始我们选择将一个矩阵变成 Jordan 型对角矩阵是特殊的 Jordan 型是因为计算他的幂将会变得非常容易。而当我们处理矩阵多项式时就避不开幂的处理。别忘了标题的后半部分线性递推到现在我们仍然没有讨论过。还是以 dp 问题为背景。假设从第个阶段到第个阶段有其中是一个向量表示所有阶段的 dp 值是转移矩阵。那么。如果存在一个次数为的矩阵多项式也就是 0 矩阵并且我们求出就算用暴力多项式取模搭配快速幂也只需要求这个)也就是说那么:也就是说只要递推出前项就可以算出很大时的情况。那么问题就变成了求一个次数最小的我们也称这样能让最后变成 0 的多项式叫化零多项式其中次数最小的首一多项式就叫做最小多项式。别忘了现在我们处理矩阵幂有了强有力的工具Jordan 型。那么对于矩阵多项式和对应的有。这是因为而。这揭示了相似变换不改变化零多项式的性质想让化零等价于让化零当然相似变换也不改变最小多项式。那么我们先研究如何让一个 Jordan 块化 0。可以发现想让一个化零是一个次数最小的多项式。因为是一个只有主对角线上方一条斜线全是 1 的矩阵乘一次就会让这个斜线向右上方移动一格。貌似一切都明朗了。对于一个矩阵我们找到其每个特征值然后求出它的 Jordan 型。对于每个假设其对应的 Jordan 块中阶数最大的是那么这个 Jordan 型的最小多项式也是的最小多项式就是 :进一步地由于小于等于代数重数因此也就是说特征多项式如果直接带入的也是可以化零的这一结论也即 Cayley-Hamilton 定理。在实际应用时我们可以直接根据特征值猜最小多项式。注意我们线性递推时只是用了化零的性质来简化计算有些时候最小多项式不便观察时直接用特征多项式/别的化零多项式也是可以的只要复杂度不爆也就是特征多项式的次数可以接受。一道例题GDKOI2023 马戏团里你最忙有一个数字初始是。进行次操作第次操作从均匀随机一个数字有的概率是有的概率是。一种方案的权值是。对每个求出的所有方案中权值乘概率之和对取模。。考虑暴力表示做了次操作最后一位是的概率是对应的答案。转移高维前缀和FWT可以获得 20 pts。我们考虑时怎么做。先考虑概率此时 and 的转移矩阵是or 的转移矩阵是。为了推广到更大的情况这里我们引入矩阵张量积的概念设有两个矩阵和其中是一个的矩阵是一个的矩阵。和的张量积Kronecker积记作是一个的分块矩阵。它的定义如下可以验证进一步地。由于每一位的转移情况是类似的我们惊奇地发现概率的转移矩阵正好就是。可以自行验证。那么再把加进来整个转移就是其中。先考虑求的最小多项式。因为下三角/上三角矩阵的特征值是方便观察的即对角线上的元素可以把算一下。而这里都是三角的并且他们对角线上的元素都是。那么和也都是三角的并且可以发现对角线上的元素都是。实际上这一步可以不用观察根据这里的思路时他们的特征值集合也会相应地进行笛卡尔积考察 Jordan 型即可说明。那么的最小多项式就是的张量积幂次是可对角化的因为和都是可对角化的。但这里要求的是的最小多项式因为有一个相加貌似还是不好处理。但最后结论是的最小多项式。更严谨的证明请见masterhuang大佬的题解。求出之后我们发现就是的一个化零多项式。这是因为所以这里的并不重要因为我们自乘一次就可以发现。那么我们就取作为的化零多项式这个次数是的非常可以接受。然后再像上面说的那样把也求出来。这样我们就只需要算出前项就可以了这个直接跑 20 pts 的暴力