View source for Edmonds matrix

{{TEX|done}}{{MSC|05C50|05C70}}

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.

The [[Tutte matrix]] is a generalisation of the Edmonds matrix to a general [[graph]].

==References==
* Rajeev Motwani, Prabhakar Raghavan, "Randomized Algorithms", Cambridge University Press (1995) ISBN 978-0-521-47465-8 {{ZBL|0849.68039}}
* Allen B. Tucker, "Computer Science Handbook", 2nd ed. CRC Press (2004) ISBN 158488360X