General theory

[math] \newcommand{\mathds}{\mathbb}[/math]

This article was automatically generated from a tex file and may contain conversion errors. If permitted, you may login and edit this article to improve the conversion.

2a. Linear algebra

You probably know from linear algebra that the important question regarding any matrix [math]d\in M_N(\mathbb R)[/math] is its diagonalization. To be more precise, the first question is that of computing the eigenvalues, which are usually complex numbers, [math]\lambda\in\mathbb C[/math]:

[[math]] dv=\lambda v [[/math]]

Then comes the computation of the eigenvectors, which are usually complex vectors too, [math]v\in\mathbb C^N[/math], and then the diagonalization problem, amounting in finding a new basis of [math]\mathbb C^N[/math], formed by eigenvectors. This basis can exist or not, and in case it exists, we reach to a formula as follows, with [math]\Lambda=diag(\lambda)[/math], and [math]P[/math] being the basis change matrix:

[[math]] d=P\Lambda P^{-1} [[/math]]

In the case of the graphs, or rather of the adjacency matrices [math]d\in M_N(0,1)[/math] of the graphs, these notions are quite important and intuitive, as shown by:

Theorem

The eigenvectors of [math]d\in M_N(0,1)[/math], with eigenvalue [math]\lambda[/math], can be identified with the functions [math]f[/math] satisfying the following condition:

[[math]] \lambda f(i)=\sum_{i-j}f(j) [[/math]]

That is, the value of [math]f[/math] at each vertex must be the rescaled average, over the neighbors.

Show Proof

We have indeed the following computation, valid for any vector [math]f[/math]:

[[math]] \begin{eqnarray*} (df)_i &=&\sum_jd_{ij}f_j\\ &=&\sum_{i-j}d_{ij}f_j+\sum_{i\not-j}d_{ij}f_j\\ &=&\sum_{i-j}1\cdot f_j+\sum_{i\not-j}0\cdot f_j\\ &=&\sum_{i-j}f_j \end{eqnarray*} [[/math]]

Thus, we are led to the conclusion in the statement.

■

The above result is quite interesting, and as an illustration, when assuming that our graph is [math]k[/math]-regular, for the particular value [math]\lambda=k[/math], the eigenvalue condition reads:

[[math]] f(i)=\frac{1}{k}\sum_{i-j}f(j) [[/math]]

Thus, we can see here a relation with harmonic functions. There are many things that can be said here, and we will be back to this later, when talking Laplace operators.

But let us pause now our study of graphs, and go back to linear algebra. Taking the scalars to be complex numbers, which is something very standard, we have the following general result, that you surely know about, from mathematics or physics classes:

Theorem

Given a matrix [math]d\in M_N(\mathbb C)[/math], consider its characteristic polynomial

[[math]] P(x)=\det(d-x1_N) [[/math]]

then factorize this polynomial, by computing its complex roots, with multiplicities,

[[math]] P(x)=(-1)^N(x-\lambda_1)^{m_1}\ldots(x-\lambda_k)^{m_k} [[/math]]

and finally compute the corresponding eigenspaces, for each eigenvalue found:

[[math]] E_i=\left\{v\in\mathbb C^N\Big|dv=\lambda_iv\right\} [[/math]]

The dimensions of these eigenspaces satisfy then the following inequalities,

[[math]] \dim(E_i)\leq m_i [[/math]]

and [math]d[/math] is diagonalizable precisely when we have equality for any [math]i[/math].

Show Proof

There are many things going on here, the idea being as follows:

(1) Given [math]d\in M_N(\mathbb C)[/math], for any eigenvalue [math]\lambda\in\mathbb C[/math] we can define the corresponding eigenspace as being the vector space formed by the corresponding eigenvectors:

[[math]] E_\lambda=\left\{v\in\mathbb C^N\Big|dv=\lambda v\right\} [[/math]]

These spaces [math]E_\lambda[/math] are easily seen to be in direct sum position, in the sense that given vectors [math]v_1\in E_{\lambda_1},\ldots,v_k\in E_{\lambda_k}[/math] coming from different eigenvalues [math]\lambda_1,\ldots,\lambda_k[/math], we have:

[[math]] \sum_ic_iv_i=0\implies c_i=0 [[/math]]

In particular we have the following estimate, with sum over all the eigenvalues, and our matrix is diagonalizable precisely when we have equality:

[[math]] \sum_\lambda\dim(E_\lambda)\leq N [[/math]]

(2) Next, consider the characteristic polynomial of our matrix, given by:

[[math]] P(x)=\det(d-x1_N) [[/math]]

Our claim is that the eigenvalues of [math]d[/math] are then the roots of [math]P[/math]. Indeed, this follows from the following computation, using the elementary fact that a linear map is bijective precisely when the determinant of the associated matrix is nonzero:

[[math]] \begin{eqnarray*} \exists v,dv=\lambda v &\iff&\exists v,(d-\lambda 1_N)v=0\\ &\iff&\det(d-\lambda 1_N)=0 \end{eqnarray*} [[/math]]

(3) Our next claim, which will lead to the result in the statement, is that we have an inequality as follows, where [math]m_\lambda[/math] is the multiplicity of [math]\lambda[/math], viewed as root of [math]P[/math]:

[[math]] \dim(E_\lambda)\leq m_\lambda [[/math]]

Indeed, for any eigenvalue [math]\lambda[/math], consider the dimension [math]n_\lambda=\dim(E_\lambda)[/math] of the corresponding eigenspace. By changing the basis of [math]\mathbb C^N[/math], as for [math]E_\lambda[/math] to be spanned by the first [math]n_\lambda[/math] basis elements, our matrix becomes as follows, with [math]e[/math] being a certain smaller matrix:

[[math]] d\sim\begin{pmatrix}\lambda 1_{n_\lambda}&0\\0&e\end{pmatrix} [[/math]]

We conclude that the characteristic polynomial of [math]d[/math] is of the following form:

[[math]] P_d =P_{\lambda 1_{n_\lambda}}P_e =(\lambda-x)^{n_\lambda}P_e [[/math]]

Thus the multiplicity of [math]\lambda[/math], as root of [math]P[/math], satisfies [math]m_\lambda\geq n_\lambda[/math], which proves our claim.

(4) Getting now to what we wanted to prove, as a first observation, what is said in the theorem is well formulated, thanks to what we found above. Next, by summing the inequalities [math]\dim(E_\lambda)\leq m_\lambda[/math] found in (3), we obtain an inequality as follows:

[[math]] \sum_\lambda\dim(E_\lambda)\leq\sum_\lambda m_\lambda\leq N [[/math]]

On the other hand, we know from (1) that our matrix is diagonalizable precisely when we have global equality. Thus, we are led to the conclusion in the statement.

■

In practice, diagonalizing a matrix remains something quite complicated. Let us record as well a useful, algorithmic version of the above result, as follows:

Theorem

The square matrices [math]d\in M_N(\mathbb C)[/math] can be diagonalized as follows:

• Compute the characteristic polynomial.
• Factorize the characteristic polynomial.
• Compute the eigenvectors, for each eigenvalue found.
• If there are no [math]N[/math] eigenvectors, [math]d[/math] is not diagonalizable.
• Otherwise, [math]d[/math] is diagonalizable, [math]d=P\Lambda P^{-1}[/math].

Show Proof

This is an informal reformulation of Theorem 2.2, with (4) referring to the total number of linearly independent eigenvectors found in (3), and with [math]d=P\Lambda P^{-1}[/math] in (5) being the usual diagonalization formula, with [math]P,\Lambda[/math] being as before.

■

Getting now towards our graph problematics, here is a key result:

Theorem

Any matrix [math]d\in M_N(\mathbb C)[/math] which is self-adjoint, [math]d=d^*[/math], is diagonalizable, with the diagonalization being of the following type,

[[math]] d=U\Lambda U^* [[/math]]

with [math]U\in U_N[/math], and with [math]\Lambda\in M_N(\mathbb R)[/math] diagonal. The converse holds too.

Show Proof

As a first remark, the converse trivially holds, because if we take a matrix of the form [math]d=U\Lambda U^*[/math], with [math]U[/math] unitary and [math]\Lambda[/math] diagonal and real, then we have:

[[math]] \begin{eqnarray*} d^* &=&(U\Lambda U^*)^*\\ &=&U\Lambda^*U^*\\ &=&U\Lambda U^*\\ &=&d \end{eqnarray*} [[/math]]

In the other sense now, assume that [math]d[/math] is self-adjoint, [math]d=d^*[/math]. Our first claim is that the eigenvalues are real. Indeed, assuming [math]dv=\lambda v[/math], we have:

[[math]] \begin{eqnarray*} \lambda \lt v,v \gt &=& \lt \lambda v,v \gt \\ &=& \lt dv,v \gt \\ &=& \lt v,dv \gt \\ &=& \lt v,\lambda v \gt \\ &=&\bar{\lambda} \lt v,v \gt \end{eqnarray*} [[/math]]

Thus we obtain [math]\lambda\in\mathbb R[/math], as claimed. Our next claim now is that the eigenspaces corresponding to different eigenvalues are pairwise orthogonal. Assume indeed that:

[[math]] dv=\lambda v\quad,\quad dw=\mu w [[/math]]

We have then the following computation, using [math]\lambda,\mu\in\mathbb R[/math]:

[[math]] \begin{eqnarray*} \lambda \lt v,w \gt &=& \lt \lambda v,w \gt \\ &=& \lt dv,w \gt \\ &=& \lt v,dw \gt \\ &=& \lt v,\mu w \gt \\ &=&\mu \lt v,w \gt \end{eqnarray*} [[/math]]

Thus [math]\lambda\neq\mu[/math] implies [math]v\perp w[/math], as claimed. In order now to finish, it remains to prove that the eigenspaces span [math]\mathbb C^N[/math]. For this purpose, we will use a recurrence method. Let us pick an eigenvector, [math]dv=\lambda v[/math]. Assuming [math]v\perp w[/math], we have:

[[math]] \begin{eqnarray*} \lt dw,v \gt &=& \lt w,dv \gt \\ &=& \lt w,\lambda v \gt \\ &=&\lambda \lt w,v \gt \\ &=&0 \end{eqnarray*} [[/math]]

Thus, if [math]v[/math] is an eigenvector, then the vector space [math]v^\perp[/math] is invariant under [math]d[/math]. In order to do the recurrence, it still remains to prove that the restriction of [math]d[/math] to the vector space [math]v^\perp[/math] is self-adjoint. But this comes from a general property of the self-adjoint matrices, that we will explain now. Our claim is that for any matrix [math]d\in M_N(\mathbb C)[/math], we have:

[[math]] d=d^*\iff \lt dv,v \gt \in\mathbb R,\,\forall v [[/math]]

Indeed, this follows from the following computation:

[[math]] \begin{eqnarray*} \lt dv,v \gt -\overline{ \lt dv,v \gt } &=& \lt dv,v \gt - \lt v,dv \gt \\ &=& \lt dv,v \gt - \lt d^*v,v \gt \\ &=& \lt (d-d^*)v,v \gt \\ &=&\sum_{ij}(d-d^*)_{ij}\bar{v}_iv_j \end{eqnarray*} [[/math]]

But this shows that the restriction of [math]d[/math] to any invariant subspace, and in particular to [math]v^\perp[/math], is self-adjoint. Thus, we can proceed by recurrence, and we obtain the result.

■

In what concerns us, in relation with our graph problems, we will rather need the real version of the above result, which is also something well-known, as follows:

Theorem

Any matrix [math]d\in M_N(\mathbb R)[/math] which is symmetric, [math]d=d^t[/math], is diagonalizable, with the diagonalization being of the following type,

[[math]] d=U\Lambda U^t [[/math]]

with [math]U\in O_N[/math], and with [math]\Lambda \in M_N(\mathbb R)[/math] diagonal. The converse holds too.

Show Proof

As before, the converse trivially holds, because if we take a matrix of the form [math]d=U\Lambda U^t[/math], with [math]U[/math] orthogonal, and [math]\Lambda[/math] diagonal and real, then we have:

[[math]] \begin{eqnarray*} d^t &=&(U\Lambda U^t)^t\\ &=&U\Lambda^tU^t\\ &=&U\Lambda U^t\\ &=&d \end{eqnarray*} [[/math]]

In the other sense now, this follows from Theorem 2.4, and its proof. Indeed, we know from there that the eigenvalues are real, and in what concerns the passage matrix, the arguments there carry over to the real case, and show that this matrix is real too.

■

With the above results in hand, time now to get back to graphs. We have here the following particular case of Theorem 2.5, with the important drawback however that in what concerns the “converse holds too” part, that is unfortunately gone:

Theorem

The adjacency matrix [math]d\in M_N(0,1)[/math] of any graph is diagonalizable, with the diagonalization being of the following type,

[[math]] d=U\Lambda U^t [[/math]]

with [math]U\in O_N[/math], and with [math]\Lambda\in M_N(\mathbb R)[/math] diagonal. Moreover, we have [math]Tr(\Lambda)=0[/math].

Show Proof

Here the first assertion follows from Theorem 2.5, because [math]d[/math] is by definition real and symmetric. As for the last assertion, this deserves some explanations:

(1) Generally speaking, in analogy with the last assertions in Theorem 2.4 and Theorem 2.5, which are something extremely useful, we would like to know under which assumptions on a rotation [math]U\in O_N[/math], and on a diagonal matrix [math]\Lambda\in M_N(\mathbb R)[/math], the real symmetric matrix [math]d=U\Lambda U^t[/math] has 0-1 entries, and 0 on the diagonal.

(2) Unfortunately, both these questions are obviously difficult, there is no simple answer to them, and things are like that. So, gone the possibility of a converse. However, as a small consolation, we can make the remark that, with [math]d=U\Lambda U^t[/math], we have:

[[math]] Tr(d)=Tr(U\Lambda U^t)=Tr(\Lambda) [[/math]]

Thus we have at least [math]Tr(\Lambda)=0[/math], as a necessary condition on [math](U,\Lambda)[/math], as stated.

■

In view of the above difficulties with the bijectivity, it is perhaps wise to formulate as well the graph particular case of Theorem 2.4. The statement here is as follows:

Theorem

The adjacency matrix [math]d\in M_N(0,1)[/math] of any graph is diagonalizable, with the diagonalization being of the following type,

[[math]] d=U\Lambda U^* [[/math]]

with [math]U\in U_N[/math], and with [math]\Lambda\in M_N(\mathbb R)[/math] diagonal. Moreover, we have [math]Tr(\Lambda)=0[/math].

Show Proof

This follows from Theorem 2.4, via the various remarks from the proof of Theorem 2.5 and Theorem 2.6. But the simplest is to say that the statement itself is just a copy of Theorem 2.6, with [math]U\in O_N[/math] replaced by the more general [math]U\in U_N[/math].

■

All the above is useful, and we will use these results on a regular basis, in what follows. However, before getting into more concrete things, let us formulate: \begin{problem} Find a geometric proof of Theorem 2.6, or of Theorem 2.7, based on the interpretation of eigenvalues and eigenvectors from Theorem 2.1. \end{problem} This question looks quite reasonable, at a first glance, after all what we have in Theorem 2.1 is all nice and gentle material, so do we really need all the above complicated linear algebra machinery in order to deal with all this. However, at a second look, meaning after studying some examples, the problem suddenly looks very complicated. So, homework for you, in case I forget to assign this, to come back to this problem, later.

2b. The simplex

As an illustration for the above, let us diagonalize the adjacency matrix of the simplest graph that we know, namely the [math]N[/math]-simplex. Let us start with:

Proposition

The adjacency matrix of the [math]N[/math]-simplex, having [math]0[/math] on the diagonal and [math]1[/math] elsewhere, is in matrix form:

[[math]] d=\begin{pmatrix} 0&1&\ldots&1&1\\ 1&0&\ldots&1&1\\ \vdots&\vdots&&\vdots&\vdots\\ 1&1&\ldots&0&1\\ 1&1&\ldots&1&0 \end{pmatrix} [[/math]]

We have the following formula for it, with [math]\mathbb I[/math] standing for the all-[math]1[/math] matrix, and with [math]1[/math] standing for the identity matrix, both of size [math]N[/math]:

[[math]] d=\mathbb I-1 [[/math]]

Equivalently, [math]d=NP-1[/math], with [math]P[/math] being the projection on the all-[math]1[/math] vector [math]\xi\in\mathbb R^N[/math].

Show Proof

Here the first assertion is clear from definitions, and the second assertion is clear too. As for the last assertion, observe first that with [math]P=\mathbb I/N[/math] we have:

[[math]] P^2=\left(\frac{\mathbb I}{N}\right)^2=\frac{\mathbb I^2}{N^2}=\frac{N\mathbb I}{N^2}=\frac{\mathbb I}{N}=P [[/math]]

Thus [math]P[/math] is a projection, and since we obviously have [math]P=P^t[/math], this matrix is an orthogonal projection. In order to find now the image, observe that for any vector [math]v\in\mathbb R^N[/math] we have the following formula, with [math]a\in\mathbb R[/math] being the average of the entries of [math]v[/math]:

[[math]] Pv=\begin{pmatrix} a\\ \vdots\\ a\end{pmatrix} [[/math]]

We conclude that the image of [math]P[/math] is the vector space [math]\mathbb R\xi[/math], with [math]\xi\in\mathbb R^N[/math] being the all-1 vector, and so that [math]P[/math] is the orthogonal projection on [math]\xi[/math], as claimed.

■

The above is very nice, in particular with [math]d=NP-1[/math] basically diagonalizing [math]d[/math] for us. However, thinking a bit, when it comes to explicitly diagonalize [math]d[/math], or, equivalently, [math]P[/math] or [math]\mathbb I[/math], things are quite tricky, and we run into the following strange problem: \begin{problem} In order to diagonalize [math]d[/math], we need solutions for

[[math]] x_1+\ldots+x_N=0 [[/math]]

and there are no standard such solutions, over the reals. \end{problem} So, this is the problem that we face, which might look a bit futile at a first glance, and in order for you to take me seriously here, let us work out some particular cases. At [math]N=2[/math] things are quickly solved, with the diagonalization being as follows, and with the passage matrix being easy to construct, I agree with you on this:

[[math]] \begin{pmatrix}0&1\\1&0\end{pmatrix} \sim \begin{pmatrix}1&0\\0&-1\end{pmatrix} [[/math]]

However, things become suddenly complicated at [math]N=3[/math], where I challenge you to find the passage matrix for the following diagonalization:

[[math]] \begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix} \sim \begin{pmatrix}2&0&0\\0&-1&0\\0&0&-1\end{pmatrix} [[/math]]

In the general case, [math]N\in\mathbb N[/math], the problem does not get any simpler, again with the challenge for you to find the passage matrix for the following diagonalization:

[[math]] \begin{pmatrix} 0&1&\ldots&1&1\\ 1&0&\ldots&1&1\\ \vdots&\vdots&&\vdots&\vdots\\ 1&1&\ldots&0&1\\ 1&1&\ldots&1&0 \end{pmatrix}\sim \begin{pmatrix} N-1&&&&0\\ &-1\\ &&\ddots&\\ &&&-1\\ 0&&&&-1 \end{pmatrix} [[/math]]

In short, you got my point, Problem 2.10 is something real. Fortunately the complex numbers come to the rescue, via the following standard and beautiful result:

Theorem

The roots of unity, [math]\{w^k\}[/math] with [math]w=e^{2\pi i/N}[/math], have the property

[[math]] \frac{1}{N}\sum_{k=0}^{N-1}(w^k)^s=\delta_{N|s} [[/math]]

for any exponent [math]s\in\mathbb N[/math], where on the right we have a Kronecker symbol.

Show Proof

There are several possible proofs for this, as follows:

(1) Nice proof. The numbers to be summed, when written more conveniently as [math](w^s)^k[/math] with [math]k=0,\ldots,N-1[/math], form a certain regular polygon in the plane [math]P_s[/math]. Thus, if we denote by [math]C_s[/math] the barycenter of this polygon, we have the following formula:

[[math]] \frac{1}{N}\sum_{k=0}^{N-1}w^{ks}=C_s [[/math]]

Now observe that in the case [math]N\slash\hskip-1.6mm|\,s[/math] our polygon [math]P_s[/math] is non-degenerate, circling along the unit circle, and having center [math]C_s=0[/math]. As for the case [math]N|s[/math], here the polygon is degenerate, lying at 1, and having center [math]C_s=1[/math]. Thus, we have the following formula, as claimed:

[[math]] C_s=\delta_{N|s} [[/math]]

(2) Ugly proof. Normally we won't bother with ugly proofs in this book, but these being mathematics too, at least in theory, here is the computation, for [math]N\slash\hskip-1.6mm|\,s[/math]:

[[math]] \begin{eqnarray*} \sum_{k=0}^{N-1}(w^k)^s &=&\sum_{k=0}^{N-1}(w^s)^k\\ &=&\frac{1-w^{sN}}{1-w^s}\\ &=&\frac{1-1^s}{1-w^s}\\ &=&0 \end{eqnarray*} [[/math]]

Thus, we are led again to the formula in the statement.

■

Summarizing, we have the solution to our problem. In order now to finalize, let us start with the following definition, inspired by what happens in Theorem 2.11:

Definition

The Fourier matrix [math]F_N[/math] is the following matrix, with [math]w=e^{2\pi i/N}[/math]:

[[math]] F_N= \begin{pmatrix} 1&1&1&\ldots&1\\ 1&w&w^2&\ldots&w^{N-1}\\ 1&w^2&w^4&\ldots&w^{2(N-1)}\\ \vdots&\vdots&\vdots&&\vdots\\ 1&w^{N-1}&w^{2(N-1)}&\ldots&w^{(N-1)^2} \end{pmatrix} [[/math]]

That is, [math]F_N=(w^{ij})_{ij}[/math], with indices [math]i,j\in\{0,1,\ldots,N-1\}[/math], taken modulo [math]N[/math].

Here the name comes from the fact that [math]F_N[/math] is the matrix of the discrete Fourier transform, that over the cyclic group [math]\mathbb Z_N[/math], and more on this later, when talking Fourier analysis. As a first example now, at [math]N=2[/math] the root of unity is [math]w=-1[/math], and with indices as above, namely [math]i,j\in\{0,1\}[/math], taken modulo 2, our Fourier matrix is as follows:

[[math]] F_2=\begin{pmatrix}1&1\\1&-1\end{pmatrix} [[/math]]

At [math]N=3[/math] now, the root of unity is [math]w=e^{2\pi i/3}[/math], and the Fourier matrix is:

[[math]] F_3=\begin{pmatrix}1&1&1\\ 1&w&w^2\\ 1&w^2&w\end{pmatrix} [[/math]]

At [math]N=4[/math] now, the root of unit is [math]w=i[/math], and the Fourier matrix is:

[[math]] F_4=\begin{pmatrix} 1&1&1&1\\ 1&i&-1&-i\\ 1&-1&1&-1\\ 1&-i&-1&i \end{pmatrix} [[/math]]

Finally, at [math]N=5[/math] the root of unity is [math]w=e^{2\pi i/5}[/math], and the Fourier matrix is:

[[math]] F_5=\begin{pmatrix} 1&1&1&1&1\\ 1&w&w^2&w^3&w^4\\ 1&w^2&w^4&w&w^3\\ 1&w^3&w&w^4&w^2\\ 1&w^4&w^3&w^2&w \end{pmatrix} [[/math]]

You get the point. Getting back now to the diagonalization problem for the flat matrix [math]\mathbb I[/math], this can be solved by using the Fourier matrix [math]F_N[/math], in the following way:

Proposition

The flat matrix [math]\mathbb I[/math] diagonalizes as follows,

[[math]] \begin{pmatrix} 1&\ldots&\ldots&1\\ \vdots&&&\vdots\\ \vdots&&&\vdots\\ 1&\ldots&\ldots&1\end{pmatrix} =\frac{1}{N}\,F_N \begin{pmatrix} N&&&&0\\ &0\\ &&\ddots\\ &&&0\\ 0&&&&0\end{pmatrix}F_N^* [[/math]]

with [math]F_N=(w^{ij})_{ij}[/math] being the Fourier matrix.

Show Proof

According to the last assertion in Proposition 2.9, we are left with finding the 0-eigenvectors of [math]\mathbb I[/math], which amounts in solving the following equation:

[[math]] x_0+\ldots+x_{N-1}=0 [[/math]]

For this purpose, we can use the root of unity [math]w=e^{2\pi i/N}[/math], and more specifically, the following standard formula, coming from Theorem 2.11:

[[math]] \sum_{i=0}^{N-1}w^{ij}=N\delta_{j0} [[/math]]

This formula shows that for [math]j=1,\ldots,N-1[/math], the vector [math]v_j=(w^{ij})_i[/math] is a 0-eigenvector. Moreover, these vectors are pairwise orthogonal, because we have:

[[math]] \lt v_j,v_k \gt =\sum_iw^{ij-ik} =N\delta_{jk} [[/math]]

Thus, we have our basis [math]\{v_1,\ldots,v_{N-1}\}[/math] of 0-eigenvectors, and since the [math]N[/math]-eigenvector is [math]\xi=v_0[/math], the passage matrix [math]P[/math] that we are looking is given by:

[[math]] P=\begin{bmatrix}v_0&v_1&\ldots&v_{N-1}\end{bmatrix} [[/math]]

But this is precisely the Fourier matrix, [math]P=F_N[/math]. In order to finish now, observe that the above computation of [math] \lt v_i,v_j \gt [/math] shows that [math]F_N/\sqrt{N}[/math] is unitary, and so:

[[math]] F_N^{-1}=\frac{1}{N}\,F_N^* [[/math]]

Thus, we are led to the diagonalization formula in the statement.

■

By substracting now [math]-1[/math] from everything, we can formulate a final result, as follows:

Theorem

The adjacency matrix of the simplex diagonalizes as follows,

[[math]] \begin{pmatrix} 0&1&\ldots&1&1\\ 1&0&\ldots&1&1\\ \vdots&\vdots&&\vdots&\vdots\\ 1&1&\ldots&0&1\\ 1&1&\ldots&1&0 \end{pmatrix} =\frac{1}{N}\,F_N \begin{pmatrix} N-1&&&&0\\ &-1\\ &&\ddots&\\ &&&-1\\ 0&&&&-1 \end{pmatrix}F_N^* [[/math]]

with [math]F_N=(w^{ij})_{ij}[/math] being the Fourier matrix.

Show Proof

This follows as said above, from what we have in Proposition 2.13, by substracting [math]-1[/math] from everything. Alternatively, if you prefer a more direct proof, this follows from the various computations in the proof of Proposition 2.13.

■

The above result was something quite tricky, and we will come back regularly to such things, in what follows. For the moment, let us formulate an interesting conclusion: \begin{conclusion} Theorem 2.7, telling us that [math]d[/math] diagonalizes over [math]\mathbb C[/math], is better than the stronger Theorem 2.6, telling us that [math]d[/math] diagonalizes over [math]\mathbb R[/math]. \end{conclusion} And isn't this surprising. But after some thinking, after all no surprise, because the graphs, as we defined them in the beginning of chapter 1, are scalarless objects. So, when needing a field for studying them, we should just go with the mighty [math]F=\mathbb C[/math].

By the way, regarding complex numbers, time to recommend some reading. Mathematically the book of Rudin is a must-read, and a pleasure to read. However, if you want to be really in love with complex numbers, and with this being an enormous asset, no matter what mathematics you want to do, nothing beats some physics reading.

The standard place for learning physics is the course of Feynman , , . If you already know a bit of physics, you can go as well with the lovely books of Griffiths , , . And if you know a bit more, good books are those of Weinberg , , . In the hope that this helps, and I will not tell you of course what these books contain. Expect however lots of complex numbers, all beautiful, and used majestically.

2c. Further graphs

Motivated by the above, let us try now to diagonalize the adjacency matrices of other graphs, more complicated than the simplex. But, what graphs to start with?

We already faced this kind of question in chapter 1, when discussing random walks and other basic questions, and we will proceed in a similar way here, by using our intuition. Passed the simplices, the “simplest” graphs are most likely the unions of simplices:

[[math]] \xymatrix@R=15pt@C=15pt{ &\bullet\ar@{-}[ddl]\ar@{-}[ddr]&&&\bullet\ar@{-}[dd]\ar@{-}[ddrr]\ar@{-}[rr]&&\bullet\ar@{-}[dd]\ar@{-}[ddll]&&\bullet\ar@{-}[dd]\ar@{-}[ddrr]\ar@{-}[rr]&&\bullet\ar@{-}[dd]\ar@{-}[ddll]\\ \\ \bullet\ar@{-}[rr]&&\bullet&&\bullet\ar@{-}[rr]&&\bullet&&\bullet\ar@{-}[rr]&&\bullet } [[/math]]

But the diagonalization question for such graphs is quickly settled, by using our results for the simplex from the previous section, and the following general fact:

Theorem

Given a disjoint union of connected graphs [math]X=X_1\cup\ldots\cup X_k[/math], the corresponding adjacency matrix is block-diagonal,

[[math]] d=\begin{pmatrix} d_1\\ &\ddots\\ &&d_k \end{pmatrix} [[/math]]

and diagonalizes in the following way,

[[math]] d=\begin{pmatrix} U_1\\ &\ddots\\ &&U_k \end{pmatrix} \begin{pmatrix} \Lambda_1\\ &\ddots\\ &&\Lambda_k \end{pmatrix} \begin{pmatrix} U_1\\ &\ddots\\ &&U_k \end{pmatrix}^* [[/math]]

with [math]d_i=U_i\Lambda_iU_i^*[/math] being diagonalizations of the adjacency matrices of the components [math]X_i[/math].

Show Proof

This is indeed something trivial and self-explanatory, coming from definitions, the idea being that when labeling the vertices of [math]X[/math] by starting with those of [math]X_1[/math], then with those of [math]X_2[/math], and so on up to those of [math]X_k[/math], the adjacency matrix [math]d[/math] takes the block-diagonal form in the statement. Thus, we are led to the above conclusions.

■

Summarizing, we know how to diagonalize the adjacency matrix of [math]X=X_1\cup\ldots\cup X_k[/math], provided that we know how to diagonalize the adjacency matrix of each [math]X_i[/math]. As an illustration here, for the graph pictured before Theorem 2.16, the diagonalization is as follows, with [math]F_N[/math] being as usual the Fourier matrix, and with [math]J_N=diag(N-1,-1,\ldots,-1)[/math] being the diagonal [math]N\times N[/math] matrix found in Theorem 2.14:

[[math]] d=\frac{1}{48}\begin{pmatrix} F_3\\ &F_4\\ &&F_4 \end{pmatrix} \begin{pmatrix} J_3\\ &J_4\\ &&J_4 \end{pmatrix} \begin{pmatrix} F_3\\ &F_4\\ &&F_4 \end{pmatrix}^* [[/math]]

Back to the general case, as in Theorem 2.16, of particular interest is the case where all the components [math]X_i[/math] appear as copies of the same graph [math]Y[/math]. And with the picture here, when [math]Y[/math] is a simplex, being something which looks quite nice, as follows:

[[math]] \xymatrix@R=15pt@C=15pt{ \bullet\ar@{-}[dd]\ar@{-}[ddrr]\ar@{-}[rr]&&\bullet\ar@{-}[dd]\ar@{-}[ddll]&&\bullet\ar@{-}[dd]\ar@{-}[ddrr]\ar@{-}[rr]&&\bullet\ar@{-}[dd]\ar@{-}[ddll]&&\bullet\ar@{-}[dd]\ar@{-}[ddrr]\ar@{-}[rr]&&\bullet\ar@{-}[dd]\ar@{-}[ddll]\\ \\ \bullet\ar@{-}[rr]&&\bullet&&\bullet\ar@{-}[rr]&&\bullet&&\bullet\ar@{-}[rr]&&\bullet } [[/math]]

In this case we can further build on Theorem 2.16, and say a bit more about the diagonalization of the adjacency matrix, the final result being as follows:

Theorem

Given a disjoint union of type [math]X=kY[/math], with [math]Y[/math] being connected, the corresponding adjacency matrix can be written in the following way,

[[math]] d=d_Y\otimes 1_k [[/math]]

and diagonalizes in the following way,

[[math]] d=(U\otimes 1_k)(\Lambda\otimes 1_k)(U\otimes 1_k)^* [[/math]]

with [math]d_Y=U\Lambda U^*[/math] being the diagonalization of the adjacency matrix of [math]Y[/math].

Show Proof

This follows from Theorem 2.16, with the only issue being at the level of the labeling of vertices, and of the tensor product notations. In order to explain this, let us take as example the graph pictured before the statement, and label it as follows:

[[math]] \xymatrix@R=15pt@C=15pt{ 11\ar@{-}[dd]\ar@{-}[ddrr]\ar@{-}[rr]&&12\ar@{-}[dd]\ar@{-}[ddll]&&21\ar@{-}[dd]\ar@{-}[ddrr]\ar@{-}[rr]&&22\ar@{-}[dd]\ar@{-}[ddll]&&31\ar@{-}[dd]\ar@{-}[ddrr]\ar@{-}[rr]&&32\ar@{-}[dd]\ar@{-}[ddll]\\ \\ 14\ar@{-}[rr]&&13&&24\ar@{-}[rr]&&23&&34\ar@{-}[rr]&&33 } [[/math]]

Observe that this is in agreement with what we did in the proof of Theorem 2.16, with the vertices of the first square coming first, then with the vertices of the second square coming second, and with the vertices of the third square coming third, according to:

[[math]] 11 \lt 12 \lt 13 \lt 14 \lt 21 \lt 22 \lt 23 \lt 24 \lt 31 \lt 32 \lt 33 \lt 34 [[/math]]

Thus, we can use the conclusions of Theorem 2.16, as such. But since our adjacency matrix has now double indices, as matrix indices, we can switch to tensor product notations, according to the following standard rule, from tensor product calculus:

[[math]] (M\otimes N)_{ia,jb}=M_{ij}N_{ab} [[/math]]

Thus, we are led to the conclusions in the statement.

■

As before with Theorem 2.16, nothing better at this point than an illustration for all this. For the graph pictured before the statement, and in the proof too, we obtain:

[[math]] d=\frac{1}{4}(F_4\otimes 1_k)(J_4\otimes 1_k)(F_4\otimes 1_k)^* [[/math]]

Moving forward, now that we understood the disjoint union operation, time to study the other basic operation for graphs, which is the complementation operation. However, things here are more tricky, with the general result on the subject being as follows:

Proposition

The adjacency matrix of a graph [math]X[/math] and of its complement [math]X^c[/math] are related by the following formula, with [math]\mathbb I[/math] being the all-one matrix,

[[math]] d_X+d_{X^c}=\mathbb I-1 [[/math]]

so if we have a diagonalization formula of type [math]d_X=U\Lambda U^*[/math], with [math]U[/math] diagonalizing as well the all-one matrix [math]\mathbb I[/math], we obtain in this way a diagonalization for [math]d_X[/math].

Show Proof

This is something trivial, and which of course does not look very good, with our point coming from the following implication, which is immediate:

[[math]] d_X=U\Lambda U^*\ ,\ \mathbb I=U\Sigma U^*\ \implies\ d_X=U(\Sigma-\Lambda-1)U^* [[/math]]

Thus, we are led to the conclusion in the statement.

■

In practice now, the next step would be to look at the complements of various particular graphs, such as the disjoint unions [math]X=X_1\cup\ldots\cup X_k[/math] from Theorem 2.16. But this does not bring any simplification, as you can easily verify yourself. Moreover, when further particularizing, and looking at the complements of the graphs [math]X=kY[/math] from Theorem 2.17, there is no simplification either. However, when particularizing even more, and taking [math]Y=K_n[/math], we are led to something nice, which is good to know, namely:

Theorem

Given a disjoint union of simplices [math]X=kK_n[/math], the adjacency matrix of the complement [math]X^c[/math] can be written as

[[math]] d=\mathbb I_n\otimes(\mathbb I_k-1_k) [[/math]]

and so diagonalizes in the following way,

[[math]] d=\frac{1}{nk}(F_n\otimes F_k)\left(L_n\otimes(L_k-1_k)\right)(F_n\otimes F_k)^* [[/math]]

with [math]F_n[/math] being the Fourier matrix, and [math]L_n=diag(n,0,\ldots,0)[/math], as a [math]n\times n[/math] matrix.

Show Proof

By using the various labeling and tensor product conventions from Theorem 2.17 and its proof, the adjacency matrix of [math](kK_n)^c[/math] is given by:

[[math]] \begin{eqnarray*} d &=&\begin{pmatrix} 0&\mathbb I_n&\ldots&\mathbb I_n&\mathbb I_n\\ \mathbb I_n&0&\ldots&\mathbb I_n&\mathbb I_n\\ &&\ddots\\ \mathbb I_n&\mathbb I_n&\ldots&0&\mathbb I_n\\ \mathbb I_n&\mathbb I_n&\ldots&\mathbb I_n&0 \end{pmatrix}\\ &=&\mathbb I_n\otimes\begin{pmatrix} 0&1&\ldots&1&1\\ 1&0&\ldots&1&1\\ &&\ddots\\ 1&1&\ldots&0&1\\ 1&1&\ldots&1&0 \end{pmatrix}\\ &=&\mathbb I_n\otimes(\mathbb I_k-1_k) \end{eqnarray*} [[/math]]

Thus, we are led to the various conclusions in the statement.

■

As before with other results of the same type, let us work out an illustration. Consider the following graph, that we already met before, in the context of Theorem 2.17:

[[math]] \xymatrix@R=15pt@C=15pt{ \bullet\ar@{-}[dd]\ar@{-}[ddrr]\ar@{-}[rr]&&\bullet\ar@{-}[dd]\ar@{-}[ddll]&&\bullet\ar@{-}[dd]\ar@{-}[ddrr]\ar@{-}[rr]&&\bullet\ar@{-}[dd]\ar@{-}[ddll]&&\bullet\ar@{-}[dd]\ar@{-}[ddrr]\ar@{-}[rr]&&\bullet\ar@{-}[dd]\ar@{-}[ddll]\\ \\ \bullet\ar@{-}[rr]&&\bullet&&\bullet\ar@{-}[rr]&&\bullet&&\bullet\ar@{-}[rr]&&\bullet } [[/math]]

The adjacency matrix of the complementary graph diagonalizes then as follows:

[[math]] d=\frac{1}{12}(F_4\otimes F_3)\left[ \begin{pmatrix} 4\\ &0\\ &&0\\ &&&0 \end{pmatrix}\otimes \begin{pmatrix} 3\\ &-1\\ &&-1 \end{pmatrix}\right] (F_4\otimes F_3)^* [[/math]]

And with this being actually not the end of the story, for this particular graph, because it is possible to prove that we have [math]F_{12}=F_4\otimes F_3[/math], with this coming from [math]F_{mn}=F_m\otimes F_n[/math], for [math]m,n[/math] prime to each other. But more on such phenomena later in this book.

Moving forward, now that we have some good understanding of the various operations for the graphs, time to get into the real thing, namely study of the graphs which are nice, simple and “indecomposable”. Although we don't have yet a definition, for what indecomposable should mean, as a main example here, we certainly have the circle:

[[math]] \xymatrix@R=16pt@C=17pt{ &\bullet\ar@{-}[r]\ar@{-}[dl]&\bullet\ar@{-}[dr]\\ \bullet\ar@{-}[d]&&&\bullet\ar@{-}[d]\\ \bullet\ar@{-}[dr]&&&\bullet\ar@{-}[dl]\\ &\bullet\ar@{-}[r]&\bullet} [[/math]]

So, in what follows we will study this circle graph, and its complement too. Let us first compute the eingenvalues and eigenvectors. This is easily done, as follows:

Proposition

For the adjacency matrix [math]d[/math] of the circle graph, we have

[[math]] d\begin{pmatrix} 1\\ w^k\\ w^{2k}\\ \vdots\\ w^{kN-k} \end{pmatrix} =(w^k+w^{-k}) \begin{pmatrix} 1\\ w^k\\ w^{2k}\\ \vdots\\ w^{kN-k} \end{pmatrix} [[/math]]

with [math]w=e^{2\pi i/N}[/math], for any [math]k[/math], and this diagonalizes [math]d[/math].

Show Proof

In what regards the first assertion, this follows from:

[[math]] \begin{eqnarray*} d\begin{pmatrix} 1\\ w^k\\ w^{2k}\\ \vdots\\ w^{kN-k} \end{pmatrix} &=& \begin{pmatrix} 0&1&0&\ldots&0&0&1\\ 1&0&1&\ldots&0&0&0\\ &&\ddots&\ddots&\ddots\\ 0&0&0&\ldots&1&0&1\\ 1&0&0&\ldots&0&1&0 \end{pmatrix} \begin{pmatrix} 1\\ w^k\\ w^{2k}\\ \vdots\\ w^{kN-k} \end{pmatrix}\\ &=&\begin{pmatrix} w^k+w^{kN-k}\\ 1+w^{2k}\\ w^k+w^{3k}\\ \vdots\\ 1+w^{kN-2k} \end{pmatrix}\\ &=&(w^k+w^{-k}) \begin{pmatrix} 1\\ w^k\\ w^{2k}\\ \vdots\\ w^{kN-k} \end{pmatrix} \end{eqnarray*} [[/math]]

As for the second assertion, this comes from this, because with [math]k=0,1,\ldots,N-1[/math] the eigenvectors that we found, which are the rows of [math]F_N[/math], are linearly independent.

■

We can now formulate a final result about the circle graph, as follows:

Theorem

The adjacency matrix of the circle graph diagonalizes as

[[math]] d=\frac{1}{N}F_N \begin{pmatrix} 2\\ &w+w^{-1}\\ &&w^2+w^{-2}\\ &&&\ddots\\ &&&&w^{N-1}+w^{1-N} \end{pmatrix}F_N^* [[/math]]

where [math]F_N=(w^{ij})[/math] with [math]w=e^{2\pi i/N}[/math] is as usual the Fourier matrix.

Show Proof

In terms of the vector [math]\xi=(w^p)[/math], and as usual with indices [math]p=0,1,\ldots,N-1[/math], the eigenvector formula that we found in Proposition 2.20 reads:

[[math]] d\xi^k=(w^k+w^{-k})\xi^k [[/math]]

By putting all these formulae together, with [math]k=0,1,\ldots,N-1[/math], we obtain:

[[math]] \begin{eqnarray*} &&d\begin{pmatrix}\xi^0&\xi^1&\xi^2&\ldots&\xi^{N-1}\end{pmatrix}\\ &=&\begin{pmatrix}2\xi^0&(w+w^{-1})\xi&(w^2+w^{-2})\xi^2&\ldots&(w^{N-1}+w^{1-N})\xi^{N-1}\end{pmatrix}\\ &=&\begin{pmatrix}\xi^0&\xi^1&\xi^2&\ldots&\xi^{N-1}\end{pmatrix} \begin{pmatrix} 2\\ &w+w^{-1}\\ &&w^2+w^{-2}\\ &&&\ddots\\ &&&&w^{N-1}+w^{1-N} \end{pmatrix} \end{eqnarray*} [[/math]]

But, since we have [math]F_N=(\xi^k)[/math], as a square matrix, this formula reads:

[[math]] dF_N=F_N\begin{pmatrix} 2\\ &w+w^{-1}\\ &&w^2+w^{-2}\\ &&&\ddots\\ &&&&w^{N-1}+w^{1-N} \end{pmatrix} [[/math]]

Now by multipliying to the right by [math]F_N^{-1}=F_N^*/N[/math], we obtain the result.

■

The above result is quite interesting, and as a first obvious conclusion, coming from this and from our previous results regarding the simplex, we have: \begin{conclusion} The adjacency matrices of both the simplex and the circle are diagonalized by the Fourier matrix [math]F_N[/math]. \end{conclusion} We will be back to this phenomenon later in this book, with a systematic discussion of the graphs diagonalized by the Fourier matrix [math]F_N[/math], and of related topics.

In the meantime, as a corollary of this, remember Proposition 2.18, regarding the complementary graphs [math]X^c[/math], with the quite technical assumptions that we found there, seemingly bound for the trash can? Well, as good news, Conclusion 2.22 is exactly what we need, guaranteeing that Proposition 2.18 applies indeed, to the circle graph. So, as our next theorem, based on the above study for the circle, we have:

Theorem

The adjacency matrix of the complement of the circle graph diagonalizes as

[[math]] d=\frac{1}{N}F_N \begin{pmatrix} N-3\\ &-1-w-w^{-1}\\ &&-1-w^2-w^{-2}\\ &&&\ddots\\ &&&&-1-w^{N-1}-w^{1-N} \end{pmatrix}F_N^* [[/math]]

where [math]F_N=(w^{ij})[/math] with [math]w=e^{2\pi i/N}[/math] is as usual the Fourier matrix.

Show Proof

Consider the circle graph [math]X[/math], that we know well from the above:

[[math]] \xymatrix@R=17pt@C=18pt{ &\bullet\ar@{-}[r]\ar@{-}[dl]&\bullet\ar@{-}[dr]\\ \bullet\ar@{-}[d]&&&\bullet\ar@{-}[d]\\ \bullet\ar@{-}[dr]&&&\bullet\ar@{-}[dl]\\ &\bullet\ar@{-}[r]&\bullet} [[/math]]

Consider as well its complement [math]X^c[/math], which is a quite crowded and scary graph, of valence [math]N-3[/math], with the picture at [math]N=8[/math] being as follows:

[[math]] \xymatrix@R=20pt@C=20pt{ &\bullet\ar@{-}[ddrr]\ar@{-}[drr]\ar@{-}[ddd]\ar@{-}[dddr]&\bullet\ar@{-}[ddd]\ar@{-}[dll]\ar@{-}[ddll]\ar@{-}[dddl]\\ \bullet\ar@{-}[ddr]&&&\bullet\ar@{-}[lll]\ar@{-}[dlll]\ar@{-}[ddll]\\ \bullet\ar@{-}[uur]\ar@{-}[drr]&&&\bullet\ar@{-}[lll]\ar@{-}[uul]\ar@{-}[ulll]\\ &\bullet\ar@{-}[urr]&\bullet\ar@{-}[uur]\ar@{-}[uull]} [[/math]]

However, at the linear algebra level things are quite simple, because by combining Theorem 2.14 and Theorem 2.21, as indicated in Proposition 2.18, we obtain:

[[math]] \begin{eqnarray*} d_{X^c} &=&\mathbb I_N-1_N-d_X\\ &=&\frac{1}{N}F_N\begin{pmatrix} N-1&&&&0\\ &-1\\ &&\ddots&\\ &&&-1\\ 0&&&&-1 \end{pmatrix}F_N^*\\ &&-\frac{1}{N}F_N \begin{pmatrix} 2\\ &w+w^{-1}\\ &&w^2+w^{-2}\\ &&&\ddots\\ &&&&w^{N-1}+w^{1-N} \end{pmatrix}F_N^* \end{eqnarray*} [[/math]]

Thus, we are led to the formula in the statement.

■

Very nice all this, so done with the circle and its complement, and on our to-do list, job for later to further explore Conclusion 2.22, and related Fourier analysis topics.

2d. The segment

As a continuation of the above study, let us discuss now the segment graph. This is a graph that we already met in chapter 1, in relation with random walk questions, and with our conclusions there being quite muddy, basically amounting in saying that this graph is something quite tough to fight with, knowing more mathematics than we do.

We will investigate here this graph, from the diagonalization point of view. As a first observation, since diagonalization solves the random walk question, as explained in chapter 1, we cannot expect much from our diagonalization study, done as we do, with bare hands. So, modesty, let us just start working on this, and we'll see what we get.

Some numerics first. These do not look very good, the result being as follows:

Proposition

The eigenvalues of the segment graph are as follows:

• At [math]N=2[/math] we have [math]-1,1[/math].
• At [math]N=3[/math] we have [math]0,\pm\sqrt{2}[/math].
• At [math]N=4[/math] we have [math]\pm\frac{\sqrt{5}\pm1}{2}[/math].
• At [math]N=5[/math] we have [math]0,\pm1,\pm\sqrt{3}[/math].
• At [math]N=6[/math] we have the solutions of [math]x^6-5x^4+6x^2-1=0[/math].

Show Proof

These are some straightforward linear algebra computations, with some tricks being needed only at [math]N=4[/math], the details being as follows:

(1) At [math]N=2[/math] the adjacency matrix and its eigenvalues are as follows:

[[math]] d=\begin{pmatrix} 0&1\\ 1&0 \end{pmatrix}\quad,\quad \begin{vmatrix} x&-1\\ -1&x \end{vmatrix} =x^2-1=(x-1)(x+1) [[/math]]

(2) At [math]N=3[/math] the adjacency matrix and its eigenvalues are as follows:

[[math]] d=\begin{pmatrix} 0&1&0\\ 1&0&1\\ 0&1&0 \end{pmatrix}\quad,\quad \begin{vmatrix} x&-1&0\\ -1&x&-1\\ 0&-1&x \end{vmatrix} =x^3-2x=x(x^2-2) [[/math]]

(3) At [math]N=4[/math] the adjacency matrix and its characteristic polynomial are as follows:

[[math]] d=\begin{pmatrix} 0&1&0&0\\ 1&0&1&0\\ 0&1&0&1\\ 0&0&1&0 \end{pmatrix}\quad,\quad \begin{vmatrix} x&-1&0&0\\ -1&x&-1&0\\ 0&-1&x&-1\\ 0&0&-1&x \end{vmatrix} =x^4-3x^2+1 [[/math]]

Now by solving the degree 2 equation, and fine-tuning the answer, we obtain:

[[math]] x=\pm\sqrt{\frac{3\pm\sqrt{5}}{2}}=\pm\frac{\sqrt{5}\pm1}{2} [[/math]]

(4) At [math]N=5[/math] the adjacency matrix and its eigenvalues are as follows:

[[math]] d=\begin{pmatrix} 0&1&0&0&0\\ 1&0&1&0&0\\ 0&1&0&1&0\\ 0&0&1&0&1\\ 0&0&0&1&0 \end{pmatrix}\quad,\quad \begin{vmatrix} x&-1&0&0&0\\ -1&x&-1&0&0\\ 0&-1&x&-1&0\\ 0&0&-1&x&-1\\ 0&0&0&-1&x \end{vmatrix} =x(x^2-1)(x^2-3) [[/math]]

(5) At [math]N=6[/math] the adjacency matrix and its eigenvalues are as follows:

[[math]] d=\begin{pmatrix} 0&1&0&0&0&0\\ 1&0&1&0&0&0\\ 0&1&0&1&0&0\\ 0&0&1&0&1&0\\ 0&0&0&1&0&1\\ 0&0&0&0&1&0 \end{pmatrix}\ ,\ \begin{vmatrix} x&-1&0&0&0&0\\ -1&x&-1&0&0&0\\ 0&-1&x&-1&0&0\\ 0&0&-1&x&-1&0\\ 0&0&0&-1&x&-1\\ 0&0&0&0&-1&x \end{vmatrix} =x^6-5x^4+6x^2-1 [[/math]]

Thus, we are led to the formulae in the statement.

■

All the above does not look very good. However, as a matter of having the dirty job fully done, with mathematical pride, let us look as well into eigenvectors. At [math]N=2[/math] things are quickly settled, with the diagonalization of the adjacency matrix being as follows:

[[math]] \begin{pmatrix} 0&1\\ 1&0 \end{pmatrix} =\frac{1}{2}\begin{pmatrix} 1&1\\ 1&-1 \end{pmatrix} \begin{pmatrix} 1&0\\ 0&-1 \end{pmatrix} \begin{pmatrix} 1&1\\ 1&-1 \end{pmatrix} [[/math]]

At [math]N=3[/math] the diagonalization formula becomes more complicated, as follows:

[[math]] \begin{pmatrix} 0&1&0\\ 1&0&1\\ 0&1&0 \end{pmatrix} =\frac{1}{4}\begin{pmatrix} 1&1&1\\ 0&\sqrt{2}&-\sqrt{2}\\ -1&1&1 \end{pmatrix} \begin{pmatrix} 0&0&0\\ 0&\sqrt{2}&0\\ 0&0&-\sqrt{2} \end{pmatrix} \begin{pmatrix} 2&0&-2\\ 1&\sqrt{2}&1\\ 1&-\sqrt{2}&1 \end{pmatrix} [[/math]]

At [math]N=4[/math] now, in view of the eigenvalue formula that we found, [math]x^4-3x^2+1=0[/math], we must proceed with care. The equation for the eigenvectors [math]dv=xv[/math] is as follows:

[[math]] \begin{pmatrix} 0&1&0&0\\ 1&0&1&0\\ 0&1&0&1\\ 0&0&1&0 \end{pmatrix} \begin{pmatrix} a\\ b\\ c\\ d \end{pmatrix} =x\begin{pmatrix} a\\ b\\ c\\ d \end{pmatrix} [[/math]]

In other words, the equations to be satisfied are as follows:

[[math]] b=xa [[/math]]

[[math]] a+c=xb [[/math]]

[[math]] b+d=xc [[/math]]

[[math]] c=xd [[/math]]

With the choice [math]a=1[/math], the solutions of these equations are as follows:

[[math]] a=1 [[/math]]

[[math]] b=x [[/math]]

[[math]] c=x^2-1 [[/math]]

[[math]] d=(x^2-1)/x [[/math]]

In order to compute now the [math]c[/math] components of the eigenvectors, we can use the formula [math]x=(\pm1\pm\sqrt{5})/2[/math] from Proposition 2.24. Indeed, this formula gives:

[[math]] \begin{eqnarray*} \left(\frac{\pm1\pm\sqrt{5}}{2}\right)^2-1 &=&\frac{6\pm 2\sqrt{5}}{4}-1\\ &=&\frac{3\pm\sqrt{5}}{2}-1\\ &=&\frac{1\pm\sqrt{5}}{2} \end{eqnarray*} [[/math]]

Thus, almost done, and we deduce that the passage matrix is as follows:

[[math]] P=\begin{pmatrix} 1&1&1&1\\ \frac{1+\sqrt{5}}{2}&\frac{1-\sqrt{5}}{2}&\frac{-1+\sqrt{5}}{2}&\frac{-1-\sqrt{5}}{2}\\ \frac{1+\sqrt{5}}{2}&\frac{1-\sqrt{5}}{2}&\frac{1-\sqrt{5}}{2}&\frac{1+\sqrt{5}}{2}\\ 1&1&-1&-1 \end{pmatrix} [[/math]]

To be more precise, according to our equations above, the first row must consist of [math]a=1[/math] entries. Then the second row must consist of [math]b=x[/math] entries, with [math]x=(\pm1\pm\sqrt{5})/2[/math]. Then the third row must consist of [math]c=x^2-1[/math] entries, but these are easily computed, as explained above. Finally, the fourth row must consist of [math]d=(x^2-1)/x[/math] entries, which means that the fourth row appears by dividing the third row by the second row, which is easily done too. In case you wonder why [math]d=\pm1[/math], here is another proof of this:

[[math]] \begin{eqnarray*} d=\pm1 &\iff&x^2-1=\pm x\\ &\iff&(x^2-1)^2=x^2\\ &\iff&x^4-2x^2+1=x^2\\ &\iff&x^4-3x^2+1=0 \end{eqnarray*} [[/math]]

Very nice all this, and leaving the computation of [math]P^{-1}[/math] for you, here are a few more observations, in relation with what we found in Proposition 2.24:

(1) In the case [math]N=5[/math] the eigenvectors can be computed too, and the diagonalization finished, via the standard method, namely system of equations, and with the numerics involving powers of the eigenvalues that we found. Exercise for you.

(2) The same stays true at [math]N=6[/math], again with the eigenvector numerics involving powers of the eigenvalues, and with these eigenvalues being explicitly computable, via the Cardano formula for degree 3 equations. Have fun with this too, of course.

(3) However, all this does not look very good, and at [math]N=7[/math] and higher we will certainly run into difficult questions, and save for some interesting remarks, normally depending on the parity of [math]N[/math], we will not be able to fully solve the diagonalization problem.

So, what to do? Work some more, of course, the hard way. Proposition 2.24 and its proof look quite trivial, but if you get into the full details of the computations, and let me assign here this, as a key exercise, you will certainly notice that, when computing that determinants, you can sort of use a recurrence method. And, this leads to:

Theorem

The characteristic polynomials [math]P_N[/math] of the segment graphs satisfy

[[math]] P_0=1\quad,\quad P_1=x\quad,\quad P_{N+1}=xP_N-P_{N-1} [[/math]]

and are the well-known Chebycheff polynomials, enjoying lots of interesting properties.

Show Proof

Obviously, many things going on here, ranging from precise to definitional, or even informal, the idea with all this being as follows:

(1) By computing determinants, as indicated above, we are led to the recurrence formula in the statement. Here is the proof at [math]N=4[/math], the general case being similar:

[[math]] \begin{eqnarray*} P_5 &=&\begin{vmatrix} x&-1&0&0&0\\ -1&x&-1&0&0\\ 0&-1&x&-1&0\\ 0&0&-1&x&-1\\ 0&0&0&-1&x \end{vmatrix}\\ &=&x\begin{vmatrix} x&-1&0&0\\ -1&x&-1&0\\ 0&-1&x&-1\\ 0&0&-1&x \end{vmatrix} +\begin{vmatrix} -1&-1&0&0\\ 0&x&-1&0\\ 0&-1&x&-1\\ 0&0&-1&x \end{vmatrix}\\ &=&x\begin{vmatrix} x&-1&0&0\\ -1&x&-1&0\\ 0&-1&x&-1\\ 0&0&-1&x \end{vmatrix} -\begin{vmatrix} x&-1&0\\ -1&x&-1\\ 0&-1&x \end{vmatrix}\\ &=&xP_4-P_3 \end{eqnarray*} [[/math]]

(2) Regarding now the intial values, according to Proposition 2.24 these should normally be [math]P_2=x^2-1[/math] and [math]P_3=x^3-2x[/math], but we can formally add the values [math]P_0=1[/math] and [math]P_1=x[/math], as for the final statement to look better, with this being justified by:

[[math]] P_0=1 [[/math]]

[[math]] P_1=x [[/math]]

[[math]] P_2=xP_1-P_0=x^2-1 [[/math]]

[[math]] P_3=xP_2-P_1=x^3-2x [[/math]]

(3) Thus, we have the recurrence formula in the statement, and with the initial values there, and an internet search, or some advanced calculus know-how, tells us that these are the well-known Chebycheff polynomials, enjoying lots of interesting properties.

■

Very nice all this, and as a continuation, barring as usual the wish to fully solve the diagonalization problem, which remains something difficult, we can for instance go back now to the random walk computations from chapter 1, for the segment graph, with the various choices there for the distinguished vertex, and improve our results there.

However, while this is certainly something doable and interesting, we will not do it here, and rather keep the above as a mere remark, or as an exercise for you. This is because we will be back to all this in the next chapter, with some even better tools.

General references

Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].