Edmonds matrix

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

$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.

References

• R. Motwani, P. Raghavan (1995). Randomized Algorithms. Cambridge University Press. p. 167.