1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – 35T41 Apr 10 '17 at 20:40
  • 1
    $\begingroup$ @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}$. $\endgroup$ – Misha Lavrov Apr 10 '17 at 20:44
  • $\begingroup$ 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. $\endgroup$ – Misha Lavrov Apr 10 '17 at 20:46
  • $\begingroup$ @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. $\endgroup$ – Ralff Apr 10 '17 at 20:47
  • $\begingroup$ 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}$). $\endgroup$ – hardmath Apr 10 '17 at 20:58
3
$\begingroup$

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.
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Ralff Apr 10 '17 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.