Is -d Always an Eigenvalue for a d-Regular Graph?

[roadrunner]

Homework Statement

Let G be a simple, connected d-regular graph and let A be its adjacency matrix.

(i) Show that A has largest eigenvalue d
(ii) Show that A has an eigenvalue of -d if and only if G is bipartite.

Homework Equations

Don't know?

The Attempt at a Solution

I really have no idea where to start with this one. It has been a LONG time since I dealt with eigenvalues.

Some direction or insight would be great!

I know that means I need to show that "No eigenvalue of a graph can exceed its maximum degree." I know that is true, I don't know how to show it.

 

[lanedance]

for a) if you just look at the matrix, it is symmetric and each row will have the same number of ones...

now consider the columns & the action of the vector (1,1,...,1)

this shows d is an eigenvalue

now you need to show it is the maximal eigenvalue... any ideas/theorems, bits of work etc. ?

 

[roadrunner]

thanks for the reply. I get that the matrix is symetric and that each row has the same number of 1's.

Where you lost me was

"consider columns & the action of the vector (1,1,...,1) this shows d is an eigenvalue"

1) why the columns?
2) how do you consider the column if you don't know how many 1's and 0's it will have?
3) where did the vector (1,1,...1) come from?
4) k-regular means you can have say, 5 vertices of degree 2 right? It doesn't have to be a complete graph does it?

Like I said, its been years since I did eignenvalues. The prof gave us this question without reviewing them, so I really don't remember anything about them except that Det(A-I*lambda)= 0 (or something like that?)

 

[lanedance]

thanks for the reply. I get that the matrix is symetric and that each row has the same number of 1's.

Where you lost me was

"consider columns & the action of the vector (1,1,...,1) this shows d is an eigenvalue"

1) why the columns?

I should have said consider the multiplication of the matrix with vector (1,1,...,1), in this case its actually the rows, that are important

2) how do you consider the column if you don't know how many 1's and 0's it will have?

remember its symmetric, every row has teh same number of ones, so so does every column

3) where did the vector (1,1,...1) come from?

try the matrix multiplication and it should be obvious

4) k-regular means you can have say, 5 vertices of degree 2 right? It doesn't have to be a complete graph does it?

I actually don't know a heap about graphs, but my matricies are ok

Though I'm pretty sure it doesn't have to be complete, though a complete graph is regular

Like I said, its been years since I did eignenvalues. The prof gave us this question without reviewing them, so I really don't remember anything about them except that Det(A-I*lambda)= 0 (or something like that?)

i think you may have a bit of reading to do, try wiki
http://en.wikipedia.org/wiki/Eigenvalue,_eigenvector_and_eigenspace

the equation (the characteristic equation of a matrix) you gave is about the 5th down & explained

 

[roadrunner]

Originally Posted by roadrunner View Post

thanks for the reply. I get that the matrix is symetric and that each row has the same number of 1's.

Where you lost me was

"consider columns & the action of the vector (1,1,...,1) this shows d is an eigenvalue"

1) why the columns?

I should have said consider the multiplication of the matrix with vector (1,1,...,1), in this case its actually the rows, that are important

So if I had say, the matrix A

0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

Then A X (1,1,1,1) would be 2,2,2,2 correct? and these numbers will always be the value of k?

 

[roadrunner]

oh, so a matrix M multiplied by (1,1,...1) will give a result such that it equals N*(1,1,1...1) where N is an eigenvalue? is that a property?

and then I need to show that this is the largest eigenvalue?


so I think I get that part, not sure how to show its the largest.

I've browsed arround and this is may have to do with spectrums or expander graphs?

I've also seen many sites that say there is (using L for lambda) L1>=L2>=L3...>=Ln but none explain why d=L1 is the largest.

Direction? :D

 

[lanedance]

i haven't had a chance to read it all but this looks useful
http://en.wikipedia.org/wiki/Perron–Frobenius_theorem

I have to shoot, but will have a look later if i get a chance

 

[roadrunner]

wow that's a mouthful to read...I don't think I'm smart enough to understand that! haha

 

[roadrunner]

Could I say something like...

Ax=lambda*x for some vector x and the adjacency matrix A, (giving a eigenvalue of lambda).

**this is a true formula**

Let x be a vector and y=lambda*x be the product vector.

Consider the product of A and any vector x. The largest value in the product vector (y) is at most k times the largest value in the vector. Therefore, its associated eigenvalue is bounded above by k. Therefore, the eigenvalues for all vectors is either k or less than k.

and for part 2:

Similarly, -k is an eigenvalue if and only if the graph is bipartite. (To
see this, break the graph G into two groups VI and V2 and construct an eigenvector
with 1's for the positions associated with VI and -1's for the positions associated
with V2. The eigenvalue for this vector is -k. On the other hand, notice that if -k
is an eigenvector then we can partition V into two sets to verify that G is bipartite.)

 

[lanedance]

Could I say something like...

Ax=lambda*x for some vector x and the adjacency matrix A, (giving a eigenvalue of lambda).

**this is a true formula**

Let x be a vector and y=lambda*x be the product vector.

Consider the product of A and any vector x. The largest value in the product vector (y) is at most k times the largest value in the vector. Therefore, its associated eigenvalue is bounded above by k. Therefore, the eigenvalues for all vectors is either k or less than k.

no that's not quite right, the argument is circular unless you already know you have the largest eigenvector

the key takeaway is

In linear algebra, the Perron–Frobenius theorem, ..., asserts that a real square matrix with positive entries has a unique largest real eigenvalue and that the corresponding eigenvector has strictly positive components...

and that there are no other eigenvectors with strictly positive components

you've found that eignevector...

may be a simpler way, not sure...

 

[lanedance]

the other thing to investigate would be the characteristic equation... not sure where it would lead... But knowing the eignevalue you do, if you can show it is monotonic above that eigenvalue, you've shown it is the largest.

hey do you have to prove this generally, not just for a single case?

 

[lanedance]

from wiki, for a bi-partite the adjacency matrix can be written
\begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix}

might be a start

 

[roadrunner]

just generally. And why is my argument circular?

ax=lambdax is the definition of an eigenvalue.

If i let y=lambdax then ax=y where y is the vector resulting from the product of ax.

I know that k is an eigenvalue.

if x is some vector [x1,x2,..xj,...xi] where xj is the largest of those values then the largest that y can be is [x1,x2,..xj,...xi] times A, and since each row and column of A has exactly k 1's in it, y will be at most [kxj, kxj, kxj,...kxj] since the largest that x could be would be that all xi's=xj. and then we would have the vector:

xj+xj+...xj
xj+xj+...xj
.
.
.
xj+xj+...xj

where xj is present exactly k times in each row (and column)

Therefore, every entry in y is <=k.

so if k was say, 4, and xj was 3 then y=[y1,y1...yj] is less than or equal to [12,12,12...12,]

and [12,12,12...12]=4[3,3,3...3]=4x=lambdax therefore lambda=x

therefore lambdax=y<=[12,12,12...12]=4[3,3,3...3]=kx

therefore lambdax<=kx
therefore lambda<=k

is that not valid? (i explained it better this time)

 

[roadrunner]

as for the bipartite part, if we have a bipartite regular graph, then there must be an even number of vertices, n.

If we split there vertices into V1 and V2 where every edge has one endpoint in V1 and one endpoint in V2, then we can label the vertices of V1 1,2,3...n/2 and label V2 with n/2+1, n/2+2...n (ie: if N was 6 then V1 is labeled 1,2,3 and V2 is labeled 4,5,6)

If we then create an adjacency matrix it will have the form

0,0,0,...0,a,a,a...a
0,0,0,...0,a,a,a...a
0,0,0,...0,a,a,a...a
.
.
.
a,a,a,...a,0,0,0...0
a,a,a,...a,0,0,0...0
a,a,a,...a,0,0,0...0

Where there are n/2 0's and a is either a 1 or a 0, and the sum of a's in one row or column=k.

This is because all vectors in V1 will not connect to each other (same for V2) and every vertice in V1 will connect to k vertices in V2 (and visa versa)

If we then pick v=[1,1,1...1,-1,-1,-1,...-1] where there are n/2 1's and n/2 -1's. (use 1 for all vertices in V1 and =1 for all vertices in V2)

then the product vector y will be equal to [-k,-k,-k,...-k,k,k,k,...k] since in the top n/2 rows, the 1's multiply 0 and the -1's multiply exactly k 1's (and some number b of 0's) and in the bottom n/2 rows the -1's multiply all 0's and the 1's multiply exactly k 1's (and some number of b zeros)

This is reduced to -k[1,1,1...1,-1,-1,-1,...-1] and therefore -k is an eigenvalue

for the reverse direction. If -k is an eigenvalue, then we can simply take graph G and partition it into a bipartite graph of V1 and V2.