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

:

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.

The Tutte matrix is a generalisation to non-bipartite graphs.

References

*cite book|author=R. Motwani, P. Raghavan |title=Randomized Algorithms |url=http://books.google.com/books/cambridge?id=QKVY4mDivBEC&pg=PR5&sig=8KZG5MvVdHKKRcLYdN91fGyIrBQ#PPA167,M1 |publisher=Cambridge University Press|year=1995|page=167
*cite book|author=Allen B. Tucker|title=Computer Science Handbook|publisher=CRC Press|date=2004|isbn=158488360X|page=12.19