Edmonds matrix

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (November 2024) (Learn how and when to remove this message)

In graph theory, the Edmonds matrix ${\displaystyle A}$ of a balanced bipartite graph ${\displaystyle G=(U,V,E)}$ with sets of vertices ${\displaystyle U=\{u_{1},u_{2},\dots ,u_{n}\}}$ and ${\displaystyle V=\{v_{1},v_{2},\dots ,v_{n}\}}$ is defined by

${\displaystyle A_{ij}=\left\{{\begin{array}{ll}x_{ij}&(u_{i},v_{j})\in E\\0&(u_{i},v_{j})\notin E\end{array}}\right.}$

where the x_ij are indeterminates. One application of the Edmonds matrix of a bipartite graph is that the graph admits a perfect matching if and only if the polynomial det(A_ij) in the x_ij is not identically zero. Furthermore, the number of perfect matchings is equal to the number of monomials in the polynomial det(A), and is also equal to the permanent of ${\displaystyle A}$. In addition, the rank of ${\displaystyle A}$ is equal to the maximum matching size of ${\displaystyle G}$.

The Edmonds matrix is named after Jack Edmonds. The Tutte matrix is a generalisation to non-bipartite graphs.