Next Previous Contents

## 1.Definition

A directed strongly regular graph (dsrg) is a (0,1) matrix A with 0's on the diagonal such that the linear span of I, A and J is closed under matrix multiplication. This concept was defined by Duval , and most, if not all, of the theory given below can be found there. Earlier, Hammersley  studied the "love problem", one version of which is a special case of the problem considered here.

One defines (integral) parameters v, k, t, λ, µ by: A is a matrix of order v, and AJ = JA = kJ, and A2 = tI + λA + µ(JIA).

In case A is symmetric, we have a strongly regular graph, and that case is excluded here. This means that we require t < k.

In particular, we exclude the case A = JI, so that the algebra spanned by I, A and J is 3-dimensional. It follows that A has precisely 3 distinct eigenvalues, say k, r, s, with multiplicities 1, f and g, respectively.

These dsrg's come in complementary pairs: together with A also JIA satisfies the definition. If the first one has parameters v, k, t, λ, µ then its complement has parameters v, vk–1, v–2k–1+t, v–2k–2+µ, v–2k+λ. In the tables below we give complementary pairs together.

For a given set of parameters, dsrg's also come in pairs: together with A also its transpose satisfies the definition.

## 1.1Hadamard matrices

We shall exclude one other case, namely that where t = 0. The theory is as follows.

First of all, the eigenvalues r, s different from k are roots of x2 + (µλ)x + µt = 0 so are algebraic integers. Next, if their multiplicities f, g differ then we can solve r, s from r+s = λµ and f.r + g.s = –k to find that r and s are rational numbers, and therefore integers. At least one is negative since A has trace 0. But JIA has eigenvalues v–1–k, –1–s, –1–r, and also has a negative eigenvalue, so we may assume that r is nonnegative and s is negative. In particular, r and s differ, some linear combination of A, I and J is a projection, and A is diagonalizable. Moreover, r.s is nonpositive, so µ is not larger than t. In particular, t is nonzero.

Remains the case where f = g = (v–1)/2. From (λµ)(v–1)/2 = –k it follows that k = (v–1)/2 and µ = λ+1. From k2 = t + λ.k + µ(v–1–k), i.e., k2 = t + k(2µ–1), it follows that k divides t. But we already excluded t = k, so t = 0 and k = 2µ–1. The graph is a tournament: the transpose of A is JIA, and bordering the (1,–1) matrix J–2A first with a first column of all –1's and then with a top row of all 1's we find a Hadamard matrix H of order 4µ that has 1's on the diagonal and is skew symmetric off-diagonal. Conversely, any such H gives rise to such A.

## 1.2The 2-dimensional case

An important subclass is that where already the linear span of A and J is closed under matrix multiplication. This happens when t = µ, and then A2 = (λµ)A + µ.J so that the eigenvalues of A are k, λµ, and 0. Conversely, when A has eigenvalue 0, we are in this case. Put d=µλ. Then the multiplicities of the eigenvalues k, –d, 0 are 1, k/d and v–1–k/d respectively.

## 1.3The 1-dimensional case

If A is a 0-1 matrix, then B = J – 2A is a ±1 matrix, and it is possible that the 1-space generated by B is closed under matrix multiplication. This happens when t = µ and v–4k+4t = d (with d as in above - clearly this is a subcase of the 2-dimensional case). Conversely, if B is a ±1 matrix with constant row sums and 1's on the diagonal such that B2 is a multiple of B, then A = (JB)/2 is the adjacency matrix of a dsrg in this subcase. Note that the set of such ±1 matrices B is closed under taking tensor products.

## 1.4Combinatorial parameter conditions

We already saw that 0 < µt. (If µ = 0 then A = JI, which was excluded.) Also, that 0 ≤ λ < t < k < v. (Indeed, λ < t, since λ+1–t = (r+1)(s+1) ≤ 0.)

Duval gave one more condition, and parameter sets violating it will not be mentioned in the table. We have –2(kt–1) ≤ µλ ≤ 2(kt). (Indeed, consider a directed edge from x to y. Paths of length 2 from x to y contribute to λ, paths in the opposite direction to µ. Thus, the difference between µ and λ is counted by the at most 2(kt) paths that cannot be reversed. The other inequality follows similarly, or by applying the first to the complementary graph.)

## 1.5No Abelian Cayley graphs

From the spectrum we can draw one more useful conclusion. (Klin et al. ) Let us write A = As + Aa where As is the symmetric 0-1 matrix (with row sums t) describing adjacency via an undirected edge, and Aa is the 0-1 matrix describing the remaining, directed, edges (with row sums kt). Since Aa has a nonzero real eigenvalue, namely kt, and its square has trace zero, Aa must also have non-real eigenvalues. On the other hand, both A and As only have real eigenvalues. It follows that A and As cannot be diagonalised simultaneously, so that As and Aa do not commute. But then these matrices do not describe differences in the same Abelian group. Thus, a directed strongly regular graph cannot be a Cayley graph of an Abelian group.

Next Previous Contents