Edmonds matrix
In graph theory, the Edmonds matrix A {\displaystyle A} of a balanced bipartite graph G = ( U , V , E ) {\displaystyle G=(U,V,E)} with sets of vertices U = { u 1 , u 2 , … , u n } {\displaystyle U=\{u_{1},u_{2},\dots ,u_{n}\}} and V = { v 1 , v 2 , … , v n } {\displaystyle V=\{v_{1},v_{2},\dots ,v_{n}\}} is defined by A i j = { x i j ( u i , v j ) ∈ E 0 ( u i , v j ) ∉ E {\displaystyle 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 xij 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 xij is not identically zero.