# T1: Algebraic Matching Algorithms (1)

This post will show how to detect and find a matching using matrix.

## Definitions

Given a bipartite graph \(G=(L, R, E)\) with \(\lvert L\rvert = \lvert R \rvert = n\), the Edmonds Matrix \(E(G)\) is defined as \(n\times n\) matrix of variables in the following.

\[\mathrm{E}_{i,j} = \begin{cases} 0, & (i,j) \not \in E \text{ and } {i\in L, j\in R}\\ 1, & (i,j)\in E \text{ and } {i\in L, j\in R} \end{cases}\]We know that the basics are always important.

### Leibniz Formula to Compute a Determinant

For more about determinant, please read the post What is determinant.

\[\textup{Det}(\textbf{a}_1, \textbf{a}_2,\ldots, \textbf{a}_n) = \sum_{(j_1,\ldots,j_n)\in \pi_n}\text{sgn}(j_1,\ldots,j_n) \prod_{i=1}^n v_{j_n i}\]where \(\pi_n\) is a permutation.

## Lovász’s Algorithm

\(\textbf{Theorem}\)[35] Let \(\textup{E}(G)\) be the Edmonds matrix of a bipartite graph \(G\). Then, \(\textup{E}(G)\) is non-zero iff \(G\) contains a perfect matching.

Wow! Cool! What a beautiful theory!

## Karp, UPpfal, Wigderson Algorithm

## Rabin and Vazirani Algorithm

## Reference

[1] Tutte, William T. “The factorization of linear graphs.” *Journal of the London Mathematical Society* 1.2 (1947): 107-111.