Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Show that a graph $G$ finite with $n$ vertices is $d$-regular if, and only if, the vector with all the coordinates equals to 1 is eigenvetor from eigenvalue $λ = d$ from the adjacency matrix $A$ from the graph $G$. The question itself was a little confused for me...

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

Funny thing, I just learned this myself this week. It is proposition 3 on page 2 of these excellent lecture notes by Padraic Bartlett. The entire set of lecture notes on spectral graph theory is here.

I will shortly write up the proof, which is quite brief.

share|improve this answer
    
Thank you so much!!!! –  Charlie May 28 '12 at 2:31
    
Today was my test...this question was in it.... –  Charlie May 29 '12 at 21:00
    
@MarylinM.J I hope you passed! –  MJD May 29 '12 at 22:01
1  
@ Mark Dominus I took Ten!!!! –  Charlie Jun 9 '12 at 20:43
add comment

Suppose that $G$ is $d$-regular. Then every vertex of $G$ is adjacent to $d$ other vertices, so each row of its adjacency matrix $A$ will have $d$ $1$’s and $n-d$ $0$’s. Let

$$A=\pmatrix{a_{11}&a_{12}&\dots&a_{1n}\\ a_{21}&a_{22}&\dots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}&a_{n2}&\dots&a_{nn}}\;,$$

and $\vec v$ be the $n\times 1$ vector whose entries are all $1$:

$$\vec v=\pmatrix{1\\1\\\vdots\\1}\;.$$

The product $\vec u=A\vec v$ is an $n\times 1$ vector whose $i$-th entry is $$u_i=\sum_{j=1}^na_{ij}\cdot1=a_{i1}+a_{i2}+\ldots+a_{in}\;.$$ Since $d$ of the numbers $a_{i1},\dots,a_{in}$ are $1$ and the rest are $0$, $u_i=d$ for every $i$. Thus, $$\vec u=\pmatrix{d\\d\\\vdots\\d}=d\vec v\;.$$ That is, $A\vec v=d\vec v$, so by definition $\vec v$ is an eigenvector of $A$ for the eigenvalue $d$.

To show the other direction, you can try to reverse this argument; that works. Alternatively, you can assume that $G$ is not $d$-regular and show that $\vec v$ is not an eigenvector for an eigenvalue $d$; that also works and may be even easier.

share|improve this answer
    
Thanks to you too! –  Charlie May 29 '12 at 21:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.