I am working on a problem in matrix analysis and I am looking for certain types of normal matrices. I suspect that these "special" normal matrices arise as adjacency matrices of certain graphs. My question, then, is what types of graphs have normal adjacency matrices?

$\begingroup$ The adjacency matrix $A$ of any undirected graph is symmetric. Therefore, $A = A^{T}$ and $AA^{T} = A^{T}A$ i.e A is normal. $\endgroup$– hbmDec 14, 2013 at 3:00

$\begingroup$ What if the graph is a directed graph? $\endgroup$– Mustafa SaidDec 14, 2013 at 3:01

$\begingroup$ Maybe you could look at some sample of graphs that arise from the type of matrices you are studying and then recognize the class of graph at play. Sometimes it is easier to recognize a class of graph by looking at sample graphs. $\endgroup$– hbmDec 15, 2013 at 20:46

$\begingroup$ @MustafaSaid Did you ever manage to get a good answer ? I am also interested in this question $\endgroup$– Sandeep SilwalJan 5, 2018 at 16:24

$\begingroup$ @SandeepSilwal I never got a got a good answer. $\endgroup$– Mustafa SaidJan 11, 2018 at 7:56
5 Answers
I think there are problems with the accepted answer.
As there, a directed graph is balanced if the indegree of each vertex is equal to its outdegree. A directed graph with adjacency matrix $A$ is balanced if and only if the diagonal entries of $AA^TA^TA$ are zero, and so normal directed graphs are balanced. The cited article in the second paragraph above refers to a result of Wu and Chua, proving that if the Laplacian of a directed graph is normal then the directed graph is balanced. (In fact the obvious variant of the proof for adjacency matrices works.)
On five vertices, my sage calculations found 111 balanced directed graphs from a total of 9608. Of these 111, I found that 49 were normal and 47 were Laplacian normal. So balanced does not imply normal.
All Laplacian normals on five vertices were adjacency normal. With obvious notation, my calculations give that if $DA$ is normal then $$ A^TAAA^T = D(AA^T)  (AA^T)D. $$ I cannot get from here to the conclusion that Laplacian normal implies normal, but this might just be stupidity on my part.
Edit: Krystal Guo went through the directed graphs on six vertices and found four directed graphs that are Laplacian normal but not normal. The first has adjacency matrix $$ \left(\begin{array}{rrrrrr} 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \end{array}\right) $$

$\begingroup$ Chris, thank you for your post. I may have prematurely accepted the first answer. The graphs I am looking for have an even number of vertices. I am highly interested in your calculations but you used an odd number of vertices (5). If the sage calculations were done with 6 vertices I would like to look at the values of the operator norms of the normal matrices. $\endgroup$ Dec 14, 2013 at 18:44

1$\begingroup$ Mustafa: There are 9608 directed graphs on 5 vertices and 1540944. So it would be possible to get the normal digraphs on 6 vertices, but would take more time than I have to devote to it. $\endgroup$ Dec 15, 2013 at 2:02

2$\begingroup$ @Chris: Doesn't the $(i,j)$ entry of $AA^T$ count the number of common outneighbor of $i$ and $j$ and the $(i,j)$ entry of $A^TA$ count the number of common inneighbor of $i$ and $j$? $\endgroup$– hbmDec 15, 2013 at 2:43


1$\begingroup$ Just for future reference, the “accepted answer” mentioned in this post refers to the one by Felix Goldberg, which has been unaccepted in the meantime. $\endgroup$ May 13 at 9:56
kregular directed ring graphs, they have circulant adjacency, are normal because of their rotational symmetry.

3$\begingroup$ Would you expand this answer and provide references to it? $\endgroup$ Dec 18, 2018 at 22:57

$\begingroup$ I'm guessing you mean vertexregular graphs which have a distinguished transitive directed cycle, which are normal because both them and their transpose can be expressed as polynomials of the "rotation matrix" (which has 1s in the superdiagonal and bottom left corner)? $\endgroup$ Dec 19, 2018 at 2:20
This turns out to be more complicated that I first thought it'd be. Apparently the graphs you are asking about are usually called normal digraphs and a proper characterization does not seem to be known. This recent paper treats characterization in the special case of Cayley digraphs and also refers to previous work on other cases (alas, almost all of it is in notimmediatelyaccessibleonline places).
There is case, I think, that is easy to work out: graph where indegrees equals\ the outdegrees. The writeup here indicates (once again, based on a 2005 paper I can't access here and now) that such graphs (called balanced) have a normal Laplacian matrix, which is easily seen to be equivalent to having a normal adjacency matrix.
For $n=1,\ldots,8$, the number of isomorphism classes of normal loopfree digraphs is apparently 1, 2, 5, 15, 49, 232, 1413, 14961.
If loops are allowed, the counts for $n=1,\ldots,8$ are 2, 6, 22, 103, 628, 5764, 85864, 2302890.
Neither sequence is in OEIS.
For all 01 matrices, rather than isomorphism classes, the numbers are in https://oeis.org/A055547 .
(This characterisation is already given here; It is added as cwanswer for better visibility).
Quote from the paper Jørgensen, Normally Regular Digraphs (2014)
(The $(i, j)$ entry of $AA^t$ (respectively $A^tA$) is the number of common outneighbours (respectively inneighbours) of $x_i$ and $x_j$).
We say that a digraph is normal if its adjacency matrix $A$ is normal, i.e., if $AA^t = A^tA$. It follows that a digraph is normal if and only if for any two (not necessarily distinct) vertices $x$ and $y$, the number of common outneighbours of $x$ and $y$ is equal to the number of common inneighbours of $x$ and $y$.

$\begingroup$ Sorry, this is already wellknown here (see comments on Godsil's answer by hbm and Godsil himself). $\endgroup$ May 13 at 9:37