\documentstyle[a4,12pt]{article}
\title{The spectrum of the van Leijenhorst matrix}
\author{A. Blokhuis, A.E. Brouwer \& R. Riebeek}
\date{May 3, 1996 - Marijn's birthday}
\begin{document}
\maketitle

\newtheorem{Theorem} {Theorem} [section]
\newcommand{\mod}{{\rm mod\,}}
\newcommand{\qed  }{\hfill$\Box$\medskip}

Dick van Leijenhorst asked for the spectrum of the matrix $M$
of order $n$ with $M_{ij} = 0$ if $i+j \le n$ and $M_{ij} = 1$
if $i+j \ge n+1$.

\begin{Theorem}
$M$ has eigenvalues $(2 \cos {\pi j \over 2n+1})^{-1}$,
where $1 \le j \le 2n$ and $j \equiv n$ $(\mod 2)$.
\end{Theorem}

The form of the spectrum suggests that it is more natural to
consider $M^{-1}$, which has entries
$(M^{-1})_{ij} = 1$ if $i+j = n+1$, $(M^{-1})_{ij} = -1$ if $i+j = n$,
and $(M^{-1})_{ij} = 0$ otherwise.

Let $N = (-1)^n M^{-1}$. We have to prove that $N$ has eigenvalues
$2 \cos {2 \pi j \over 2n+1}$, $1 \le j \le n$.
We can write $N = A - B$, where both $A$ and $B$ are 0-1 matrices
(and $A$ and $B$ are zero wherever $N$ is zero). With
$P = \left( \begin{array}{cc}
A & B \\
B & A 
\end{array} \right)$
we see that $P$ is the adjacency matrix of a path of length $2n$.
Each eigenvector $u$ of $N$ with eigenvalue $\theta$ yields
an antisymmetric eigenvector
$\left( \begin{array}{c}
u \\
-u
\end{array} \right)$
of $P$ with eigenvalue $\theta$, and conversely.
But the antisymmetric eigenvectors of $P$ are precisely those that
can be extended to eigenvectors of a $(2n+1)$-cycle by defining it
to be zero on the additional point. It follows that indeed the eigenvalues
are $\theta = 2 \cos {2 \pi j \over 2n+1}$, where $1 \le j \le n$.
\qed
\end{document}


