最近一直在写毕业论文, 也想不起来更新博客. 发现很久没写了, 上来补一篇.
过年的时候和好友聚餐, 去吃回转寿司(配图从网上随便找的, 非去过的店铺, 仅供参考). 回转寿司里有一个很长的转盘, 厨师把寿司放到传送带上, 然后传送带不断旋转, 这样顾客能够随意挑选自己想要的寿司.

我的好朋友吃饱了以后就开始犯强迫症了. 他看转盘上的寿司摆放不均匀, 每次看到一个寿司到左边的寿司和到右边的寿司距离不相等, 他就把那个寿司挪一下位置, 让它刚好在左右两个寿司的正中间. 挪着挪着他就问我: 你说我这么一直挪着, 如果没其他人放寿司或者拿走寿司, 最终这些寿司能摆放均匀么?
我说我感觉上可以, 他也说感觉上可以. 我们怎么证明呢? 当时给了他一个解答, 后来又想到一个更有意思的解答. 仅仅用到一些数值代数知识.
记我们有$n$个寿司, 顺时针或者逆时针顺序编号, 第$i$个寿司到第$i+1$个寿司的距离是$d_{i}$. 因为是个转盘, 所以第$n+1$个寿司实际上就是第$1$个寿司, 为了描述方便, 后面凡出现$n+1$的时候都认为是$1$, 这样就不用特殊说明了. 另外$d_{1}+d_{2}+\cdots+d_{n}=L$, 也即转盘长度. 我好友的操作实际上就是对向量$d$左乘一个矩阵. 举个例子来说明一下, 为了写着方便, 以$n=3$为例, 他只会有挪动三个寿司的操作, 也就是三种不同操作, 分别相当于对$d$左乘的矩阵是这三种:
$
\left(
\begin{array}{ccc}
0.5 & 0.5 &0 \\
0.5& 0.5 &0 \\
0 & 0 & 1
\end{array}
\right)
$,
$
\left(
\begin{array}{ccc}
1 & 0 & 0 \\
0 & 0.5 & 0.5 \\
0 & 0.5& 0.5
\end{array}
\right)
$,
$
\left(
\begin{array}{ccc}
0.5 & 0 & 0.5 \\
0 & 1 &0 \\
0.5 & 0 & 0.5
\end{array}
\right)
$.
这种矩阵有什么特点? 稍微变型一下. 我们定义$n$个列向量$u_1, u_2, \ldots, u_n$: 其中$u_i$是这个样子的, 他的第$i$个分量是$1/\sqrt{2}$, 第$i+1$个分量是$-1/\sqrt{2}$, 其余分量全是$0$. 于是可以验证前面提到的矩阵实际上可以写成这样: $I-u_1u_1^T, I-u_2u_2^T, \ldots, I-u_nu_n^T$. 这个非常像Householder变换. 因为这几个矩阵都差不多, 我们拿出其中一个$I-u_iu_i^T$来分析一下.
很显然$I-u_iu_i^T$的秩是$n-1$, 它有唯一一个$0$特征值, $u_i$就是它的特征向量. 而其余特征值都是$1$.
我们需要想办法说明, 每一次挪动寿司都会导致一个量发生不可逆的变化, 这样才能证明, 不会操作了半天又退回到某个状态. 这里我们用向量的模长.
对于任意一个向量$d$, 如果将$I-u_iu_i^T$左乘$d$, 那么$d$的模长会变小, 除非$d$和$u_i$垂直. 具体是这样的:
$\| (I-u_iu_i^T)d \|^2 = \| d – u_iu_i^Td \|^2 = d^Td – 2(u_i^Td)^2 + (u_i^Td)^2 = d^Td – (u_i^Td)^2$
所以, 除非$d$和所有的$u_1,u_2,\ldots,u_n$都垂直, 否则在这$n$个矩阵的轮流作用下, $d$肯定是会一直变化的, 因为他模长变小了. 收敛到什么状态呢? 那就是$d$和所有的$u_1,u_2,\ldots,u_n$都垂直, 所以我们来看他们一列列堆起来构成的矩阵 $M=(u_1, u_2, \ldots, u_n)$, 如果收敛了, 只能是$M^Td=0$. 很显然$M$这个矩阵的秩至少是$n-1$, 因为我们观察他的前$n-1$列, 第$i$列的第$i$行元素非零, 其他列的那一行却是$0$, 所以线性无关. 因此$M^Td=0$的解空间至多是一维的. 容易找到一组解是$(1,1,\ldots,1)^T$, 所以所有解都是它的常数倍. 因此不停操作, 不停左乘矩阵, 不停迭代, 最终收敛到所有分量都相等, 也就是相邻寿司之间的距离都相等.
那从$d$出发开始迭代, 收敛到什么状态呢. 可以发现$d_1 + d_2 + \ldots + d_n=L$这个在操作过程中是保持不变的. 实际上看, 寿司距离加起来肯定永远是转盘长度. 从计算上看, 如果定义$e$是各个维度全是$1$的向量, 可以验证$e^T u_i = 0$ , 所以 $e^T (I-u_i u_i^T) d = e^T d – e^T u_i u_i^T d = e^Td = L $ , 这个就说明在每次变化后, $d_1 + d_2 + \ldots + d_n$不变. 所以最终收敛的时候, $d_i = L / n$.
也就是说, 经过我好友的不懈努力, 最终是可以让所有寿司均匀摆放的!