This problem is at the interface of matrix algebra and spectral graph theory.

Let $\mathbf{S}$ be a symmetric $n\times n$ matrix, with positive entries $S_{ij}\geq 0$, and $\mathbf{D} = \mathrm{diag}(\mathbf{S})$ denote the extracted diagonal of $\mathbf{S}$. This would typically be the signless Laplacian of a graph.

Let $\mathcal{E}(\mathbf{S}) = \left\{\mathbf{U} \in \mathcal{SO}(n) \; \left| \;\mathbf{S}' = \mathbf{U}^T \mathbf{SU}, \; S'_{ij} \geq 0, \; \mathbf{D}' = \mathrm{diag}(\mathbf{S}') = \mathbf{D}\right. \right\}.$

In other words, given a symmetric matrix $\mathbf{S}$ with positive entries, $\mathcal{E}(\mathbf{S})$ is the set of special orthogonal matrices $\mathbf{U} \in \mathcal{SO}(n)$ such that the orthogonal transform of $\mathbf{S}$,

$\mathbf{S}' = \mathbf{U}^T \mathbf{SU},$

has all positive elements $S'_{ij} \geq 0$, and has the same diagonal entries as $\mathbf{S}$

$\mathbf{D}' = \mathrm{diag}(\mathbf{S}') = \mathbf{D}$.

Under which condition on $\mathbf{S}$ is the set $\mathcal{E}$ reduced to the singleton identity $\left\{\mathbf{I}_n\right\}$?

This would mean that the matrix $\mathbf{S}$ is entirely determined by any orthogonally similar form (and in particular, the diagonalized form, through the spectral theorem) and its diagonal entries.

Equivalently, under which conditions is a weighted graph entirely determined by the spectrum of its signless Laplacian and the degrees of its nodes?

For example, it would seem to me that having distinct node degrees for a connected weighted graph could be a lead.

Any ideas or related articles are welcome!

  • $\begingroup$ Is $S$ given or not? The second paragraph seems to suggest that $S$ is given, but your definition of $\mathcal E$ seems to suggest that $S$ is dependent on $U$. $\endgroup$ – user1551 Jul 20 '16 at 15:25
  • $\begingroup$ @user1551 it seems clear to me that $S$ is given. What makes you think that $S$ depends on $U$? $\endgroup$ – Omnomnomnom Jul 20 '16 at 15:35
  • $\begingroup$ @Omnomnomnom If $S$ is given, to write $\color{red}{\exists} S'=U^TSU$ would sound a bit odd because $S'$ is completely determined by $U$ and $S$. The OP probably means $$\mathcal E=\{U\in SO(n):\ S'=U^TSU\ge0,\, \operatorname{diag}(S')=\operatorname{diag}(S)\},$$ but I find their current definition of $\mathcal E$ confusing. $\endgroup$ – user1551 Jul 20 '16 at 15:45
  • 1
    $\begingroup$ $\mathbf{S}$ is given, and we want to find $\mathbf{U}$ depending on $\mathbf{S}$, which belongs to $\mathcal{E}(\mathbf{S})$. I have edited the post to make it clearer. $\endgroup$ – user288227 Jul 20 '16 at 15:55
  • 1
    $\begingroup$ In the definition of $\mathcal{E}$, I meant to say that there exists a matrix $\mathbf{S}' $ which is orthogonally similar to $\mathbf{S}$, which has positive entries and the same diagonal as $\mathbf{S}$. I have also edited the definition of $\mathcal{E}$. $\endgroup$ – user288227 Jul 20 '16 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.