I am finding a solution of the following problem. I would like you to give a short proof.
Let A be the adjacency matrix of a d-regular graph G. Prove that d is an eigenvalue of A with multiplicity at least the number of connected components of G.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
If I understood correctly the question, the answer is obvious. Denote by $n$ the number of the components of $G$. For every component $C$ of $G$, take the vector $[C]$ whose coefficient corresponding to a vertex $v\in G$ equals $1$ if $v\in C$, and $0$, otherwise. It is immediate that $A[C]=d[C]$. The linear subspace $S$ generated by all $[C]$'s is $n$-dimensional and $As=ds$ for any $s\in S$.
answered Jan 17, 2014 at 11:46
-
$\begingroup$ v vertex or edge? S means that? $\endgroup$ Commented Jan 20, 2014 at 7:04
-
$\begingroup$ The coefficients of the vector (= column) $[C]$ correspond to all the vertices $v$ of the graph $G$. By definition, $S$ is the the linear subspace of columns generated by all $[C]$'s. $\endgroup$ Commented Jan 20, 2014 at 9:17
-
$\begingroup$ why multiplicity at least the number of connected components? $\endgroup$ Commented Jan 20, 2014 at 9:28
-
$\begingroup$ When you have a linear subspace $S$ of dimension $n$ such that $As=ds$ for all $s\in S$, the multiplicity of the eigenvalue $d$ of $A$ is at least $n$. This is elementary linear algebra. (To see this, you may write everything in the basis containing a basis of $S$.) $\endgroup$ Commented Jan 20, 2014 at 9:41