The Automorphism Group of the Spectral Incidence Graph over Finite Fields

Abstract

Let ${\mathbb{F}}_q$ be a finite field with $q$ elements and let ${\mathbb{V}}_0={\mathbb{F}}_q^n$ be the $n$-dimensional vector space over ${\mathbb{F}}_q$, for an integer $n\ge 2$. We introduce the \emph{spectral incidence graph} of ${\mathbb{V}}_0$, denoted by $\mathbf{SIG}({\mathbb{V}}_0)$, a bipartite graph whose two vertex classes consist of the one-dimensional subspaces of $M_n({\mathbb{F}}_q)$ generated by matrices having at least one eigenvector in ${\mathbb{V}}_0$, and the one-dimensional subspaces of ${\mathbb{V}}_0$ (i.e. the projective space ${\mathbb{P}}^{n-1}({\mathbb{F}}_q)$), respectively. A matrix vertex $⟨M⟩$ and a point vertex $⟨v⟩$ are adjacent if and only if $v$ is an eigenvector of $M$. We determine several structural parameters of $\mathbf{SIG}({\mathbb{V}}_0)$, including its twin classes, connectivity, domination number, diameter, vertex degrees, and number of edges. We show that every automorphism of $\mathbf{SIG}({\mathbb{V}}_0)$ preserves the two parts of the bipartition. We prove that the kernel of the induced action of $Aut(\mathbf{SIG}({\mathbb{V}}_0))$ on the projective part ${\mathbb{P}}^{n-1}({\mathbb{F}}_q)$ is precisely ${\prod }_{\mathcal{C}\in \mathcal{T}}{S}_{\mathcal{C}}$, where $\mathcal{T}$ denotes the set of twin classes of matrix vertices and $S_{\mathcal{C}}$ is the symmetric group on $\mathcal{C}$. We then determine the full automorphism group of $\mathbf{SIG}({\mathbb{V}}_0)$. For $n\ge 3$, we prove that $Aut(\mathbf{SIG}({\mathbb{V}}_0))\cong \left({\prod }_{\mathcal{C}\in \mathcal{T}}{S}_{\mathcal{C}}\right)⋊P\Gamma L_n(q)$. For $n=2$, we obtain $Aut(\mathbf{SIG}({\mathbb{V}}_0))\cong \left({\prod }_{i=1}^{q+1}{S}_q\times {\prod }_{i=1}^{\frac{q(q+1)}{2}}{S}_q\right)⋊S_{q+1}.$

25 pages Revised version. The incorrect Theorem 2.5 has been removed and the corresponding result has been reformulated and proved independently. The manuscript has also been carefully revised for mathematical accuracy and clarity