I'm stuck on some of the theory in these notes, i'm trying to learn about randomized algorithms in general and am currently stuck on some notes regarding perfect matchings.
Here is a link to the notes http://www.cs.berkeley.edu/~sinclair/cs271/n2.pdf and my question concerns the material from the isolating lemma (on the penultimate page excluding references) to the end.
Ok so i'll try and explain what i understand to perhaps highlight exactly what i don't understand. In general we have a bipartite graph $G$ which we know has a perfect matching, we use this algorithm to find a perfect matching. I'd also like to highlight if at any point i use the term matching i mean perfect matching.
So i am fine with the isolating lemma which states
$\textbf{Lemma}$-Let $S_{1},...,S_{k}$ be subsets of a set $S$ of cardinality $m$. Let each element $x \in S$ have a weight $w_{x}$ chosen independently and uniformly at random from the set $\{0,1,...,2m-1\}.$ Then $$\mathrm{Pr}(\exists\; \mathrm{a\;unique\;set\;of\;minimum\;weight})\geq \frac{1}{2}.$$
This lemma is used in the following context for bipartite matchings which i am also fine with. Given a bipartite graph the set $S=E$, where $E$ is the edge set of $G$. Then $S_{1},...,S_{k}$ are the matchings of $G$ and each edge $(ij) \in E$ is assigned a weight $w_{ij}$ in $\{0,1,...,2|E|-1\}$ independently and uniformly at random. The weight $w(M)$ of a matching $M$ is simply the sum of all the weights of it's edges.
The matrix $B$ is the matrix central to the whole algorithm which is obtained as follows. Replace every entry of the Tutte matrix which is $x_{ij}$ with $2^{w_{ij}}$. Recall the Tutte matrix is obtained form the $n\times n$ bipartite graph by placing $x_{ij}$ in entry $a_{ij}$ if edge $(ij) \in E$ and placing $0$ otherwise.
So here is the algorithm which outputs a perfect matching provided we have a unique minimum weight matching, if no such matching exists it fails.
$\textbf{Algorithm}$:Calculate $2^{w}$ the largest power of $2$ to divide $det(B)$
for each edge $(i,j)$ in parallel do
compute $t_{ij}=det(B_{ij})\frac{2^{w_{ij}}}{2^{w}}$ where $B_{ij}$ is the $(i,j)$ minor of $B$, place $(i,j)$ in $M$ iff $t_{ij}$ is an odd integer.
If $M$ is a perfect matching then output $M$ else output fail.
$\textbf{EndAlgorithm}$
Ok so here is the main claim and the proof of which is the source of my problems :)
$\textbf{Claim}$: If the minimum weight perfect matching is unique then the above algorithm outputes it.
i will give a rough outline of the proof as it is in the attachment
$\textbf{Proof}$: It says that if $M_{0}$ is the minimum weight matching then it's weight is the $w$ we calculated, the reason for this is that
$det(B)=\sum_{M \in \mathcal{M}(G)} \pm 2^{w(M)}$ where $\mathcal{M}(G)$ is the set of all matchings. This is easy to see and in addition $det(B)/2^{w}$ is odd.
It then says for an edge $(i,j)$, $B_{ij}$ corresponds to the perfcect matchings in $G\setminus \{ij\}$.
It then claims that $t_{ij}$ is odd if and only if $(i,j)$ is an edge of $M_{0}$. It states $det(B_{ij})=\sum_{M \in \mathcal{M}(G \setminus \{i,j\})} \pm 2^{w(M)}$
which they say is equal to (which i'm not sure is correct because of no $\pm $)
$ 2^{-w_{ij}} \sum_{M \cup \{i,j\} \in \mathcal{M}(G)} 2^{w (M \cup \{i,j\})}$
firstly what does ${M \cup \{i,j\} \in \mathcal{M}(G)}$ mean? If we already have a perfect matching how can we add the edge $\{i,j\}$ and still obtain a perfect matching?Is this a notational mistake on their behalf?
Secondly i dont undertstand how $t_{ij}$ is odd if $\{i,j\} \in M_{0}$? This is because surely $det(B_{ij})/2^{w}$ is even as by removing $\{i,j\}$ from $G$ surely we have removed $M_{0}$ and so the weight of every matching in $G \setminus\{i,j\}$ is larger than $w$ and so $t_{ij}=2^{w_{ij}}det(B_{ij})/2^{w}$ is even? I'd really appreciate any help in clarifying this, thanks.
For the first question:
The summation $2^{-w_{ij}}∑_{M∪\{i,j\}∈M(G)}2^{w(M∪\{i,j\})}$ is not running over perfect matchings $M$, but instead think of arbitrary edge set $M$ which satisfies $M∪\{i,j\}∈M(G)$. In other words, the summation is over all edge sets obtained from perfect matchings containing $ij$ by removing $ij$.
The second question may confused you because of the first problem. The matching $M_0 - ij$ is still there, contributing to the summation so that the result is odd. Your reasoning is somehow correct except that you still have $M_0 - ij$.