Edmonds matrix

{{No footnotes|date=November 2024}}

In graph theory, the Edmonds matrix $A$ of a balanced bipartite graph $G\; =\; (U,\; V,\; E)$ with sets of vertices $U\; =\; \backslash \{u\_1,\; u\_2,\; \backslash dots\; ,\; u\_n\; \backslash \}$ and $V\; =\; \backslash \{v\_1,\; v\_2,\; \backslash dots\; ,\; v\_n\backslash \}$ is defined by

:$A\_\{ij\}\; =\; \backslash left\backslash \{\; \backslash 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) 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.