
Edmonds matrix

In graph theory, the Edmonds matrix formula_1 of a balanced bipartite graph formula_2 with sets of vertices formula_3 and formula_4 is defined by 
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 formula_1. In addition, rank of formula_1 is equal to the maximum matching size of formula_8.
The Edmonds matrix is named after Jack Edmonds. The Tutte matrix is a generalisation to non-bipartite graphs.