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 [3], and most, if not all, of the theory given below can be found there. Earlier, Hammersley [11] 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 + µ(J–I–A).
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 = J–I, 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 J–I–A satisfies the definition. If the first one has parameters v, k, t, λ, µ then its complement has parameters v, v–k–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.
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 J–I–A 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 J–I–A, 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.
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.
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 = (J–B)/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.
We already saw that 0 < µ ≤ t. (If µ = 0 then A = J–I, 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(k–t–1) ≤ µ–λ ≤ 2(k–t). (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(k–t) paths that cannot be reversed. The other inequality follows similarly, or by applying the first to the complementary graph.)
From the spectrum we can draw one more useful conclusion. (Klin et al. [19]) 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 k–t). Since Aa has a nonzero real eigenvalue, namely k–t, 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.