I'm trying to understand the proof of the "magic theorem" about the Tutte matrix which states:
Let $T$ be the Tutte matrix of $G(V, E)$. Then, $$\det(T) = 0 \quad\Longleftrightarrow\quad G \text{ has no perfect matching}.$$
At that point, I know how to build the Tutte matrix but I'm stuck in the following points:
- how does the determinant of this matrix shows that my graph has a perfect matching
- the big point; understand how to compute the determinant which is $$ \det(T) = \sum_{\pi \in S_{n}} (-1)^{sgn(\pi)}\prod_{i = 1}^{n}t_{i, \pi(i)} $$
Actually I'm trying to understand this article Tutte matrix and Sufficiency of Perfect Matching but without much success, that's why I'm asking here.
Thanks for the help
The definition used on the website you link to isn't the greatest one. In fact, I think it's incorrect as stated. The Tutte matrix is skew-symmetric, but that doesn't follow from the definition given there. The image used there comes from Wikipedia page on the Tutte matrix, where it is stated explicitly that it is skew-symmetric, but then, using their notation, that implies that $x_{ij}=x_{ji}.$ It is better, in my opinion, to define the Tutte matrix as the skew-symmetric matrix $T$ were the $(i,j)$-entry of $T$ is the variable $t_{ij}$ if $i$ and $j$ are adjacent and 0 otherwise. Since $T$ is skew-symmetric, $t_{ij}=-t_{ji}$ for all relevant $i$ and $j$ (this way, you don't need to worry about whether or not $i<j$ or $j<i$ as in the other definition).
A perfect matching $M$ in the graph $G$ corresponds to a permutation $\pi$ with the property that each cycle in $\pi$ is a transposition. Specifically, if $\{i,j\}$ is an edge of $M$, then $(i\ j)$ is a cycle in the permutation, so $\pi(i)=j$ and $\pi(j)=i$ and the permutation $\pi$ is the composition of these cycles. The product in $\det T$ corresponding to $\pi$ has $n/2$ factors of the form $-t_{i,j}t_{j,i}$ (the negative sign follows from the fact that $t_{i,j}=-t_{j,i}$). So each matching contributes a nonzero product to $\det T.$
Now, suppose that $H$ is a spanning subgraph of $G$ and the connected components of $H$ are cycles and edges. Each cycle in $G$ can be oriented in one of two ways, either "clockwise" or "counterclockwise." For example, consider a cycle $C$ in $H$ with vertices $1,2,$ and $3.$ Then one orientation is $1,2,3$ and the other is $3,2,1.$
If we choose an orientation for each cycle of $H$, then we get a permutation $\pi$. Using the cycle $C$ as above, either $(1\ 2\ 3)$ or $(3\ 2\ 1)$ is a cycle in $\pi.$ Now consider two permutations $\phi$ and $\psi$ that are identical in all cycles except the one coming from $C$, where they have opposite orientations. Then, since $t_{1,2}t_{2,3}t_{3,1}=(-t_{3,2})(-t_{2,1})(-t_{1,3})=-t_{3,2}t_{2,1}t_{1,3},$ the products in $\det T$ corresponding to $\phi$ and $\psi$ will cancel each other out. Something similar will happen for any cycle in $G$.
This accounts for all possible products in $\det T$.
Thus, the only nonzero contribution to $\det T$ comes from the perfect matchings.
This isn't a full proof, but hopefully it gives you a better intuition about the relationship between matchings and $\det T.$
As for computing $\det T$, it's not practical in the general case. Consider a complete bipartite graph $K_{n,n}$, with both vertex parts the same size. If we assume that both vertex parts are labelled by the same set $S$, then a perfect matching corresponds to a permutation on $S$. There are $n!$ of these, so $\det T$ would have $n!$ terms. Except for small graphs, that is too large for practical purposes.
If you want an algorithm for finding matchings based on $\det T$, this paper might be of interest.