Adjacency matrix — where it appears
Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.
A matrix with no numbers in it
A graph arrives as vertices and edges. Two different matrices can be built from it, they answer different questions, and one of them has a null vector that is exact — the only object in these essays whose kernel is known before anything runs.
A graph is alternating modulo two
Random 0/1 matrices are invertible modulo two at the uniform law's rate, 0.289, and a random graph's adjacency matrix was predicted to follow the symmetric law instead, about 0.42. At twenty vertices it does: 0.409 of 3,000 graphs. At twenty-one it is zero, and at every odd order from nine to twenty-one, on every graph. An adjacency matrix has a zero diagonal, so modulo two it is alternating, its rank is even, and its determinant is the parity of the graph's perfect matchings — of which a graph with an odd number of vertices has none. The law it follows is the alternating one, which the symmetric law matches only at even order; put a coin on the diagonal and the symmetric law returns at every order. Modulo three and five, where a zero diagonal is only a constraint, graphs reach the symmetric law from below by sixteen vertices, as predicted.
Named alongside it
The objects these essays reach for when they reach for this one.
Exact ground truthRank is a decisionAlgebraic connectivityConnected componentsDeterminantExact arithmeticGraph laplacianModular arithmeticNull spaceQuadratic formUnlucky prime