# Edmonds matrix

In graph theory, the Edmonds matrix $A$ of a balanced bipartite graph $G = (V,E)$ is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once. Suppose that the vertex set $V = A \cup B$ where $A = \{a_1,\ldots,a_n\}$ and $B = \{b_1,\ldots,b_n\}$ .
The Edmonds matrix is an $n \times n$ matrix $A$ with entries $$A_{ij} = \begin{cases} x_{ij}\;\;\mbox{if}\;(a_i,b_j) \in E \\ 0\;\;\;\;\mbox{otherwise} \end{cases}$$ where the $x_{ij}$ are indeterminates. The determinant of this matrix is then a polynomial in the variables $x_{ij}$ and is non-zero (as a polynomial) if and only if a perfect matching exists.