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 '13 at 3:00

$\begingroup$ What if the graph is a directed graph? $\endgroup$– Mustafa SaidDec 14 '13 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 '13 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 '18 at 16:24

$\begingroup$ @SandeepSilwal I never got a got a good answer. $\endgroup$– Mustafa SaidJan 11 '18 at 7:56
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 '13 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 '13 at 2:02

$\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 '13 at 2:43


$\begingroup$ @hbm: Yes. This gives a characterization of normality, but it does not seem to help much. $\endgroup$ Dec 15 '13 at 16:33
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.
kregular directed ring graphs, they have circulant adjacency, are normal because of their rotational symmetry.

2$\begingroup$ Would you expand this answer and provide references to it? $\endgroup$ Dec 18 '18 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 '18 at 2:20