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 } i<j\\ -x_{ji}\;\;\mbox{if}\;(i,j) \in E \mbox{ and } i>j\\ 0\;\;\;\;\mbox{otherwise} \end{cases}

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

Determinant of Tutte matrix is as follows $ det(T) = \Sigma_{\pi \in S_n} (-1)^{sgn(\pi)}\Pi_{i=1}^{n} t_{i,\pi(i)}$. We know that every permutation can be expressed as disjoint cycles. For example permutation $ \{5, 1, 4, 3, 2\}$ can be expressed as two cycles $ \{(1\rightarrow 5 \rightarrow 2 \rightarrow 1) , (3 \rightarrow 4 \rightarrow 3) \}$. Also $ sgn(\pi)$ is the number of swaps we need do required to convert $ \{1, 2, \ldots n\}$ to the permutation $ \pi$. We observe the following important properties which help solve the problem.
  • PROPERTY-1 If $ c_i = (t_1\rightarrow t_2 \rightarrow t_3 \ldots t_n\rightarrow t_1)$ is a cycle in $ \pi$ then if we replace $ c_i$ with reverse cycle $ c'_i = (t_n\rightarrow t_1\rightarrow t_2 \rightarrow \ldots t_n)$ then $ sgn(\pi)$ remains the same - because we did not change the number of swaps required but just changed the order of swaps. For instance, let $ \pi=\{5, 1, 4, 3, 2\}$ then cycle $ c_1 = \{(1\rightarrow 5 \rightarrow 2 \rightarrow 1)\}$ now we replace it with $ c'_1 =\{2\rightarrow 5 \rightarrow 1 \rightarrow 2\}$. This results in $ \pi'=\{2, 5, 4, 3, 1\}$.
  • PROPERTY-2 Let $ c_i$ is a cycle of odd length in $ \pi$ and let $ \pi'$ be the permutation by replacing $ c_i$ with its reverse cycle $ c'_i$. Then the corresponding terms in the determinant for $ c_i$ and $ c'_i$ are $ \Pi_{\pi(i)\in c_i} t_{i,\pi(i)}$ and $ \Pi_{\pi(i)\in c_i} t_{\pi(i),i}$. For example in the previous example $ c_1 = \{(1\rightarrow 5 \rightarrow 2 \rightarrow 1)\}$ so the corresponding term in the determinant for $ c_1$ is $ t_{1,5}t_{5,2}t_{2,1}$. On the other hand the reverse cycle $ c'_1 \{2 \rightarrow 5 \rightarrow 1 \rightarrow 2\}$ has the following term $ t_{2,5}t_{5,1}t_{1,2}$in the determinant.
  • PROPERTY-3 If all the cycles in the permutation $ \pi$ are even and corresponding term in the determinant (i.e. $ \Pi_{i=1}^{n} t_{i,\pi(i)}$) is non-zero then its the set $ \{(1,\pi(1)), (2,\pi(2))\ldots (n,\pi(n))\}$ is a valid perfect match in the graph. This is because by the definition of Tutte matrix $ t_{u,v}$ represents an edge in the graph and the permutation $ \pi$ is giving a subset of $ n$ edges since the product is non-zero, on the other than this sub-set of edges is a match.

"IF $ G$ has a perfect match THEN $ det(T)$ has at least one non-zero term"

Let $ M$ be the perfect match in $ G$ then we construct a permutation $ \pi(u)=v, \pi(v)=u$ where $ (u,v)\in M$, 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 $ \pi$ in $ det(T)$ is non-zero.

IF $ det(T)=0$ THEN $ G$ has no perfect matching

Now consider the case when $ G$ 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 $ \pi$ be that permutation and $ c_i$ be the odd cycle. Now we replace $ c_i$ with its reverse cycle $ c'_i$ and create the permutation $ \pi'$. By PROPERTY-1 $ sgn(\pi) = sgn(\pi')$. Now we exploit the skew-symmetry of the Tutte matrix. By PROPERTY-2 the terms corresponding to $ \pi$, $ \pi'$ in the determinant are as follows. $ \Pi_{\pi(k)\in c_i} t_{k,\pi(k)}$, $ \Pi_{\pi(k)\in c_i} t_{\pi(k),k}$. But by skew-symmetry $ t_{\pi(k),k} = - t_{k,\pi(k)}$, on the other hand since the cycle length is odd this gives that the actual terms corresponding to $ \pi$ and $ \pi'$ are $ (-1)^{sgn(\pi)}\Pi_{i=1}^{n}t_{i,\pi(i)}$ and $ -(-1)^{sgn(\pi')}\Pi_{i=1}^{n}t_{i,\pi(i)}$. This means all the terms corresponding to permutations with at least one odd cycle can be grouped and pairs such as $ \pi$ and $ \pi'$ be cancelled. So the only contribution for the $ det(T)$ comes from permutations will all even cycles - in this case we have none, so $ det(T)=0$.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)