A question and some thoughts
by t0rajir0u, Jan 30, 2009, 7:01 AM
Question: Does there exist a satisfying graph-theoretic interpretation of the condition that two graphs are isospectral?
I've been thinking about this question for some time now. I don't really have the background to discuss it in detail, but briefly, the spectrum of a graph is the set of eigenvalues of its adjacency matrix; the powers of those eigenvalues then describes the powers of the adjacency matrix, hence the distribution of paths of length
on the graph. Intuitively, I think of the spectrum as describing "flows" on a graph.
Two graphs that are isomorphic are also isospectral, but the converse does not hold. This is not surprising: two graphs are isomorphic if and only if their adjacency matrices are similar up to permutation matrices, while two graphs are isospectral if and only if their adjacency matrices are similar up to any invertible matrix in
. Needless to say, this is a much weaker condition, and it's hard to come up with a convincing description of it in graph-theoretic terms.
I have a vague idea that some intermediate notion of isomorphism is possible first by considering weighted graphs and then by finding some way of formalizing what it means to conjugate an adjacency matrix by something other than a (weighted) permutation matrix. But I don't really know what's going on here.
Anyway, the motivation for this question is the following characterization of a class of nilpotent matrices:
Observation. A matrix
with non-negative real coefficients is nilpotent if and only if it is the weighted adjacency matrix of a directed acyclic graph.
I like this because it is highly intuitive: there are no paths of length greater than on a directed acyclic graph on vertices, or else they wouldn't be acyclic. A nicely behaved class of directed acyclic graphs is the set of directed trees with edges pointing away from or towards the root. This observation is the basis of the following
Observation. The nilpotent Jordan normal form theorem is (almost) equivalent to the statement that every (weighted) directed acyclic graph is isospectral to a directed [url=hhttp://en.wikipedia.org/wiki/Path_graph]path graph[/url].
Again, I like this because it is highly intuitive. A path is the simplest example of a directed acyclic graph, and to suggest that they are representative of the set of directed acyclic graphs in a particular way is a statement that I think is manageable by other means; I also think such statements should generalize to representative statements about other classes, and it would be very interesting to see the extent to which such statements translated into pure linear algebra.
Along those lines, I have become very interested lately with the idea that linear algebra is really just combinatorics, but I don't think I have the background to understand what Baez really means when he says that. Nevertheless, it is interesting to think about, and is one of the motivations for the above question.
I've been thinking about this question for some time now. I don't really have the background to discuss it in detail, but briefly, the spectrum of a graph is the set of eigenvalues of its adjacency matrix; the powers of those eigenvalues then describes the powers of the adjacency matrix, hence the distribution of paths of length
on the graph. Intuitively, I think of the spectrum as describing "flows" on a graph.Two graphs that are isomorphic are also isospectral, but the converse does not hold. This is not surprising: two graphs are isomorphic if and only if their adjacency matrices are similar up to permutation matrices, while two graphs are isospectral if and only if their adjacency matrices are similar up to any invertible matrix in
. Needless to say, this is a much weaker condition, and it's hard to come up with a convincing description of it in graph-theoretic terms.I have a vague idea that some intermediate notion of isomorphism is possible first by considering weighted graphs and then by finding some way of formalizing what it means to conjugate an adjacency matrix by something other than a (weighted) permutation matrix. But I don't really know what's going on here.
Anyway, the motivation for this question is the following characterization of a class of nilpotent matrices:
Observation. A matrix
with non-negative real coefficients is nilpotent if and only if it is the weighted adjacency matrix of a directed acyclic graph.I like this because it is highly intuitive: there are no paths of length greater than
on a directed acyclic graph on vertices, or else they wouldn't be acyclic. A nicely behaved class of directed acyclic graphs is the set of directed trees with edges pointing away from or towards the root. This observation is the basis of the followingObservation. The nilpotent Jordan normal form theorem is (almost) equivalent to the statement that every (weighted) directed acyclic graph is isospectral to a directed [url=hhttp://en.wikipedia.org/wiki/Path_graph]path graph[/url].
Again, I like this because it is highly intuitive. A path is the simplest example of a directed acyclic graph, and to suggest that they are representative of the set of directed acyclic graphs in a particular way is a statement that I think is manageable by other means; I also think such statements should generalize to representative statements about other classes, and it would be very interesting to see the extent to which such statements translated into pure linear algebra.
Along those lines, I have become very interested lately with the idea that linear algebra is really just combinatorics, but I don't think I have the background to understand what Baez really means when he says that. Nevertheless, it is interesting to think about, and is one of the motivations for the above question.
-
and 
are isotropic if, for every 
and 
are two square matrices, then they are isospectral if and only if 
for all 
.
eigenvalues, but what we are interested in is the distinction between geometric and algebraic multiplicity (i.e. the nature of the connected components of the isospectral graph path), which is perhaps too subtle to capture by graph-theoretic means.
April 2009
March 2009