Feeds:
Posts
Comments

## Graphs are sparse matrices

John Horton Conway taught my freshman linear algebra course at Princeton in 1991, a great mathematician and a wonderful teacher.  I was an arrogant kid coming with an overdose of number theory gained from two summers in Ohio at the geek camp by Arnold Ross and was more familiar with extensions of Z/(p), quite familiar with irreducible polynomials and so on, cocky about finite dimensional vector fields.  But he did manage to weld into our minds a few things forever.  One of them was the diagonalizability of symmetric matrices like the rest of the millions of mathematicians.  Jordan canonical forms were murky and I never needed them in my varied career since.  At 42 now, I think another thing should have been welded in my mind from a freshman course, this:

Every finite noded graph is exactly identical to a sparse square matrix with rows equal to the cardinality of the vertex set.

This is a theorem (or a lowly proposition if one is snobbish) that is as fundamental as the diagonalizability of symmetric matrices but somehow escaped the freshmen, and lays the foundations of a large class of results, so much so that we should chastise mathematicians and computer scientists for getting the definitions of graph wrong.

Mathematicians don’t always make clear in their habits of writing what they really mean when they say “let G=(V,E) be a graph”; they actually mean “let G=(V,E,F) be an edge-weighted graph with weight 1.0 (in F) per edge”.  But computer scientists don’t know this and so they analyze graphs with poorer concepts than they should.  They assume F is auxiliary data but mathematicians could not prove anything interesting about graphs at all without F which is the incidence matrix data for 1.0 per edge in E.  Now the relation to sparse matrices is clear as is clear the idea that every implementation of graph data structure should always ship packaged with both matrix operations and with graph operations.  It’s silly not to have this as the standard graph implementation as basic as least-square ships with linear models in stats.

Advertisements