The spectrum of a graph

Let $\Gamma = (X,E)$ be a (possibly directed) finite graph on $v = \vert X \vert$ vertices. The adjacency matrix of $\Gamma$ is the $v \times v$ matrix $A = A( \Gamma ) = (a_{xy} )_{ x,y \in X }$ with rows and columns indexed by $X$ and entries $a_{xy} = \char93$ of edges from $x$ to $y$.

(We may consider $A$ as a linear transformation on the vector space $V = K^X$ of maps from $X$ into $K$, where $K$ is some field such as ${\mathbb{R}}$ or ${\mathbb{C}}$. Now it is meaningful to consider what happens with $A$ when we choose a different basis in $V$.)

The spectrum of $\Gamma$ is by definition the spectrum of $A$, that is, its set of eigenvalues together with their multiplicities. (Formally, a multiset.)

The characteristic polynomial of $\Gamma$ is that of $A$, that is, the polynomial $p_A$ defined by $p_A ( \theta ) = \det ( \theta I - A )$.

Example    Let $\Gamma$ be the path $P_3$ with three vertices and two edges. Assigning some arbitrary order to the three vertices of $\Gamma$, we find that the adjacency matrix $A$ becomes one of $\left(\begin{array}{ccc} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \\ \end{array}\right)$ or $\left(\begin{array}{ccc} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \\ \end{array}\right)$ or $\left(\begin{array}{ccc} 0 & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \\ \end{array}\right)$. The characteristic polynomial is $p_A ( \theta ) = \theta^3 - 2 \theta$. The spectrum is $\sqrt 2$, 0, $- \sqrt 2$. Eigenvectors:

$$\begin{picture}(360,20)(-7,-5) \put(0,0){\circle{4}}\put(2,0)... ...size $\sqrt 2$}} \put(330,0){\makebox(0,0)[c]{.}} \end{picture}$$

(Here, for an eigenvector $u$, we write $u_x$ as a label at the vertex $x$; one has $Au = \theta u$ if and only if $\sum_{ y \leftarrow x } u_y = \theta u_x$.)

Example    Let $\Gamma$ be the tournament with adjacency matrix $A = \left(\begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ \end{array}\right)$. Then $A$ has characteristic polynomial $p_A ( \theta ) = \theta^3 - 1$ and spectrum 1, $\omega$, $\omega^2$, where $\omega$ is a primitive cube root of unity.

Example    Let $\Gamma$ be the directed graph with two vertices and a single directed edge. Then $A = \left(\begin{array}{cc} 0 & 1 \\ 0 & 0 \\ \end{array}\right)$ with $p_A ( \theta ) = \theta^2$ and spectrum $0^2$ (multiplicity written as exponent). The eigenvalue 0 has geometric multiplicity 1 and algebraic multiplicity 2.

By Perron-Frobenius theory, we know something about the largest eigenvalue of a graph.

Proposition 1.4.1   Each graph $\Gamma$ has a real eigenvalue $\theta_0$ with nonnegative real corresponding eigenvector, and such that for each eigenvalue $\theta$ we have $\vert \theta \vert \le \theta_0$.

If $\Gamma$ is strongly connected, then $\theta_0$ has multiplicity 1.

If $\Gamma$ is primitive (strongly connected, and such that not all cycles have a length that is a multiple of some integer $d > 1$), then $\vert \theta \vert < \theta_0$ for all eigenvalues $\theta$ different from $\theta_0$.

The function $\theta_0 (G)$ decreases when vertices or edges are removed from $G$.

Exercise     Let $\Gamma$ be a tournament, that is, a directed graph in which there is precisely one edge between any two distinct vertices, in other words, of which the adjacency matrix $A$ satisfies $A^\top + A = J-I$.

(i) Show that all eigenvalues have real part not less than $-1/2$.

(ii) The tournament $\Gamma$ is called regular when each vertex has the same number of out-arrows. Clearly, when there are $n$ vertices, this number of out-arrows is $(n-1)/2$. Show that all eigenvalues $\theta$ have real part at most $(n-1)/2$, and that ${\rm Re} (\theta) = (n-1)/2$ occurs if and only if $\Gamma$ is regular (and then $\theta = (n-1)/2$).

(iii) Show that $A$ either has full rank $n$ or has rank $n-1$, and that $A$ has full rank when $\Gamma$ is regular.

Hint: for a vector $u$, consider the expression $\bar{u}^\top (A^\top + A) u$.