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.

  • $\begingroup$ your comments about the graph Laplacian don't fit. I think the standard approach is to show that with no perfect matching implies a permanent of zero for the adjacency matrix. Then show the sign function does not change the result, so the determinant of the adjacency matrix is zero, and hence it has an eigenvalue of zero. $\endgroup$ – user8675309 Jan 13 at 22:08
  • $\begingroup$ How to show that the sign function does not change the result? What do you mean by this? $\endgroup$ – 6-0 Jan 14 at 10:57
  • 1
    $\begingroup$ your bounty asks for an answer from a reputable source. I had the book 33 Miniatures in mind here in my initial comment. I'll plan on expanding as a proper bounty response some time later today. In the interim, miniature 24 answers your question, and miniature 22 gives some nice related/additional discussion of perfect matchings and determinants. A free pre-print is here: kam.mff.cuni.cz/~matousek/stml-53-matousek-1.pdf $\endgroup$ – user8675309 Jan 15 at 20:05
  • $\begingroup$ Thank you very much. Please send answer to receive bounty. $\endgroup$ – 6-0 Jan 15 at 20:41

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.


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.