21–30 of 40 posts
Yes social networks are graphs but think about electrical circuits. They are hyper-graphs. See the picture of an electrical circuit in:
https://en.wikipedia.org/wiki/Hypergraph
How does Linear Algebra deal with Hypergraphs?
What I'm interested to learn more about is Hypergraphs. They basically seem like a more real-world thing than basic graphs. Yes social networks are graphs but think about electrical circuits. They are hyper-graphs. See the picture of an electrical circuit in: https://en.wikipedia.org/wiki/Hypergraph How does Linear Algebra deal with Hypergraphs?
Can someone please explain to me why there are 17 paths of length 4 between v1 (1) and itself.
The (1,1) entry of the matrix multiplication of A^2 with itself is exactly this calculation. Matrix multiplication is a dance one sees everywhere. It's crippling to teach young minds that matrix multiplication is composing linear functions, when the dance shows up so many other ways.
Path counting is for example at the heart of automata theory in computer science. For a finite state machine, the question becomes "is there a path?" rather than "how many paths?" Think of 0 as false, and any positive integer 1, 2, 3, ... as true, and one sees this same dance in automata theory.
A question for the more informed: "What are recent developments in linear algebra?" Perhaps, we can broaden the scope and include numerical/randomized linear algebra. I come from a machine learning background, and the most recent directions I am aware of are in applications of Krylov subspace methods to very large number of data points and low-precision training (both in the context of Gaussian processes).
Still, you could throw out our course and spend a semester teaching people how to really think about singular value decomposition. It's everywhere, critical for example in machine learning, yet pure math types think it's "applied".
Riemannian geometry begins with an inner product at each point (though what's amazing about O'Neill's text is that he slips by you a categorical definition first at every step). As another route up the mountain, one could now understand parallel transport as a local version of the singular value decomposition, and work out the whole theory that way. This requires a fluid, intuitive grasp of singular values, rather than the textbook definition. We should teach that understanding.
The consequences of Theorem 2.2 are wrong as stated. Substitute k = n, and count the number of eigenvalues they say exist.
Caught another mistake:
Section 3.2: First, an observation: the column sums of Q(G) are all zero is wrong. Contradicts their definition of Q(G).
Earlier quoted context omitted.
> 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…
Of course, as a sibling comment notes, unlabeled graphs are often more interesting, for which one has to look at equivalence classes of adjacency matrices. The spectrum is nice here because it is automatically invariant to vertex permutations and hence a graph isomorphism invariant. The existence of nonisomorphic cospectral graphs is not immediately obvious, although there are simple examples, and that there are infinite families of cospectral pairs is even less obvious. So at the very least, it's interesting that the spectrum is not a complete invariant, and that it does work well for certain classes of graphs.
I opened this pdf expecting to see a section on total unimodularity (TU). For example, if an undirected graph is bipartite, its node-edge incidence matrix is TU. Any linear program operating on a TU matrix is guaranteed to have an integer solution. This means that any integer program can be relaxed to a linear program. Thus, the problems of bipartite matching and maximum flow can be easily solved using Simplex. Some…
Perhaps 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…
Pardon my ignorance, is the spectrum of a graph something more than simply the set of it's eigenvalues?
Perhaps 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…
I mean, this is a link to a pdf titled "chapter 3" buried deep in the directories of someone's academic homepage. There's no context about who the author is (is it a student project from a course? Part of a dissertation? notes for a draft of a book?), except that I think I can extract their name from the URL. It's pretty hard to tell, thus, who the desired audience is or what the aim of it is.
So whether one should expect one thing or another from this random pdf... I mean, without knowing more, what is there to reasonably expect?
For instance (and I can imagine this because I've taught an undergraduate course on graph theory, among other undergrad math courses), if these are notes from a course, then the instructor may have some good, context specific reasons for focusing on some topics while not going into details on others. But, as I said above, it's really impossible to know because this has just been plunked on HN with no context, as if that is somehow valuable.