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

  • Thread starter roadrunner
  • Start date
  • Tags
    Graph
In summary: A and a vector x with eigenvalue lambdathen (Ax) = (lambda)xso (A^2)x = (lambda)^2*xso (A^3)x = (lambda)^3*xetc.now think about the magnitude of the product vectorsIn summary, we can show that the adjacency matrix A of a simple, connected d-regular graph has a largest eigenvalue of d and an eigenvalue of -d if and only if the graph is bipartite. This can be proven by considering the product of A with any vector x and the resulting magnitude of the product vector. This property is known as the Perron-Frobenius theorem.
  • #1
roadrunner
103
0

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.
 
Last edited:
Physics news on Phys.org
  • #2
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. ?
 
Last edited:
  • #3
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?)
 
  • #4
roadrunner said:
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
roadrunner said:
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
roadrunner said:
3) where did the vector (1,1,...1) come from?
try the matrix multiplication and it should be obvious
roadrunner said:
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
roadrunner said:
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
 
  • #5
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?
 
  • #6
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
 
Last edited:
  • #8
wow that's a mouthful to read...I don't think I'm smart enough to understand that! haha
 
  • #9
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.)
 
  • #10
roadrunner said:
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...
 
  • #11
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?
 
  • #12
from wiki, for a bi-partite the adjacency matrix can be written
[tex]\begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix}[/tex]

might be a start
 
  • #13
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)
 
  • #14
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.
 

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

What is Graph Theory?

Graph Theory is a branch of mathematics that studies the properties and relationships of objects called vertices or nodes, connected by lines or edges. It is used to model and solve problems related to networks and relationships.

What are the practical applications of Graph Theory?

Graph Theory has many practical applications in various fields, such as computer science, engineering, social sciences, and biology. It is used to model and analyze complex systems and networks, such as social networks, transportation networks, and communication networks.

What are Eigenvalues in Graph Theory?

Eigenvalues in Graph Theory are numerical values associated with a graph that represent the relative importance or centrality of each node in the graph. They are used to measure the influence or significance of a node in a network.

How are Eigenvalues calculated in Graph Theory?

Eigenvalues can be calculated using different methods, such as the Power Method or the Jacobi Method. These methods involve iterations and matrix operations to find the dominant eigenvalue and corresponding eigenvector of a given graph.

What is the significance of Eigenvalues in Graph Theory?

Eigenvalues play a crucial role in graph analysis and algorithms. They are used to identify important nodes in a network, detect communities and clusters, and measure the robustness and stability of a graph. They also have applications in machine learning and data analysis.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
521
  • Calculus and Beyond Homework Help
Replies
24
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
882
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
695
Replies
8
Views
1K
Back
Top