Laplacian matrix and the eigenvalue 0 of bipartite graphs with no perfect matching

Question

Let $G$ be a bipartite graph with no perfect matching. Show that $\lambda = 0$ is an eigenvalue of the adjacency matrix of $G$.

Hint: I do know that I should use the Laplacian matrix of $G$ and also $\lambda =0$ is the smallest eigenvalues of the Laplacian matrix.

Answer 1

Well, this answer was obtained independently of anything, and the proof is actually fairly simple--no need to consider permanents.

So let us write the adjacency matrix of $G=(V,E)$ as $A_G$ where the entries are $a_{uv}$; $u,v \in V(G)$ and also:

1. For every pair of distinct vertices $u,v$, the equation $a_{uv}=a_{vu}=1$ holds iff $uv$ is in $E$; otherwise $a_{uv}=a_{vu}=0$.
2. The diagonal entries of $A(G)$ are 0. Equivalently, for every vertex $u$, the equation $a_{uu}=0$ holds.

We establish the following:

Prop: Let $G$ be a bipartite graph that does not have a perfect matching. Then $A_G$ has an eigenvalue of 0.

Convention: For each vector $w \in \mathbb{R}^V$ and each vertex $v \in V$ we write the $v$-th component of $w$ as $w(v)$. For each $v \in V$ let us write $\chi_v$ to be the vector in $L_V = \mathbb{R}^V$ where $\chi_v(v)=1$ and $\chi_v(u)=0$ for each $u \in V(G)\setminus \{v\}$. We prove the following:

---

If $G$ does not have a perfect matching, then there is a subset $S$ of one side of $G$ that satisfies $|N_G(S)| < |S|$ by Hall's Matching Theorem. So let $S$ be a subset of one side of $G$ satisfying $|N_G(S)| < |S|$

Claim: Then as $|S| > |N_G(S)|$ the following holds: $\{A_G\chi_v; v \in S \}$ is a linearly dependent set of vectors. Precisely, there exists scalars $c_v; v \in S$; at least one of the $c_v$s nonzero, such that $\sum_{v \in S} A_G (c_v\chi_v) = 0$ is satisfied.

To see this, for each subset $U \subseteq V$ let us define $L_{U}$ as follow: $L_{U} \doteq \{w \in \mathbb{R}^V; w(v) = 0$ for all $v \not \in U\}$. Then for each subset $U$ of $V$, the set $L_{U}$ is a linear subspace $\mathbb{R}^V$ of dimension $|U|$.

Now for each $v \in S$, the vector $A_G \chi_v$ is in $L_{N(S)}$. But $L_{N(S)}$ has dimension $|N(S)| < |S|$. So the $|S|$ vectors $A_G \chi_v$s; $v \in S$, are not linearly independent, and thus indeed there exists scalars $c_v; v \in S$ at least one of the $c_v$s nonzero, such that $\sum_{v \in S} A_G (c_v\chi_v) = A_G(\sum_{v \in S} c_v\chi_v) = 0$ is satisfied.

Note however, that the set $\{\chi_v; v \in S\}$, is a linearly independent set of vertices in $\mathbb{R}^V$, and so $\sum_{v \in S} c_v\chi_v$ is a nonzero vector as at least one of the $c_v$s is nonzero. Thus $\sum_{v \in S} c_v \chi_v$ is an eigenvector of $A_G$, with eigenvalue 0.