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$。

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

其中向量的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，有一个比较显然的性质

我们只需要在右侧乘上$(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不变是等价的，具体一点，

）。

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

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

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

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