be a graph with the vertex set $[n]$ and let $\sigma$ be a permutation in $S_n$. Then $\sigma$ is an automorphism of $G$ if and only if every eigenspace of ${\mathbf{A}( G )}$ is $\sigma$-invariant.

Recall that the $n$-dimensional vector space $\operatorname{\mathbb{R}}^n$ is endowed with the [*inner product*]{} $\langle\cdot,\cdot\rangle$ such that $\langle\pmb{u},\pmb{v}\rangle=\pmb{v}^t\pmb{u}=\sum_{i=1}^n u_i\cdot v_i$ for any vectors $\pmb{u}=(u_1,\ldots,u_n)^t$ and $\pmb{v}=(v_1,\ldots,v_n)^t$ in $\operatorname{\mathbb{R}}^n$. Since the matrix $\mathbf{A}(G)$ is symmetric, there is an orthonormal basis of $\operatorname{\mathbb{R}}^n$ consisting of eigenvectors of ${\mathbf{A}( G )}$ according to the real spectral theorem (see [@Axler] for details).

We begin with the necessity of the assertion. In accordance with the relation (\[Equation00\]), $\sigma$ is an automorphism of $G$ if and only if $\mathbf{P}_{\sigma}^t\mathbf{A}\mathbf{P}_{\sigma}=\mathbf{A}$, so for any eigenvector $\pmb{v}$ of $\mathbf{A}$ corresponding to some eigenvalue $\lambda$, $$\mathbf{P}_{\sigma}^t\mathbf{A}\mathbf{P}_{\sigma}\pmb{v}=\mathbf{A}\pmb{v}=\lambda\pmb{v}.$$ Consequently, $\mathbf{A}\mathbf{P}_{\sigma}\pmb{v}=\lambda\mathbf{P}_{\sigma}\pmb{v}$, which means $\mathbf{P}_{\sigma}\pmb{v}$ is also an eigenvector of $\mathbf{A}$ corresponding to $\lambda$, and thus every eigenspace of $\mathbf{A}$ is $\mathbf{P}_{\sigma}$-invariant.

Conversely, let us select an orthonormal basis $\pmb{x}_1,\ldots,\pmb{x}_n$ of $\operatorname{\mathbb{R}}^n$, consisting of eigenvectors of $\mathbf{A}$ such that $\mathbf{A}\pmb{x}_i = \lambda_i\pmb{x}_i$, $i=1,\ldots,n$. Since every eigenspace of $\mathbf{A}$ is $\mathbf{P}_{\sigma}$-invariant, for every $\pmb{x}_i$ we have $$\mathbf{A}\mathbf{P}_{\sigma}\pmb{x}_i
 = \lambda_i\mathbf{P}_{\sigma}\pmb{x}_i
 = \mathbf{P}_{\sigma} \lambda_i\pmb{x}_i
 =\mathbf{P}_{\sigma}\mathbf{A}\pmb{x}_i.$$ Consequently, for an arbitrary vector $\pmb{v}=\sum_{i=1}^na_i\pmb{x}_i$ in $\operatorname{\mathbb{R}}^n$, 