## Wednesday, March 10, 2010

### [TECH] Tutte matrix and Sufficiency of Perfect Matching.

I know that this is a standard results. But a hands on proof is really useful because it makes things more clear. I knew the fact that any permutation could be broken into disjoint cycles. However I did not know how the sign of the permutation changes if we swap the elements with in a disjoint cycle. It turns out that some of the fundamental properties of the signs of the permutation can be used to prove the sufficiency of a perfect matching in graph. A Tutte Matrix is defined as follows.

$A_{ij} = \begin{cases} x_{ij}\;\;\mbox{if}\;(i,j) \in E \mbox{ and } ij\\ 0\;\;\;\;\mbox{otherwise} \end{cases}$

Given a Tutte matrix we now prove the sufficiency of perfect matching

Determinant of Tutte matrix is as follows . We know that every permutation can be expressed as disjoint cycles. For example permutation can be expressed as two cycles . Also is the number of swaps we need do required to convert to the permutation . We observe the following important properties which help solve the problem.
• PROPERTY-1 If is a cycle in then if we replace with reverse cycle then remains the same - because we did not change the number of swaps required but just changed the order of swaps. For instance, let then cycle now we replace it with . This results in .
• PROPERTY-2 Let is a cycle of odd length in and let be the permutation by replacing with its reverse cycle . Then the corresponding terms in the determinant for and are and . For example in the previous example so the corresponding term in the determinant for is . On the other hand the reverse cycle has the following term in the determinant.
• PROPERTY-3 If all the cycles in the permutation are even and corresponding term in the determinant (i.e. ) is non-zero then its the set is a valid perfect match in the graph. This is because by the definition of Tutte matrix represents an edge in the graph and the permutation is giving a subset of edges since the product is non-zero, on the other than this sub-set of edges is a match.

### "IF has a perfect match THEN has at least one non-zero term"

Let be the perfect match in then we construct a permutation where , this permutation on the other hand has even cycles - because we created a cycle for every pair. Now we apply PROPERTY-3 and the term corresponding to in is non-zero.

### IF THEN has no perfect matching

Now consider the case when does not have no perfect matching. Then by PROPERTY-3 all the terms corresponding permutations with even cycles must be zero - otherwise our assumption leads to contradiction. Now consider the permutations with at least one odd cycle, let be that permutation and be the odd cycle. Now we replace with its reverse cycle and create the permutation . By PROPERTY-1 . Now we exploit the skew-symmetry of the Tutte matrix. By PROPERTY-2 the terms corresponding to , in the determinant are as follows. , . But by skew-symmetry , on the other hand since the cycle length is odd this gives that the actual terms corresponding to and are and . This means all the terms corresponding to permutations with at least one odd cycle can be grouped and pairs such as and be cancelled. So the only contribution for the comes from permutations will all even cycles - in this case we have none, so .