Tutte矩阵

行列式里的排列先变成圈覆盖 ​

Leibniz展开的一项由一个排列σ选择每行的一个列位置。若该项非零，则所有选出的边都在G中，且对角为零排除了固定点；排列分解成长度至少2的有向圈，覆盖全部顶点。

若圈覆盖含奇圈，选择包含最小编号顶点的那个奇圈并反向，其它圈不变。选择规则反向前后相同，因此是一个无固定点的配对；奇圈长度至少3，反向确实得到不同排列。排列符号不变，但T的边方向每反转一次贡献一个负号，奇数次使乘积变号，两项相消。在特征2中，相同两项相加也为零。

消去后只剩全部由偶圈组成的覆盖。每个偶圈交替取边，就能拆成两个完美匹配；二圈的两个匹配取同一条边。因此，若G根本没有完美匹配，所有幸存项也都不存在，行列式恒等于零。[1, §1.1]

一个匹配贡献的平方单项式不会消失 ​

反过来，给定完美匹配M，选择把每条匹配边的两个端点互换的排列。它的项是

每个换位的排列符号−1，与 $T_{ij}{T}_{ji}=-x_e^2$ 的负号抵消，故总系数为+1。要产生完全相同的平方单项式，必须在每条M边上使用两个方向，不能换成其它圈覆盖，所以没有第二项消掉它。系数1在任何域中都非零，这也解释了为什么此处可以选任意素数域，而无须担心所有系数一起模p消失。

一次数值消元替代形式展开 ​

每个非零项有n个一次因子，所以非零det T的总次数恰为n。对事先固定的图，每个边变量独立均匀取自S，由多项式恒等式测试理路多项式恒等式测试Polynomial identity testing · PIT对形式多项式电路逐门随机求值，以次数预算给出单边漏检界，保留非零见证并处理小域与位成本。，有完美匹配时单次行列式碰巧为零的概率至多min(1,n/|S|)。无完美匹配时所有代入都为零。

实际计算使用精确行化简理路行化简Row reduction用初等行变换把矩阵化为阶梯形以求解线性方程组和判定秩。：每列找一个非零主元，必要时交换行并翻转符号；用主元消去下方元素，最后把主元相乘。无可选主元则行列式为零。使用O(n³)次域操作、O(n²)个域元素空间；每轮另有m个随机边值。若域元素有b位，乘除的位成本须另乘相应算术代价，不能把浮点LU的误差阈值搬进这个精确零测试。

四个顶点的三种配对 ​

完全图K₄的边按01、02、03、12、13、23排序，变量分别记a、b、c、d、e、f。直接展开可核得

其中af、be、cd对应三种完美匹配。这个小例子的平方表达式方便手算；一般图的正确性已经由圈覆盖证明，不依赖预先学习另一种矩阵不变量。

若只保留01、02、13、23四边，并把四个变量全设为1，便有af−be=0，行列式为零，但图有两个完美匹配。反之，只在某个真实完美匹配的边上代1、其余边代0，矩阵由二阶块组成，行列式为1。这证明存在好点，却不意味着算法事先知道该选哪些边。

唯一最低权留下唯一最低二进制幂 ​

现在给每边一个正整数wₑ，把变量代成 $2^{w_e}$，得到整数矩阵B。设唯一最小权完美匹配为M，总权W。由隔离引理理路隔离引理Isolation lemma · Isolating lemma · MVV isolation lemma给固定集合族的元素独立赋小整数权，以元素阈值和并集界保证唯一最小解，并区分隔离存在性与求解能力。，若每边独立均匀取wₑ∈{1,…,2m}且图有匹配，出现这种唯一性的概率至少1/2。

奇圈配对在整数代入后仍然消去。任一剩余偶圈覆盖可拆成两个完美匹配M₁、M₂，该项的二进制指数为w(M₁)+w(M₂)≥2W。达到2W时，两者只能都等于唯一的M；对应的二圈覆盖只有一个，系数为+1。其它项指数至少2W+1，因此

这里ν₂(z)是非零整数z能被2整除的最大次数，ν₂(0)=∞。一般图指数为2W；不能直接套二分图较小邻接矩阵的W公式。

删除两个端点，逐边识别匹配 ​

对每条e={i,j}，令Dₑ为从B同时删去第i、j行和第i、j列所得主子式的行列式。若e∈M，残图的唯一最小匹配为M去掉e，总权W−wₑ，于是ν₂(Dₑ)=2(W−wₑ)。

若e∉M，残图的任一完美匹配N加上e都成为原图的另一完美匹配，故w(N)+wₑ>W。残图中所有幸存圈覆盖的指数都严格大于2(W−wₑ)；相加只会使二进阶继续增大或变成∞，不能降低。因此

这给出直接可执行的筛边规则。它采用删两个端点的主子式，便于独立重算；不是把论文中伴随矩阵单个代数余子式的公式原样复制过来。

完整手算与未隔离时的反例 ​

给K₄六边权依次为(1,3,5,6,4,2)。三个匹配权为3、7、11，唯一最小匹配为{01,23}。整数矩阵为

有 $\det B=(8-128+2048{)}^2=3717184=2^6\cdot 58081$。删01两端点，D₀₁=16，二进阶4加2w₀₁=2恰为6；删23两端点，D₂₃=4，二进阶2加4也为6。其余四边的和分别为14、22、22、14，都不入选。

若六边权都为1，det B=16且每个Dₑ=4，六条边都会满足二进阶等式。它们显然不是匹配，说明未隔离时不能只信筛边条件。程序必须检查候选边真实存在、没有共用端点、恰好覆盖n个顶点；只有通过检查才返回MATCHING，否则返回RETRY。

有限重试给出可验真的搜索接口 ​

先固定并排序原图的边表，权向量按这个表对齐。每轮独立重抽全部权，构造B，计算det B及m个主子式，筛边后检查。若图有完美匹配，隔离成功足以保证这一轮恢复它；t轮仍未返回的概率至多2⁻ᵗ。若图没有完美匹配，验证器永远不会接受错误边集。

预算耗尽输出UNKNOWN，不输出确定的NO。奇数顶点数、非空却完全无边等结构情况可以直接证明NO；它们与随机失败不同。无限重试在YES实例上期望轮数至多2，在NO实例上可能永不结束，因此不能把它称为对所有输入都终止的Las Vegas判定算法。

大整数是算法成本的一部分 ​

本实现逐个求主子式，不追求快速矩阵逆。每轮至多m+1次O(n³)精确有理消元，共O((m+1)n³)次有理算术操作；主子式顺序处理，工作矩阵空间O(n²)个有理数，另有O(m)条输出记录。

wₑ≤R时矩阵项占R+1位。任一r阶子式的绝对值至多 $r!2^{rR}$，令 $L=O(n(R+\log (n+1)))$。行主元消元的活动元素是已选主元块的加边子式与主元子式之比：对分块矩阵先消去左上可逆块，右下一个元素就是相应加边行列式除以该块行列式。每次选主元后同样适用，行交换只改变所取行的次序。故约分后的分子、分母都有O(L)位，消元倍数和单次乘减的临时结果也只多常数倍位长。

参考代码使用精确Fraction并及时约分。若用朴素长乘除和欧几里得约分，O(L³)可作为一次有理操作的保守位成本上界，于是O((m+1)n³L³)是这里足够说明多项式性的宽松界；不是快速整数算法的最佳界。工作数据占O(n²L+mL)位量级。取R=2m时L仍是n、m的多项式；若把巨大二进制原成本直接放进指数，这个性质可能丢失。

交付可复算的代数证书 ​

代数随机化证书终点要求同时保留有限域代入的存在性证据、整数权表、主行列式、逐边主子式以及最终匹配。有限域证据可独立用模运算重算，最终边集只需线性扫描端点即可验真；后者不要求审核者相信随机种子或隔离事件。

如果目标只是最快地找到匹配，应比较已有增广路算法与输入结构。此处的价值是完整展示“形式非零判定→随机隔离→数值提取→确定证书验证”的连接，不能用较短的代数描述代替实际位成本。