gdkoi23 马戏团里你最忙，tensor product关于最小多项式的性质

· · 个人记录

写错了，转移矩阵不是一个矩阵的幂，而是两个矩阵的幂的和。看新的blog

今天听科普课的时候提到了计算量子物理中的tensor network方法，虽然没听懂但是让我想起了这个题，所以处理一下，不过我还没学到tensor，写的比较简陋吧，但是简陋也有简陋的好处，可能更适合中国宝宝体质。官方题解一笔带过，洛谷上也没题解，有没有在役选手有兴趣写一篇题解交一下啊（

我们每轮用一个向量x，x_i表示这一轮结束时那个数为i的概率，x^\prime表示下一轮的，那么存在一个线性变换A满足x^\prime=Ax，而且这个A乘向量很快，可以用法嘛塔在O(2^nn)时间内计算。这个题的核心问题是，A其实是每一位上的一个2\times 2矩阵A_0的tensor product，而tensor product的幂是很有性质的。不懂的话你先别急，后面会说的。

首先我们看一下A_0（就是对于一位的线性变换）是啥。每位随机到0,1的概率都是\frac{1}{2}，随机到\mathrm{and},\mathrm{or}的概率分别是q,p(p+q=1)，那就是说a有\frac{q}{2}的概率变成0，\frac{p}{2}的概率变成1，剩下\frac{1}{2}的概率还是a。

\begin{bmatrix}p_0^\prime\\p_1^\prime\end{bmatrix}=\begin{bmatrix}\frac{1+q}{2}&\frac{q}{2}\\\frac{p}{2}&\frac{1+p}{2}\end{bmatrix}\begin{bmatrix}p_0\\p_1\end{bmatrix}

中间的矩阵就是A_0。而我们需要的线性变换矩阵就是A_0^{\otimes n}，A_0的tensor product n次幂。关于tensor product，我们还是要说两句，不然你可能啥也不知道。tensor product的定义是

Ax\otimes By=(A\otimes B)(x\otimes y)

其中向量的tensor product就是状态的笛卡尔积。就是说，比如我们有一个两位二进制数，那么它的状态实际上就是 两位分别的状态 的笛卡尔积（就是所有二元组"(第一位的一种状态, 第二位的一种状态)"），对吧。那么如果本来对于两位x,y分别有一个线性变换A,B，现在我要对这个笛卡尔积x\otimes y找一个效果相当于A,B合起来的线性变换，我们就管它叫A\otimes B，它的定义就是上面这个式子。

所以我们可以看到，如果对于一位状态的变换是A_0，那么对n位的就是A_0^{\otimes n}。这里幂的指数前面有个\otimes，表示这是\otimes意义下的幂。

关于tensor product，有一个比较显然的性质

(AC)\otimes (BD)=(A\otimes B)(C\otimes D)

我们只需要在右侧乘上(x\otimes y)，就可以证明这个式子了。

我们知道，按照这个题的意义，我们可以把两个分别长n,m的向量x,y的笛卡尔积用一个新的向量(x\otimes y)_{im+j}=x_iy_j来表示，而矩阵的tensor product也可以用一个新的矩阵(A\otimes B)_{im+j,km+l}=a_{i,k}b_{j,l}来表示。（实际上我有点先起名再定义了，但是tensor product确实就是为了解决具有这种形式的问题而发明的，这个就是它标准的矩阵表示）

好的现在我们回去考虑这个题。考虑A_0的jordan标准型A_0=P^{-1}JP，根据前面提到的性质我们知道A_0^{\otimes n}=(P^{-1})^{\otimes n}J^{\otimes n}P^{\otimes n}，同时我们还可以知道(P^{-1})^{\otimes n}P^{\otimes n}=I。那么如果J是对角的，A_0^{\otimes n}=(P^{-1})^{\otimes n}J^{\otimes n}P^{\otimes n}就给出了A_0^{\otimes n}的一个对角化。

同时，我们可以注意到，如果A,B都是对角的，那么A\otimes B的特征值集合就是A的特征值集合和B的特征值集合的笛卡尔积，就是说从A的特征值选一个，B的特征值选一个，它俩乘起来就是AB的一个特征值。如果不是对角的，通过考察jordan标准型，结论也是一样的。所以我们知道，如果A_0的特征值是\lambda,\mu，那么A_0^{\otimes n}的所有特征值就是\lambda^n,\lambda_{n-1}\mu,\lambda_{n-2}\mu^2,...,\lambda\mu^{n-1},\mu^n。也就是说A_0^{\otimes n}只有n+1个不同特征值。

这意味着，如果A_0可对角化，那么A_0^{\otimes n}的最小多项式就是\prod\limits_k(x-\lambda^k\mu^{n-k})，只有n+1次。

现在问题是A_0不可对角化怎么办。因为它是列马尔可夫的，它肯定有一个特征值1，而不可对角化说明有重复特征值，那么另一个特征值肯定也是1。所以A_0的jordan标准型必然是非零位置全1的上三角矩阵。所以A_0^{\otimes n}是那个分形，就是把行列下标看成集合（0-indexed），(A_0^{\otimes n})_{i,j}=[i\subseteq j]。

我们可以把这个矩阵看成一张有向图的邻接矩阵，如果i\subseteq j就从i到j连一条边。这个矩阵只有特征值1，我们只需要算1的最大jordan块大小，那就只需要算A-I的多少次幂才是0矩阵。那么A-I的意义其实是去掉了到自己的边，k次幂的意义就是在这个图上走k步。显然我们最多走n步（从0走到2^n-1是最多的）就不能再走了。所以这个最大jordan块大小就是n+1，那么最小多项式次数也是n+1。

至于这个题怎么做，有了这个最小多项式不超过n+1次的性质，相信聪明的你一定已经会了吧！！1

其实马尔可夫的性质是不必要的。

接下来我们考虑更一般的性质。现在有一个k\times k的jordan标准型J，我们希望求出J^{\otimes n}的最小多项式长度。首先需要考虑它的形态，前面2\times 2 jordan块的情况，结果是J^{\otimes n}_{i,j}=[i\subseteq j]，这里其实是说我们i,j各有n个二进制位，如果希望J^{\otimes n}_{i,j}=1，我们每一位都得选择i=j（主对角线）或i+1=j（副对角线），而体现在二进制上就是包含。

好的回到一般的情况，现在是k进制位，就需要i,j在k进制表示下，i的每一位要么是j的对应位，要么是j的对应位-1。

所以我们还是来考察一个特征值对应的子矩阵要多少次幂能到0矩阵（这里因为是上三角，你写一下分块就知道它和多少次幂后rank不变是等价的，具体一点，

\begin{bmatrix} A&B\\ O&C \end{bmatrix}^2 = \begin{bmatrix} A^2&AB+BC\\ O&C^2 \end{bmatrix}

）。

还是看成有向图的邻接矩阵，我们每次可以让n个k进制位中的若干位+1，那加nk次就肯定加不动了，所以答案就是nk+1对吧。然后设有m个不同特征值，那么J^{\otimes n}又有最多\binom{k+1}{m-1}个不同特征值，我们就给出了最小多项式次数上界(nk+1)\binom{k+1}{m-1}。当然有些特征值出现次数很少，这个界很容易进一步降低:

\sum_{c:\sum c_i\leq k}\min\left(\frac{k!}{\prod (c_i!)},nk+1\right)

可以通过枚举k的分拆计算。这里c是各特征值在乘积中的次数的序列。所以关键问题在于不同特征值需要很少。

然而我不知道这是不是足够精确，比如我应该打表看看不同出现次数的特征值到底多少次幂之后变成0，以及不同大小的jordan块有什么影响。不过我估计这么有用的问题，我想要说的前人们应该都说过了吧。

确实说过了，见https://arxiv.org/pdf/2010.11873 ，给出了tensor product的最小多项式的精确结果（已知两个矩阵的最小多项式，可以知道tensor product的最小多项式）。