graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, the Edmonds matrix

A

of a balanced

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...

G = (U, V, E)

with

set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

s of vertices

U = \

and

V = \

is defined by :

A_ = \left\{ \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 In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...

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 mathematics, a monomial is, roughly speaking, a polynomial which has only one term. Two definitions of a monomial may be encountered: # A monomial, also called power product, is a product of powers of variables with nonnegative integer expone ...

in the polynomial det(''A''), and is also equal to the

permanent Permanent may refer to: Art and entertainment * ''Permanent'' (film), a 2017 American film * ''Permanent'' (Joy Division album) * "Permanent" (song), by David Cook Other uses * Permanent (mathematics), a concept in linear algebra * Permanent (cy ...

A

. In addition,

rank Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as: Level or position in a hierarchical organization * Academic rank * Diplomatic rank * Hierarchy * H ...

A

is equal to the

maximum matching Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adj ...

size of

G

. The Edmonds matrix is named after

Jack Edmonds Jack R. Edmonds (born April 5, 1934) is an American-born and educated computer scientist and mathematician who lived and worked in Canada for much of his life. He has made fundamental contributions to the fields of combinatorial optimization, pol ...

. The

Tutte matrix In graph theory, the Tutte matrix ''A'' of a graph ''G'' = (''V'', ''E'') is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once. If the set of vert ...

is a generalisation to non-bipartite graphs.

References

* * Algebraic graph theory {{combin-stub