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
[2],
and most, if not all, of the theory given below can be found there.
Earlier, Hammersley
[10]
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 *A*^{2} = *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*–2*k*–1+*t*,
*v*–2*k*–2+*µ*,
*v*–2*k*+*λ*.
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
*x*^{2} + (*µ*–*λ*)*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 *k*^{2} = *t* + *λ*.*k* +
*µ*(*v*–1–*k*), i.e.,
*k*^{2} = *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*–2*A* 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
*A*^{2} = (*λ*–*µ*)*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* – 2*A*
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*–4*k*+4*t* = *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 *B*^{2} 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.
[18])
Let us write *A* = *A*_{s} + *A*_{a}
where *A*_{s} is the symmetric 0-1 matrix
(with row sums *t*) describing adjacency via an undirected edge,
and *A*_{a} is the 0-1 matrix describing the remaining,
directed, edges (with row sums *k*–*t*).
Since *A*_{a} has a nonzero real eigenvalue, namely
*k*–*t*, and its square has trace zero, *A*_{a}
must also have non-real eigenvalues. On the other hand, both *A* and
*A*_{s} only have real eigenvalues. It follows that
*A* and *A*_{s} cannot be diagonalised simultaneously,
so that *A*_{s} and *A*_{a} 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