Hacker News Reader

Comment by rjtobin | Hacker News Reader

Just a side note: The join of two graphs does correspond to a reasonably nice matrix operation: take the two adjacency matrices A and B (of dim m and n respectively, say), then form an (n+m)x(n+m) block matrix:

A J

J B

where J is the all one matrix (of the appropriate sizes to make the above matrix square).

Further aside: this block form might seem unnatural, but it pops up all the time in adjacency matrices of graphs. For example, bipartite graphs are exactly those that can be written in the form

0 A

B 0

(Where B = transpose(A))

View on HN

Yep, I definitely agree! Nominally, there are plenty of interesting results in spectral graph theory which make use of operations like these (esp. when computing laplacians/spectral partitions, etc), but, like most tools, while we can represent many groups/associated structures as linear-algebraic operations, there are subtle results that emerge from looking at an axiomatic treatment which aren't as clear when working with the linear-algebraic picture.

Like what?

Prove that a topological sort exists for a given graph using only linear algebraic properties of the adjacency matrix or the laplacian.

Or even, give a proof that a graph is a DAG iff there exists a topological sort using only linear algebraic operations on the adjacency matrix.

The point is, I'm sure you can do this; in some sense, we can perform every operation on a graph as we can its adjacency matrix, but why make it so complicated when there are easier pictures to work with?

Why perform surgery with a chainsaw when a scalpel will do without such a mess?

https://cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.pd...

I get that lin alg maybe isn't your picture of elegance, but you can't say that proof is laborious or esoteric. Any intro-level LA course is enough to grok it.

No, Lin-Alg is in fact what I work on in my research on spectral graph theory and graph partitions for approximation algorithms; but I do think there are different tools for different jobs.

There are plenty of interesting results where linear algebra shines and is beautiful (Kirchoff's theorems for counting trees, random walks on lattices as electrical networks, harmonic functions on graphs, topological data analysis) but there's plenty of statements where linear algebra is a hammer that's wholly unnecessary---statements that are already simple or elegant using other descriptions of graphs.

Though: interesting paper you linked to, thanks for that.

rjtobin, Sorry I don't understand what happens if the two graphs have common vertices?

For example, in the algebra I described, you can do 1 -> (1 + 2) and this represents a graph with vertices {1,2} and two edges (1,1) and (1,2). How would that work with your matrix join?

I didn't really think about that case. In full generality, then the corresponding (n+m-k)x(n+m-k) matrix can be written as the matrix whose top-left (n-k)x(n-k) block is A\B, whose bottom-right (m-k)x(m-k) block is B\A, and where everything else is 1.

Note that both involve relabelling vertices. Many graph theorists do this freely (it's the same graph), but perhaps you have some application in mind where you don't want to do this.

Thank you for clarifying. I see how your construction works now.

Reply on news.ycombinator.com