从矩阵谱分解到矩形的最少正方形剖分

上次听AK讲到谱分解的时候，若有所思，下面将对思考稍作记录。

矩阵谱分解

关于谱分解有很多定义，主要区别在于条件的强弱，有的要求一个n阶矩阵不仅要求可对角化，而且加强条件至其n个特征值λ1,λ2,...,λn互异，我们这里由于不深入讨论谱分解，所以就采用最简单的定义来说。

定义：若n阶矩阵A可对角化，那么存在n个n阶方阵Gi使得A=∑ni=1λiGi.

证明:设矩阵A的n个特征值为λ1,λ2,...,λn，其对应的特征向量进行Gram-Schmidt 正交化后为α1,α2,...,αn，那么有Aαi=λiαi。令P=[α1,α2,...,αn]，可以写成矩阵形式有AP=P⋅diag(λ1,λ2,...,λn)。
此时，令：P−1=(βT1,βT2,...βTn,)T，注意到这里的可逆性是由Gram-Schmidt 正交化保证的，当然，如果条件加强至特征值均互异，那么特征向量是相互独立的，这样不需要进行正交化，也可以保证可逆性。βi和αi的size相同。

于是谱分解的命题得证，上述证明同时给出了谱分解的一个构造。

问题引入

在讲座中AK猜测谱分解可以像SVD那样对图像进行压缩，但是有个不好的地方在于和SVD不同，谱分解要求矩阵(图像)为方阵。

当时有若干想法（假设谱分解可以用于图像压缩）：

• 既然谱分解只能作用于方阵，而对于一个m⋅n的图像矩阵A，那我们是否能对一个矩形方阵先进行正方形剖分，后处理呢？
• 正方形剖分后，分别进行压缩后重组的图像和直接进行压缩（假设是图像本来就是方阵的情况下）是否有区别？如果有，那么从肉眼角度，区别大不大？
• 既然要正方形剖分，那么这样的剖分是否存在？如果存在是否有最小正方形个数的剖分（这样的剖分可以使得处理和重组次数都最小）？如果有最小的剖分，那么这样的剖分数的方法是否唯一？
• 矩形的正方形剖分种类是否有限？

后来觉得不太对劲，虽然由谱分解A=∑ni=1λiGi，可以舍弃掉特征值较小的部分。但是，较小？实际上，矩阵的特征值完全有可能是复数，甚至几乎都是复数(当然这里的复数是特指虚部不为0的意思)。而SVD所求的特征值是ATA的，作为实对称矩阵的所有特征值必为实数。先用SVD来验证一下，“剖分-重组”的思路如何:

(a)和(b)两图都用SVD处理(仅保留一个特征值)，从(a)中可以发现“剖分-重组”从肉眼上差别不大，但是从(b)中可以发现差别还是有点明显的，实际上这种思路本身就不抱太大的希望2333。

矩形的最少正方形剖分

和完美正方形剖分不同的是，我们这里关注的是分成的正方形数量最小，而不需要和完美正方形剖分那样要求每个正方形大小互异。

• 正方形剖分是否存在？
  存在性是显然的，我们以一个5x3的矩形为例，我们显然可以如下图(a)所示

将其分成15个小正方形显然是一种剖分，存在性即可证明。此时实际上不仅给出了一种剖分的构造同时也给出了”de数”(剖分后正方形的数量，de是decomposition的缩写)的一个上界，由最小数原理（自然数集的任一非空子集必有最小数）知道，”de数”必有最小值，即对于任意矩形，存在最少的正方形剖分。

关于”de数”的界还可以参考这篇文章Tiling a Rectangle with the Fewest Squares ，这篇文章指出，对于一个m⋅n的矩形，其中m≥n，那么log2n≤ de数 ≤mn+C⋅log2n,其中C是一个常数，虽然这个结论没什么太大的用处，但是上下界都出现的log2n引起了我的注意，它恰是辗转相除法的时间复杂度，为何突然扯到辗转相除法呢？且听我慢慢分析。

• 贪心策略下的剖分

狗蔡在ak那场讨论班中给出了一种贪心的办法，即上图(b)中的办法。
对于这个5x3的矩形，先取一个以短边的正方形，即3x3的正方形，然后一直下去，可以观察发现似乎可以作为一种剖分的办法。

做了两三次手动计算后发现，实际上这就是一个辗转相除法，可以说明最后剩下的正方形的边长大小恰好就是gcd(m,n)。对于相邻Fibonacci数型的矩形，这样的方法也是很优美的说，如下图所示：

对于这个8x13的矩形，我们甚至可以从繁分数的角度来一目了然：

用F{1,1,1,1,2}表示，4个1恰好就是黄、绿、蓝、红四个正方形，最后一个2就是紫色的两个正方形。遗憾的是，这种辗转相除法并不是最优解，因为很快就构造出了反例：

上面是9x10的矩形，可以发现右边这种辗转大法并不是最优的。但似乎可以证明，斐波那契型的矩形是最优解（具体是否有看到这样的文献不是太记得了ww）

• “de数”剖分的方法是否唯一？

从目前来看，这个问题并不确定，一般情况下，除了对称解外，至今没有找到通用反例。但是对于斐波那契型矩形而言，却很容易构造多解。（利用辗转相除法）

好吧还是给出构造吧（如下图所示），注意到由于每次划分的时候，两部分之间都可以对调（如图），而由辗转相除法的复杂度可以估计数量大约有O(logn)个，由乘法原理知道，这种情况下。同一个de数有O(2[logn])=O(n)种划分。

• 矩形的正方形剖分种类是否有限？

考虑一个这样的额外问题，一个矩形的正方形剖分的方法的种类是否是有限的呢？辗转相除法是一种通用剖分，直接分为m⋅n个矩形也是一种通用剖分，所以对于一个矩形，它至少有两种方法，那么方法数是否有上界呢？

这个问题是和AK在吃饭的时候解决的，当时西园一楼的天花板恰好就是一个一个的小格子，有灯的部分恰好是有小格子的大矩形，恰好可以用来观察。下面这一步思考虽然有冗余，但是恰是思考的过程，我们可以得到：

其中DSquare，DRectangle，DTetris分别表示正方形剖分种数，矩形剖分种数和俄罗斯方块剖分种数，用Sname表示他们的剖分方法的集合。其如下图所示：

上述不等式成立的原因是，显然有SSquare⊆SRectangle⊆STetris，所以我们只需要给出DTetris的一个有限上界就可以说明正方形剖分种类是有限的了，实际上这个有限上界并不难给出。

考虑一个m⋅n的矩形，可以容易知道它一共有m(n+1)+n(m+1)条单位边，其中横向的有m(n+1)条，纵向的有n(m+1)条。对这些边进行二染色，即要么染色，要么不染色，设这样的处理种数的集合为Sbin，显然有STetris⊆Sbin，于是立马有：

综上所述，正方形剖分种数的有限性得证。

数值求解

我们不妨回顾一下完全背包问题：

（完全背包问题）有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是ci，价值是wi。将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

而对于我们的剖分问题而言，我们可以将m⋅n的矩形看成是一个容量为mn的背包，有n种物品（注意到，不妨设m≥n，那么最大最大的正方形边长为n）,那我们可以改写一下完全背包问题：

（矩形最少正方形剖分）有n种物品和一个容量为mn的背包，每种物品都有无限件可用。第i种物品的体积是c2i，价值是1。将哪些物品装入背包可使这些物品的体积总和等于背包容量，且价值总和最小。

可以看出，矩形最少正方形剖分问题应该是比完全背包问题要强的，而完全背包问题是NP-complete问题，所以说可以大致估计矩形最少正方形剖分问题也应该是NP-complete问题。所以，本问题不妨从最优化的角度入手。

先约定一些符号，下面的模型也可以直接参考论文Minimum Tiling of a Rectangle by Squares：。对矩形建立一个平面直角坐标系，不过不是连续的，而是格点状的，左下角的格子看做为(0,0)，

我们称边长为k的正方形占据着坐标(i,j)是指，坐标(i,j)恰好为正方形k的左下角，用k∈(i,j)表示。由此定义，我们等会讨论的关注点都在上左下角！（注意辣）。更进一步定义：

其中，对于一个MN的矩形，t∈{1,2,...,N},i∈Nt={0,1,...,N−t}以及j∈Mt={0,1,...,M−t}。由此，我们可以建立一个0-1规划的模型：

优化目标容易理解，而限制条件的目的是使得任意一个坐标(i,j)最多只有一个正方形占据（占据是指k∈(i,j)），上图(a),(b)给出两种案例给大家理解限制条件中和号的范围取定。（重申一次，我们考察的是正方形的左下角，上图黑框给出左下角的范围）另一方面，限制条件还有一个功能：使得矩形每个位置均在一个正方形内，没有缺漏。（想一想为什么，假设有缺漏，直接以这点为(i,j)考虑一下限制条件即可）

这个0-1规划问题问题如何求解，额，只能上启发式算法了，特别注意到的是，模型中优化目标有MN2个0-1变量，限制条件有大约O(MN)个。规模可以说是相当地巨大。

这灰常考验计算能力，截止至2016年6月14日，已经在这里公布了380x380以内的矩形的计算结果。同时这里给出了一个在线的可视化结果。

下面给出40x40以内的直观结果，z轴表示de数，纵横代表m,n，其中m≥n所以有一半是没有的，下面给大家欣赏一下：

一些补充

• 最少正方形剖分的应用

最少正方形剖分是有直接的应用的，如有关量子霍尔阵列电阻的文章。

• 猜想1：de(m,n)=de(km,kn)

其实从上图（右）可以看出很多斜率相同的格点的值是相同的，这个猜想如果成立可以迅速扩大矩形的规模（现在是380x380），另外这个猜想至今没有找到反例。

• 猜想2：若m≥n，那么有de(m+n,n)=de(m,n)+1

这个稍微画个图大致就会觉得还是蛮有道理的，但是很遗憾的是，在近几年里，这个猜想被推翻，反例是：de(112,53)=de(59,53)=11。

• 猜想3：de(m,n)∼g(m)=logϕ(m⋅5√)，其中ϕ=1+5√2。

上面提到了繁分数，对于Fibonacci型的矩形，如Fk⋅Fk+1的矩形，其繁分数对应的数码之和，或者说de(Fk,Fk+1)是满足（应该是成立的，暂时没证明），de(Fk,Fk+1)∼logϕ(Fk+1⋅5√)，而对于一般情况我们用程序验证一下de(m,n)和g(m)的关系，如下图所示：

可以看出效果还是可以的，“阶”大致吻合。