Feb. 22 -- the adjacency matrix and the integrality condition (p.36-38) Let G=(V,E) be a graph with n vertices. Choose a labeling v_1,...,v_n of the vertices. A basic construction for much of graph theory: The _adjacency matrix_ A=A(G) is the matrix whose (i,j) entry a_{i,j} is the number of edges from v_i to v_j. As with the incidence matrix of a design, this will turn out to be much more than mere bookkeeping. Strictly speaking A depends not just on G but on the labeling, but different labelings yield similar matrices P^{-1} A P for some permutation matrix P (more on this below). Also: The entries a_{i,j} are nonnegative integers (this might change for weighted graphs, but we're not going in that direction). No loops: the diagonal entries a_{i,i} are all zero. (In particular the trace of A is zero.) Edges are undirected: A is symmetric. So we can use results special to real symmetric matrices, notably the decomposition of R^n as an orthogonal direct sum of eigenspaces. No multiple edges: each a_{ij} is either 0 or 1. Since we use {1,2,...,n} to index both vertices and rows/columns, it's useful to think of the (i,j) entry a_{i,j} as being really the (x,y) entry where x = v_i, y = v_j. This makes it canonical: A is really a linear operator (self-transformation) on a vector space R^V with an orthogonal basis e_x (x in V), and it takes e_x to the sum of e_y over y in the neighborhood of x -- morally speaking it takes x to G(y). For example, the degree of x is the inner product of Ae_x with the all-1's vector \j, which (since A is symmetric) is also the inner product of e_x in A\j. A graph is regular of degree k iff A\j=k\j, i.e. \j is a k-eigenvector. The adjacency matrix of the complementary graph G@ is J-I-A (where J is the all-1's square matrix of order n, as before). So what does A^2 do? It takes e_x to the sum of e_y, and then each e_y to a sum of its e_z's; so the (x,z) entry is the number of paths (x,y,z) of length 2 (note that x=z is possible). Likewise the (x,x') entry of A^3 is the number of length-3 paths (x,y,z,x') (again with repeats and trackbacks allowed), etc. For that matter the (x,y) entry of A^1 is the number of length-1 paths, i.e. the number of edges {x,y}; and the (x,y) entry of A^0 is 1 if x=y and 0 else, so it does behave like the number of "length-0 paths"... For an undirected graph, the length-m paths from x to x' are in bijection with the length-m paths from x' to x (just retrace the path backwards), so A^m is symmetrical, as it should be since A is. Now we know from linear algebra that we can analyze A^k via the "spectrum" (i.e. eigenvalues) and eigenspaces of A. This is one reason why the adjacency matrix and its spectrum is such an important graph invariant. [Note that the spectrum really is an invariant: reindexing the vertices changes A to a similar matrix but does not change the spectrum; equivalently, it's just a different indexing of the coordinates for the linear operator on R^V.] A further example: the diagonal entries of A^m are the number of closed paths (x_1,x_2,...,x_m) of length m going through a given vertex x_1; thus the sum is the number of closed paths with no restriction on the x_m (and with a choice of initial point x_1 and direction, e.g. each pentagon counts 10 times). But the sum of the diagonal entries of a matrix is its trace, and the trace of A^m is the sum of the m-th powers of its eigenvalues counted with multiplicity. There's even a remarkably fruitful analogy with the spectrum of the Laplacian in analysis (the motivation is that the Laplacian can be visualized as taking x to a(x)-x, where a(x) is the average of an infinitesimal neighborhood of x); this connection has been productive in both directions, with ideas and results in graph theory suggesting analogues in analysis -- some proved, some open -- and vice versa. === Back to the adjacency of a graph and its spectrum. It's particularly nice when A is a strongly regular graph. We already saw that it's regular of degree k iff A\j=k\j; as happened in Chapter 1, this is tantamount to AJ=KJ, and since here A and J are symmetrical we deduce (p.37, 2.14) A J = J a = k J. If it's strongly regular then we also get to describe A^2: its (x,z) entry is the number of paths (x,y,z), which is just the number of common neighbors y of x and z. And we already know what that is: k if x=z; \lam if x is adjacent to z; and \mu if x is disjoint from z. This means (p.37, 2.13) A^2 = k I + \lam A + \mu (J-I-A). Conversely a graph is strongly regular iff it satisfies (2.13) and (2.14) (and is neither complete nor null). Applying (2.13) to \j yields k^2 = k + \lam k + \mu (n-k-1), i.e. k (k-\lam-1) = \mu (n-k-1) as seen already (2.6). Since \j is an eigenvector and A is symmetric, A acts on the orthogonal complement of \j (recall the usual argument: if = 0 then = = 0 because A\j is a multiple of \j). This orthogonal complement is sometimes denoted R^V_0: it's the space of vectors in R^V whose coordinates sum to zero. What could be the eigenvalues of this operator on R^V_0? Since the letter \lam is already in use, let \rho be an eigenvalue, and u a (nonzero) eigenvector, so Au = \rho u. Since R^V_0 is the kernel of J we have Ju=0, so (2.13) yields \rho^2 u = (k + \lam \rho - \mu(\rho+1)) u and since u is nonzero this is equivalent to the quadratic equation \rho^2 - (\lam-mu) h + (\mu-k) = 0. let r and s be the roots. Note that they are always real -- as they must be for a self-adjoint transformation -- because r s = \mu - k <= 0. Moreover they're distinct, else \lam=\mu=0 and we have a null graph. So we may, and always do without loss of generality, order them so r>s: r = (\lam - \mu + \sqrt(D)) / 2, s = (\lam - \mu - \sqrt(D)) / 2. where D = (\lam-\mu)^2 + 4 (k-\mu). Let f and g be the multiplicities. We compute them by solving linear equations: since R^V_0 is the direct sum of the r- and s-eigenspaces, we compare dimensions to get f + g = n - 1; and since A has trace zero, fr + gs + k = 0 (remember that A also has the 1-dimensional k-eigenspace spanned by j). These equations are independent because r and s are distinct, and we find an elementary if somewhat offputting formula (bottom of page 37): f, g = (1/2) ( n - 1 + \pm ((n-1)(\mu-\lam) - 2k) / sqrt(D) ) with D as above. Theorem (p.37, 2.16 = integrality condition) f and g are nonnegative integers. [check that this is the case in each of our arsenal of examples so far. How are the eigenvalues r,s and multiplicities f,g of the complementary graph related with those of G?] It *almost* follows that D is a square; that is already a strong condition, and already implies that f and g are rational -- which is why Theorem 2.16 is sometimes called the rationality condition. Why almost? Because it could be that the numerator vanishes, i.e. that (n-1)(\mu-\lam) = 2k ! This can indeed happen, and already is the case for the pentagon with (n,k,\lam,\mu)=(5,2,0,1) (and indeed for all Paley graphs, of which the pentagon is the first example). In that case we say G is of _Type I_. We then have n = 1 + 2k/(\mu-\lam) but also (since G is not complete) n > 1 + k so the denominator \mu - \lam is positive but less than 2. Hence \lam = \mu - 1 and n = 1+2k; the condition k (k-\lam-1) = \mu (n-k-1) then yields k = 2 \mu so Type I <==> (4 \mu + 1, 2 \mu, \mu - 1, \mu) (and D = n = 4\mu+1, f=g=2\mu), as with Paley. Similar to BRC, we then have (but don't prove) a further condition, here due to Van Lint and Seidel 1966, that forces n=4\mu+1 to be a sum of two squares -- so for n<45 we get 5, 9, 13, 17, 25, 29, 37, 41, all prime powers so there are Paley graphs, while 21 and 33 are excluded; but 45 is allowed, and -- unlike the situation with finite projective planes -- actually arises (Mathon 1975). If not Type I then D is a square; such graphs are said to be of Type II. These are not mutually exclusive: already L_2(3) = P(9) has both properties (in general Type I is also Type II iff n is a square).