精华内容
下载资源
问答
  • 特征多项式

    千次阅读 2019-01-09 19:05:00
    特征多项式与常系数线性齐次递推 一般来说,这个东西是用来优化能用矩阵乘法优化的递推式子的。 通常,这种递推式子的特征是在齐次的条件下,转移系数也可以通过递推得到。 对于这样的递推,通常解法为$O(NK)$的...

    特征多项式与常系数线性齐次递推

    一般来说,这个东西是用来优化能用矩阵乘法优化的递推式子的。

    通常,这种递推式子的特征是在齐次的条件下,转移系数也可以通过递推得到。

    对于这样的递推,通常解法为$O(NK)$的递推或者$O(k^3\log n)$的矩阵乘法,但是有些**毒瘤**的出题人~~吉老师~~,会将这样的递推强行出成$K\le 1000$,特别,对于常系数线性齐次递推有些出题人甚至会出成$20000$!

    这样,就需要引入一个非常有趣~~头秃~~的概念:特征多项式。

    首先,我们需要介绍$Cayley-Hamilton$定理

    对于一个$n$阶的一个方阵,它的特征多项式为$p(\lambda)=|\lambda E-A|=\lambda^n+b_1\lambda^{n-1}+b_2\lambda^{n-2}+...+b_n$

    那么显然:$p(A)=0$

    也就是说:$A^N+b_1A^{n-1}+...+b_n=0$,即$p(\lambda)$为原多项式的化零多项式。

    因此,这个特征多项式可以通过高斯消元及拉格朗日插值求出。

    求矩阵的特征多项式

    一个$O(n^4)$的做法

    显然,我们得到的特征多项式是一个$n$阶多项式,那么只需要知道$n+1$个点的点值就可以得到了。

    也就是,我们把$n+1$个数代入$|\lambda E-A|$中(作为$\lambda$),然后暴力高斯消元即可得到一个矩阵的特征多项式。

    那么,接下来,只需要拉格朗日插值即可。

    这个做法作为一个$n^4$的做法其实想要卡掉矩阵乘法是很难的,除非将递推的项数放到$10^{1000}$这样的级别,如[BZOJ4162]

    那么接下来,我们考虑刚刚的做法能否被优化。

    显然,每次$n^3$求矩阵行列式太慢了。

    一个$O(n^3)$的做法

    对于这样的矩阵:$A=P\times B\times P^{-1}$

    称$A,B$是相似的,也就是说,对于$A,B$的特征多项式相同。

    构造还是很容易的,只需要保留每行与每行之间的关系即可。

    对于这样的矩阵,我们称之为上海森堡矩阵。

    $\begin{pmatrix} a_{1,1}&a_{1,2}&a_{1,3}&\cdots&a_{1,n}\\ a_{2,1}&a_{2,2}&a_{2,3}&\cdots&a_{2,n}\\ 0&a_{3,2}&a_{3,3}&\cdots&a_{3,n}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&a_{n,n} \end{pmatrix}$

    那么,对于这样的矩阵,求行列式的时间复杂度就降为$n^2$了!

    然后,总时间复杂度为$n^3+n^2\log m$,或者为$n^3+n\log n \log m$(并无卵用),然后对于$n^3 \log m$的矩阵乘法构成了鲜明的优势(大雾

    显然,其实上面的东西没有那么有用...

    但是还是有必要知道的,万一他卡你呢?

    常系数线性齐次递推的矩阵的特征多项式

    定义:递推式为$f_i=\sum\limits_{j=1}^na_j\times f_{i-j},i>n$的递推。

    讲道理,这个东西才非常有用...

    对于所有的常系数线性齐次递推来说,它们的矩阵形态类似,同样,他们的特征多项式也类似...

    其实手画一下就可以发现,它们的特征多项式都是$p(\lambda)=\lambda^n-a_1\lambda^{n-1}-a_2\lambda^{n-2}-...-a_n$

    按照行列式的定义展开式子退一下就得到啦!

    特征多项式的使用手册

    其实,使用方法很简单啦,就是运用之前得到的特征多项式性质,$p(A)=A^N+b_1A^{n-1}+...+b_n=0$

    那么,对于这样的式子,就可以做到将所有的$A^K$用$A^0\sim A^n$的矩阵线性表达出来了。

    $A^{x+y}=A^x \times A^y$

    那么$A^x=\sum\limits_{i=0}^n b_i\times A^i,A^y=\sum\limits_{i=0}^nc_i\times A^i$

    也就是:$A^{x+y}=\sum\limits_{i=0}^n\sum\limits_{j=0}^nb_i\times c_{j}\times A^{i+j}$

    因为有:$p(A)=0$也就是说:$A^{x+y}=\sum\limits_{k=0}^{2\times n}(\sum\limits_{i=0}^{\min(n,k)}b_ic_{k-i})A^k \mod p(\lambda)$

    然后显然,可以用倍增(其实就是快速幂)上述操作,也就是我们得到了一个$n^2\log m$复杂度的递推。

    对于上述暴力操作可以用$NTT$或$FFT$优化上述多项式相乘和多项式取模。

    也就是说,我们得到了一个$n\log n \log m$的优秀做法!(拿头写啊

    关于答案

    $A^x=\sum\limits_{i=0}^n b_i\times A^i$

    这个式子已经给我们答案了,也就是说,这个矩阵的前$n$项加上系数相加即可,但是显然这个东西是$n^4$的

    如果要求$f_m$的话,这个东西只需要用到$f_0\sim f_n$即可

    如果求矩阵的话,还是老老实实的一个一个乘吧...

    例题.jpg

    求矩阵特征多项式裸题:[BZOJ4162]

    常系数线性齐次递推$n^2\log m$裸题:[BZOJ4161]

    高难度的东西:[NOI 2017 泳池]

    附件

    NOI 2017 泳池 题解

    对我来说,可能我只能接受$k\le 2000$,如果再大就想要打人了...

    首先70分的暴力基本雷同[UNR 2 积劳成疾](http://uoj.ac/problem/311)

    大概就是推一个$f[i][j],s[i][j]$即可,[我不想再写一遍了](https://winniechen.cn/?p=152)

    剩下的就是可以把这个转移写成矩阵的形式,然后就可以拿到优秀的$90$分了。

    最后,根据上面的东西,优化一下就可以AC掉这道题了!

    转载于:https://www.cnblogs.com/Winniechen/p/10246295.html

    展开全文
  • 方阵特征多项式的快速算法。 Rizwana Rehman 和 Ilse CF Ipsen 在“La Budde's Method For Computing Character Polynomials”中描述了算法 例如,请访问: ...
  • 特征多项式生成M序列

    2013-11-21 18:27:34
    根据特征多项式得到对应的m序列,特征多项式的输入为matlab通用的多项式输入方式。返回一个m序列。
  • 传递矩阵的特征多项式 定义正则有理矩阵的“特征多项式”为所有子式的最小公分母。 定义特征多项式的次数为"McMillan阶数",或简称,的“阶数”,并记为。

    传递矩阵的特征多项式

    1. 定义正则有理矩阵\hat{G}(s)的“特征多项式”为\hat{G}(s)所有子式的最小公分母。
    2. 定义特征多项式的次数为"McMillan阶数",或简称,\hat{G}(s)的“阶数”,并记为\delta \hat{G}(s)
    展开全文
  • 1、特征值、特征向量 A是复数域的方阵、lambda是一个复数、x是...2、特征矩阵、特征多项式、特征方程 求法:先求特征值——>然后求每一个特征值对应的基础解系——>最后获得全部特征向量表示 ...

    1、特征值、特征向量

    A是复数域的方阵、lambda是一个复数、x是一个n*1的非零矢量

    2、特征矩阵、特征多项式、特征方程

    求法:先求特征值——>然后求每一个特征值对应的基础解系——>最后获得全部特征向量表示

     

     

     

    展开全文
  • 利用代数几何方法,研究具有多输入的2-D广义系统Roesser模型的特征多项式系数的任意配置问题。通过引入恰当形式的状态反馈,消除了2-D广义系统的无穷远极点,得到了相应的闭环系统。以代数几何方法为工具,将此闭环...
  • 对三维欧氏空间中平面构形的特征多项式进行了研究。用代数与几何的方法,以特征多项式为不变量,把平面个数不多于5的构形进行了分类,同时计算了空间中一些图形有规律的非中心平面构形的特征多项式
  • 特征值与特征向量 设 A\mathscr{A}A 是数域 PPP 上线性空间 VVV 的一个线性变换,如果对于数域 PPP 中一数 λ0\lambda_0λ0​ ,存在一个非零向量 ξ\xiξ 使得 Aξ=λ0ξ ...特征多项式 设 AAA 是

    特征值与特征向量

    A \mathscr{A} A 是数域 P P P 上线性空间 V V V 的一个线性变换,如果对于数域 P P P 中一数 λ 0 \lambda_0 λ0 ,存在一个非零向量 ξ \xi ξ 使得
    A ξ = λ 0 ξ \mathscr{A} \xi = \lambda_0\xi Aξ=λ0ξ
    那么 λ 0 \lambda_0 λ0 称为 A \mathscr{A} A 的一个特征值,而 ξ \xi ξ 称为 A \mathscr{A} A 的数域特征值 λ 0 \lambda_0 λ0 的一个特征向量

    特征多项式

    A A A 是数域 P P P上愿意 n n n 阶矩阵, λ \lambda λ 是一个文字,矩阵 λ E − A \lambda E-A λEA 的行列式
    ∣ λ E − A ∣ = ∣ λ − a 11 − a 12 ⋯ − a 1 n − a 21 λ − a 22 ⋯ − a 2 n ⋮ ⋮   ⋮ − a n 1 − a n 2 ⋯ λ − a n n ∣ |\lambda E-A|= \begin{vmatrix} \lambda - a_{11}&-a_{12}&\cdots&-a_{1n}\\ -a_{21}&\lambda-a_{22}&\cdots&-a_{2n}\\ \vdots&\vdots&\ &\vdots\\ -a_{n1}&-a_{n2}&\cdots&\lambda-a_{nn} \end{vmatrix} λEA=λa11a21an1a12λa22an2 a1na2nλann
    称为 A A A 的特征多项式,这是数域 P P P 上的一个 n n n 次多项式。

    展开全文
  • 随机矩阵特征多项式的相关函数的行列式表示,娄泰山,郭铁信,本文利用正交多项式的性质给出了高斯辛系综中酉辛群上的随机矩阵特征多项式的相关函数和矩的简洁的行列式表示,且行列式的元为正
  • 本文提供了计算矩阵的特征多项式的一种简单算法。本算法首先将矩阵通过简单的行和列变换化为Hessenberg形,然后采用一组公式和递推算法,来计算矩阵的特征多项式。本算法在计算上是简单、直观的,同时适用...
  • 设A是主对角线可以有非零元的(0―1)对称矩阵。本文提出:A的特征多项式的前几个系数可以由A所对应的图的边数、环数和三角形个数所确定;当A的行和相等时,A和A的特征多项式之间有一个简单的关系式。
  • 设A(G)是图G的邻接矩阵,J是全1方阵,1是单位矩阵。称S(G)=J-1-2A(G)为图G的seidel矩阵,与之对应的多项式Sc(λ)=|λI|-S(G)|称为图G的seidel特征多项式。本文给出了完全图Kn的seidel特征多项式及其谱。
  • 采用傅里叶分析的方法对相位提取算式作了理论分析,并根据特征多项式设计分析理论构造了新的、对移相误差不敏感的相位提取算式。经实验验证,该算法有效地提高了相移干涉仪测量表面形貌的Ra值,重复测量精度达5倍以上,...
  • 求矩阵的特征多项式

    千次阅读 2018-03-07 15:09:00
     首先你要知道矩阵的特征多项式是什么。  直接消元就可以了。  时间复杂度:\(O(n^5)\)或\(O(n^4)\)。 一个稍微快一点的做法  观察到特征多项式的次数是\(n\)。  我们就可以插值。  具体来说,先求出当\(x=0\...
  • 设图G为简单图,G的无符号拉普拉斯矩阵Q(G)=D(G)+A(G),其特征多项式记为φ(G,λ)=∑ni=0pi(G)λn-i。给出了双圈图的无符号拉普拉斯特征多项式的常数项pn(G),并证明了pn(G)仅与双圈图的基图有关。
  • 特征多项式及Cayley-Hamilton定理

    千次阅读 2019-05-21 22:07:03
    大佬blog 大佬blog 大佬blog 学数学的时候,可能会接触到一个叫做特征根法,特征根方程的东西,当时不觉明历。 实际上这是和线性代数...特征多项式是指对一个nnn阶(转移)方阵AAA , f(λ)=det⁡(λE−A)=λN+b...
  • 矩阵特征多项式的系数公式

    万次阅读 2019-05-17 11:33:43
    时间是个常数,但对勤奋者...关于nnn阶矩阵的特征多项式,书上只给出了最高次项、次高次项和常数项: ∣λE−A∣=λn−(trA)λn−1+⋯+(−1)n∣A∣.(1)|\lambda E-A|=\lambda^n-(tr A)\lambda^{n-1}+\cdots+(-1)^n...
  • 用Gauss过程的Karhunen-Loeve展开,把一些特殊的矩阵值二次Winer泛函表示成独立Wishart随机矩阵的和,然后运用逼近的方法计算了这些矩阵值二次Wiener泛函的特征多项式和矩的期望.
  • 特征p的有限域上曲线v ^ 2 = u ^ p-au-b的特征多项式
  • 线性代数:特征值Sylvester降幂公式(特征多项式的降阶计算公式)------------------------------------------------------------------------------------------------------欢迎使用Markdown编辑器新的改变功能...
  • 给出了由平面图经一元运算而构造的4类图,并得到了这4类图的特征多项式
  • 将简单图的邻接矩阵的特征多项式系数定理推广到适合符号图的情形,并将其用于研究n阶单圈符号图的零度.当n≥5时,得到了它的上界为n- 4,并刻画了零度为n- 4的图;得到了单圈符号图的零指数集合.
  • 设G是一个简单无向图,A是图G的邻接矩阵,对角矩阵D=diag(d1,d2,…dn)是G的顶点度矩阵,则...本文研究了G的拟拉普拉斯矩阵的特征多项式Qc(P)的系数,利用图G的边数、度序列和三角形个数给出了Qc(u)的一些系数的代数表达式。
  • F(X)=C0Xn+C1Xn-1+……+Cn-1X1+Cn(C0≠0)为矩阵的特征多项式 牛顿恒等式 ...一个矩阵的x次方对矩阵的特征多项式取模表示为一个矩阵的0-n-1次方乘系数后的和 这一步可以n^2*logx求出系数多项式 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 37,617
精华内容 15,046
关键字:

特征多项式