在数学里面经常可以提出这样一些问题：它们叙述起来很简单，答案看起来也很显然，但是要仔细证明却非常困难。即使是线性代数这样的“入门课”中也不缺少这样的问题：

问题：设域 \(\mathbb{F}\) 上的所有 \(n\) 阶矩阵构成的向量空间为 \({\rm Mat}_n(\mathbb{F})\)，\(M\) 是 \({\rm Mat}_n(\mathbb{F})\) 的一个子空间。

1. 如果 \(M\) 中的所有矩阵关于矩阵乘法两两可以交换，那么 \(M\) 的维数最大是多少？
2. 如果 \(M\) 中的所有矩阵的秩都不超过 \(r\)，这里 \(0<r<n\)，那么 \(M\) 的维数最大是多少？
3. 如果 \(M\) 中所有矩阵都是幂零的，即对任何 \(A\in M\)，存在一个正整数 \(m\) 使得 \(A^m=0\)，那么 \(M\) 的维数最大是多少？
4. 如果 \(M\) 中所有非零矩阵都是可逆矩阵，那么 \(M\) 的维数最大是多少？

下面的问题与统计物理中的 Dimer 格点模型有关：

问题：一张 \(8\times8\) 的国际象棋棋盘，用 \(1\times2\) 的多米诺骨牌密铺，有多少种不同的方法？

下图是其中一种：

答案是 12988816，非常大的一个数字，绝对不是一个一个数出来的。1961 年德国物理学家 Kasteleyn 借助于线性代数中的一个结论首先解决了这个问题，接下来就介绍他的方法。

下图是一种密铺的示例：

2021/03/15 更新：刚得知 Youtube 上的博主 mathologer 制作了一期非常精彩的节目，介绍 Aztec 钻石图与多米诺洗牌算法，非常值得一看！

2021/01/01 更新：2021 年的第一天，有人在 Shadertoy 上放了一个精彩的动画，演示多米诺洗牌算法的步骤：

Aigner 和 Ziegler 所著的 Proofs from the book 一书 （中文译版《数学天书中的证明》） 是一本非常精彩的数学读物，其中包含了 40 余个著名的数学问题和它们的巧妙解答。这些问题并不深奥，但也绝非没有受过严格数学训练的人所能欣赏，其中往往包含了相当的洞察力和聪明才智，读起来让人神清气爽，大叹数学之妙。

然而读完这本书的人恐怕都会有意犹未尽的感觉：这就没啦？我还没看够呢！

有一个问题我想是非常适合放在这本书里的，我也非常期待能在未来的版本中看到它，这就是 Aztec 钻石图的多米诺铺砌的计数问题。这个问题完美符合该书选题的标准：

1. 表述初等，不需要太多的背景知识就能能理解。
2. 内涵丰富。Aztec 钻石图是当前代数组合学中一个热点问题，它与交错符号矩阵、表示论、概率论、统计力学都有着深刻而奇妙的联系，有许多悬而未决的问题有待解决。
3. 有多种令人拍案叫绝的解答，每个解答都不平凡，要么需要深刻的数学知识，要么需要开很大的脑洞。

我来介绍一下这个问题：

依次把 \(2,4,\ldots,2n\) 个单位正方形对称地摞在一起，放在 \(x\) 轴上方，然后关于 \(x\) 轴对称地反射过去，得到的图形叫做 \(n\) 阶的 Aztec 钻石图，记作 \(\mathrm{AZ}(n)\)。下图显示的是 \(\mathrm{AZ}(10)\)：

用 1x2 的多米诺骨牌不重叠不遗漏地盖住这些方格，可以得到 Aztec 钻石图的一个多米诺骨牌铺砌。下图显示的是 \(\mathrm{AZ}(10)\) 的一种可能的铺砌：

可以看到图中出现了四种不同颜色的骨牌，为什么这样染色后面会解释。

我们的问题是：

问题 1：\(\mathrm{AZ}(n)\) 总共有多少种不同的多米诺骨牌铺砌？

这里不考虑铺砌的对称性，比如全部用水平的骨牌铺砌和全部用竖直的骨牌铺砌是两种不同的铺砌。

问题 2：如何在 \(\mathrm{AZ}(n)\) 的所有铺砌中等概率地随机任选一种？

第一个问题的答案是 \(2^{n(n+1)/2}\)，这个表达式很简洁，这暗示这个问题也应该有一个简洁的解答（确实如此）。

第二个问题的答案叫做多米诺洗牌算法，正是本文要介绍的。

Aztec 钻石图多米诺铺砌的计数问题最早由 Elkies、Kuperberg、Propp 和 Larson 在 1992 年的论文 Alternating sign matrices and domino tilings 中进行了深入的研究，在这篇文章中他们一共给出了 4 种不同的解答。时至今日人们发现的解法已经超过一打，不幸的是没有一种可以算是“简单的”，但其中最精彩的仍然要数 Elkies 等人论文中的第四个解法：多米诺洗牌算法。后来 Propp 在另一篇文章 Generalized domino-shuffling 中用图变换的方式重新表述了这个算法，并同时解决了在给定边的权重情况下对铺砌随机取样的问题。本文就来介绍 Propp 的结果。

本文的代码放在 Github 上。