Skip to main content
3 of 3
added 108 characters in body
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Is there a bipartite graph whose determinant corresponds to number of perfect matchings?

Let $M\in\{0,1\}^{n\times n}$ be a square integer matrix. If we consider $M$ as biadjacency of a balanced bipartite graph on $2n$ vertices having $n$ vertices of color $1$ and $n$ vertices of color $2$ we canonically associate permanent of $M$ to the number of perfect matchings in the graph.

Is there a bipartite graph which is balanced we can associate to the square of the determinant or absolute value of the determinant in a canonical manner without computing the determinant explicitly?

Update Observe the construction of the graph is non-canonical in any known way. It has to be clever.

Turbo
  • 13.9k
  • 1
  • 27
  • 76