考虑$4\times 4$的矩阵

$$\left[\begin{matrix}
0 & a & b & c\\
-a & 0 & d & e\\
-b & -d & 0 & f\\
-c & -e & -f & 0\\
\end{matrix}\right]$$

可以暴算得到其行列式为

$$a^2f^2+b^2e^2+c^2d^2+2acdf-2abef-2bcde$$

其pf值为$af+be-cd$。暴算即可验证$N=4$的时候结论成立。

证明：我们要证的就是

$$\sum_{\alpha\in PM(n)}\sum_{\beta\in PM(n)}\text{sgn}(\alpha)\text{sgn}(\beta)\prod_{(i,j)\in\alpha}A_{i,j}\prod_{(i,j)\in\beta}A_{i,j}=\sum_{\gamma\in S(n)}\text{sgn}(\gamma)\prod_iA_{i,\gamma_i}$$

然后我们考虑一个$\gamma$，如果它有长度为奇数的循环，那么

• 这个循环长度为$1$，则$\exists i,\gamma_i=i$，而$A_{i,i}=0$。故它对右边不产生贡献。
• 否则找出长度为奇数的、包含的最小数最小的那个循环并把它倒过来(求逆元)，记这样的变换为$rev$。即：设$\gamma=\sigma_1\sigma_2\dots\sigma_q$，其中$\sigma_i$是循环，且$\sigma_i$中最小数小于$\sigma_{i+1}$中最小数。记最小的$i$满足$|\sigma_i|\equiv 1\pmod 2$，则$rev(\gamma)=\prod_{j\ne i}\sigma_j\times (\sigma_i)^{-1}$。
  然而$rev(rev(\gamma))=\gamma$，$\text{sgn}(\gamma)=\text{sgn}(rev(\gamma))$，且$\prod_iA_{i,\gamma_i}=-\prod_iA_{i,rev(\gamma)_i}$。

所以有奇数个循环的$\gamma$的总贡献是$0$，因为有长度为$1$的循环节的$\gamma$贡献是$0$，否则$\gamma$的贡献与$rev(\gamma)$的贡献抵消。

剩下的$\gamma$就是所有循环节长度都是偶数的排列(这些$\gamma$的集合记为$S_e(n)$)。事实上这种排列的数目就是$|PM(n)|^2$。我们可以构造出$S_e(n)\to PM(n)\times PM(n)$的一个一一映射。

首先，一个$\gamma\in S_e(n)$可以画成若干个环，每个环都是有向的。比如说$\gamma=(1\ 3\ 2\ 6)(4\ 9)(5\ 10\ 7\ 8)$，如下左图。

然后，对于轮换$(a_1 a_2 \dots a_k)(k>2)$，在$\alpha$中拆成$(a_1,a_2),(a_3,a_4),\dots$等匹配，在$\beta$中拆成$(a_2,a_3),(a_4,a_5),\dots$等匹配。这里要求$a_1$是轮换中最小的数，这样$\alpha$和$\beta$是唯一的。

对于长度为$2$的轮换$(a b)$，$\alpha$和$\beta$中都有$a,b$配对。

上面那个图中间是$\alpha$，右边是$\beta$。

这是一个一一对应。因为它的逆映射就是把两个匹配拼在一起，形成若干个环，给环定方向的时候按照“环中最小的点连向其在$\alpha$中的匹配点”来定。记这个一一对应为$\varphi$。

我们证明引理1：$\varphi(\gamma)=(\alpha,\beta)$，那么$\text{sgn}(\gamma)\prod_{i=1}^n(-1)^{[\gamma_i<i]}=\text{sgn}(\alpha)\text{sgn}(\beta)$。

因为$(3\ 4\ 1\ 2)$是偶置换，所以置换$a$的奇偶性只与有序二元组的无序集合$\{(a_1,a_2),(a_3,a_4),\dots,(a_{n-1},a_n)\}$有关。那么我们不用在意$\alpha_{2i-1}<\alpha_{2i+1}$这样的奇奇怪怪的限制了。

在计算$\varphi$映射的时候，我们先找出$\gamma$的所有环(轮换)，对每一个环将边交替地放入$\alpha,\beta$。对于一条边$(i,\gamma_i)$，如果$\gamma_i<i$，那么$\alpha$或$\beta$中的顺序是$\gamma_i,i$；否则是$i,\gamma_i$。然后对每个$\gamma_i<i$的$i$交换$i$和$\gamma_i$在对应的$\alpha$或$\beta$中的位置。这样$\text{sgn}(\alpha)\text{sgn}(\beta)$改变了$\prod_{i=1}^n(-1)^{[\gamma_i<i]}$，且$\alpha$或$\beta$中每一个二元组都是形如$i,\gamma_i$的形式。这样可以认为$\gamma$中的一个轮换是$(i_1\ i_2\ i_3\dots i_k)$，此时$\alpha$中对应的位置是：
$$i_1\ i_2\ \dots\ i_k$$
而$\beta$中对应的位置是：
$$i_2\ i_3\ \dots\ i_1$$
所以这几块对$\text{sgn}(\alpha)\text{sgn}(\beta)$的贡献是把$i_1\ i_2\ \dots\ i_k$变成$i_2\ i_3\ \dots\ i_1$需要的对换数，即为$k-1$。而$k-1$是奇数。

所以$\text{sgn}(\alpha)\text{sgn}(\beta)\prod_{i=1}^n(-1)^{[\gamma_i<i]}$是$(-1)$的$\gamma$的轮换的个数次方。而$\gamma$的轮换长度都是偶数的，所以上述式子就是$\text{sgn}(\gamma)$。

引理1得证。由引理1可以得到每个$\gamma$对行列式的贡献等于$\varphi(\gamma)$对$\text{pf}^2$的贡献。本定理得证。

考虑如下算法：

• 找出$G$的一个生成树$T_1$
• 给$T_1$的边随意定向
• 考虑不在$T_1$中的所有边，它们在对偶图中对应的边构成了对偶图一棵生成树$T_2$
• 从$T_2$的叶子开始可以递推出不在$T_1$的所有边的方向。递推的规则是：每个面都有奇数条边是顺时针的。
• (如下图，红色粗线是$T_1$，蓝色是$T_2$，红色细线是后来递推出的方向)
• (图来自[1])

它显然是个多项式算法。

为了证明这个定向是pfaffian的，我们需要这两个引理：

1. 如果每一个nice cycle都是oddly oriented，那么这个定向是pfaffian的；
   点击展开证明
   证明：
   先分析分析。$s=1$的pfaffian orientation等价于对每一个完备匹配$M\in PM(n)$，$M$的逆序对数与如下数字同奇偶：$M$中的每一对$a,b(a<b)$，如果这条边在定向中是$b\to a$，那么加$1$。$s=-1$等价于这两个数不同奇偶。
   换句话说，一个定向是$s=1$的pfaffian orientation，当且仅当对于所有完备匹配$M$，把$M$中的二元组$a,b$按照定向的顺序写下来(如果图中的边是$a\to b$，那么顺序是$a,b$，否则是$b,a$)，得到一个排列，其逆序对数都是偶数。$s=-1$的情况即逆序对数是奇数。
   我们考虑这样得到的任意两个排列$\alpha,\beta$，满足$\forall i,(\alpha_{2i-1}\to \alpha_{2i})\in E,(\beta_{2i-1}\to \beta_{2i})\in E$。只要证明了$\text{sgn}(\alpha)\text{sgn}(\beta)=1$，就可以证明原命题。
   我们知道两个匹配拼在一起就是一些长度为偶数的圈。考虑其中一个圈$C$，顶点为$v_1,v_2,\dots,v_{2k}$。首先，$C$是一个nice cycle，因为考虑匹配$\alpha$，删除$C$上的点和边之后显然没问题，$C$内的点不会与$C$外的点匹配(连这样的边都没有)，所以删掉$C$和$C$内的东西之后剩下的图还是有完备匹配。
   由题设，$C$是nice cycle，那么它是oddly oriented的。
   然后假设在$\alpha$和$\beta$中$v_1,v_2,\dots,v_{2k}$都是排在一起的，即$\alpha$中有一个片段形如$v_1,v_2,v_3,\dots,v_{2k}$($v_{2i-1}$与$v_{2i}$的顺序可以调动)，同理$\beta$中有一个形如$v_2,v_3,\dots,v_{2k},v_1$的片段。考虑$C$中每条边$(v_i,v_{i+1})$，它一定出现在$\alpha$中或$\beta$中。如果它是$v_i\to v_{i+1}$则不用管；否则我们在对应的排列中(比如，$i$是奇数就是$\alpha$；$i$是偶数就是$\beta$)交换两个元素的位置。现在$\alpha$中有片段$v_1,v_2,\dots,v_{2k}$(顺序就是这样的)，$\beta$中有片段$v_2,v_3,\dots,v_1$，且我们一共用了奇数次(因为$C$是oddly oriented的)交换。再通过奇数次交换可以把$v_1,v_2,\dots,v_{2k}$变成$v_2,v_3,\dots,v_1$。所以，一个环对$\alpha\times\beta$的逆序对数的贡献是偶数。
   这样就证明了，任意的$\alpha$和$\beta$拥有相同的奇偶性。换句话说，这个定向是pfaffian的。
2. 如果一个定向的每个面都是奇数条顺时针的边，那么每个nice circle都是oddly oriented。
   点击展开证明
   证明：
   考虑一个长度为偶数的圈$C$，$C$内部有$e$条边，$f$个面，$v$个点，根据欧拉公式有$e=v+f-1$。令$d(face,edge)$表示$edge$这条边在面$face$中的定向，顺时针为$1$，逆时针为$0$；对于在$C$最外圈的边$edge$，令$d(edge)$表示$d(\text{最外圈},edge)$。
   那么在模$2$意义下我们有$f=\sum_{face\text{是一个面}}\sum_{edge\in face}d(face,edge)=\sum_{edge\in C\text{的外面一圈}}d(edge)+e$。
   这个公式是因为：考虑$edge$，如果它在外面一圈上，那么它的贡献是$d(edge)$；否则它的贡献就是$1$(它被算了两个面，一个面是顺时针，一个面是逆时针)。$f$的组成部分有($e$减去圈$C$的长度)个$1$，因为$C$是偶圈所以模$2$意义下就是$e$个$1$；还有$\sum_{edge\in C\text{的外面一圈}}d(edge)$(记这个量为$S$好了)。即$f=e+S$。
   再考虑欧拉公式就有$v+S-1=0$。然而$v$是偶数(因为$C$是nice cycle，去掉它之后图有完备匹配，点数显然是偶数)，所以$S$就是奇数咯，那么$C$就是oddly oriented的啦。

Q.E.D

哦对了，这是我第一次用jQuery写博客，那几个按钮啥的都是jQuery的简单应用

其实一开始要我学jQuery的时候，我是拒绝的。。但是这玩意太tm漂亮了

不过不会jQuery的话写网页就会混不下去?我猜的

你能看到这里才是真的神犇

组织又要出新歌了。。好像完全换了个风格。。(吸毒神曲

我就知道这种名字是写不出歌的(坐等打脸)

果真曲子改名了。。

从30s预览中可以听出，应该是吃货歌

以及根本听不出歌词是什么鬼嘛，只听出了Burry,Cherry(坐等打脸)