# The determinant and perfect matching.

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}$.

• That's not the adjacency matrix. If $G$ has 4 vertices, the adjacency matrix is a 4X4 matrix. I think you need to review the definition. – 35T41 Apr 10 '17 at 20:40
• @35T41 This is the bipartite adjacency matrix; for most results along these lines, it's okay to use it instead of the full adjacency matrix, because if $A$ is the full matrix and $B$ is the bipartite version, then $A$ has the block structure $\begin{bmatrix}0 & B \\ B & 0\end{bmatrix}$. – Misha Lavrov Apr 10 '17 at 20:44
• Note that in the $4 \times 4$ version, we have $$\det \begin{bmatrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0\end{bmatrix}=0$$ as well. – Misha Lavrov Apr 10 '17 at 20:46
• @35T41 I provided the definition of the adjacency matrix for this reasons. The determinant for the $4 \times 4$ version is also equal to 0. – Ralff Apr 10 '17 at 20:47
• As mentioned in the Answer, the permanent of $\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}$ is two (counting the number of perfect matchings of $K_{2,2}$). – hardmath Apr 10 '17 at 20:58

## 1 Answer

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.
• Thank you so much for the clarification. I was actually reading about the permanent, and it is obvious from the permanent that if the determinant is not 0 then a perfect matching exists just not the converse. I think I must have read the theorem incorrectly. – Ralff Apr 10 '17 at 20:51