Intersection Array - Distance Adjacency Matrices

Distance Adjacency Matrices

Suppose G is a connected distance-regular graph. For each distance i = 1, ..., d, we can form a graph G_i in which vertices are adjacent if their distance in G equals i. Let A_i be the adjacency matrix of G_i. For instance, A₁ is the adjacency matrix A of G. Also, let A₀ = I, the identity matrix. This gives us d + 1 matrices A₀, A₁, ..., A_d, called the distance matrices of G. Their sum is the matrix J in which every entry is 1. There is an important product formula:

From this formula it follows that each A_i is a polynomial function of A, of degree i, and that A satisfies a polynomial of degree d + 1. Furthermore, A has exactly d + 1 distinct eigenvalues, namely the eigenvalues of the intersection matrix B,of which the largest is k, the degree.

The distance matrices span a vector subspace of the vector space of all n × n real matrices. It is a remarkable fact that the product A_i A_j of any two distance matrices is a linear combination of the distance matrices:

This means that the distance matrices generate an association scheme. The theory of association schemes is central to the study of distance-regular graphs. For instance, the fact that A_i is a polynomial function of A is a fact about association schemes.