Lesson 7

Lemma. If \(\det(T) \neq 0\), then \(G\) has a perfect matching.

Proof. We first show that all terms of \(\det(T)\) corresponding to permutations with at least one odd cycle cancel out.

Let \(P\) be the set of permutations in \(S_{n}\) that contain at least one odd cycle. For each \(\sigma \in P\), let \(C_{\sigma}\) denote the odd cycle in \(\sigma\) containing \(1\), and let \(\sigma'\) be the permutation obtained by reversing \(C_{\sigma}\) in \(\sigma\). Observe that this construction yields a perfect pairing of permutations in \(P\).

We now show that the term in the determinant corresponding to \(\sigma\) cancels with the term corresponding to \(\sigma'\). Since \(\sigma\) and \(\sigma'\) have the same number of even cycles, it follows that \(\text{sign}(\sigma) = \text{sign}(\sigma')\). Consider the sum of the corresponding determinant terms: \[\prod_{i=1}^{n} T_{i, \sigma(i)}+ \prod_{i=1}^{n} T_{i, \sigma'(i)}.\] Since \(\sigma\) and \(\sigma'\) differ only on \(C_{\sigma}\), this sum becomes \[\left( \prod_{i \notin C_\sigma}T_{i, \sigma(i)}\right) \cdot \left( \prod_{i \in C_\sigma}T_{i, \sigma(i)}+ \prod_{i \in C_\sigma}T_{i, \sigma'(i)}\right). \tag{$*$}\] Suppose \(C_{\sigma} = (i_{1}\ i_{2}\ …\ i_{k})\) for some odd \(k\). Then \[\prod_{i \in C_\sigma}T_{i, \sigma(i)}= \prod_{j=1}^{k} T_{i_j, i_{j+1}}, \quad \text{with }i_{k+1}= i_{1}.\] Since \(\sigma'\) reverses \(C_{\sigma}\), we have \[\prod_{i \in C_\sigma}T_{i, \sigma'(i)}= \prod_{j=1}^{k} T_{i_j, i_{j-1}}= (-1)^{k} \prod_{j=1}^{k} T_{i_j, i_{j+1}},\] because \(T\) is skew-symmetric.

Therefore, the expression (\(*\)) evaluates to the zero polynomial, since \(k\) is odd. This shows that all terms in \(\det(T)\) corresponding to permutations with at least one odd cycle cancel out.

We are now left with permutations consisting only of even cycles. Since \(\det(T) \neq 0\), there exists at least one such permutation \(\sigma\) whose corresponding term does not vanish.

Consider any even cycle \(C = (i_{1}, …, i_{2k})\) in \(\sigma\). The associated term in \(\det(T)\) includes the monomial \(x_{i_1,i_2}\cdot x_{i_2,i_3}\cdots x_{i_{2k},i_1}\). The non-vanishing of this term implies that the edges \((i_{1},i_{2}), (i_{2},i_{3}), …, (i_{2k},i_{1})\) are all present in \(G\).

Selecting every other edge, namely \((i_{1},i_{2}), (i_{3},i_{4}), …, (i_{2k-1}, i_{2k})\), produces a matching. Repeating this process for each even cycle in \(\sigma\) yields a perfect matching in \(G\).◼