Tutte matrix - Determinant 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
 A: 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.
