Can graph spectrums be derived from incident matrices?

  • Context: Graduate 
  • Thread starter Thread starter 1Truthseeker
  • Start date Start date
  • Tags Tags
    Graph Matrices
Click For Summary
SUMMARY

The discussion centers on the relationship between the eigenvalues of adjacency matrices and incident matrices in graph theory. It establishes that while the set of eigenvalues from an adjacency matrix (sa) can be considered a graph spectrum, the eigenvalues from an incident matrix (si) cannot be directly compared due to the non-square nature of incident matrices. Instead, singular values of the incident matrix are relevant, as they relate to the eigenvalues of the line graph of the original graph G.

PREREQUISITES
  • Understanding of graph theory concepts, specifically adjacency and incident matrices.
  • Knowledge of eigenvalues and their significance in linear algebra.
  • Familiarity with singular value decomposition and its applications.
  • Basic comprehension of line graphs and their relationship to original graphs.
NEXT STEPS
  • Study the properties of adjacency matrices in graph theory.
  • Learn about singular value decomposition and its implications for incident matrices.
  • Explore the concept of line graphs and their eigenvalues.
  • Investigate the differences between eigenvalues and singular values in linear algebra.
USEFUL FOR

Mathematicians, computer scientists, and researchers in graph theory who are interested in the spectral properties of graphs and their applications in various fields.

1Truthseeker
Messages
43
Reaction score
0
Will the set of eigenvalues of an incident matrix derive an equivalent notion of a graph spectrum as it does with an adjacency matrix?

Specifically:

Let sa be the set of eigenvalues of an adjacency matrix for graph G.

And,

Let si be the set of eigenvalues of an incident matrix for graph G.

What are the differences between sa and si? Could these both be considered spectrums of the graph? If not, why?

Thanks much!
 
Physics news on Phys.org
What is your definition for incident matrix? If it's the usual definition, then it's likely not a square (nxn) matrix so it doesn't make sense to talk about eigenvalues. You can however look at its singular values which I think are related to eigenvalues of the line graph of G.
 

Similar threads

Graduate Adjacency matrices: (a) notation discrepancy, and (b) applications
  • · Replies 3 ·
Replies
3
Views
2K
Graduate A reasonable analogy for understanding similar matrices?
  • · Replies 4 ·
Replies
4
Views
3K
Graduate When can transitivity emerge from cycle-suppressing dynamics?
  • · Replies 1 ·
Replies
1
Views
529
Graduate Uniqueness of identity elements for rectangular matrices
  • · Replies 1 ·
Replies
1
Views
3K
Graduate About computing the tangent space at 1 of certain lie groups
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad Diagonalization and similar matrices
  • · Replies 3 ·
Replies
3
Views
3K
Graduate Combinatorial Algorithm for Sorting Adjacency Matrices in Polynomial Time
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Why Does a Blackbody Emit Broadband Radiation from Monochromatic Light?
  • · Replies 23 ·
Replies
23
Views
3K
Undergrad Effective Hamiltonian to Rotational Term Values
  • · Replies 0 ·
Replies
0
Views
3K
Undergrad Meaning of "passage to the quotient"?
  • · Replies 3 ·
Replies
3
Views
1K