Show that det A is even.

Question

Let $G$ be a graph with no perfect matching and let $A$ be the adjacency matrix of $G$. Show that $\det(A)$ is even.

Ref: "Graphs and Matrices" by R. B. Bapat.

Answer 1

The permanent of $A$ counts the number of perfect matchings. So if $G$ has no perfect matching then $\text{perm}(A)=0$. Moreover, the determinant and the permanent of a matrix are congruent modulo $2$: $$\text{perm}(A)= \sum\limits_{\sigma \in S_{n}} \prod_{i=1}^n a_{\sigma(i),i}\equiv \sum_{\sigma \in S_n}\text{sgn}(\sigma )\prod_{i=1}^n a_{\sigma(i),i}=\det(A)\pmod{2}.$$ Hence $$\det(A)\equiv \text{perm}(A)=0\pmod{2}$$ that is $\det(A)$ is an even number.