Edmonds matrix

In graph theory, the Edmonds matrix $A$ of a balanced 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}=\{\begin{array}{cc}{x}_{ij}& (u_i,v_j)\in E\\ 0& (u_i,v_j)\notin E\end{array}$

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) 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 $A$. In addition, the rank of $A$ is equal to the maximum matching size of $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.

Template:Graph-stub