Graph Theory and Linear Algebra [pdf]
math.utah.edu
Graph Theory and Linear Algebra [pdf]
1–10 of 40 posts
Re: Graph Theory and Linear Algebra [pdf]
#2Perhaps I was wrong to expect mention of explicit discsussion of spectral graph theory? Anyway, always interesting topics to me.
On a related note: Gilbert Strang (MIT) has a relatively new class in the area of Linear Algebra (of course!) and learning: from data: "Matrix Methods in Data Analysis, Signal Processing, and Machine Learning" > https://ocw.mit.edu/courses/mathematics/18-065-matrix-method...
With Part IV: Special Matrices discussing the Laplacian and Distance matrices as noted in the posted paper. [TOC: https://math.mit.edu/~gs/learningfromdata/dsla_toc.pdf]
Re: Graph Theory and Linear Algebra [pdf]
#3Perhaps I was wrong to expect mention of explicit discsussion of spectral graph theory? Anyway, always interesting topics to me. On a related note: Gilbert Strang (MIT) has a relatively new class in the area of Linear Algebra (of course!) and learning: from data: "Matrix Methods in Data Analysis, Signal Processing, and Machine Learning" > https://ocw.mit.edu/courses/mathematics/18-065-matrix-method... With Part IV: S…
> Perhaps I was wrong to expect mention of explicit discsussion of spectral graph theory?
Agreed... if you're going to write down the Laplacian at least demonstrate the null space connected component relationship.
Edit: looks like maybe an undergraduate paper?
Re: Graph Theory and Linear Algebra [pdf]
#4Perhaps I was wrong to expect mention of explicit discsussion of spectral graph theory? Anyway, always interesting topics to me. On a related note: Gilbert Strang (MIT) has a relatively new class in the area of Linear Algebra (of course!) and learning: from data: "Matrix Methods in Data Analysis, Signal Processing, and Machine Learning" > https://ocw.mit.edu/courses/mathematics/18-065-matrix-method... With Part IV: S…
> Perhaps I was wrong to expect mention of explicit discsussion of spectral graph theory? Agreed... if you're going to write down the Laplacian at least demonstrate the null space connected component relationship. Edit: looks like maybe an undergraduate paper?
Oh, ah, nice find, yeah, if you go down the URL:
https://www.math.utah.edu/~gustafso/s2017/2270/projects-2017...
Projects from a LA class at UofU.
Re: Graph Theory and Linear Algebra [pdf]
#5Perhaps I was wrong to expect mention of explicit discsussion of spectral graph theory? Anyway, always interesting topics to me. On a related note: Gilbert Strang (MIT) has a relatively new class in the area of Linear Algebra (of course!) and learning: from data: "Matrix Methods in Data Analysis, Signal Processing, and Machine Learning" > https://ocw.mit.edu/courses/mathematics/18-065-matrix-method... With Part IV: S…
You are most definitely not wrong. I would have expected some mention of the spectrum of a graph beyond simply defining what the eigenvalues are.
Incidentally, one interesting thing about the graph spectrum is that it's actually not a very interesting invariant. Among other things, almost all trees are cospectral, as proven in the following paper by Allen Schwenk in 1973: https://www.researchgate.net/publication/245264768_Almost_al...
Re: Graph Theory and Linear Algebra [pdf]
#6If that was interesting, you might like the book "Linear Algebra Methods in Combinatorics"
https://people.cs.uchicago.edu/~laci/CLASS/HANDOUTS-COMB/BaF...
Re: Graph Theory and Linear Algebra [pdf]
#7Perhaps I was wrong to expect mention of explicit discsussion of spectral graph theory? Anyway, always interesting topics to me. On a related note: Gilbert Strang (MIT) has a relatively new class in the area of Linear Algebra (of course!) and learning: from data: "Matrix Methods in Data Analysis, Signal Processing, and Machine Learning" > https://ocw.mit.edu/courses/mathematics/18-065-matrix-method... With Part IV: S…
You are most definitely not wrong. I would have expected some mention of the spectrum of a graph beyond simply defining what the eigenvalues are. Incidentally, one interesting thing about the graph spectrum is that it's actually not a very interesting invariant. Among other things, almost all trees are cospectral, as proven in the following paper by Allen Schwenk in 1973: https://www.researchgate.net/publication/2452…
> Among other things, almost all trees are cospectral
This does not really mean that the spectrum is not interesting, does it? Only that all trees have nearly the same spectrum. Sure, there's not much variability inside the class of trees, but almost no graphs are trees. After all, the matrix associated to a tree is basically a permutation of the identity.
Re: Graph Theory and Linear Algebra [pdf]
#8awesome - spent couple of years deep in this space for dissertation using graph theory to boost linear algebra computes; lots of room to extend our discrete result into approximate / continuous computes and boost AI, GPUs, etc.
similar result came out around the same time using category theory as basis; our work was intentionally simpler / more applied, partly to make it more accessible from an algorithmic perspective and also to put it into practice, etc.
* www - https://scholar.afit.edu/etd/2632/
* pdf - https://www.sagemath.org/files/thesis/augeri-thesis-2008.pdf
Re: Graph Theory and Linear Algebra [pdf]
#9awesome - spent couple of years deep in this space for dissertation using graph theory to boost linear algebra computes; lots of room to extend our discrete result into approximate / continuous computes and boost AI, GPUs, etc. similar result came out around the same time using category theory as basis; our work was intentionally simpler / more applied, partly to make it more accessible from an algorithmic perspectiv…
p.s. my user name from that work -- aghilmort is canonical alpha sort / scrabble sort of algorithm and logarithm
Re: Graph Theory and Linear Algebra [pdf]
#10Earlier quoted context omitted.
You are most definitely not wrong. I would have expected some mention of the spectrum of a graph beyond simply defining what the eigenvalues are. Incidentally, one interesting thing about the graph spectrum is that it's actually not a very interesting invariant. Among other things, almost all trees are cospectral, as proven in the following paper by Allen Schwenk in 1973: https://www.researchgate.net/publication/2452…
> Among other things, almost all trees are cospectral This does not really mean that the spectrum is not interesting, does it? Only that all trees have nearly the same spectrum. Sure, there's not much variability inside the class of trees, but almost no graphs are trees. After all, the matrix associated to a tree is basically a permutation of the identity.
You're right, of course. I should have said that the spectrum isn't all that useful for telling two graphs of the same order apart. Certain eigenvalues are frequently useful by themselves (e.g. the largest, second largest, and smallest eigenvalues often contain some information).
But, speaking of information, consider this: the adjacency matrix of a simple, loopless graph of order n is a symmetric n x n matrix with all zeroes on the diagonal. That means the adjacency matrix contains (literally) n^2/2 - n bits of information, while the number of connected graphs of order n as n -> infinity grows exponentially [0]. That implies that for the purpose of telling two graphs of the same order apart, the spectrum is of fairly limited utility, which is what I was thinking of when I wrote that it was not an interesting invariant.
---
[0]: https://users.cecs.anu.edu.au/~bdm/papers/BCM_Connected1.pdf