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$
$\endgroup$
5
asked Dec 14, 2013 at 2:42
-
$\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$– hbmCommented Dec 14, 2013 at 3:00
-
$\begingroup$ What if the graph is a directed graph? $\endgroup$– Mustafa SaidCommented Dec 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$– hbmCommented Dec 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 SilwalCommented Jan 5, 2018 at 16:24
-
$\begingroup$ @SandeepSilwal I never got a got a good answer. $\endgroup$– Mustafa SaidCommented Jan 11, 2018 at 7:56
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
6
I think there are problems with the accepted answer.
As there, a directed graph is balanced if the in-degree of each vertex is equal to its out-degree. A directed graph with adjacency matrix $A$ is balanced if and only if the diagonal entries of $AA^T-A^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 $D-A$ is normal then $$ A^TA-AA^T = D(A-A^T) - (A-A^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) $$
answered Dec 14, 2013 at 15:44
-
$\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$ Commented 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$ Commented Dec 15, 2013 at 2:02
-
2$\begingroup$ @Chris: Doesn't the $(i,j)$ entry of $AA^T$ count the number of common out-neighbor of $i$ and $j$ and the $(i,j)$ entry of $A^TA$ count the number of common in-neighbor of $i$ and $j$? $\endgroup$– hbmCommented Dec 15, 2013 at 2:43
-
$\begingroup$ @Chris Godsil, thank you very much. $\endgroup$ Commented Dec 15, 2013 at 11:28
-
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$ Commented May 13, 2023 at 9:56
$\begingroup$
$\endgroup$
2
k-regular 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$ Commented Dec 18, 2018 at 22:57
-
$\begingroup$ I'm guessing you mean vertex-regular 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$ Commented Dec 19, 2018 at 2:20
$\begingroup$
$\endgroup$
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 not-immediately-accessible-online places).
There is case, I think, that is easy to work out: graph where in-degrees equals\ the out-degrees. The write-up 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.
answered Dec 14, 2013 at 10:49
$\begingroup$
$\endgroup$
For $n=1,\ldots,8$, the number of isomorphism classes of normal loop-free 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 0-1 matrices, rather than isomorphism classes, the numbers are in https://oeis.org/A055547 .
answered May 13, 2023 at 14:03
$\begingroup$
$\endgroup$
1
(This characterisation is already given here; It is added as cw-answer 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 out-neighbours (respectively in-neighbours) 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 out-neighbours of $x$ and $y$ is equal to the number of common in-neighbours of $x$ and $y$.
-
$\begingroup$ Sorry, this is already well-known here (see comments on Godsil's answer by hbm and Godsil himself). $\endgroup$ Commented May 13, 2023 at 9:37