(DRAFT) Graphs with integral spectra

Which graphs have integral spectrum?
To read:
  1. Frank Harary, "Which graphs have integral spectra?"
  2. D. Cvetkovic, M. Doob, H. Sachs, "Spectra of Graphs"


Hereafter, graph means undirected graph without self-loops and parallel edges, specifically
Graph is a pair $(V, E)$, where $V$ is called vertex-set, $E$ is a edge-set, elements of which are two-element subsets of $V$ (unordered pairs) Such unordered pairs are called edges of undirected graph. An edge $e=\{v, w\}$ will further be denoted by $vw$. If there is an edge $vw$, then vertices $v$ and $w$ are said to be adjacent. An edge $vw$ is said to be incident to its vertices, and to be "connecting" them.
But sometimes term can accidentally be used in general (loose) sense, to denote also multidigraphs.
Multigraph is a tuple $(V, E, \phi)$ of two sets, where $V$ is vertex-set, $E$ is edge-set, and $phi$ is a map from $E$ to the set of unordered pairs from $V$. If there is an edge $e\in E$, s.t. $\phi(e) = \{v, w\}$, then vertices $v, w$ are said to be adjacent, and also they are incident with $e$.
(Multi-)digraph is the same with two-element subsets replaced by ordered pairs.
Let $V = (v_1, \ldots, v_n)$. Then Adjacency matrix of (multi-)graph $(V, E)$ is a matrix $(a_{ij})\in\Matr_{n,n}$, where $a_{ij}$ is the number of edges, connecting $v_i$ and $v_j$, i.e. number of edges incident to both $v_i$ and $v_j$
Here, the spectrum of a graph will denote (if not specified) the spectrum of its adjacency matrix.

Rank 1

Let's first consider graphs with adjacency matrix of rank 1. Let $G=(V,E)$ be the graph, $\mathcal A\in\Matr_{n,n}$ be it's adjacency matrix and $A: \RR^n\to\RR^n$ be corresponding (in canonical basis $(e_j), j=\overline{1,n}$ in $\RR^n$) linear mapping. Rank of this operator $A$ (and matrix $\mathcal A$) is $\rank A = \dim\Img A$. If $\rank A = 1$, this operator can be represented in the form $$A x = (x|a) b$$ where $(\cdot|\cdot)$ means dot product, $a\in\RR^n, b\in\Img A$. If $n>1$, then $\dim\Ker A = n - \dim\Img A > 0$ and consequently $0\in\spec A$. Now let's $x\notin\Ker A$. Then $x = \alpha b$, and $$A x = (x|a) b = (\alpha b|a) b = (b|a) \alpha b = (b|a) x$$ Id est, $(b|a)$ is eigenvalue of $A$. Corresponding matrix will be $$\mathcal A = (b_i a_j)_{n\times n} = \begin{pmatrix}b_1 \\ \vdots \\ b_n\end{pmatrix} \begin{pmatrix}a_1 & \cdots & a_n\end{pmatrix} = \begin{pmatrix} a_1 b_1 & \cdots & a_n b_1 \\ \vdots & \ddots & \vdots \\ a_1 b_n & \cdots & a_n b_n \end{pmatrix}$$ because $A e_j = (e_j, a) b = a_j b$.

Let $A$ be operator of rank 1, such that $A x = (x|a) b$.
If $n=1$, then $\spec A = \{0\}$.
If $n>1$, then $\spec A = \{0, (b|a)\}$.
  • Graph with adjacency matrix of rank 1 will always have integral spectra
  • If (multi-)graph doesn't have self-loops, then main diagonal is filled with zeros, i.e. $b_i a_i = 0, i=\overline{1,n}$, which means that $(b|a)=0$ and $\spec A$ consists of single point $0$. Together with symmetry restriction, this probably leaves no graphs, except for the trivial one with matrix $(1)$.
  • Enumeration of graphs with such matrices can be reduced to enumeration of vectors $a, b$, so that $b_i a_j = b_j a_i$ (and $b_i a_i = 0$ for graphs without loops).
Probably, the only adjacency matrix of rank 1 which is both symmetric and can be represented in this way is $$\begin{pmatrix} a & \cdots & a \\ \vdots & \ddots & \vdots \\ a & \cdots & a \end{pmatrix}$$ where $a\in\NN$. TODO: proof

Rank 2

There are exact formulas for eigenvalues of an operators of rank two (Dronov, Avilov, "Spectral analysis of operators of rank two"). Linear map of rank two can be (uniquely) represented in the form $$A x = \xi_1(e_1) + \xi_2(e_2)$$ where $\xi_1, \xi_2\in{\RR^n}^\ast = \LB(\RR^n, \RR)$ are linearly independent linear functionals.
Let $A_0 = A|\Img A$ be restriction of $A$ to $\Img A$ and $\mathcal A_0$ be the matrix, corresponding to $A_0$. $$\mathcal A_0 = (a_{ij}) = ( \xi_i(e_j) ) = \begin{pmatrix} \xi_1(e_1) & \xi_1(e_2) \\ \xi_2(e_1) & \xi_2(e_2) \end{pmatrix}$$ If $n>2$, then $0\in\spec A$. Non-zero eigenvalues of $A$ are the roots of charpoly $\chi(\lambda) = \lambda^2 - (a_{11} + a_{22})\lambda + (a_{11}a_{22} - a_{12}a_{21})$ and are given by exact formulas $$\lambda = \frac{1}{2}\left( - (a_{11} + a_{22}) \pm \sqrt{(a_{11} + a_{22})^2 - 4(a_{11}a_{22} - a_{12}a_{21})} \right)$$ where $a_{ij}=\xi_i(e_j)$

In order for this polynomial to have all the roots integer, it should have integer coefficients (always true for adjacency matrices) and $(a_{11} + a_{22})^2 - 4(a_{11}a_{22} - a_{12}a_{21})$ should be a perfect square (i.e. there should be an integer square root).
If $\mathcal A$ is an adjacency matrix, coefficients are all non-negative integer, and $a_{ij} = a_{ji}$. The actual task is to realize conditions for $(a_{11} + a_{22})^2 - 4(a_{11}a_{22} - a_{12}a_{21})$ to be a perfect square.
Note, that $$(a_{11} + a_{22})^2 - 4(a_{11}a_{22} - a_{12}a_{21}) = a_{11}^2 + a_{22}^2 - 2 a_{11}a_{22} + 4 a_{12} a_{21} = (a_{11} - a_{22})^2 + 4 a_{12} a_{21}$$ Let $m = a_{11}- a_{22}$, $p = a_{12} = a_{21}$. Then, the task reduces to finding conditions under which $m^2 + (2p)^2 = k^2$ for some $k$. I.e. it's a question of distribution of pythagorean triples. (TODO)

Now let's consider graphs without self-loops with adjacency matrices of rank 2, consisting only of two vertices. Absence of loops means main diagonal being filled with zeros: $a_{11} = a_{22} = 0$. $$\mathcal A = \begin{pmatrix} 0 & p \\ p & 0 \end{pmatrix}$$ In this case $m=0, k=2p$. And eigenvalues are numbers of the form $\lambda=\pm p$ and $0$ if $n>2$.

TODO: generation of symmetric matrices of dimension $n>2$ and rank 2 and with integer elements

Rank 3


Comments powered by Disqus