# Orthogonal similarity of adjacency matrices of graphs which are cospectral and have a common equitable partition

Let $$G$$ and $$H$$ be two undirected graphs of the same order (i.e., they have the same number of vertices). Denote by $$A_G$$ and $$A_H$$ the corresponding adjacency matrices. Furthermore, denote by $$\bar G$$ and $$\bar H$$ the complement graphs of $$G$$ and $$H$$, respectively.

When $$G$$ and $$H$$ are cospectral, and $$\bar G$$ and $$\bar H$$ are cospectral, it is known (see e.g., Theorem 3 in Van Dam et al. [1]) that there exists an orthogonal matrix $$O$$ such that $$A_G\cdot O=O\cdot A_H$$ and furthermore, $$O\cdot \mathbf{1}=\mathbf{1}$$, where $$\mathbf{1}$$ denotes the vector consisting of all ones.

Suppose that, in addition, $$G$$ and $$H$$ have a common equitable partition. That is, there exist partitions $${\cal V}=\{V_1,\ldots,V_\ell\}$$ of the vertices in $$G$$ and $${\cal W}=\{W_1,\ldots,W_\ell\}$$ of the vertices in $$H$$ such that (i) $$|V_i|=|W_i|$$ for all $$i=1,\ldots,\ell$$; and (ii) $$\text{deg}(v,V_j)=\text{deg}(w,W_j)$$ for any $$v$$ in $$V_i$$ and $$w$$ in $$W_i$$, and this for all $$i,j=1,\ldots,\ell$$.

Question:

• What extra structural conditions on the orthogonal matrix $$O$$, apart from $$A_G\cdot O=O\cdot A_H$$ and $$O\cdot \mathbf{1}=\mathbf{1}$$, can be derived when $$G$$ and $$H$$ are cospectral, have cospectral complements, and have a common equitable partition?

I am particularly interested in showing that one can assume that $$O$$ is block structured according to the partitions involved. That is, if $$\mathbf{1}_{V_i}$$ and $$\mathbf{1}_{W_i}$$ denote the indicator vectors of the (common) partitions $${\cal V}$$ and $${\cal W}$$, respectively, can $$O$$ be assumed to satisfy $$\text{diag}(\mathbf{1}_{V_i})\cdot O=O\cdot \text{diag}(\mathbf{1}_{W_i}),$$ for $$i=1,\ldots,\ell$$? Here, $$\text{diag}(v)$$ for a vector $$v$$ denotes the diagonal matrix with $$v$$ on its diagonal.

UPDATE

Since my posting, the following came to my attention:

• Cospectral graphs with a common equitable partition necessarily have cospectral complements. So, the latter assumption can be removed. Indeed, graphs with a common equitable partition are easily seen to have the same number of walks of any length. When, in addition the graphs are cospectral, Theorem 3 in [1] and Theorem 1.3.5 in [2] imply that they must have cospectral complements.
• Graphs $$G$$ and $$H$$ for which there exists an orthogonal matrix $$O$$ such that (i) $$A_GO=OA_H$$; (ii) $$O\mathbf{1}=\mathbf{1}$$; and (iii) $$\mathsf{diag}(\mathbf{1}_{V_i})O=O\mathsf{diag}(\mathbf{1}_{W_i})$$ for $$i=1,\ldots,\ell$$, where characterised [3] as graphs that are cospectral wrt to the WL$$_1$$-closure of the adjacency matrices. Here, the $$\mathsf{WL}_1$$-closure can be considered to be an extension of the generalized adjacency matrix. It can be inductively defined by means of symbolic expressions $$e$$, as follows.
• basic expressions $$e=X$$, $$e=I$$, $$e=J$$ with $$X$$ a matrix variable, $$I$$ identity matrix, $$J$$ the all-ones matrix (all of the same dimension) are in $$\mathsf{WL}_1(X)$$;
• if $$e_1$$ and $$e_2$$ are expressions in $$\mathsf{WL}_1(X)$$, then also $$e_1+e_2$$, $$e_1\cdot e_2$$, $$e_1^*$$, and $$a\cdot e_1$$ for scalars $$a\in\mathbb{C}$$, are in $$\mathsf{WL}_1(X)$$;
• if $$e$$ is an expression in $$\mathsf{WL}_1(X)$$, then also $$\mathsf{diag}(e(X)\mathbf{1})$$ is in $$\mathsf{WL}_1(X)$$.

Then $$G$$ and $$H$$ are cospectral wrt $$\mathsf{WL}_1(A_G)$$ and $$\mathsf{WL}_1(A_H)$$ when $$e(A_G)$$ and $$e(A_H)$$ are cospectral for any expression $$e$$ in $$\mathsf{WL}_1(X)$$. (In particular, they will be cospectral wrt their adjacency matrices, adjacency matrices of their complements, Seidel matrix, Laplacian, normalized Laplacian, ...)

It is shown (Lemma 9 in [3]) that when $$G$$ and $$H$$ are cospectral wrt $$\mathsf{WL}_1(A_G)$$ and $$\mathsf{WL}_1(A_H)$$ then $$G$$ and $$H$$ are cospectral (trivial) and $$G$$ and $$H$$ have a common equitable partition.

Revised question My original question thus asked whether the converse also holds. That is, are any two cospectral graphs with a common equitable partition necessarily cospectral wrt to the WL$$_1$$-closure of the adjacency matrices? If not, what is a counter example?

As a final remark, Theorem 6.2 in [4] seems to imply that cospectrality and having a common equitable partition is equivalent to the existence of an orthogonal matrix $$O$$ such that $$A_GO=OA_H$$, $$O=S+T$$ for a doubly stochastic matrix $$S$$, $$A_GS=SA_H$$, and such that for $$i=1,\ldots,\ell$$,

• $$\mathbf{1}_{V_i}=S\mathbf{1}_{W_i}$$, $$\mathbf{1}^t_{V_i}S=\mathbf{1}^t_{W_i}$$
• $$\mathbf{0}=T\mathbf{1}_{W_i}$$, $$\mathbf{0}=\mathbf{1}^t_{V_i}T$$.

Hence, the orthogonal matrix $$O$$ can be assumed to satisfy $$\mathbf{1}_{V_i}=O\mathbf{1}_{W_i}$$ for $$i=1,\ldots,\ell$$. This is a weaker condition than $$\mathsf{diag}(\mathbf{1}_{V_i})O=O\mathsf{diag}(\mathbf{1}_{W_i})$$.

[1] Cospectral graphs and the generalized adjacency matrix, E.R. van Dam, W.H. Haemers, J.H. Koolen. Linear Algebra and its Applications 423 (2007) 33–41. https://doi.org/10.1016/j.laa.2006.07.017

[2] Dragoš M. Cvetković, Peter Rowlinson, and Slobodan Simić. An Introduction to the Theory of Graph Spectra. London Mathematical Society Student Texts. Cambridge University Press, 2009. https://doi.org/10.1017/CBO9780511801518.

[3] Mario Thüne. Eigenvalues of matrices and graphs. PhD thesis, University of Leipzig, 2012. http://ul.qucosa.de/api/qucosa%3A12068/attachment/ATT-0/

[4] Ada Chan and Chris D. Godsil. Symmetry and eigenvectors. In Graph symmetry (Montreal, PQ, 1996), volume 497 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pages 75–106. Kluwer Acad. Publ., Dordrecht, 1997. https://doi.org/10.1007/978- 94- 015- 8937- 6_3.

• Perhaps a good starting point could be to find two graphs of the same order that are co-spectral and have a common equitable partition, yet are not cospectral with regards to their (signed) Laplacians or Seidel matrix? This would suffice to distinguish the two settings mentioned above. – Sirolf Jun 19 '19 at 15:00
• I posted the previous comment as a new question. See link – Sirolf Jun 21 '19 at 12:38