Eigenvalues of Matrices whose Elements are Ramanujan Sums or Kloosterman Sums

Noboru Ushiroya National Institute of Technology Wakayama College Nadacho Gobo Wakayama 644-0023 Japan

              ushiroya@wakayama-nct.ac.jp

Abstract

Let c_{q}(n) be the Ramanujan sum and let S(m, n; q) be the Kloosterman sum. We study the eigenvalues of q × q matrices whose (m, n) entry is c_{q}(m − n) or S(m, n; q), where q is a fixed positive integer. We also study the eigenvalues of matrices whose entries are sums of Ramanujan sums or sums of Kloosterman sums.

1 Introduction

For q, n ∈ ℕ = {1, 2, …}, Ramanujan [9] defined the Ramanujan sum c_{q}(n) by

c_{q}(n) = ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} exp(\frac{2πikn}{q}),

where gcd(k, q) is the greatest common divisor of k and q. For m, n, q ∈ ℕ, Kloosterman [5] defined the Kloosterman sum S(m, n; q) by

S(m, n; q) = ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} exp(\frac{2πi}{q}(mk + nk^{∗})),

where k^{∗} is the inverse of k modulo q. If m = 0 or n = 0, then the Kloosterman sum reduces to the Ramanujan sum. The Ramanujan sum and the Kloosterman sum have many interesting properties. However, in this paper we focus only on the eigenvalues of matrices whose elements are Ramanujan sums or Kloosterman sums. A reason why we consider these eigenvalues is as follows. The well-known large sieve inequality (see, e.g., [2])

∑_{q≤Q} ∑_{gcd(k,q)=1}|∑_{n≤x} a_{n} exp(\frac{2πikn}{q})|^{2} ≤ (Q^{2} + 4πx) ∑_{n≤x} |a_{n}|^{2}  (1)

can be rewritten as

∑_{m,n≤x} a_{m}\overline{a_{n}}(∑_{q≤Q} c_{q}(m − n)) ≤ (Q^{2} + 4πx) ∑_{n≤x} |a_{n}|^{2},

where \overline{a_{n}} is the complex conjugate of a_{n}, since

∑_{q≤Q} ∑_{gcd(k,q)=1}|∑_{n≤x} a_{n} exp(\frac{2πikn}{q})|^{2}

= ∑_{q≤Q} ∑_{gcd(k,q)=1} ∑_{m,n≤x} a_{m}\overline{a_{n}} exp(\frac{2πik(m − n)}{q})

= ∑_{m,n≤x} a_{m}\overline{a_{n}} ∑_{q≤Q} ∑_{gcd(k,q)=1} exp(\frac{2πik(m − n)}{q})

= ∑_{m,n≤x} a_{m}\overline{a_{n}}(∑_{q≤Q} c_{q}(m − n)).

Let X = (X_{mn})_{m,n=1}^{x} be the matrix whose (m, n) entry is X_{mn} = ∑_{q≤Q} c_{q}(m − n) and let a = (a_{1}, a_{2}, …, a_{x}). From (1) we see that the Rayleigh quotient

R(X, a) := ( ∑_{m,n≤x} a_{m}X_{mn}\overline{a_{n}})/(∑_{n≤x} a_{n}\overline{a_{n}})

is not less than Q^{2} + 4πx for every nonzero vector a. If we can prove that X is nonnegative definite, then we have R(X, a) ∈ [λ_{m}(Q, x), λ_{M}(Q, x)], where λ_{m}(Q, x), λ_{M}(Q, x) are the minimal and maximal positive eigenvalue of the matrix X respectively, and a is a vector perpendicular to the eigenspace corresponding to the eigenvalue 0. We cannot explicitly obtain λ_{M}(Q, x) or λ_{m}(Q, x) under general conditions; however, we prove in Theorem 2 that λ_{M}(Q, x) = λ_{m}(Q, x) = x holds under a very restricted condition in which x is the least common multiple of 1, 2, …, Q. Moreover, since

∑_{q≤Q} ∑_{gcd(k,q)=1}|∑_{n≤x} a_{n} exp(\frac{2πikn}{q})|^{2} ≤ ∑_{q≤Q} ∑_{gcd(k,q)=1} (∑_{n≤x} |a_{n}|)^{2}

= ∑_{q≤Q} φ(q) (∑_{n≤x} |a_{n}|)^{2}

≪ Q^{2} (∑_{n≤x} |a_{n}|)^{2}

holds for every sequence {a_{n}}_{n=1}^{x}, we have

(∑_{n≤x} |a_{n}|)^{2} ≥ \frac{λ_{m}(Q, x)}{Q^{2}} ∑_{n≤x} |a_{n}|^{2}  (2)

for every vector (a_{1}, a_{2}, …, a_{x}) perpendicular to the eigenspace corresponding to the eigenvalue 0. If we take

a_{n} = \begin{cases}1, & if n ∈ S ; \\ 0, & otherwise, \end{cases}

for some set S. and if we can show that (a_{1}, a_{2}, …, a_{x}) is perpendicular to the eigenspace corresponding to the eigenvalue 0, then we have from (2) that

#\{S ∩ [1, x]\} ≥ \frac{λ_{m}(Q, x)}{Q^{2}},

from which

lim_{x→∞} #{S ∩ [1, x]} = ∞

follows in the case λ_{m}(Q, x) = x and Q = x^{1/2−ε} for some ε > 0. Regretfully, we can obtain neither λ_{M}(Q, x) nor λ_{m}(Q, x) under general conditions; however, we expect that the above idea will lead to an estimate from below.

We also investigate the eigenvalues of B_{q} = (S(m, n; q))_{m,n=1}^{q} and Y = (Y_{mn})_{m.n=1}^{x} = (∑_{q=1}^{Q} S(m, n; q))_{m,n=1}^{x}, where x is the least common multiple of 1, 2, …, Q. Many results concerning the Kloosterman sum have been obtained by many mathematicians. For example, it is well known that Weil’s bound [12]

|S(a, b; q)| ≤ τ(q) gcd(a, b, q)\sqrt{q}

holds where τ(q) = ∑_{d|q} 1. Kuznetsov’s bound [6]

∑_{q≤Q} \frac{S(a, b; q)}{q} ≪ Q^{\frac{1}{6} +ε}

is also well known. However, as for the eigenvalues of matrices whose elements are the Kloosterman sums, to my knowledge, few results are known. We obtain in Theorem 3 and 4 the eigenvalues of matrices whose elements are Kloosterman sums. Of course there is no relation between the eigenvalues and Weil’s bound or Kuznetsov’s bound, however, we expect that our study contributes somewhat to the theory of Kloosterman sums.

2 Properties of Ramanujan sums and Kloosterman sums

In this section we show some properties of the Ramanujan sums c_{q}(n) and the Kloosterman sums S(m, n; q). Let

δ(m, n) = \begin{cases}1, & if m = n ; \\ 0, & if m ≠ n, \end{cases}

and let

φ(q) = #{k ≤ q; gcd(k, q) = 1}

be the Euler totient function. The following properties of the Ramanujan sums are well known (see, e.g., [1, 7, 8, 10]).

c_{q}(n) = c_{q}(−n),  (3)
c_{q}(0) = φ(q),  (4)
c_{q}(n) = c_{q}(n′) if n ≡ n′ (mod q),  (5)
∑_{k=1}^{q} c_{q}(k) = 0.  (6)

The following properties of the Kloosterman sums are also well known (see, e.g., [4]).

S(m, n; q) = S(n, m; q),
S(m, n; q) = S(m′, n′; q) if m ≡ m′ (mod q) and n ≡ n′ (mod q).

We write d | n if d divides n. We first prove the following lemma.

Lemma 1. If x ∈ ℕ, q | x and r | x, then we have

∑_{a=1}^{x} c_{q}(m − a)c_{r}(a − n) = \begin{cases}xc_{q}(m − n), & if q = r; \\ 0, & otherwise, \end{cases}  (7)

∑_{a=1}^{x} S(m, a; q)S(a, n; r) = \begin{cases}xc_{q}(m − n), & if q = r; \\ 0, & otherwise. \end{cases}  (8)

In order to prove Lemma 1, we prepare the following lemma.

Lemma 2. If x ∈ ℕ, q | x, r | x and gcd(k, q) = gcd(ℓ, r) = 1, then we have

∑_{a=1}^{x} exp(2πi(\frac{k}{q} + \frac{ℓ}{r})a) = \begin{cases}x, & if q = r and k + ℓ ≡ 0 (mod q); \\ 0, & otherwise. \end{cases}

Proof. The proof proceeds along the same line as the proof of [8, Theorem 1]. We first note that the following holds by the partial-sum formula of a geometric series.

∑_{a=1}^{x} exp(2πi(\frac{k}{q} + \frac{ℓ}{r})a) = \begin{cases}x, & if k/q + ℓ/r is an integer; \\ 0, & otherwise. \end{cases}

If q ≠ r, then k/q + ℓ/r = (kr + ℓq)/qr is not an integer since gcd(k, q) = gcd(ℓ, r) = 1. If q = r, then k/q + ℓ/r = (k + ℓ)/q is an integer or not according to whether k + ℓ is congruent to 0 (mod q) or not. This completes the proof of Lemma 2.

Now we can prove Lemma 1.

Proof of Lemma 1. By the definition of the Ramanujan sums we have

∑_{a=1}^{x} c_{q}(m − a)c_{r}(a − n) = ∑_{a=1}^{x} ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} exp(\frac{2πik(m − a)}{q}) ∑_{\begin{matrix}ℓ=1 \\ gcd(ℓ,r)=1 \end{matrix}}^{r} exp(\frac{2πiℓ(a − n)}{r})

= ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} ∑_{\begin{matrix}ℓ=1 \\ gcd(ℓ,r)=1 \end{matrix}}^{r} exp(2πi(\frac{km}{q} − \frac{ℓn}{r})) ∑_{a=1}^{x} exp(2πi(−\frac{k}{q} + \frac{ℓ}{r})a).

Since

∑_{a=1}^{x} exp(2πi(−\frac{k}{q} + \frac{ℓ}{r})a) = \begin{cases}x, & if q = r and −k + ℓ ≡ 0 (mod q); \\ 0, & otherwise; \end{cases}

holds by Lemma 2, we have

∑_{a=1}^{x} c_{q}(m − a)c_{r}(a − n) = xδ(q, r) ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} ∑_{\begin{matrix}ℓ=1 \\ gcd(ℓ,q)=1 \\ ℓ≡k (mod q) \end{matrix}}^{q} exp(2πi(\frac{km}{q} − \frac{ℓn}{q}))

= xδ(q, r) ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} exp(\frac{2πi}{q}(m − n)k)

= xδ(q, r)c_{q}(m − n) = \begin{cases}xc_{q}(m − n), & if q = r; \\ 0, & otherwise. \end{cases}

Therefore (7) holds.

Next we prove (8). We have

∑_{a=1}^{x} S(m, a; q)S(a, n; r) = ∑_{a=1}^{x} ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} exp(\frac{2πi}{q}(mk + ak^{∗})) ∑_{\begin{matrix}ℓ=1 \\ gcd(ℓ,r)=1 \end{matrix}}^{r} exp(\frac{2πi}{r}(aℓ + nℓ^{∗}))

= ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} ∑_{\begin{matrix}ℓ=1 \\ gcd(ℓ,r)=1 \end{matrix}}^{r} exp(2πi(\frac{mk}{q} + \frac{nℓ^{∗}}{r})) ∑_{a=1}^{x} exp(2πi(\frac{k^{∗}}{q} + \frac{ℓ}{r})a).

Since

∑_{a=1}^{x} exp(2πi(\frac{k^{∗}}{q} + \frac{ℓ}{r})a) = \begin{cases}x, & if q = r and k^{∗} + ℓ ≡ 0 (mod q); \\ 0, & otherwise \end{cases}

holds by Lemma 2 and since k^{∗} + ℓ ≡ 0 (mod q) is equivalent to ℓ^{∗} ≡ −k (mod q), we have

∑_{a=1}^{x} S(m, a; q)S(a, n; r) = xδ(q, r) ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} ∑_{\begin{matrix}ℓ=1 \\ gcd(ℓ,q)=1 \\ ℓ^{∗}≡−k (mod q) \end{matrix}}^{q} exp(2πi(\frac{mk}{q} + \frac{nℓ^{∗}}{q}))

= xδ(q, r) ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} exp(\frac{2πi}{q}(m − n)k)

= xδ(q, r)c_{q}(m − n) = \begin{cases}xc_{q}(m − n), \\ & = if q = r; \\ 0, & otherwise. \end{cases}

Therefore (8) holds. This completes the proof of Lemma 1.

Consider the function φ̃ defined by

φ̃(q) = #{1 ≤ k ≤ q; gcd(k, q) = 1, k + k^{∗} ≡ 0 (mod q)},

where k^{∗} is the inverse of k (mod q). It is easy to see that φ̃(q) can be rewritten as

φ̃(q) = #{1 ≤ k ≤ q; gcd(k, q) = 1, k^{2} ≡ −1 (mod q)}.

Recall that an arithmetic function f : ℕ ↦ ℂ is said to be a multiplicative function if f satisfies

f(mn) = f(m)f(n)

for every m, n ∈ ℕ satisfying gcd(m, n) = 1. We let P denote the set of prime numbers. We have the following lemma.

Lemma 3. The function q ↦ φ̃(q) is a multiplicative function satisfying

φ̃(2) = 1,
φ̃(2^{e}) = 0 if e ≥ 2,

φ̃(p^{e}) = 0 if p ∈ P, p ≡ −1 (mod 4) and e ≥ 1, φ̃(p^{e}) = 2 if p ∈ P, p ≡ 1 (mod 4) and e ≥ 1.

Proof. Multiplicativity follows from the Chinese remainder theorem. The other parts follow from [11, p. 91].

Next we prove the following lemma.

Lemma 4. If x ∈ ℕ, q | x and r | x, then we have

∑_{m=1}^{x} ∑_{a=1}^{x} c_{q}(m − a)S(a, m; r) = \begin{cases}x^{2}φ̃(q), & if q = r; \\ 0, & otherwise. \end{cases}

Proof. First, we have

∑_{m=1}^{x} ∑_{a=1}^{x} c_{q}(m − a)S(a, m; r)

= ∑_{m=1}^{x} ∑_{a=1}^{x} ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} exp(\frac{2πik(m − a)}{q}) ∑_{\begin{matrix}ℓ=1 \\ gcd(ℓ,r)=1 \end{matrix}}^{r} exp(\frac{2πi}{r}(aℓ + mℓ^{∗}))

= ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} ∑_{\begin{matrix}ℓ=1 \\ gcd(ℓ,r)=1 \end{matrix}}^{r} ∑_{m=1}^{x} exp(2πi(\frac{k}{q} + \frac{ℓ^{∗}}{r})m) ∑_{a=1}^{x} exp(2πi(−\frac{k}{q} + \frac{ℓ}{r})a).  (9)

Since

∑_{m=1}^{x} exp(2πi(\frac{k}{q} + \frac{ℓ^{∗}}{r})m) = \begin{cases}x, & if q = r and k + ℓ^{∗} ≡ 0 (mod q); \\ 0, & otherwise, \end{cases}

∑_{a=1}^{x} exp(2πi(−\frac{k}{q} + \frac{ℓ}{r})a) = \begin{cases}x, & if q = r and −k + ℓ ≡ 0 (mod q); \\ 0, & otherwise \end{cases}

hold by Lemma 2, and since

k + ℓ^{∗} ≡ 0 (mod q) and − k + ℓ ≡ 0 (mod q)

is equivalent to

ℓ ≡ k (mod q) and k + k^{∗} ≡ 0 (mod q),

we see that (9) is equal to

x^{2}δ(q, r) ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \\ k+k^{∗}≡0 (mod q) \end{matrix}}^{q} ∑_{\begin{matrix}ℓ=1 \\ gcd(ℓ,q)=1 \\ ℓ≡k (mod q) \end{matrix}}^{q} 1 = x^{2}δ(q, r) ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \\ k+k^{∗}≡0 (mod q) \end{matrix}}^{q} 1

= x^{2}δ(q, r)φ̃(q) = \begin{cases}x^{2}φ̃(q), & if q = r; \\ 0, & otherwise. \end{cases}

This completes the proof of Lemma 4.

3 Some results

3.1 The case of Ramanujan sums

Let c_{q}(n) be the Ramanujan sums. We first consider the following q × q matrix

A_{q} = (c_{q}(m − n))_{m,n=1}^{q} = ( \begin{matrix}c_{q}(0) & c_{q}(1) & c_{q}(2) & ⋯ & c_{q}(q − 1) \\ c_{q}(1) & c_{q}(0) & c_{q}(1) & ⋯ & c_{q}(q − 2) \\ c_{q}(2) & c_{q}(1) & c_{q}(0) & ⋯ & c_{q}(q − 3) \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ c_{q}(q − 1) & c_{q}(q − 2) & c_{q}(q − 3) & ⋯ & c_{q}(0) \end{matrix} ) ,

where q is a fixed positive integer. We begin with the following lemma. Lemma 5. Let A_{q} = (c_{q}(m − n))_{m,n=1}^{q}. For every integer j ≥ 2, we have

A_{q}^{j} = q^{j−1}A_{q}.  (10)

Proof. We first prove (10) for j = 2. From Lemma 1 we see that the (m, n) entry of A_{q}^{2} equals

∑_{a=1}^{q} c_{q}(m − a)c_{q}(a − n) = qc_{q}(m − n),

which is equal to the (m, n) entry of qA_{q}. The general case j ≥ 2 follows by induction.

We let tr(M) = ∑_{m=1}^{k} M_{mm} denote the trace of M where M is a k × k matrix. Next we consider the trace of A_{q}^{j} where j ∈ ℕ. Lemma 6. Let A_{q} = (c_{q}(m − n))_{m,n=1}^{q}. Then we have for every j ∈ ℕ

tr(A_{q}^{j}) = q^{j}φ(q).  (11)

Proof. Since c_{q}(0) = φ(q), we have

tr(A_{q}) = ∑_{m=1}^{q} c_{q}(m − m) = ∑_{m=1}^{q} c_{q}(0) = ∑_{m=1}^{q} φ(q) = qφ(q).

Therefore (11) holds for j = 1. If j ≥ 2, then we have by Lemma 5 and the above result

tr(A_{q}^{j}) = q^{j−1}tr(A_{q}) = q^{j−1}qφ(q) = q^{j}φ(q).

Let E_{q} denote the q × q identity matrix and let det(M) denote the determinant of M where M is a square matrix. We prove the following theorem.

Theorem 1. Let A_{q} = (c_{q}(m − n))_{m,n=1}^{q}. Then the characteristic polynomial of A_{q} is

det(λE_{q} − A_{q}) = λ^{q−φ(q)}(λ − q)^{φ(q)}.

In particular, the matrix A_{q} has eigenvalues 0, q with multiplicity q − φ(q), φ(q), respectively.

Proof. We first suppose λ > q. Since det(exp(M)) = exp(tr(M)) holds for every square matrix M, we have

det(λE_{q} − A_{q}) = λ^{q} det(E_{q} − \frac{1}{λ}A_{q}) = λ^{q} exp(tr(log(E_{q} − \frac{1}{λ}A_{q}))).

Since

log(E_{q} − \frac{1}{λ}A_{q}) = ∑_{j=1}^{∞} \frac{(−1)^{j−1}}{j} (−\frac{1}{λ}A_{q})^{j} = ∑_{j=1}^{∞} \frac{(−1)^{j−1}}{j} (−\frac{1}{λ})^{j}A_{q}^{j}

holds, we have by Lemma 6

tr(log(E_{q} − \frac{1}{λ}A_{q})) = ∑_{j=1}^{∞} \frac{(−1)^{j−1}}{j} (−\frac{1}{λ})^{j}tr(A_{q}^{j})

= ∑_{j=1}^{∞} \frac{(−1)^{j−1}}{j} (−\frac{1}{λ})^{j}q^{j}φ(q) = φ(q) log(1 − \frac{q}{λ}).

Therefore we obtain

det(λE_{q} − A_{q}) = λ^{q} exp(φ(q) log(1 − \frac{q}{λ}))
= λ^{q}(1 − \frac{q}{λ})^{φ(q)} = λ^{q−φ(q)}(λ − q)^{φ(q)}.  (12)

Since (12) holds for every λ > q and both sides of (12) are polynomials of λ, we see that (12) holds for every λ. This completes the proof of Theorem 1.

Remark 1. A q × q matrix C is called a circulant matrix if C takes the form

C = (\begin{matrix}c(0) & c(q − 1) & ⋯ & c(2) & c(1) \\ c(1) & c(0) & c(q − 1) & & c(2) \\ ⋮ & c(1) & c(0) & ... & ⋮ \\ c(q − 2) & & ... & ... & c(q − 1) \\ c(q − 1) & c(q − 2) & ⋯ & c(1) & c(0) \end{matrix}) .  (13)

We immediately see that A_{q} = (c_{q}(m − n))_{m,n=1}^{q} is a circulant matrix since c_{q}(a) = c_{q}(−a) = c_{q}(q − a) holds for every a, 1 ≤ a ≤ q. It is well known that the eigenvalues of (13) are given by

λ_{j} = ∑_{a=1}^{q} c(q − a)ω_{j}^{a},  (14)

where ω_{j} = exp(2πij/q) and 1 ≤ j ≤ q. Substituting c(q − a) by c_{q}(q − a) = c_{q}(a), we see that the eigenvalues of A_{q} are equal to

λ_{j} = ∑_{a=1}^{q} c_{q}(a)ω_{j}^{a} = ∑_{a=1}^{q} ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} exp(\frac{2πika}{q}) exp(\frac{2πija}{q})

= ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} ∑_{a=1}^{q} exp(\frac{2πia(k + j)}{q}) = \begin{cases}q, & if gcd(j, q) = 1; \\ 0, & otherwise. \end{cases}

Thus we can easily obtain the eigenvalues of A_{q}. However, we proved Theorem 1 without using a property of a circulant matrix since the proof of Theorem 1 applies also to that of Theorem 3.

As for the eigenvectors of a circulant matrix, it is also well known that the eigenvectors of (13) are given by

v_{j} = (1, ω_{j}, ω_{j}^{2}, …, ω_{j}^{q−1}),  (15)

where ω_{j} = exp(2πij/q) and 1 ≤ j ≤ q.

From the above remark we immediately obtain the following corollary.

Corollary 1. Let A_{q} = (c_{q}(m − n))_{m,n=1}^{q}. Then the eigenvalues λ_{j} and the eigenvectors v_{j} (1 ≤ j ≤ q) of A_{q} are given by the following.

If gcd(j, q) = 1, then

λ_{j} = q,

v_{j} = (\underbrace{1, ω_{j}, ω_{j}^{2}, …, ω_{j}^{q−1}}_{q}),

and if gcd(j, q) > 1, then

λ_{j} = 0,

v_{j} = (\underbrace{1, ω_{j}, ω_{j}^{2}, …, ω_{j}^{q′−1}}_{q′}, \underbrace{1, ω_{j}, ω_{j}^{2}, …, ω_{j}^{q′−1}}_{q′}, …, \underbrace{1, ω_{j}, ω_{j}^{2}, …, ω_{j}^{q′−1}}_{q′}),

where ω_{j} = exp(2πij/q) and q′ = q/ gcd(j, q).

Next we consider the x × x matrix X = (X_{mn})_{m,n=1}^{x} = (∑_{q=1}^{Q} c_{q}(m − n))_{m,n=1}^{x} where Q is a fixed positive integer and x is the least common multiple of 1, 2, …, Q. We proceed along similar lines to the case of A_{q}.

Lemma 7. Let X = (X_{mn})_{m,n=1}^{x} = (∑_{q=1}^{Q} c_{q}(m − n))_{m,n=1}^{x} where x is the least common multiple of 1, 2, …, Q. For every integer j ≥ 2, we have

X^{j} = x^{j−1}X.  (16)

Proof. First, we prove (16) for j = 2. From Lemma 1, we see that the (m, n) component of X^{2} equals

(X^{2})_{mn} = ∑_{k=1}^{x} X_{mk}X_{kn} = ∑_{k=1}^{x}(∑_{q=1}^{Q} c_{q}(m − k))(∑_{r=1}^{Q} c_{r}(k − n))

= ∑_{q=1}^{Q} ∑_{r=1}^{Q} ∑_{k=1}^{x} c_{q}(m − k)c_{r}(k − n) = ∑_{q=1}^{Q} ∑_{r=1}^{Q} xδ(q, r)c_{q}(m − n)

= x ∑_{q=1}^{Q} c_{q}(m − n) = xX_{mn}.

Hence, (16) holds for j = 2. The general case j ≥ 2 follows by induction.

Next we consider the trace of X^{j} where j ∈ ℕ. We set Φ(Q) = ∑_{q=1}^{Q} φ(q).

Lemma 8. Let X = (X_{mn})_{m,n=1}^{x} = (∑_{q=1}^{Q} c_{q}(m − n))_{m,n=1}^{x} where x is the least common multiple of 1, 2, …, Q. Then we have for every j ∈ ℕ

tr(X^{j}) = x^{j}Φ(Q).  (17)

Proof. Since c_{q}(0) = φ(q), we have

tr(X) = ∑_{m=1}^{x} X_{mm} = ∑_{m=1}^{x} ∑_{q=1}^{Q} c_{q}(0) = ∑_{m=1}^{x} ∑_{q=1}^{Q} φ(q) = xΦ(Q).

Thus (17) holds for j = 1. If j ≥ 2, then we have by Lemma 7 and the above result

tr(X^{j}) = x^{j−1}tr(X) = x^{j−1}xΦ(Q) = x^{j}Φ(Q).

Therefore (17) holds for every j ∈ ℕ.

Let E_{x} be the x × x identity matrix where x is a positive integer. We prove the following theorem.

Theorem 2. Let X = (X_{mn})_{m,n=1}^{x} = (∑_{q=1}^{Q} c_{q}(m − n))_{m,n=1}^{x} where x is the least common multiple of 1, 2, …, Q. Then the characteristic polynomial of X is

det(λE_{x} − X) = λ^{x−Φ(Q)}(λ − x)^{Φ(Q)}.

In particular, the matrix X has eigenvalues 0, x with multiplicity x−Φ(Q), Φ(Q), respectively.

Proof. The proof proceeds along the same lines as the proof of Theorem 1. We first suppose λ > x. Since det(exp(M)) = exp(tr(M)) holds for every square matrix M, we have

det(λE_{x} − X) = λ^{x} det(E_{x} − \frac{1}{λ}X) = λ^{x} exp(tr(log(E_{x} − \frac{1}{λ}X))).

Since

log(E_{x} − \frac{1}{λ}X) = ∑_{j=1}^{∞} \frac{(−1)^{j−1}}{j} (−\frac{1}{λ}X)^{j} = ∑_{j=1}^{∞} \frac{(−1)^{j−1}}{j} (−\frac{1}{λ})^{j}X^{j}

holds, we have by Lemma 8

tr(log(E_{x} − \frac{1}{λ}X)) = ∑_{j=1}^{∞} \frac{(−1)^{j−1}}{j} (−\frac{1}{λ})^{j}tr(X^{j})

= ∑_{j=1}^{∞} \frac{(−1)^{j−1}}{j} (−\frac{1}{λ})^{j}x^{j}Φ(Q) = Φ(Q) log(1 − \frac{x}{λ}).

Therefore we have

det(λE_{x} − X) = λ^{x} exp(Φ(Q) log(1 − \frac{x}{λ}))
= λ^{x}(1 − \frac{x}{λ})^{Φ(Q)} = λ^{x−Φ(Q)}(λ − x)^{Φ(Q)}.  (18)

Since (18) holds for every λ > x and both sides of (18) are polynomials of λ, (18) holds for every λ. This completes the proof of Theorem 2.

Remark 2. X as well as A_{q} is a circulant matrix. By (14) we see that the eigenvalues λ_{j} (1 ≤ j ≤ x) of X are given by

λ_{j} = ∑_{a=1}^{x} ∑_{q=1}^{Q} c_{q}(a)ω_{j}^{a} = ∑_{q=1}^{Q} ∑_{a=1}^{x} ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} exp(2πia(\frac{k}{q} + \frac{j}{x}))

= ∑_{q=1}^{Q} ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} ∑_{a=1}^{x} exp(2πia(\frac{k}{q} + \frac{j′}{x′} )),

where ω_{j} = exp(2πij/x), j′ = j/ gcd(j, x), and x′ = x/ gcd(j, x). Since it follows from Lemma 2 that

∑_{a=1}^{x} exp(2πia(\frac{k}{q} + \frac{j′}{x′} )) = \begin{cases}x, & if q = x′ and k + j′ ≡ 0 (mod q); \\ 0, & otherwise, \end{cases}

we have

λ_{j} = ∑_{q=1}^{Q} ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \\ k+j′≡0 (mod q) \end{matrix}}^{q} xδ(q, x′) = x ∑_{q=1}^{Q} δ(q, x′) ∑_{\begin{matrix}k=1 \\ gcd(k,x′)=1 \\ k≡−j′ (mod q) \end{matrix}}^{q} 1 = \begin{cases}x, & if x′ ≤ Q; \\ 0, & otherwise. \end{cases}  (19)

Therefore Theorem 2 can be recovered from the following lemma.

Lemma 9. Let Q ∈ ℕ and x is the least common multiple of 1, 2, …, Q. Then we have

#\{1 ≤ j ≤ x; \frac{x}{gcd(j, x)} ≤ Q\} = Φ(q).

Proof. It is easy to see that

#\{1 ≤ j ≤ x; \frac{x}{gcd(j, x)} ≤ Q\}

= ∑_{q=1}^{Q} #\{1 ≤ j ≤ x; \frac{x}{gcd(j, x)} = q\}

= ∑_{q=1}^{Q} #\{1 ≤ j ≤ x; gcd(j, x) = \frac{x}{q}\}

= ∑_{q=1}^{Q} #\{1 ≤ j ≤ x; j = \frac{x}{q}k for some 1 ≤ k ≤ q such that gcd(k, q) = 1\}

= ∑_{q=1}^{Q} #{1 ≤ k ≤ q; gcd(k, q) = 1} = ∑_{q=1}^{Q} φ(q) = Φ(Q).

Now we have the following corollary by (15) and (19).

Corollary 2. Let X = (X_{mn})_{m,n=1}^{x} = (∑_{q=1}^{Q} c_{q}(m − n))_{m,n=1}^{x} where x is the least common multiple of 1, 2, …, Q. Then the eigenvalues λ_{j} and the eigenvectors v_{j} (1 ≤ j ≤ x) of X are given by the following.

If x′ = x/ gcd(j, x) ≤ Q, then λ_{j} = x,

v_{j} = (\underbrace{1, ω_{j}, ω_{j}^{2}, …, ω_{j}^{x′−1}}_{x′}, \underbrace{1, ω_{j}, ω_{j}^{2}, …, ω_{j}^{x′−1}}_{x′}, …, \underbrace{1, ω_{j}, ω_{j}^{2}, …, ω_{j}^{x′−1}}_{x′}),

and if x′ = x/ gcd(j, x) > Q, then λ_{j} = 0,

v_{j} = (\underbrace{1, ω_{j}, ω_{j}^{2}, …, ω_{j}^{x′−1}}_{x′}, \underbrace{1, ω_{j}, ω_{j}^{2}, …, ω_{j}^{x′−1}}_{x′}, …, \underbrace{1, ω_{j}, ω_{j}^{2}, …, ω_{j}^{x′−1}}_{x′}),

where ω_{j} = exp(2πij/x).

3.2 The case of Kloosterman sums

Let S(m, n; q) be the Kloosterman sums. We first consider the following q × q matrix

B_{q} = (S(m, n; q))_{m,n=1}^{q},

where q is a fixed positive integer. We begin with the following lemma. Lemma 10. Let B_{q} = (S(m, n; q))_{m,n=1}^{q}. Then we have

B_{q}^{2} = qA_{q}.

Proof. From Lemma 1 we see that the (m, n) entry of B_{q}^{2} equals

∑_{a=1}^{q} S(m, a; q)S(a, n; q) = qc_{q}(m − n),

which is equal to the (m, n) entry of qA_{q}.

Next we consider the trace of B_{q}^{j} where j ∈ ℕ. Lemma 11. Let B_{q} = (S(m, n; q))_{m,n=1}^{q}. For j ∈ ℕ, we have

tr(B_{q}^{2j}) = q^{2j}φ(q),  (20)
tr(B_{q}^{2j−1}) = q^{2j−1}φ̃(q).  (21)

Proof. We first prove tr(B_{q}) = qφ̃(q). It follows that

tr(B_{q}) = ∑_{m=1}^{q} S(m, m; q) = ∑_{m=1}^{q} ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} exp(\frac{2πi}{q}(mk + mk^{∗}))

= ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} ∑_{m=1}^{q} exp(\frac{2πi}{q}(k + k^{∗})m).  (22)

Since it follows that

∑_{m=1}^{q} exp(\frac{2πi}{q}(k + k^{∗})m) = \begin{cases}q, & if k + k^{∗} ≡ 0 (mod q); \\ 0, & otherwise, \end{cases}

we see that (22) is equal to

q ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \\ k+k^{∗}≡0 (mod q) \end{matrix}}^{q} 1 = q #\{1 ≤ k ≤ q; gcd(k, q) = 1, k + k^{∗} ≡ 0 (mod q)\} = qφ̃(q).

Therefore tr(B_{q}) = qφ̃(q) holds.

Next we prove (20). By Lemma 6 and Lemma 10 we have

tr(B_{q}^{2j}) = tr((B_{q}^{2})^{j}) = tr((qA_{q})^{j}) = q^{j}tr(A_{q}^{j}) = q^{j}q^{j}φ(q) = q^{2j}φ(q).

Therefore (20) holds.

Next we prove (21) for j ≥ 2. We have by Lemma 5 and Lemma 10

tr(B_{q}^{2j−1}) = tr(B_{q}^{2(j−1)}B_{q}) = tr((qA_{q})^{j−1}B_{q})
= tr(q^{j−1}q^{j−2}A_{q}B_{q}) = q^{2j−3}tr(A_{q}B_{q}).  (23)

Since tr(A_{q}B_{q}) = q^{2}φ̃(q) holds by Lemma 4, we see that (23) is equal to

q^{2j−3}q^{2}φ̃(q) = q^{2j−1}φ̃(q).

This completes the proof of Lemma 11.

Now we can prove the following theorem.

Theorem 3. Let B_{q} = (S(m, n; q))_{m,n=1}^{q}. Then the characteristic polynomial of B_{q} is

det(λE_{q} − B_{q}) = λ^{q−φ(q)}(λ − q)^{\frac{φ(q)+φ̃(q)}{2}} (λ + q)^{\frac{φ(q)−φ̃(q)}{2}} .

In particular, the matrix B_{q} has eigenvalues 0, q, −q with multiplicity q−φ(q), \frac{φ(q)+φ̃(q)}{2}, \frac{φ(q)−φ̃(q)}{2}, respectively.

Proof. The proof proceeds along the same lines as the proof of Theorem 1. We first suppose λ > q. Since det(exp(M)) = exp(tr(M)) holds for every square matrix M, we have

det(λE_{q} − B_{q}) = λ^{q} det(E_{q} − \frac{1}{λ}B_{q}) = λ^{q} exp(tr(log(E_{q} − \frac{1}{λ}B_{q}))).

Since

log(E_{q} − \frac{1}{λ}B_{q}) = ∑_{j=1}^{∞} \frac{(−1)^{j−1}}{j} (−\frac{1}{λ}B_{q})^{j} = ∑_{j=1}^{∞} \frac{(−1)^{j−1}}{j} (−\frac{1}{λ})^{j}B_{q}^{j}

holds, we have by Lemma 11

tr(log(E_{q} − \frac{1}{λ}B_{q})) = ∑_{j=1}^{∞} \frac{(−1)^{j−1}}{j} (−\frac{1}{λ})^{j}tr(B_{q}^{j})

= ∑_{j=1}^{∞} \frac{(−1)^{2j−2}}{2j − 1} (−\frac{1}{λ})^{2j−1}tr(B_{q}^{2j−1}) + ∑_{j=1}^{∞} \frac{(−1)^{2j−1}}{2j} (−\frac{1}{λ})^{2j}tr(B_{q}^{2j})

= ∑_{j=1}^{∞} \frac{1}{2j − 1}(−\frac{1}{λ})^{2j−1}q^{2j−1}φ̃(q) + ∑_{j=1}^{∞} \frac{−1}{2j}(−\frac{1}{λ})^{2j}q^{2j}φ(q)

= φ̃(q) ∑_{j=1}^{∞} \frac{1}{2j − 1}(−\frac{q}{λ})^{2j−1} + φ(q) ∑_{j=1}^{∞} \frac{−1}{2j}(−\frac{q}{λ})^{2j}.  (24)

Since it follows that

∑_{j=1}^{∞} \frac{1}{2j − 1}x^{2j−1} = \frac{1}{2} log \frac{1 + x}{1 − x},

∑_{j=1}^{∞} \frac{1}{2j} x^{2j} = −\frac{1}{2} log(1 − x^{2}),

we see that (24) is equal to

\frac{φ̃(q)}{2} log \frac{1 − q/λ}{1 + q/λ} + \frac{φ(q)}{2} log(1 − \frac{q^{2}}{λ^{2}} ).

Therefore we obtain

det(λE_{q} − B_{q}) = λ^{q} exp(\frac{φ̃(q)}{2} log \frac{λ − q}{λ + q} + \frac{φ(q)}{2} log(1 − \frac{q^{2}}{λ^{2}} ))

= λ^{q}(\frac{λ − q}{λ + q} )^{\frac{φ̃(q)}{2}} (1 − \frac{q^{2}}{λ^{2}} )^{\frac{φ(q)}{2}}

= λ^{q−φ(q)}(λ − q)^{\frac{φ(q)+φ̃(q)}{2}} (λ + q)^{\frac{φ(q)−φ̃(q)}{2}} .  (25)

Since (25) holds for every λ > q and both sides of (25) are polynomials of λ, (25) holds for every λ. This completes the proof of Theorem 3.

Although B_{q} is not a circulant matrix, we can obtain the eigenvectors of B_{q} by mimicking the method which was used in the case of A_{q}. Let

u_{j} = (ω_{j}, ω_{j}^{2}, …, ω_{j}^{q}),

where ω_{j} = exp(2πij/q) and 1 ≤ j ≤ q. We have the following corollary concerning the eigenvectors of B_{q}.

Corollary 3. Let B_{q} = (S(m, n; q))_{m,n=1}^{q}. Then the following holds.

If gcd(j, q) > 1, then

B_{q}u_{j} = 0.

If gcd(j, q) = 1 and j + j^{∗} ≡ 0 (mod q), then

B_{q}u_{j} = qu_{j}.

If gcd(j, q) = 1 and j + j^{∗} ≢ 0 (mod q), then

B_{q}(u_{j} + u_{−j^{∗}}) = q(u_{j} + u_{−j^{∗}}),
B_{q}(u_{j} − u_{−j^{∗}}) = −q(u_{j} − u_{−j^{∗}}).

Proof. We have for 1 ≤ m ≤ q

(B_{q}u_{j})(m) = ∑_{n=1}^{q} S(m, n; q)u_{j}(n)

= ∑_{n=1}^{q} ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} exp(\frac{2πi}{q}(mk + nk^{∗})) exp(\frac{2πijn}{q})

= ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} exp(\frac{2πimk}{q} ) ∑_{n=1}^{q} exp(\frac{2πin}{q}(k^{∗} + j)).  (26)

Noting that

∑_{n=1}^{q} exp(\frac{2πin}{q}(k^{∗} + j)) = \begin{cases}q, & if k^{∗} + j ≡ 0 (mod q); \\ 0, & otherwise, \end{cases}

we see that (26) is equal to 0 in the case gcd(j, q) > 1 since there exist no k such that gcd(k, q) = 1 and k^{∗} + j ≡ 0 (mod q) in this case. If gcd(j, q) = 1, then (26) is equal to

q ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \\ k^{∗}+j≡0 (mod q) \end{matrix}}^{q} exp(\frac{2πimk}{q} ) = q ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \\ k≡−j^{∗} (mod q) \end{matrix}}^{q} exp(\frac{2πimk}{q} )

= q exp(−\frac{2πimj^{∗}}{q} ) = \begin{cases}q exp(2πimj/q), & if j + j^{∗} ≡ 0 (mod q); \\ q exp(−2πimj^{∗}/q), & if j + j^{∗} ≢ 0 (mod q). \end{cases}

From this we have for j satisfying gcd(j, q) = 1

(B_{q}u_{j}) = \begin{cases}qu_{j}, & if j + j^{∗} ≡ 0 (mod q); \\ qu_{−j^{∗}}, & if j + j^{∗} ≢ 0 (mod q). \end{cases}  (27)

Thus B_{q}u_{j} = qu_{j} holds if gcd(j, q) = 1 and j + j^{∗} ≡ 0 (mod q).

Similarly, if gcd(j, q) = 1 and j + j^{∗} ≢ 0 (mod q), then we obtain B_{q}(u_{j} + u_{−j^{∗}}) = q(u_{j} + u_{−j^{∗}}) and B_{q}(u_{j} − u_{−j^{∗}}) = −q(u_{j} − u_{−j^{∗}}) since B_{q}u_{j} = qu_{−j^{∗}} and B_{q}u_{−j^{∗}} = qu_{j} hold by (27). This completes the proof of Corollary 3.

Remark 3. We note that

#{1 ≤ j ≤ q; (j, q) = 1, j + j^{∗} ≡ 0 (mod q)} = φ̃(q),
#{1 ≤ j ≤ q; (j, q) = 1, j + j^{∗} ≢ 0 (mod q)} = φ(q) − φ̃(q).

From this we have

#\{1 ≤ j ≤ q; B_{q}u_{j} = qu_{j} or B_{q}(u_{j} + u_{−j^{∗}}) = q(u_{j} + u_{−j^{∗}})\} = \frac{φ(q) + φ̃(q)}{2},

#\{1 ≤ j ≤ q; B_{q}(u_{j} − u_{−j^{∗}}) = −q(u_{j} − u_{−j^{∗}})\} = \frac{φ(q) − φ̃(q)}{2},

which coincide with the multiplicities of non-zero eigenvalues described in Theorem 3.

We give the following example.

Example 1. B_{2} = ( \begin{matrix}1 & −1 \\ −1 & 1 \end{matrix} ) has eigenvalues 0, 2.

B_{3} = ( \begin{matrix}−1 & 2 & −1 \\ 2 & −1 & −1 \\ −1 & −1 & 2 \end{matrix} ) has eigenvalues 0, 3, −3.

B_{4} = ( \begin{matrix}−2 & 0 & 2 & 0 \\ 0 & 2 & 0 & −2 \\ 2 & 0 & −2 & 0 \\ 0 & −2 & 0 & 2 \end{matrix} ) has eigenvalues 0, 4, −4 with multiplicity 2, 1, 1, respec-

tively, since φ(4) = 2 and φ̃(4) = 0.

B_{5} = ( \begin{matrix}(3 − \sqrt{5})/2 & −1 − \sqrt{5} & −1 + \sqrt{5} & (3 + \sqrt{5})/2 & −1 \\ −1 − \sqrt{5} & (3 + \sqrt{5})/2 & (3 − \sqrt{5})/2 & −1 + \sqrt{5} & −1 \\ −1 + \sqrt{5} & (3 − \sqrt{5})/2 & (3 + \sqrt{5})/2 & −1 − \sqrt{5} & −1 \\ (3 + \sqrt{5})/2 & −1 + \sqrt{5} & −1 − \sqrt{5} & (3 − \sqrt{5})/2 & −1 \\ −1 & −1 & −1 & −1 & 4 \end{matrix} )

has eigenvalues 0, 5, −5 with multiplicity 1, 3, 1, respectively, since φ(5) = 4 and φ̃(5) = 2. We note that \sqrt{5} appears in B_{5} since cos π/5 = (1 + \sqrt{5})/4.

More generally, if p is an odd prime number satisfying p ≡ 1 (mod 4), then B_{p} has eigenvalues 0, p, −p with multiplicity 1, \frac{p+1}{2}, \frac{p−3}{2}, respectively, since φ(p) = p−1 and φ̃(p) = 2.

If p is an odd prime number satisfying p ≡ −1 (mod 4), then B_{p} has eigenvalues 0, p, −p with multiplicity 1, \frac{p−1}{2}, \frac{p−1}{2}, respectively, since φ(p) = p − 1 and φ̃(p) = 0.

We remark that by Theorem 1, if p is any prime number, then A_{p} has eigenvalues 0, p with multiplicity 1, p − 1, respectively, since φ(p) = p − 1.

Next we consider the x × x matrix Y = (Y_{mn})_{m,n=1}^{x} = (∑_{q=1}^{Q} S(m, n : q))_{m,n=1}^{x} where Q is a fixed positive integer and x is the least common multiple of 1, 2, …, Q. We proceed along similar lines to the case of X.

Lemma 12. Let Y = (Y_{mn})_{m,n=1}^{x} = (∑_{q=1}^{Q} S(m, n; q))_{m,n=1}^{x} where x is the least common multiple of 1, 2, …, Q. Then

Y^{2} = xX.

Proof. By Lemma 1 we see that the (m, n) component of Y^{2} equals

(Y^{2})_{mn} = ∑_{a=1}^{x} Y_{ma}Y_{an} = ∑_{a=1}^{x}(∑_{q=1}^{Q} S(m, a; q))(∑_{r=1}^{Q} S(a, n; r))

= ∑_{q=1}^{Q} ∑_{r=1}^{Q} ∑_{a=1}^{x} S(m, a; q)S(a, n; r) = ∑_{q=1}^{Q} ∑_{r=1}^{Q} xδ(q, r)c_{q}(m − n)

= x ∑_{q=1}^{Q} c_{q}(m − n) = xX_{mn},

which is, of course, equal to the (m, n) component of xX.

Next we consider the trace of Y^{j} where j ∈ ℕ. We set Φ̃(Q) = ∑_{q=1}^{Q} φ̃(q).

Lemma 13. Let Y = (Y_{mn})_{m,n=1}^{x} = (∑_{q=1}^{Q} S(m, n; q))_{m,n=1}^{x} where x is the least common multiple of 1, 2, …, Q. For j ∈ ℕ, we have

tr(Y^{2j}) = x^{2j}Φ(Q),  (28)
tr(Y^{2j−1}) = x^{2j−1}Φ̃(Q).  (29)

Proof. We first prove tr(Y) = xΦ̃(Q). Since

tr(Y) = ∑_{m=1}^{x} ∑_{q=1}^{Q} S(m, m; q) = ∑_{m=1}^{x} ∑_{q=1}^{Q} ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} exp(\frac{2πi}{q}(mk + mk^{∗}))

= ∑_{q=1}^{Q} ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \end{matrix}}^{q} ∑_{m=1}^{x} exp(\frac{2πi}{q}(k + k^{∗})m),  (30)

and

∑_{m=1}^{x} exp(\frac{2πi}{q}(k + k^{∗})m) = \begin{cases}x, & if k + k^{∗} ≡ 0 (mod q); \\ 0, & otherwise \end{cases}

hold, we see that (30) is equal to

x ∑_{q=1}^{Q} ∑_{\begin{matrix}k=1 \\ gcd(k,q)=1 \\ k+k^{∗}≡0 (mod q) \end{matrix}}^{q} 1

= x ∑_{q=1}^{Q} #{1 ≤ k ≤ q; gcd(k, q) = 1, k + k^{∗} ≡ 0 (mod q)}

= x ∑_{q=1}^{Q} φ̃(q) = xΦ̃(Q).

Therefore tr(Y) = xΦ̃(Q) holds.

Next we prove (28). By Lemma 8 and Lemma 12 we have

tr(Y^{2j}) = tr((Y^{2})^{j}) = tr((xX)^{j}) = x^{j}tr(X^{j}) = x^{j}x^{j}Φ(Q) = x^{2j}Φ(Q).

Therefore (28) holds.

Next we prove (29) for j ≥ 2. We have by Lemma 12

tr(Y^{2j−1}) = tr(Y^{2(j−1)}Y) = tr((xX)^{j−1}Y)
= tr(x^{j−1}x^{j−2}XY) = x^{2j−3}tr(XY).

Since

tr(XY) = ∑_{m=1}^{x} ∑_{q=1}^{Q} ∑_{r=1}^{Q} ∑_{a=1}^{x} c_{q}(m − a)S(a, m; r)

= ∑_{q=1}^{Q} ∑_{r=1}^{Q} ∑_{m=1}^{x} ∑_{a=1}^{x} c_{q}(m − a)S(a, m; r)

= ∑_{q=1}^{Q} ∑_{r=1}^{Q} δ(q, r)x^{2}φ̃(q) = x^{2} ∑_{q=1}^{q} φ̃(q) = x^{2}Φ̃(Q)

holds by Lemma 4, we have

tr(Y^{2j−1}) = x^{2j−3}x^{2}Φ̃(Q) = x^{2j−1}Φ̃(Q).

This completes the proof of Lemma 13.

Let E_{x} be the x × x identity matrix where x is a positive integer. We prove the following theorem.

Theorem 4. Let Y = (Y_{mn})_{m,n=1}^{x} = (∑_{q=1}^{Q} S(m, n; q))_{m,n=1}^{x} where x is the least common multiple of 1, 2, …, Q. Then the characteristic polynomial of Y is

det(λE_{x} − Y) = λ^{x−Φ(Q)}(λ − x)^{\frac{Φ(Q)+Φ̃(Q)}{2}} (λ + x)^{\frac{Φ(Q)−Φ̃(Q)}{2}} .

In particular, the matrix Y has eigenvalues 0, x, −x with multiplicity x−Φ(Q), \frac{Φ(Q)+Φ̃(Q)}{2}, \frac{Φ(Q)−Φ̃(Q)}{2}, respectively.

Proof. The proof proceeds along the same lines as the proof of Theorem 3. We first suppose λ > x. Since det(exp(M)) = exp(tr(M)) holds for every square matrix M, we have

det(λE_{x} − Y) = λ^{x} det(E_{x} − \frac{1}{λ}Y) = λ^{x} exp(tr(log(E_{x} − \frac{1}{λ}Y))).

Since

log(E_{x} − \frac{1}{λ}Y) = ∑_{j=1}^{∞} \frac{(−1)^{j−1}}{j} (−\frac{1}{λ}Y)^{j} = ∑_{j=1}^{∞} \frac{(−1)^{j−1}}{j} (−\frac{1}{λ})^{j}Y^{j}

holds, we have by Lemma 13

tr(log(E_{x} − \frac{1}{λ}Y)) = ∑_{j=1}^{∞} \frac{(−1)^{j−1}}{j} (−\frac{1}{λ})^{j}tr(Y^{j})

= ∑_{j=1}^{∞} \frac{(−1)^{2j−2}}{2j − 1} (−\frac{1}{λ})^{2j−1}tr(Y^{2j−1}) + ∑_{j=1}^{∞} \frac{(−1)^{2j−1}}{2j} (−\frac{1}{λ})^{2j}tr(Y^{2j})

= Φ̃(Q) ∑_{j=1}^{∞} \frac{1}{2j − 1}(−\frac{1}{λ})^{2j−1}x^{2j−1} + Φ(Q) ∑_{j=1}^{∞} \frac{−1}{2j}(−\frac{1}{λ})^{2j}x^{2j}

= \frac{Φ̃(Q)}{2} log \frac{1 − x/λ}{1 + x/λ} + \frac{Φ(Q)}{2} log(1 − \frac{x^{2}}{λ^{2}} ).

Therefore we have

det(λE_{x} − Y) = λ^{x} exp(\frac{Φ̃(Q)}{2} log \frac{λ − x}{λ + x} + \frac{Φ(Q)}{2} log(1 − \frac{x^{2}}{λ^{2}} ))

= λ^{x}(\frac{λ − x}{λ + x})^{\frac{Φ̃(Q)}{2}} (1 − \frac{x^{2}}{λ^{2}} )^{\frac{Φ(Q)}{2}}

= λ^{x−Φ(Q)}(λ − x)^{\frac{Φ(Q)+Φ̃(Q)}{2}} (λ − x)^{\frac{Φ(Q)−Φ̃(Q)}{2}} .  (31)

Since (31) holds for every λ > x and both sides of (31) are polynomials of λ, (31) holds for every λ. This completes the proof of Theorem 4.

Remark 4. It is too difficult for us to obtain the eigenvectors of Y.

4 Acknowledgments

The author sincerely thanks the editor and the referee, whose comments and suggestions essentially improved this paper.

References

[1] E. Cohen, Rings of arithmetic functions, Duke Math. J., 19 (1952), 115–129.

[2] A. C. Cojocaru and M. Ram Murty, An Introduction to Sieve Methods and Their Applications, Cambridge Univ. Press, 2005.

[3] G. H. Hardy, Note on Ramanujan’s trigonometrical function c_{q}(n), and certain series of arithmetical functions, Proc. Cambridge Phil. Soc., 20 (1921), 263–271.

[4] H. Iwaniec and E. Kowalski, Analytic Number Theory, AMS Colloquium Publications, Vol. 53, Providence, 2004.

[5] H. D. Kloosterman, On the representation of numbers in the form ax^{2} + by^{2} + cz^{2} + dt^{2}, Acta Mathematica 49 (1926), 407–464.

[6] N. V. Kuznetsov, Petersson’s conjecture for cusp forms of weight zero and Linnik’s conjecture. Sums of Kloosterman sums, Math Sbornik 111 (1980), 334–383.

[7] P. J. McCarthy, Introduction to Arithmetical Functions, Springer-Verlag, 1986.

[8] M. Ram Murty, Ramanujan series for arithmetical functions, Hardy-Ramanujan Journal, 36 (2013), 21–33.

[9] S. Ramanujan, On certain trigonometrical sums and their applications in the theory of numbers, Transactions of the Cambridge Phil. Society, 22 (1918), 179–199.

[10] W. Schwarz and J. Spilker, Arithmetical Functions, Cambridge Univ. Press, 1994.

[11] I. M. Vinogradov, Elements of Number Theory, Trans. from the 5th rev. ed. by S. Kravetz. New York, Dover, 1954.

[12] A. Weil, On some exponential sums, Proc. Natl. Acad. Sci. USA, 34 (1948), 204–207.

2010 Mathematics Subject Classification: Primary 11L03; Secondary 11L05, 15A18. Keywords: Ramanujan sum, Kloosterman sum, eigenvalue.

(Concerned with sequences \underline{A054532}, \underline{A054533}, \underline{A054534}, and \underline{A054535}.)

Received August 23 2017; revised versions received November 28 2017; February 14 2018. Published in Journal of Integer Sequences, March 6 2018.

Return to Journal of Integer Sequences home page.