Eigenvalues of a completely disconnected graph

In summary: The first eigenvalue is supposed to be zero, but it is not because there are 3 pairs of nodes which are connected only to each other. The first eigenvalue is actually 2.220446049250313E-16.
  • #1
kosmos
11
0
According to theory the eigenvalues of a completely disconnected graph (no two nodes are connected) must be all 0. But the normalized Laplacian of such a graph will be an identity matrix whose eigenvalues will be all 1s. Please correct me!
 
Physics news on Phys.org
  • #2
kosmos said:
According to theory the eigenvalues of a completely disconnected graph (no two nodes are connected) must be all 0. But the normalized Laplacian of such a graph will be an identity matrix whose eigenvalues will be all 1s. Please correct me!

I believe you can not create a normalize Laplacian from a graph with isolated vertices.
They have degree 0, so you cannot calculate the entries ##-1 \over \sqrt{d_i d_j}## in the matrix.
 
  • #3
The value is 0 if the degree is 0 as per definition. So we will get an identity matrix.

http://www.math.ucsd.edu/~sbutler/spectral/
 
Last edited by a moderator:
  • #4
Can't find the reference in your link...

However, from wikipedia I can see that the entries on the main diagonal would be set to zero, so it will not be an identity matrix.
These entries would correspond to eigenvalues of zero.
 
  • #5
Page no. 9 of this pdf file http://www.math.ucsd.edu/~sbutler/PDF/spectral1.pdf ... and i think this reference has missed that out! ...thanks for helping out mate!
 
Last edited by a moderator:
  • #6
kosmos said:
Page no. 9 of this pdf file http://www.math.ucsd.edu/~sbutler/PDF/spectral1.pdf ... and i think this reference has missed that out! ...thanks for helping out mate!

Yes, this reference missed out on that.
However, in the introductory paragraph it is assumed that there are no isolated vertices, so it is not wrong.

And you're welcome. :)
 
Last edited by a moderator:
  • #7
I get the following eigenvalues for the matrix attached as text file. It can be viewed in spreadsheet as it is in csv format. The first eigen value is supposed to be zero. There are 20 nodes in graph. There are 3 pairs of nodes which are connected only to each other. So there are 15 partitions as shown by the values below, assuming -4 is zero.
-4.0
-2.220446049250313E-16
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
1.1102230246251565E-16
4.440892098500626E-16
1.9999999999999998
2.0
2.0
2.0
2.000000000000001
 

Attachments

  • data.txt
    1.6 KB · Views: 358
  • #8
Sorry for posting it in this thread ... I should have done it in the other one. I got the problem. The portion of my implementation which checked if the nodes where adjacent had a mistake. So it was producing wrong first eigenvalue. Now it works fine. I am getting the required number of zeroes and no negative values. :) ... Thanks for your help again!
 
  • #9
Cheers! :smile:
 

Related to Eigenvalues of a completely disconnected graph

1. What is a completely disconnected graph?

A completely disconnected graph is a type of graph where none of the vertices (nodes) are connected to each other. This means that there are no edges (lines) connecting any of the vertices, and each vertex exists in its own isolated cluster. It is also known as a null graph.

2. What are eigenvalues in the context of a completely disconnected graph?

Eigenvalues are a mathematical concept used to describe how a linear transformation affects a vector. In the context of a completely disconnected graph, the eigenvalues represent the possible values that a vertex can have, and how it affects the rest of the graph.

3. How are the eigenvalues of a completely disconnected graph determined?

The eigenvalues of a completely disconnected graph can be determined by finding the roots of its characteristic polynomial. The characteristic polynomial is a function that describes the relationship between the eigenvalues and the matrix of the graph's adjacency matrix.

4. What is the significance of eigenvalues in a completely disconnected graph?

The eigenvalues of a completely disconnected graph can provide important information about the graph's structure and behavior. For example, they can help determine the number of connected components in the graph, and the maximum degree of any vertex.

5. What are some applications of studying the eigenvalues of a completely disconnected graph?

Studying the eigenvalues of a completely disconnected graph can have various applications in fields such as network analysis, social sciences, and physics. For instance, it can be used to analyze the structure and connectivity of large networks, predict the spread of information or diseases through a social network, or understand the behavior of quantum systems.

Similar threads

A Eigenvalues of block matrix/Related non-linear eigenvalue problem
    • Linear and Abstract Algebra
Replies
1
Views
1K
Quadratic eigenvalue problem and solution (solved in Mathematica)
    • Linear and Abstract Algebra
Replies
2
Views
1K
MATLAB FEM, Matlab and the modes of an element
    • MATLAB, Maple, Mathematica, LaTeX
Replies
32
Views
2K
A The eigenvalue power method for quantum problems
    • Quantum Physics
Replies
2
Views
1K
I Meaning of Third Eigenvalue in a Tilted Ellipse in a 3x3 Matrix
    • Linear and Abstract Algebra
Replies
3
Views
2K
MHB Finding the Set of Eigenvalues
    • Linear and Abstract Algebra
Replies
7
Views
2K
How Does the Graph Laplacian Explain the Multiplicity of Eigenvalue Zero?
    • Calculus and Beyond Homework Help
Replies
1
Views
1K
MHB Help! Wrong Eigenvalues Using Matrix A
    • Linear and Abstract Algebra
Replies
7
Views
2K
I Proof that if T is Hermitian, eigenvectors form an orthonormal basis
    • Linear and Abstract Algebra
Replies
3
Views
2K
Operator T, ##T^2=I##, -1 not an eigenvalue of T, prove ##T=I##.
    • Calculus and Beyond Homework Help
Replies
2
Views
370

Hot Threads

Recent Insights

Back
Top