The determinant and perfect matching.

Question

I have seen the theorem several times that the determinant of the adjacency matrix of a bipartite graph $G$ is not equal to 0 if and only if $G$ has a perfect matching. We can also write this as

$$ det(A^G) \neq 0 \longleftrightarrow \mathsf{there \; exists \; a \; perfect \; matching}$$

Note the adjacency matrix is defined here as the bipartite adjacency matrix, which is an $n \times n$ matrix whose $i$, $j$th element is 1 if $[u_i,v_j]$ is an edge, and 0 otherwise.

If we let G = $K_{2,2}$, the adjacency matrix, $A^G$, is given by

$$ A^G = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} $$

But, $det(A^G)=0$, so this theorem is wrong, right? There are 2 perfect matching in $K_{2,2}$.

Answer 1

This theorem is false; there are several true results along these lines that you might have mistaken for this one.

• One direction is true: if $\det(A^G) \ne 0$, then a perfect matching exists.
• The permanent (Wikipedia link) of $A^G$ counts the number of perfect matchings, so in particular it is nonzero if and only if a perfect matching exists.
• The determinant of the bipartite version of the Tutte matrix (Wikipedia link) is not the zero polynomial if and only if a perfect matching exists; in your example, this would be $$\det \begin{bmatrix} x_{11} & x_{12} \\ x_{21} & x_{22} \end{bmatrix} = x_{11} x_{22} - x_{12} x_{21},$$ which is not the zero polynomial.