Let $G$ be a simple graph with incidence matrix $M$.
a) Show that the adjacency matrix of its line graph $L(G)$ is $M^t M − 2I$, where $I$ is the $m × m$ identity matrix.
b) Using the fact that $M^t M$ is positive-semidefinite, deduce that:
$\hspace{1cm}$i) each eigenvalue of $L(G)$ is at least $−2$,
$\hspace{1cm}$ii) if the rank of $M$ is less than $m$, then $−2$ is an eigenvalue of $L(G)$.
I could prove part a but could not prove part b. Please help me with it. Thank you.
First, let's observe that $M^tM$ is positive semidefinite. This means that it has only non-negative eigenvalues. So, let's find the eigenvalues for $M^tM-2I_m$. $$\vert (M^tM-2I_m)-\lambda I_m \vert=0$$ $$\vert M^tM-(\lambda+2)I_m \vert=0$$ Because we know that $M^tM$ has non-negative eigenvalues, $$(\lambda+2)\geq0$$ $$\lambda\geq-2$$ And there's point (i).
Point (ii) is a little more difficult.
First, it's very easy to see, by the IMT, that if $rank(M^tM)<m$, then $M^tM$ must have the eigenvalue $0$. Additionally, by the same argument above, we can show that this also implies $M^tM-2I_m$ must have the eigenvalue $-2$. Now, I'm not certain that notation $^t$ means transpose (I've always seen $^T$), but if it does, we can show that $rank(M)<m$ implies that $rank(M^tM)<m$.
This requires two very cool facts. First, column rank is equal to row rank: $rank(M)=rank(M^T)$, and rank cannot be increased by multiplication: $rank(AB)\leq min(rank(A),rank(B))$. $$rank(M^tM)\leq min(rank(M^t),rank(M))$$ $$rank(M^tM)\leq min(rank(M),rank(M))$$ $$rank(M^tM)\leq rank(M)$$ $$rank(M^tM)\leq rank(M)<m$$ $$rank(M^tM)<m$$ In summary, $rank(M)<m$ implies that $rank(M^tM)<m$ which implies that $M^tM$ has an eigenvalue $0$ which implies that $M^tM-2I_m$ has an eigenvalue $-2$.