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.

[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