Edmonds matrix

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.

References

• R. Motwani, P. Raghavan (1995). Randomized Algorithms. Cambridge University Press. p. 167. ISBN 9780521474658.
• Allen B. Tucker (2004). Computer Science Handbook. CRC Press. p. 12.19. ISBN 1-58488-360-X.