【ICPC 2024 Regional 昆明热身赛 D】LCA Determinant 题解

math
algorithm
combinatorics
original problem
solution
Author

sun123zxy

Published

November 30, 2024

热身赛 D 供题人.原题出自 2023 年 BIT 校赛 H,非常荣幸被组题人收入热身赛供大家把玩.看到很多人对题目背后的动机感兴趣,也把题解放到这里,趁机聊聊此类行列式背后的技巧和理论.

Example 1 You are given a tree consisting of \(n\) vertices. Vertices are numbered from \(1\) to \(n\). The vertex \(1\) is the root of the tree. Each vertex has a weight \(a_i\). Consider a matrix \[ A := \begin{pmatrix} a_{\operatorname{lca}(i,j)} \end{pmatrix}_{n \times n} = \begin{pmatrix} a_{\operatorname{lca}(1,1)} & a_{\operatorname{lca}(1,2)} & \dots & a_{\operatorname{lca}(1,n)} \\ a_{\operatorname{lca}(2,1)} & a_{\operatorname{lca}(2,2)} & \dots & a_{\operatorname{lca}(2,n)} \\ \vdots & \vdots & \ddots & \vdots \\ a_{\operatorname{lca}(n,1)} & a_{\operatorname{lca}(n,2)} & \dots & a_{\operatorname{lca}(n,n)} \end{pmatrix} \] where \(\operatorname{lca}(i,j)\) denotes the lowest common ancestor of vertex \(i\) and vertex \(j\). Calculate the determinant of matrix \(A\).

Solution

本题定位智慧 / 猜结论 / 线代高手 / 出进正赛会被骂题,结论为 \[ \det A = a_1 \prod_{\substack{u \in V \\ u \neq 1}} (a_u - a_{\operatorname{fa}(u)}) \] 其中 \(V\) 是全体树上节点构成的集合,\(\operatorname{fa}(u)\) 代表节点 \(u\) 在树上的父亲节点.

赛时技巧而言,样例已给出树为单链之一例,选手应考虑补充举例菊花图的情况,并分别应用行列式消法变换证明两种特殊情况的正确性.分析两种消去方法的共性便可得到结论的雏形.

一般地,考虑对节点按深度从小到大进行重标号,由于重标号对行和列进行的置换相同,行列式的值和正负性均不会发生变化.现在归纳地证明结论.当 \(n=1\) 时,结论平凡.当 \(n \geq 2\),假设结论对全体大小为 \(n-1\) 的树成立.现给定一颗大小为 \(n\) 的按上述方法重标号后的树,设其对应行列式为 \(A_n\).由重标号方法,编号为 \(n\) 的节点一定为叶子节点;且由 \(n \geq 2\),其父节点存在.在行列式中做消法变换:

  • 将第 \(n\) 列减去第 \(\operatorname{fa}(u)\) 列;
  • 将第 \(n\) 行减去第 \(\operatorname{fa}(u)\) 行.

行列式变为 \[ \begin{aligned} &\phantom{\to} \begin{pmatrix} a_{\operatorname{lca}(1,1)} & a_{\operatorname{lca}(1,2)} & \dots & a_{\operatorname{lca}(1,n)} \\ a_{\operatorname{lca}(2,1)} & a_{\operatorname{lca}(2,2)} & \dots & a_{\operatorname{lca}(2,n)} \\ \vdots & \vdots & \ddots & \vdots \\ a_{\operatorname{lca}(n,1)} & a_{\operatorname{lca}(n,2)} & \dots & a_{\operatorname{lca}(n,n)} \end{pmatrix} \\ &\to \begin{pmatrix} a_{\operatorname{lca}(1,1)} & a_{\operatorname{lca}(1,2)} & \dots & a_{\operatorname{lca}(1,n)} - a_{\operatorname{lca}(1,\operatorname{fa}(n))} \\ a_{\operatorname{lca}(2,1)} & a_{\operatorname{lca}(2,2)} & \dots & a_{\operatorname{lca}(2,n)} - a_{\operatorname{lca}(2,\operatorname{fa}(n))} \\ \vdots & \vdots & \ddots & \vdots \\ a_{\operatorname{lca}(n,1)} & a_{\operatorname{lca}(n,2)} & \dots & a_{\operatorname{lca}(n,n)} - a_{\operatorname{lca}(n,\operatorname{fa}(n))} \end{pmatrix} \\ &= \begin{pmatrix} a_{\operatorname{lca}(1,1)} & a_{\operatorname{lca}(1,2)} & \dots & 0 \\ a_{\operatorname{lca}(2,1)} & a_{\operatorname{lca}(2,2)} & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ a_{\operatorname{lca}(n,1)} & a_{\operatorname{lca}(n,2)} & \dots & a_n - a_{\operatorname{fa}(n)} \end{pmatrix} \\\\ &\to \begin{pmatrix} a_{\operatorname{lca}(1,1)} & a_{\operatorname{lca}(1,2)} & \dots & 0 \\ a_{\operatorname{lca}(2,1)} & a_{\operatorname{lca}(2,2)} & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ a_{\operatorname{lca}(n,1)} - a_{\operatorname{lca}(\operatorname{fa}(n),1)} & a_{\operatorname{lca}(n,2)} - a_{\operatorname{lca}(\operatorname{fa}(n),2)} & \dots & a_n - a_{\operatorname{fa}(n)} \end{pmatrix}\\ &= \begin{pmatrix} a_{\operatorname{lca}(1,1)} & a_{\operatorname{lca}(1,2)} & \dots & 0 \\ a_{\operatorname{lca}(2,1)} & a_{\operatorname{lca}(2,2)} & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & a_n - a_{\operatorname{fa}(n)} \end{pmatrix} \\ &\to (a_n - a_{\operatorname{fa}(n)}) \det A_{n-1} \\ &= a_1 \prod_{\substack{u \in V \\ u \neq 1}} (a_u - a_{\operatorname{fa}(u)}) \end{aligned} \] 故结论对任意 \(n \in \mathbb N_+\) 均成立.

Remark

Idea 来自去年和队友 vp UCup 做到的 Universal Cup 2023 Stage 7 Zaporizhzhia Problem K. Determinant, or…?(甚至更难一点?).官方题解给到的证明是递归构造分块矩阵,神似 FMT 的实现代码和与本题类似的变换技巧似乎暗示着更一般的结论.回顾证明,我们对行和列进行对称的消法变换,最终将矩阵化为对角矩阵,从而计算出行列式的值.按照线性代数的观点,若将这些变换用矩阵 \(P^{-1}\) 记录,上述过程事实上完成了对称矩阵 \(A\) 的合同对角化,即 \(A = P \Lambda P^\mathrm{T}\)\(P^{-1} A (P^{-1})^\mathrm{T} = \Lambda\).我们指出,用于合同对角化的矩阵 \(P\) 完全由树上偏序关系决定,且 \(\det P = 1\).一般地,类似结论对任意下确界存在的偏序集成立——这是偏序集上广义 Zeta / Möbius 变换框架下的强大结果.感兴趣的同学可参考 [1](没错,就是写 generatingfunctionology 的那个 Wilf :p).不过也许你懒得去找这篇论文,所以我们把和本题相关的关键几式转录于此并做一些批注:

  • \[ P := \begin{pmatrix} p_{i,j} \end{pmatrix}_{n \times n} \text{ where } p_{i,j} := \begin{cases} 1 & j \leq i \\ 0 & \text{otherwise} \end{cases} \] 这里 \(P\) 被称为偏序集上的 Zeta 变换,而对应的 \(P^{-1}\) 被称为 Möbius 变换.对本题而言, \[ p_{i,j} = \begin{cases} 1 & j \text{ is an ancestor of } i \\ 0 & \text{otherwise} \end{cases} \] 而其逆矩阵 \[ \left( P^{-1} \right)_{i,j} = \begin{cases} 1 & j = i \\ -1 & j = \operatorname{fa}(i) \\ 0 & \text{otherwise} \end{cases} \] 恰记录了对行列式所作的消法变换.

  • \[ a_{i \land j} = A_{i,j} = (P \Lambda P^\mathrm{T})_{i,j} = \sum_{k} p_{i,k} \lambda_k p_{j,k} = \sum_{\substack{k \leq i \\ k \leq j}} \lambda_k = \sum_{\substack{k \leq i \land j}} \lambda_k = \sum_{k} p_{i \land j, k} \lambda_k = (P \vec \lambda)_{i \land j} \] 描述了对角化前后两个数列的变换关系.可见已知 \(\vec \lambda\),求 \(\vec a = P \vec \lambda\) 的过程便是偏序集上的 Zeta 变换.已知 \(\vec a\),反求 \(\vec \lambda = P^{-1} \vec a\) 的过程便是偏序集上的 Möbius 反演.对本题而言,Zeta 变换 \(P\) 是树上前缀和,而反演 \(P^{-1}\) 是树上差分.

  • \[ \det A = \det P \det \Lambda \det P^\mathrm{T} = \det \Lambda = \prod_{k} \lambda_k \] 只需注意到 \(\det P = 1\)——按拓扑序重标号后的 \(P\) 是对角线全一的下三角矩阵.

至此,行列式变换技巧背后的系统理论得以建立,配合反演理论如法炮制便可造出一众钓鱼行列式:

  • LCA Determinant / 树上前缀和 / 树上差分:

    \[ \det (a_{\operatorname{lca}(i,j)})_{n \times n} = a_1 \prod_{\substack{2 \leq u \leq n}} (a_u - a_{\operatorname{fa}(u)}) \]

  • MIN Determinant / 前缀和 / 差分:

    \[ \det \begin{pmatrix} a_{\min(i,j)} \end{pmatrix}_{n \times n} = a_1 \prod_{2 \leq k \leq n} (a_k - a_{k-1}) \]

  • AND Determinant / 高维前缀和 / 容斥原理:

    \[ \det \begin{pmatrix} a_{i \& j} \end{pmatrix}_{2^n \times 2^n} = \prod_{0 \leq k < 2^n} \sum_{t \subseteq k} (-1)^{\operatorname{popcount}(k)-\operatorname{popcount}(t)} a_t \] 借助 FMT 可做到 \(O(n 2^n)\)

  • GCD Determinant / Zeta 变换 / Möbius 反演: \[ \det \begin{pmatrix} a_{\gcd(i,j)} \end{pmatrix}_{n \times n} = \prod_{1 \leq k \leq n} \sum_{d \mid k} \mu(\frac k d) a_d \] 借助类似埃筛的方法可以做到 \(O(n \log n)\)

对于一般的偏序,Zeta / Möbius 变换有没有快速计算方法呢?这篇论文 [2] 给出了 \(O(nk)\) 时间复杂度下的算法,这里 \(k\) 是偏序集的宽度.

偏序并不是此类行列式求解问题的终点.上述论证成立的核心在于 \(p_{i,k} p_{j,k} = p_{i \land j,k}\),而 \(\land\) 可以是任何一种二元运算.稍加改动,循环矩阵的行列式求值也被我们纳入囊中:

  • Cyclic Determinant / 离散 Fourier 变换 / 离散 Fourier 逆变换: \[ \det \begin{pmatrix} a_{(i+j) \bmod n} \end{pmatrix}_{0 \leq i,j < n} = \prod_{0 \leq k < n} \frac 1 n \sum_{0 \leq t < n} \omega_n^{-kt} a_t \] 借助 FFT 可以做到 \(O(n \log n)\)

快把这些问题和你的小伙伴分享,一起成为线代高手吧!

References

[1]
H. S. Wilf, “Hadamard determinants möbius functions, and the chromatic number of a graph,” Bulletin of the American Mathematical Society, vol. 74, no. 5, pp. 960–964, 1968.
[2]
T. Pegolotti, B. Seifert, and M. Püschel, “Fast m\"obius and zeta transforms.” arXiv, Nov. 24, 2022. doi: 10.48550/arXiv.2211.13706.