I am currently trying to understand the proof of Benson's Lemma (1.9.1) in Generalized Quadrangles by Payne and Thas.


We have two $k × k$ matrices $Q$ and $M$. We want to determine some formula for $\operatorname{tr}(QM)$. The following information has been proven thus far:

The matrix $Q$ is a permutation matrix with order $n$. Hence, the eigenvalues $\xi$ of $Q$ are all $n$-th roots of unity.


The matrix $M$ is a real symmetric matrix. It has eigenvalues $\lambda_0, \lambda_1,$ and $\lambda_2$ with multiplicity $m_0, m_1,$ and $m_2$ respectively. We know that each $\lambda_j$ is an integer, and furthermore that $\lambda_0 = 0$ and $m_1 = 1$.

We also know that $QM = MQ$, and that $\operatorname{tr}(QM)$ is an integer. Lastly, we know that there is some eigenvalue $\theta_1$ of $QM$ such that $\theta_1 = \lambda_1$.


Since both $Q$ and $M$ are normal matrices, they are both diagonalizable. Moreover, since they commute, they are simultaneously diagonalizable (by $S$, say). Then

$$ S(QM)S^{-1} = (SQS^{-1})(SMS^{-1}),$$

and so the eigenvalues $\theta$ of $QM$ have the form $\theta = \xi\lambda$ where $\xi$ is an eigenvalue of $Q$ and $\lambda$ is an eigenvalue of $M$. Since the eigenvalue $\theta_1$ agrees with $\lambda_1$ (which has a multiplicity of $1$ as an eigenvalue of $M$), it follows that $\theta_1$ has a multiplicity of $1$ as an eigenvalue of $QM$. Moreover, since $\lambda_0 = 0$ has a multiplicity of $m_0$ in $M$, it follows that $0$ is an eigenvalue of $QM$ also with multiplicity of $m_0$.

Therefore, all other eigenvalues of $QM$ have the form $\xi\lambda_2$. We know that there are exactly $m_2$ such eigenvalues.

The Problem

Payne and Thas claim the following fact:

For each divisor $d$ of $n$, let $U_d$ denote the sum of all primitive $d$-th roots of unity. Then $U_d$ is an integer. For each divisor $d$ of $n$, the primitive $d$-th roots of unity all contribute the same number of times to eigenvalues $\theta$ of $QM$ with $|\theta| = \lambda_2$. Let $a_d$ denote the multiplicity of $\xi_d\lambda_2$ as an eigenvalue of $QM$, with $d \mid n$ and $\xi_d$ a primitive $d$-th root of unity, then we have

$$\operatorname{tr}(QM) = \lambda_1 + \sum_{d \mid n}(a_dU_d)\lambda_2.$$

This bolded statement is what I am having trouble understanding.

  • If $\xi_1$ and $\xi_2$ are two different primitive $d$-th roots of unity, why should the multiplicity of $\xi_1\lambda_2$ and $\xi_2\lambda_2$ be equal?

  • If $\xi$ is a $d$-th root of unity, and there exists an eigenvalue $\xi\lambda_2$ of $QM$, why do all other $d$-th roots of unity appear as well?


This is a geometric fact—the roots of unity must all appear equally often because otherwise the sum of all the eigenvalues of $QM$ (the trace of $QM$) won't be an integer—it'll be a complex number.

Note that the eigenvalues of $M$ are integers, and the eigenvalues of $Q$ are roots of unity, and the eigenvalues of $QM$ are products of an eigenvalue of $M$ and an eigenvalue of $Q$.

From a purely geometric perspective, if $\lambda$ is an integer and $u_1, \ldots, u_d$ are the $d$th roots of unity, then $\lambda u_1, \ldots, \lambda u_d$ are equally-spaced complex numbers in the plane with equal magnitude. Their sum is an integer $(\lambda)$ but if we take any unevenly-weighted linear combination of them, the result is necessarily a complex number.

Because the trace of a matrix is equal to the sum of its eigenvalues (counting multiplicities repeatedly), and because the trace of $QM$ is known to be an integer, there cannot be any uneven weights. It must be that for each integer eigenvalue $\lambda$ of $M$, the values $\lambda u_1, \ldots \lambda u_d$ occur equally often as eigenvalues of $QM$ (i.e. have the same multiplicity.)


$\def\i{\mathrm{i}}$First, by definition, for any $d \in \mathbb{N}_+$, the $d$-th cyclotomic polynomial is$$ {\mit Φ}_d(x) = \prod_{\substack{0 \leqslant l \leqslant d - 1\\(l, d) = 1}} ( x - ω_d^l), $$ where $ω_d = \exp\left( \dfrac{2π\i}{d} \right)$. Note that ${\mit Φ}_d(x) \in \mathbb{Z}[x] \subseteq \mathbb{Q}[x]$ and ${\mit Φ}_d(x)$ is irreducible in $\mathbb{Q}[x]$, thus for any $0 \leqslant l \leqslant d - 1$ such that $(l, d) = 1$, the minimal polynomial of $ω_d^l$ over $\mathbb{Q}$ is ${\mit Φ}_d(x)$.

Next, for any $f(x) \in \mathbb{Q}[x]$, if $\dfrac{f(x)}{x - ω_d^l} \in \mathbb{C}[x]$ for some $0 \leqslant l \leqslant d - 1 $ and $(l, d) = 1$, i.e. $f(ω_d^l) = 0$, because the minimal polynomial of $ω_d^l$ over $\mathbb{Q}$ is ${\mit Φ}_d(x)$, then $\dfrac{f(x)}{{\mit Φ}_d(x)} \in \mathbb{Q}[x]$. This further implies that if $\dfrac{f(x)}{(x - ω_d^l)^m} \in \mathbb{C}[x]$ for some $m \in \mathbb{N}_+$, then $\dfrac{f(x)}{({\mit Φ}_d(x))^m} \in \mathbb{Q}[x]$.

Now, because all eigenvalues of $QM$ are of the form $ξλ$, where $ξ$ and $λ$ are eigenvalues of $Q$ and $M$, respectively, and the multiplicity of $λ_0 = 0$ as an eigenvalue of $M$ is $m_0$, and that of $λ_1$ as an eigenvalue of $M$ is $1$, and $θ_1 = λ_1 \in \mathbb{Z}$, then$$ |xI - QM| = x^{m_0} (x - λ_1) f_0(x), $$ where$$ f_0(x) = \prod_{j = 1}^{k - m_0 - 1} (x - λ_2 ξ_j) \in \mathbb{C}[x], \quad ξ_j^n = 1. $$ Note that $QM \in \mathrm{M}_{k × k}(\mathbb{Z})$ implies $|xI - QM| \in \mathbb{Z}[x]$, then $f_0(x) \in \mathbb{Z}[x]$. Define$$ f(x) = \frac{1}{λ_2^{k - m_0 - 1}} f_0(λ_2 x) = \prod_{j = 1}^{k - m_0 - 1} (x - ξ_j) \in \mathbb{Q}[x]. $$ For any $d \mid n$, suppose the multiplicity of $ω_d^l$ ($0 \leqslant l \leqslant d - 1$ and $(l, d) = 1$) in $f(x)$ is $a_{d, l}$ and $a_d = \max\limits_{\substack{0 \leqslant l \leqslant d - 1\\(l, d) = 1}} a_{d, l}$. Because $\dfrac{f(x)}{(x - ω_d^l)^{a_d}} \in \mathbb{C}[x]$ for some $l$, then $\dfrac{f(x)}{({\mit Φ}_d(x))^{a_d}} \in \mathbb{Q}[x]$, which implies $a_{d, l} = a_d$ for all $0 \leqslant l \leqslant d - 1$ and $(l, d) = 1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.