代数问题

Published: by Creative Commons Licence

  • Tags:

拉格朗日定理

拉格朗日定理:对于任意有限群$G$以及其某个子群$H$,都有$|G|$ 能被$|H|$ 整除。

证明:

当$G=H$时,定理显然成立,下面考虑$G\neq H$,此时有$|H|<|G|$。

考虑$H$在$G$中的补集中的任意元素$x_1$,我们构建$H$的左陪集:

下面我们证明$H$的这些左陪集与$H$的交集为空,假设存在交集,即:$h_i=x_1*h_j$

那么我们可以直接推出:$x_1=h_i*h_j^{-1}\in H$

而这与$x_1$不属于$H$的前提相悖,因此证明完成。

如果$H$与$xH$的并集不等于$G$,那么就存在额外的元素$x_2$,落在$H$和$xH$之外。于是我们继续构建$H$的左陪集$x_2H$。

重复这个流程,直到得到左陪集与$H$的并集等于$G$为止。假设这时候我们得到的左陪集为$x_1H,x_2H,\ldots, x_kH$。

下面我们证明这些左陪集也是互不相交的,假设$x_iH$与$x_jH$($i < j$)交集非空,那么有:

,这与我们之前的$x_j \notin x_iH$前提相悖,因此证明成立。

可以发现这k个左陪集与$H$都拥有$|H|$个元素,且互不相交,且并为$G$。因此可以得出:$(k+1)|H|=|G|$ ,因此$|H|$能够整除$|G|$,命题成立。

$rank(A^TA)=rank(A)$

对于任意$m\times n$矩阵$A$,都有$rank(A^TA)=rank(A)$。

证明:

考虑对于$A^TA$零空间中的向量$x$,有

因此,$A^TA$和$A$具有相同的零空间,$A$的零空间的秩为$rank(N(A))$,那么$A^TA$的秩为$rank(A^TA)=m-rank(N(A))=rank(A)$。

实对称矩阵特征向量两两正交

考虑对称矩阵$A$,以及其某个特征向量$x$和$y$。有

将第一个式子的左右两端都乘上$y^T$,可以得到:

这意味着,$\lambda_1\neq \lambda_2\Rightarrow y^Tx=0$。

奇异值分解存在性证明

奇异值分解是指对于任意$n\times m$矩阵$A$,我们都能将其分解为如下形式$A=U\Sigma V^T$的形式,其中$U$和$V$是标准正交矩阵,而$\Sigma$是对角线矩阵。

首先我们对矩阵$A^TA$做奇异值分解,得到$A^TA=V\Lambda V^T$,因此我们直接得到了一个标准正交矩阵。接下来我们证明两个$V$中的正交向量列$v_i$和$v_j$在$A$的线性变换下依旧正交。

因此我们得到了正交矩阵$AV$。但是这里$AV$不一定是标准化的。我们可以将$AV$右乘一个对角矩阵帮助其标准化:

两个相似矩阵的特征多项式相同

证明非常简单,设$P$为某个可逆矩阵,$A$为某个方阵。那么

特征多项式

考虑某个交换环$R$上的$n\times n$矩阵$A$,我们定义它的特征多项式为:$f(x)=|xI-A|$,其中$x\in R$。考虑到行列式的定义,显然$A$的特征多项式是$n$阶多项式。

要计算$A$的特征多项式,我们可以用插值法,找出特征多项式在$0,1,2,\ldots n$的取值,之后用插值法插出多项式即可。后面的步骤需要的时间为$O(n^2)$,因此瓶颈在于如何快速得到特征多项式在$O(n)$个点的取值。

由于两个相似矩阵的特征多项式相同,因此我们可以通过计算$A$的某个相似矩阵来加速行列式的计算。由于每个矩阵都相似与某个上海森堡矩阵相似,因此我们可以将$A$化为某个上海森堡矩阵,上海森堡矩阵长相为:

即对于任意$i>j+1$,都有$a_{i,j}=0$。

花费$O(n^3)$时间复杂度就可以将$A$化为上海森堡矩阵。

接下来我们直接认为$A$是一个上海森堡矩阵。容易发现通过消元法求$f(x)$,其中$x$是给定值,所需要的时间复杂度仅为$O(n^2)$。因此计算$f$在$O(n)$个点上的特征函数值需要的总时间复杂度为$O(n^3)$。

这里总的时间复杂度为$O(n^3)$。

Cayley-Hamilton定理

任意交换环上的方阵$A$和其特征多项式$f$,都满足$f(A)=0$。

特征多项式与矩阵快速幂

要求计算$n\times n$矩阵$A$的$k$次幂$A^k$,其中$n\leq 50$,$k\leq 2^{10000}$。

直接上矩阵快速幂,时间复杂度为$n^3\log_2k$,如果$k$小点还是有机会的,但是不好意思,过不了。

现在我们用特征多项式来加速。

我们先以$O(n^3)$的时间复杂度算出$A$的特征多项式$f$,之后利用Cayley-Hamilton定理可以发现:

而这里$f$是$n$阶多项式。我们可以先计算出$x^k\mod f(x)$,之后用$A$代入$x$即可。

定义$g(i)=A^i \mod f(A)$,那么我们可以利用下面的发现进行快速幂算出$A^k$。

这里我们需要处理的是多项式卷积和除法,我们可以利用快速卷积进行加速(如果要求计算的是取模结果,且模数不是很好的情况下,可以选择暴力计算),那么时间复杂度为$O(n\log_2n\log_2k)$(暴力的情况下为$O(n^2log_2k)$)。

之后我们得到的是$g(k)$,其代表的是一个$n-1$阶的多项式,我们可以将$A$代入得出最终结果,这里的时间复杂度为$O(n^4)$。

因此总的时间复杂度从$O(n^3\log_2k)$优化到了$O(n^4+n\log_2n\log_2k)$(暴力的情况下为$O(n^4+n^2log_2k)$)。

特征多项式与递推数列

现在考虑一个问题,存在一个数列${x_i}$,我们已知前$n$项$x_0,x_1\ldots,x_{n-1}$,已知一种递推关系

要求我们计算$x_k$,其中$k\leq 10^9$,$n\leq 1000$。

我们可以用矩阵运算来表示线性递推关系,建立一个矩阵

同时建立输入向量:

那么就有:

现在我们将问题转换为,存在一个$n\times n$矩阵$A$,我们希望求解$A^kx$,其中$x$是长度为$n$的列向量,$n\leq 1000$,$k\leq 2^{10000}$。

在特征多项式与矩阵快速幂一节中,我们给出了两种时间复杂度$O(n^3\log_2k)$和$O(n^4+n\log_2n\log_2k)$,显然两种都是低效的方式。

下面我们来进行优化整个算法。首先我们需要通过行列式以及插值法来找特征多项式吗,考虑到$A$非常简单,我们可以直接手推出特征多项式:

这样我们就避免了$O(n^3)$时间复杂度的计算特征多项式的流程。

之后由于我们实际上不需要真的得出$A^k$,这只是个中间产物而已。假设我们已经得出了

那么我们直接跳过中间产物的计算,一步到达结果:

这里我们避免了计算$A^k$,直接通过计算$x^k \mod f(x)$的系数以$O(n)$的时间复杂度得到了值。

这里总的时间复杂度为$O(n\log_2n\log_2k)$。

线性函数和线性递推关系

考虑给定一个$n\times 1$的向量$x$和$n\times n$的方阵$A$,我们希望求$(A^kx)(1)$,其中$k\leq 2^{10000}$,而$n\leq 100$。

首先会想到矩阵加快速幂,时间复杂度为$O(n^3\log_2k)$,但是绝对会超时。下面聊一下如何用特征多项式进行加速计算。

首先设$f(x)$是$A$的特征多项式,那么利用Cayley-Hamilton定理可以推出:

我们可以发现序列${A^i}$存在长度不超过$n$的递推关系。

但是问题是该如何找出这递推关系呢?我们可以先搁置这个问题,继续看看利用递推关系,我们是否可以加速计算$(A^kx)(1)$。记$y_i=(A^ix)(1)$,那么利用递推关系,可以得出:

我们发现序列${y_i}$也存在长度为$n$的递推关系。而我们要求的就是$y_k$。

剩下的流程实际上就和特征多项式与递推数列这一节的内容一样了。这部分的时间复杂度为$O(n\log_2n\log_2k)$。

现在还剩下最后一个问题,如何找到序列${A^i}$和${y_i}$公共的递推关系呢你可以这样做,计算出$y_0,y_1,\ldots,y_{2n}$,(直接暴力计算,这里需要花费$O(n^3)$的时间复杂度,但是如果矩阵非常稀疏的话,我们实际上可以在$O(n^2)$时间复杂度内计算得出)。之后通过BMerlekamp-Massey算法找出它们之间的最短线性递推关系(对应的就是矩阵$A$的最小多项式)即可。BM算法可以以$O(m^2)$的时间复杂度,找出长度为$m$的数列的最短的线性递推关系。

总的时间复杂度为$O(n^3+n\log_2n\log_2k)$(最优的情况下是$O(n^2+n\log_2n\log_2k)$)。天呐撸。

Berlekamp Massey算法的应用

要了解Berlekamp-Massey算法,推荐看一下论文

这里只是提一下怎么使用BM算法。

考虑有存在一组长度为$n$的向量序列$v_0,v_1,…$,其中$v_i=Av_{i-1}$,$A$是一个$n\times n$方阵,而$v_0$是给定值。问题要求你求$v_k$的第$t$个元素$v_k(t)$。

一般主流的做法就是对矩阵$A$进行快速幂,这个需要的时间复杂度为$O(n^3\log_2k)$。但是假如$n\leq 1000$呢,该怎么办。假如矩阵比较稀疏,比如我们从$v_i$中得到$v_{i+1}$只需要$O(n)$的时间复杂度的话,我们就可以用下面的方式在$O(n^2\log_2n)$的时间复杂度内得到结果。

另外一种方式就是求矩阵$A$的特征方程,之后利用特征方程进行快速求解,但是求特征方程需要的时间复杂度是$O(n^3)$。

事实上,我们之所以会选择$A$的特征方程,是因为特征方程一定是$A$的零化多项式。而我们在线性函数和线性递推关系一节中已经说过${A^i}$序列满足的线性递推关系,${v_i}$也是满足的,实际上:

自然${v_i(t)}$也是满足的,

我们可以通过直接计算${v_i}$序列的前面几项$v_0,v_1,\ldots, v_m$,之后利用BM算法在$V(t)={v_0(t),v_1(t),\ldots, v_m(t)}$组成的序列中推出最短线性递推关系,由于$A$的特征方程也一定是该序列的一个递推关系,因此${A^i}$,${v_i}$,${v_i(t)}$的最短线性递推关系最多是$n$项。

那么我们到底该怎么选择$m$,能保证BM推出的线性关系没有问题呢?假设我们用BM算法处理了$m$个数值,之后如果由于最短递推关系不再满足而发生重构,那么重构后的递推关系不小于$\lceil \frac{m+1}{2} \rceil$,但是我们提过整个序列的最短递推关系不会超出$n$项,因此假如我们选择$m=2n$就足够了。

如果我们需要计算整个$v_k$而非仅仅是$v_k(t)$,那么我们就不能使用BM算法了(当然如果你要使用BM算法,那你需要对列向量的每个维度跑一遍BM才行,因为两个维度的线性递推关系可能是不同的)。我们可以通过直接算$A$的特征方程来进行加速,整个过程的时间复杂度是$O(n^3)$,依旧会优于通常的$O(n^3\log_2n)$的做法。

这里有一个不错的题目

矩阵树定理

行列式

先回忆下行列式的定义。

对于一个1~n的排列p,其中逆序对的数目记作$\delta(p)$。

记1~n的所有排列的集合为$P_n$,记排列$p$的第$i$个元素为$p_i$。

方阵的行列式定义为

通过定义求行列式值的时间复杂度为$O(n!)$,在n较大时是不可行的。由于矩阵i行加上j行乘上某个常数,不会改变矩阵的行列式值,因此我们可以利用高斯消元法将矩阵转换为上三角矩阵,再通过计算对角线元素的乘积和得到行列式值,时间复杂度为$O(n^3)$。

矩阵树定理

设G是一个有n个顶点的无向图,定义度数矩阵$D(G)$为:

定义$e(i,j)$为点i与点j之间边的数目,定义邻接矩阵$A$为:

定义拉普拉斯矩阵$L$为:

记图G的生成树个数为$t(G)$。

命题1:L(G)的行列式值为0。

证明:

L(G)所有列的和都是0,因此矩阵的行向量是线性相关的,故矩阵的秩小于n,矩阵的行列式值为0。

记$A/i$表示矩阵A删除第i行i列得到的n-1阶主子式。

命题2:如果G是不连通的,那么L(G)的n-1阶主子式的行列式值为0。

图G至少可以分为两个连通分块$G_1$,$G_2$,设$G_1$中含有$m$个顶点。我们将其$L(G)$行列式化作如下形式:

命题3:如果G是一个树,那么L(G)的任意n-1阶主子式为行列式值为1。

当G只有两个顶点的时候,命题很显然成立。

利用归纳法,假设命题在G少于n个时始终成立,现在考虑G正好有n个顶点的时候的情况。

将顶点1视作根,设x任意一个叶结点,y是x的父亲。我们通过换行换列将第x行(列)和第n行(列)交换,将y行(列)与n-1行(列)交换。由于是偶数次交换,因此行列式值不变。此时行列式形式如下:

删除第n行n列后的行列式值后得到的$L(G)/n$,为图G删除了顶点x后新图$G'$,除了y的度数额外多1。

定理1:对于任意1<=r<=n,L(G)移除后第r行r列后得到的n-1阶主子式$L(G)/r$的行列式绝对值等于$t(G)$

我们观察矩阵B,矩阵B为n行m列矩阵,n是图的点数,m是图的边数。初始时B全为0,之后对于边$e_j=(u,v)$,我们将$B_{uj}$和$B_{vj}$一个设为1,一个设为-1,顺序不重要。

之后我们考虑$BB^T$,对于$i\neq j$其第i行第j列的值是$B$的第i行和第j行的点积,为点i和点j之间边的数目取反。当$i=j$时,其值为点i的度数。

同理可得$|L(G)/r|=|(B/r)(B/r)^T|$。根据Binet-Cauchy公式可以得到:

上面的$B_{1..n,x}$是指B的1~n行,x列的子矩阵。$|B_{1..n,x}/r|$是1当且仅当x形成G的生成树,否则均为0。

因此定理得证。

无向无环图的邻接矩阵的秩

无向无环图(即森林)的邻接矩阵的秩为$2M$,其中$M$是森林的最大匹配。

我们考虑森林的邻接矩阵,知道矩阵的秩等于这个矩阵的最大行列式非0的子式的大小。特别的是,对于对称矩阵,我们可以选择相同的行列,得到行列式非0的最大子式。

而相同行列组成的子式,在图论中实际上是导出子图的概念。即我们仅考虑一部分顶点的导出子图以及它们的邻接矩阵。下面我们来考虑如果计算导出子图的邻接矩阵的行列式是否为0,考虑行列式的定义:

考虑乘积的部分,如果它非零,意味着置换$\pi$分解后的每个循环,对应的图中也存在这样一个环。由于图是无向无环图,因此不存在长度非2的环(长度为2的环存在,因为是无向边)。即当且仅当整个置换都被分解为长度为2的环的时候,乘积部分非0。这相当与所有顶点的一个完美匹配。由于对于树,如果有完美匹配,那么匹配一定唯一,因此,树上的完美匹配一定仅贡献一次,即森林的矩阵行列式非0当且仅当森林存在完美匹配。

因此考虑原来森林的最大匹配,以及匹配的顶点所对应的导出子图,这个导出子图的邻接矩阵一定是森林的邻接矩阵的最大行列式非0子式 。即得出了我们的结论:无向无环图的邻接矩阵的秩等于该图上最大匹配乘2。

这里是codeforces的一道原题。它要求我们计算无向无环图的邻接矩阵的秩的期望。这等价于要求我们计算无向无环图的最大匹配的期望。

由于期望满足线性性质,且森林最大匹配的计算可以采取贪心算法,因此,我们可以记指示变量$X_i$表示第$i$条边是否会被放入最大匹配中。因此期望为$\sum_{i}E[X_i]$。而$E[X_i]=p_i$,其中$p_i$为第$i$条边被选入匹配的概率。利用这些现在在树上遍历即可。

计算二分图匹配数的奇偶性

问题1:给定一个左右各$n$个结点的二分图,要求计算二分图匹配数的奇偶性,其中$n\leq 2\times 10^3$

如果我们将左边的结点视作$1$到$n$的标号,而右边的$n$个结点视作位置,则我们实际上要求的是有多少置换,其中如果存在边$(i,j)$,则表示标号$i$可以放在位置$j$上。

谈到置换数,实际上是没有什么办法可以算的(除非状压,但是在这里是不现实的)。但是需要注意到我们只需要关注结果的奇偶性即可,即结果需要模$2$。

用矩阵$A$来描述二分图的边,$A_{i,j}=1$当且仅当在左边第$i$个结点和右边第$j$个结点之间存在一条边。考虑矩阵的秩的定义:$\det(A)=\sum_{\sigma}(-1)^{r(\sigma)}\prod_iA_{i,\sigma(i)}$

其中$\sigma$是置换,而$r(\sigma)$统计置换$\sigma$中的逆序对数目。由于是在模2意义下的,因此有$(-1)^{r(\sigma)}=1\mod 2$。这时候行列式为:$\det(A)=\sum_{\sigma}\prod_iA_{i,\sigma(i)}$,其实际上就是在统计所有的可能的置换。

因此我们只需要计算$\det(A)$就可以得到结果。这里可以使用bitset来优化时间复杂度,最终的结果为$O(\frac{n^3}{32})$。

问题2:给定一个左右各$n$个结点的二分图,要求对所有边判断,如果删除这条边,计算匹配总数的奇偶性,其中$n\leq 2\times 10^3$

首先我们用问题1的方式得出二分图的匹配数的奇偶性。这里时间复杂度为$O(\frac{n^3}{32})$。

接下来我们考虑余子式的定义。矩阵$A$在$(i,j)$处的余子式$M_{i,j}$表示从$A$中删除第$i$行和第$j$列后矩阵的行列式。而矩阵$A$在$(i,j)$处的代数余子式为$C_{i,j}=(-1)^{i+j}M_{i,j}$。同时有$\det(A)=\sum_{j=1}^nA_{i,j}C_{i,j}$。因此考虑删除边$(i,j)$,对应的就是将邻接矩阵$A$的第$i$行第$j$列元素设置为$0$。这时候对行列式奇偶性的影响为$C_{i,j}$。

因此我们需要对所有$(i,j)$,计算$C_{i,j}$,这不是一个小工作量。

继续我们考虑$A$的伴随矩阵$adj(A)$,其中$adj(A){i,j}=C{j,i}$。$A$与$adj(A)$的关联在于$A^{-1}=\frac{adj(A)}{\det(A)}$。

我们可以$O(\frac{n^3}{32})$求出$A^{-1}$,之后将其乘上$\det(A)$就可以得到伴随矩阵了。

提供一道题目

问题3:给定一个左右各$n$个结点的二分图,要求对所有边判断,如果必须匹配这条边,计算匹配总数的奇偶性,其中$n\leq 2\times 10^3$

这个问题和问题2实际上是一样的,考虑所有的匹配,仅可以分为两类,一类是第$i$条边被匹配,一类是第$i$条边被禁用。因此只需要知道禁用这条边后的奇偶性和原奇偶性就可以求出必选某条边的奇偶性了。

矩阵快速幂多点求值

问题1:给定一个$n\times n$矩阵$A$,并且给出$m$个请求,第$i$个请求要求计算$A^{c_i}x_i$。其中$n\leq 100, m\leq 100, c_i\leq 10^9$。

很显然可以想到矩阵快速幂,但是这样的时间复杂度为$O(n^3\sum_{i=1}^m\log_2c_i)$,太慢了。

有两种方法,先讲复杂的,我们可以直接求出矩阵的特征多项式,之后利用特征多项式在$O(n^3+n^2\sum_{i=1}^m\log_2c_i)$内求解,这是可行的,就是比较复杂。

还有一种方法,就是我们预处理出$A^{2^0},A^{2^1},\ldots, A^{2^{30}}$共31个矩阵,与处理的时间复杂度为$O(31n^3)$。

之后对于第$i$个情感,我们可以利用$x_i$去乘最多$O(\log_2c_i)$个矩阵,注意到矩阵乘法是满足结合性的,因此我们可以先计算矩阵之间的乘法,也可以先计算矩阵和向量之间的乘法,而后者实际上只需要$O(n^2)$的时间复杂度,因此回答请求的部分,每个请求都可以以$O(n^2\log_2c_i)$回答,因此总的时间复杂度为$O(31n^3+n^2\sum_{i=1}^m\log_2c_i)$。

矩阵

置换矩阵

置换矩阵是指每一行每一列恰好有一个$1$,其余元素是$0$的方阵。对于大小为$n\times n$的置换矩阵,很显然总共有$n!$种不同的置换矩阵。

置换矩阵的性质:

  • 两个置换矩阵的乘积也是置换矩阵
  • 如果$A$是置换矩阵,则$A^T=A^{-1}$。

第二点的证明可以观察行交换矩阵$P_{ij}$,可以发现$P_{ij}P_{ij}^T=I$,而所有矩阵都可以表示为行交换矩阵的乘积。

LU分解

每个$R^{n\times n}$矩阵$A$都可以通过高斯消元,转换为置换矩阵,下三角矩阵和上三角矩阵的乘积。

进一步可以得到

其中$P$是置换矩阵,$L$是单位下三角矩阵,$U$是单位上三角矩阵,且$L$与$U$的对角线元素均为$1$,$D$是对角线矩阵。

有些矩阵可以分解为$P=LU$的形式,其中$L$是下三角矩阵,$U$是上三角矩阵。一个可逆矩阵$A$可以进行LU分解当且仅当$A$的所有子式都非$0$。且如果存在LU分解,则矩阵$A$的$LDU$分解是唯一的。

矩阵乘法

矩阵乘法满足下面性质:

  • 如果$A$和$B$均为上(下)三角矩阵,则$AB$也是上(下)三角矩阵

转置矩阵

矩阵$A$的转置记作$A^T$。转置矩阵拥有如下性质:

  • $(A^T)^{-1}=(A^{-1})^T$
  • $(AB)^T=B^TA^T$

对称矩阵

如果$A^T=A$,则称$A$是对称矩阵。

对称矩阵有下面性质:

  • 对称矩阵只有实数特征值
  • 我们可以为对称矩阵选择正交的特征向量

正交矩阵

如果一个$R^{n\times n}$矩阵$A$的列(行)向量为单位向量,且不同列(行)向量相互正交,那么矩阵$A$称为正交矩阵。

很显然置换矩阵也是正交矩阵。

正交矩阵$A$有下面性质:

  • $A^{-1}=A^T$
  • $\det(A)=\plusmn 1$

矩阵求逆

一个$n\times n$矩阵$A$有逆矩阵$A^{-1}$,等价于下面条件:

  • $A$的行列式值非0
  • $A$的行向量线性无关
  • $A$的列向量线性无关
  • $Ax=0$当且仅当$x=0$

一些推广:

  • 如果$A$是上(下)三角矩阵,则$A$可逆当且仅当对角线元素中不含$0$。
  • 如果$A$中对于任意$i$均满足$\sum_{j\neq i}^n|a_{ij}|<|a_{ii}|$,则$A$一定可逆

第二条性质的证明如下,设任意向量$x$满足$Ax=0$,设$x$中绝对值最大的成分为$x_i$,那么$A_ix$一定与$a_{ii}x_i$同号(即非$0$)。因此等式的唯一解为$x=0$,故可以推出$A$可逆。

矩阵$A$的逆矩阵有如下性质:

  • 如果$A$是对称矩阵,则$A^{-1}$也是对称矩阵
  • 如果$A$是上(下)三角矩阵,则$A^{-1}$也是上(下)三角矩阵
  • 如果$A$是稀疏矩阵,则$A^{-1}$可能是密集矩阵
  • $A^{-1}$是唯一的

投影

对于列向量$a$以及点$b$,$b$在$a$上的投影为$p=a\frac{a^Tb}{a^Ta}$,也可以写作$p=Pb$,其中$P=\frac{aa^T}{a^Ta}$。

对于$R^m$的子空间$S$,设其基为$n$个列向量,由这$n$个列向量可以组成一个$m\times n$的矩阵$A$。子空间$S$的投影矩阵为$P=A(A^TA)^{-1}A^T$。

对于任意投影矩阵$P$,都满足:

  • $P$是对称矩阵
  • $P^2=P$
  • $I-P$的是$P$的正交补空间,$(I-P)P=0$,可以通过$(I-P)b=b-Pb=e$得到误差向量。

特征值

对于方阵$A$,如果存在一个非零向量$x$,满足$Ax=\lambda x$,则称$x$是$A$的特征向量,且$\lambda$称为特征值(注意$\lambda$允许为$0$)。

可以发现$(A-\lambda I) x=0$,因此$x$位于$A-\lambda I$的零空间中,因此$A-\lambda I$一定是奇异矩阵。可以得到$|A-\lambda I|=0$。

$R^{n\times n}$上的方阵$A$的特征值$\lambda_1,\ldots,\lambda_n$满足下面性质:

  1. 如果$A$是个上(下)三角矩阵,则对角线上的所有元素正好是$A$的全部特征值。
  2. 特征值不一定是实数,可能是复数。
  3. $A$一定有$n$个复数特征值,但是可能有重复。
  4. $\prod_{i=1}^n\lambda_i=|A|$
  5. $\sum_{i=1}^n\lambda_i=\sum_{i=1}^nA_{i,i}$
  6. 如果$A$的$n$个特征值各不相同,那么对应的$n$个特征向量则线性无关。

第$6$个性质的证明是这样的,设$n$个特征向量线性相关,则有$c_1x_1+\ldots+c_nx_n=0$,继而进行推导:

接下来通过归纳法就可以证明$c_1=0$,从而证明$c_1=\ldots=c_n=0$。因此$n$个特征向量线性无关。

如果$n\times n$的方阵$A$有$n$个线性无关的特征向量$x_1,\ldots,x_n$,以及对应的$n$个特征值$\lambda_1,\ldots,\lambda_n$,那么我们称$A$是可对角化的。记特征向量矩阵$X$的第$i$列向量为$x_i$,特征值矩阵$\Lambda$为对角线为$\lambda_1,\ldots,\lambda_n$的矩阵,可以发现:

可以发现$A^k=(X\Lambda X^{-1})^k=X\Lambda^kX^{-1}$,即$A^k$与$A$拥有相同的特征向量,但是对应的特征值为$\lambda_1^k,\ldots, \lambda_n^k$。

利用特征值可以实现矩阵快速幂。对于矩阵$A^kc$,若$c$处在$A$的特征向量组成的向量空间中,那么$c=a_1x_1+\ldots+a_mx_m$,这时候我们可以发现有$A^kc=a_1\lambda_1^kx_1+\ldots+a_m\lambda_m^kx_m$。

相似矩阵

如果对于$R^{n\times n}$上的矩阵$A$和$B$,存在某个可逆矩阵$C$,满足$A=CBC^{-1}$,那么称$A$与$B$相似。很显然相似关系满足自反性,传递性,对称性,一次相似关系是一类等价关系。

很显然一个矩阵$A$如果有$n$个不同的特征值,则$A$一定与其特征值矩阵$\Lambda$相似。

如果$A$与$B$相似,则满足:

  1. $A$与$B$拥有共同的特征值。(特征向量可能不同)

第一个性质的证明如下,设$Bx=\lambda x$,则有

参考资料

《生成树的计数和应用》