Edmonds matrix
2020 Mathematics Subject Classification: Primary: 05C50 Secondary: 05C70 [MSN][ZBL]
In graph theory, the Edmonds matrix 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
Edmonds matrix. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Edmonds_matrix&oldid=54444