INTERTWINING RELATIONS BETWEEN

THE FOURIER TRANSFORM AND DISCRETE FOURIER TRANSFORM, THE

RELATED FUNCTIONAL IDENTITIES AND BEYOND

Vladimir B. Matveev

Max-Planck-Institut  Laboratoire  Steklov Mathematical
für Mathematik de Physique Mathématique  Institute
Vivatsgasse 7  Université de Bourgogne  Fontanka 27
53111 Bonn  21114 Dijon  127011 St-Petersbourg
Germany  France  Russia

e-mails: matveev@mpim-bonn.mpg.de, matveev@u-bourgogne.fr, vmatveev@pdmi.ras.ru

INTERTWINING RELATIONS BETWEEN THE FOURIER TRANSFORM, AND

DISCRETE FOURIER TRANSFORM , THE RELATED FUNCTIONAL IDENTITIES

AND BEYOND

Vladimir B. Matveev

Abstract

Starting from the spectral decomposition for the matrix or operator roots of unity we derive in a very simple way the connection between Gauss sums and spectral multiplicities of the discrete Fourier transform (DFT) , also known as Schur matrix Φ(n). Next we propose simple explicit construction of the real orthogonal matrices O_{n} diagonalizing Φ(n). We establish different intertwining relations between Fourier transform (FT) and DFT coming from the knowledge of the Gauss sums and Poisson summation. Finally we present some way to generate the eigenvectors of the DFT involving the eigenfunctions of the FT or any absolutely convergent series. This gives us a source for generating various linear and nonlinear functional identities, in particular, some theta functional identities.

CONTENTS

1. Introduction

2. Spectral decomposition for the operator roots of unity

3. Some remarks on the Fourier transform

4. The spectral theory of DFT and the Gauss sum

5. Real orthogonal matrices diagonalizing Schur matrix Φ(n)

6. Examples with n ≤ 8

7. Unitary equivalence of F (2n + 1) and Φ(2n + 1)

8. Poisson summation and intertwining relation between FT and DFT 9. Generation of eigenvectors of the DFT from absolutely convergent se-

ries

10. Functional identities

11. Non-Abelian Z-circulants

12. Connection between DFT and Haprper-Hofschtadter Hamiltonian 13. Concluding remarks

1 Introduction

There are different mathematical and physical communities , not closely connected even now, for which the discrete Fourier transform (DFT) is frequently used as important tool but also as a source of interesting mathematical problems. One of the reasons is that the numerical computation of the usual (continuous) Fourier transform (FT) passes through the computation of the DFT, for which the powerful algorithms of the Fast Fourier transform were created, starting from the pioneering work by Cooley and Tukey [1], ( see [2] for the history and simple introduction to these aspects of the DFT and [20] for information about more advanced algorithms).

Another point is that DFT is ultimately connected with different number theoretical problems : the trace of the DFT matrix is the famous Gauss sum up to the trivial normalization factor. This was used by Schur [9] in order to present the new method of evaluation of the Gauss sums. The Gauss sum G(n) (see the section 3 for the definition ) can also be considered as a first component of the DFT of the exponential e^{\frac{2πik^{2}}{n}}.

Historically, (up to my knowledge), DFT first time appeared as a tool for diagonalization of the circulant matrices. This aspect of the DFT is especially important in connection with the different aspects of the theory of the integrable systems [27] , [28], [29] , [30] [31].

DFT is of extreme importance for the people working on digital signal processing , reconstruction of images and many other fields of practical interest. Particular importance of the diagonalization of DFT for the needs of the signal processing was emphasized by Dickinson and Steglitz [13].

The spectral theory of DFT is of non-contestable interest for the harmonic analysis on nil-manifolds. Its connections with the theory of theta functions on nil-manifolds and related algebraic structures were discovered by Auslander and Tolimiery [16] ,[17], [19] The present article is organized as follows. We start in section 2 from formulation of the spectral theorem for the matrix or operator valued roots of unity valid in any Hilbert space and including original Riesz spectral theorem for the Fourier transform as particular case. ^{1}

In section 3 we recall some basic properties of the Fourier transform (including Riesz spectral decomposition of the FT) which we use below since we wanted to make our presentation maximally independent from other sources.

In section 4 we develop the spectral theory of the DFT quite similar to that of the FT at many points and explain the connection of the spectral multiplicities of the DFT with Gauss sum. Although, the results presented in section 3 are known, our presentation seems to be more transparent with respect to existing in the literature.

Section 5 contains the construction the orthonormal basis of the eigenvectors of the DFT. For realise this construction we use the basis of eigenvectors, coming from the spectral decomposition of the DFT and the knowledge of spectral multiplicities of the DFT. Its completeness was proved, (using the definition slightly different from ours but equivalent to what we mean), by McClellan and Parks [12] in 1972. Next we apply to this basis Gram-Schmidt formulas which are especially comfortable in our situation : The associated Gram matrices are obtained with no calculations as a blocks of the corresponding spectral projectors.

The question how to construct the the real orthogonal matrices diagonalizing DFT was posed by Carlitz [10] in 1959. First complete solution, (different from ours ) was obtained only 25 years later in the article by Tolimiery [21]. The same question was discussed in the articles , written by McClennan and Parks [12], Dickinson and Steglitz[13], Balian and Itzykson [22], Mehta [23] and Gutzwiller [24] and representing rather different points of view and results.

The latest article devoted to this problem was published recently by Gutzwiller [24], showing that the interest to the problem was keeped till the last times. Surprisingly, the simplest opportunity to solve the problem was not realized before and the constructions presented in the aforementioned references are more complicated and less universal i.e. depending on arithmetic properties of n.

1The corresponding statement should be well known, unfortunately I was not able to find an explicit reference. Riesz formulated his theorem in connection with Fourier transform, with no comments on its general nature, coming from the only relation F^{4} = I.

The same kind of spectral theorem was found much later by Dickinson and Steglitz in the case of the DFT, again with no comments on its general origin.

In the section 6, playing illustrative role, we produce explicitly the real orthogonal matrices diagonalizing DFT for n = 2, 3, 4, 5, 6, 7, 8

Section 7 contains the observation which comes from comparison of the spectral multiplicities of the F (2n + 1), (i.e. FT restricted on the subspace L_{2n+1} spanned by the first 2n + 1 eigenfunctions of the quantum harmonic oscillator), and Φ(2n + 1). We see that the spectral multiplicities are the same and hence their exist the some isometric mapping Q : L_{2n+1} → C^{2n+1} satisfying the relation QF (2n + 1)Q^{−1} = Φ(2n + 1).

Section 8 explores the Poisson summation formula in order to establish the intertwining relation between FT and DFT providing the explicit construction of the eigenvectors of the DFT containing any number of the functional parameters. Taking into account that DFT is a finite dimensional operator, this gives us a source of interesting functional identities.

In the section 9 we show how to generate 4 eigenvectors of the DFT corresponding to the eigenvalues 1, i, −1, −i from any absolutely convergent series. The result of this section generalizes in a natural way one of the main statements of the section 8 concerning the generation of the eigenvectors of the FT from the eigenfunctions of the Fourier transform.

In the section 10 we establish some functional identities for theta functions exploring the results of the section 9. We construct the eigenvectors of DFT in terms of the generalized theta functions which leads ,in particular, to the important duality relations, showing that θ(\frac{t+k}{n}, \frac{a}{n^{2}} ) and θ_{j/n,0}(a, t), j, k = 1, …, n − 1 are connected by the discrete Fourier transform. Many other functional identities (different from theta functional identities ) can be produced in a same way.

In the section 11 we extend the result of Cremona, about diagonalization of the circulant matrices, by the discrete Fourier transform to the case of non-Abelian Z-circulants, which seems to be missing in existing literature.

In section 12 we briefly discuss the connection of the DFT with Harper-Hofstatdter model.

2 Spectral decomposition of the matrix or operator roots of unity

Let U is some bounded operator in a Hilbert space satisfying the relation U^{n} = I and q = e^{\frac{2πi}{n}} Theorem 2.1 Spectral decomposition of U is given by the following formula

U = ∑_{m=0}^{n−1} q^{m}P_{m},  P_{m} = \frac{1}{n} ∑_{j=0}^{n−1} q^{−jm}U^{j}.  (1)

The spectral Projectors P_{j} , forming the resolution of identity for U, are self adjoint operators satisfying the relations

∑_{j=0}^{n−1} P_{j} = I,  P_{j}^{2} = I,  UP_{j} = q^{j}P_{j},
P_{j}P_{m} = 0 for m ≠ j; P_{j}^{∗} = P_{j}.  (2)

The proof of the formulas (1-2) is immediate consequence of the well known properties of the q^{j}.

In the finite dimensional case the multiplicity m_{j} of the eigenvalue q^{j} can be computed by the formula

m_{j} = Tr P_{j} = \frac{1}{n} ∑_{k=0} q^{−kj}Tr U^{k}  (3)

(which, sometimes, is not very easy to do : see the remarks about Gauss sum below in the section 3). Looking at (3) we can say that traces of U^{k} and spectral multiplicities of the eigenvalues of U are connected via discrete Fourier transform (see the definition below in section 3). Below (see section 3) we will see that particular case of (3) corresponding to n = 4, together with the knowledge of Gauss sums, allows to compute the spectral multiplicities of the discrete Fourier transform in a simplest possible way.

For any function f(z) defined at the points q^{j} corresponding to the nontrivial spectral projectors P_{j} we can define associated function of U :

f(U) = ∑_{j=1}^{n−1} f(q^{j})P_{j}.  (4)

In particular taking f(U) = U^{k} we get the formula

U^{k} = ∑_{j=1} q^{jk}P_{j},

showing together with (1) that the two vectors (P_{0}, …, P_{n−1}) and (I, U, U^{2}, …, U^{n−1}) with matrix valued components are connected by the direct and inverse DFT transform up to the unitarity factor.

3 Some remarks about the Fourier Transform

Let F (f) is a Fourier transform defined by the formula

f̃(k) = F (f)(k) = \frac{1}{\sqrt{2π}} ∫_{R} f(x)e^{ikx} dx  (5)

The inversion formula reconstructing f from f̃ is

f(x) = \frac{1}{\sqrt{2π}} ∫_{R} f̃(k)e^{−ikx} dk.  (6)

Formulas (5-6) are valid without additional comments for any smooth absolutely integrable function f. For the correct extensions of the formulas (5-6) on the larger functional spaces see for example [3], [4]. For these larger classes spectral decompositions given below also can be applied with necessary precisions but in this article it is not essential. Since (F^{2}f)(x) = f(−x) we obviously have

F^{4} = I, (F^{3}f)(x) = (F^{−1}f)(x) = f̃(−x),  (7)

where I is the unity operator. Hence, according to (1), we have the following spectral decomposition of F :

F = P_{0} + iP_{1} − P_{2} − iP_{3},  (8)

where the spectral projectors P_{j} are defined by the formula

P_{j} = \frac{1}{4} ∑_{k=0}^{3}(−i)^{jk}F^{k},  (9)

which is of course just a particular case of (1). It is clear from the formulas (7) and (9) that any continuous absolutely integrable function f(x) generates the 4 eigenfunctions f_{j} of F:

F (f_{j}) = i^{j}f_{j}, j = 0, 1, 2, 3

via the formula

f_{j}(x) = f(x) + (−i)^{j}f̃(x) + (−i)^{2j}f(−x) + (−i)^{3j}f̃(−x).  (10)

This allows to generate the eigenfunctions of F quite different from the most known ψ_{n} = e^{− \frac{x^{2}}{2}} H_{n}(x), which are also eigenfunctions of the quantum Harmonic oscillator H, (see also the discussion in section 4).

For instance, taking f = exp(−αx^{2} + itx) with α > 0, t ∈ C , we get

F (f)(x) = \frac{1}{\sqrt{2α}}e^{− \frac{(x−t)^{2}}{4α}} , F^{2}(f)(x) = f(−x), F^{3}(f)(x) = e^{− \frac{(x+t)^{2}}{4α}} .

(11)

Hence, using (10), we can generate the 2-parametric family of eigenfunctions f_{j}(x, α, t) = P_{j}f of the Fourier operator:

f_{0} = e^{−αx^{2}+itx} + e^{−αx^{2}−itx} + \frac{1}{\sqrt{2α}} (e^{− \frac{(x−t)^{2}}{4α}} − e^{− \frac{(x+t)^{2}}{4α}} ) ,
= 2 (e^{−αx^{2}} cos tx + \frac{1}{\sqrt{2α}}e^{− \frac{x^{2}+t^{2}}{4α}} cosh \frac{xt}{2α}) ,
f_{1} = e^{−αx^{2}+itx} − e^{−αx^{2}−itx} − i\frac{1}{\sqrt{2α}} (e^{− \frac{(x−t)^{2}}{4α}} − e^{− \frac{(x+t)^{2}}{4α}} )
= 2i (e^{−αx^{2}} sin tx + \frac{1}{\sqrt{2α}}e^{− \frac{x^{2}+t^{2}}{4α}} sinh \frac{xt}{2α}) ,
f_{2} = e^{−αx^{2}+itx} + e^{−αx^{2}−itx} − \frac{1}{\sqrt{2α}} (e^{− \frac{(x−t)^{2}}{4α}} + e^{− \frac{(x+t)^{2}}{4α}} )
= 2 (e^{−αx^{2}} cos tx − \frac{1}{\sqrt{2α}}e^{− \frac{x^{2}+t^{2}}{4α}} cosh \frac{xt}{2α}) ,
f_{3} = e^{−αx^{2}+itx} − e^{−αx^{2}−itx} + i\frac{1}{\sqrt{2α}} (e^{− \frac{(x−t)^{2}}{4α}} − ie^{− \frac{(x+t)^{2}}{4α}} )
= 2i (e^{−αx^{2}} sin tx + \frac{1}{\sqrt{2α}}e^{− \frac{x^{2}+t^{2}}{4α}} sinh \frac{xt}{2α}) .

Since F is linear operator the linear combinations of the functions above, corresponding to the different values of parameters α and t, are also producing the eigenfunctions. We can even integrate them with respect to t and α with some densities ρ(α, t) , with compact support, vanishing for α ≤ ϵ, ϵ > 0. In this way we can generate eigenfunctions of F depending on any number of the functional parameters ρ_{i}(α, t).

Additional important way to generate the infinite number of the eigenfunctions of F from the given eigenfunction, belonging to Schwartz space S, - is to use the creation and annihilation operators a, and a^{∗} :

a = −\frac{d}{d x} + x, a = \frac{d}{d x} + x

Using the integration by parts, it is easy to check that in the Schartz space (i.e. the space of the smooth functions rapidly decreasing with all their derivatives), the following intertwining relations holds.

F a = ia F, F a^{∗} = −ia^{∗}

It turns out that for any eigenfunction f ∈ S of F , corresponding to the eigenvalue i^{k}, we have the relations

F (a^{j} f) = i^{k+j}a^{j}f, F ((a^{∗})^{j}f) = i^{k−j} (a^{∗})^{j}f.

The case of the eigenfunctions of the quantum harmonic oscillator, (see also the next section), is isolated by taking as a starting point the vacuum eigenfunction ψ_{0} = e^{− \frac{x^{2}}{2}} , satisfying the relations

F (ψ_{0}) = ψ_{0}, a^{∗}ψ_{0} = 0.

The later case is distinguished also in a sense that the eigenfunctions of the form a^{k} ψ_{0} are orthogonal with respect to the standart scalar product in L^{2}(R) and form its basis.

It is clear from (9) that the operator

P_{0} + P_{2} = \frac{I + F^{2}}{2}

projects any function into the direct orthogonal sum of the eigenspaces corresponding to the eigenvalues 1 and −1 The operator

P_{1} + P_{3} = \frac{I − F^{2}}{2}

projects any function to the direct orthogonal sum of the eigenspaces corresponding to the eigenvalues i and −i. It is obvious from the formula (10) that the eigenfunctions, corresponding to the eigenvalues ±1, are even functions and eigenfunctions corresponding to the eigenvalues ±i are odd functions. Taking f(x) in (10) to be even function we obviously have

f_{1}(x) = f_{2}(x) = 0, f_{0,2}(x) = 2(f(x) ± f̃(x)).

In the case where f is chosen to be odd function we get

f_{0,2} = 0, f_{1,3} = 2(f(x) ∓ if̃(x))

We can formulate the same saying that F ± I maps even functions to the eigenfunctions of F corresponding to the eigenvalues ±1 and F ∓ iI maps the odd functions to the eigenfunctions corresponding to the eigenvalues ±i. In this way we also obtain all possible eigenfunctions.

Next remark is that F can be represented in a following form

\begin{matrix}F = A + iB, A = P_{0} − P_{2} = \frac{F +F^{−1}}{2} , \\ B = P_{1} − P_{3} = \frac{F −F^{−1}}{2i} . \end{matrix}

The operators A and B have the eigenvalues 0, 1, −1 and satisfy the relations

\begin{matrix}A^{2} = P_{0} + P_{2}, & A^{3} = A, \\ B^{2} = P_{1} + P_{3}, & B^{3} = B, \\ AB = BA = 0, & A^{2} + B^{2} = I, \end{matrix}

which are immediate consequence of the properties of the spectral projectors P_{j}.

We will see below that all the main formulas of this section find theirs natural analogues in the spectral theory of the DFT: we have only to replace F by the Schur matrix Φ(n) in the corresponding formulas.

4 Spectral theory of the DFT and the Gauss sum

We define the matrix Φ(n) corresponding to the discrete Fourier transform of the size n by the formula

Φ_{jk}(n) = \frac{1}{\sqrt{n}}q^{jk},  j, k = 0, …, n − 1,  q = e^{\frac{2πi}{n}} .  (12)

The matrix Φ is unitary and symmetric in the same time and hence the inverse of Φ is obtained by the complex conjugation. The DFT (discrete Fourier transform ) f → f̃ describes the action of Φ on the finite sequences ,(vectors), f = (f_{0}, …, f_{n−1}) :

f̃_{k} = \frac{1}{\sqrt{n}} ∑_{j=0}^{n−1} f_{j} e^{\frac{2πijk}{n}}  (13)

The unitarity of Φ(n) implies the Parcerval identity

∑_{j=0}^{n−1} |f_{j}|^{2} = ∑_{j=0}^{n−1} |f̃_{j}|^{2}.

The sequence f̃_{j} is periodic i.e. f̃_{j+n} = f̃_{j}. It is often useful to think that the sequence f_{j} is also extended periodically with the same period n. The inversion formula giving the reconstruction of f_{j} from the knowledge of f̃_{k} obviously can be written as

f_{j} = \frac{1}{\sqrt{n}} ∑_{k=0}^{n−1} f̃_{k} e^{− \frac{2πijk}{n}} , or f = Φ^{−1}f̃.  (14)

The easy calculation shows that Φ^{2} has the following form

Φ^{2} = ( \begin{matrix}1 & 0 & … & 0 & 0 \\ 0 & 0 & … & 0 & 1 \\ 0 & 0 & … & 1 & 0 \\ ⋮ & ⋮ & … & 0 & 0 \\ 0 & 1 & 0 & … & 0 \end{matrix} ) .

In other words , quite similarly to (7), we find that

Φ_{jm}^{2} = δ_{n−j,m} = Φ_{mj}^{2}, (Φ^{2}f)_{j} = f_{n−j}, Φ^{4} = I, Φ^{3} = Φ^{−1} = Φ^{∗}. (15)

2 It is also easy to see that the trace of Φ^{2} takes depending on parity of n only two values 1 or 2:

Tr Φ^{2} = \frac{3 + (−1)^{n}}{2}  (16)

The quantity G = \sqrt{n} Tr Φ is the famous Gauss sum :

\frac{1}{\sqrt{n}}G(n) = Tr F = \frac{1}{\sqrt{n}} ∑_{s=0}^{n−1} q^{s^{2}} = \frac{1 + (−i)^{n}}{1 − i} .  (17)

The last equality in (17) represents one of the most important results of Gauss (see [6] for the history , generalizations and different proofs).

The spectral decomposition of Φ is obtained from formula (1) by taking n = 4 :

Φ = ∑_{j=0}^{3} i^{j} p_{j},  p_{j} = \frac{1}{4} ∑_{k}(−i)^{jk}Φ^{k}.  (18)

2The connection of the Gauss sum with the trace of DFT and the relations (15) where discovered by Schur [9], who used them for provide a new method of evaluation of the Gauss sum for odd values of n.

Of course, again we have

∑_{j=0}^{3} p_{j} = I,  p_{j} p_{k} = p_{j} δ_{jk},  (19)

and all the projectors p_{j} are real symmetric matrices. It follows from the spectral decomposition above, that any sequence (vector) f_{j}, j = 0, …, n − 1 generates the eigenvector of Φ : Φv = i^{k}v via a formula

v_{j}(k) = f_{j} + (−i)^{k}f̃_{j} + (−1)^{k}f_{n−j} + (−i)^{3k}f̃_{−j}.  (20)

Of course for the sequences f_{j} extended periodically we can replace f_{n−j} by f_{−j} in (20). Again we have the formulas similar to those in the previous section:

p_{0} + p_{2} = \frac{I+Φ^{2}}{2} , p_{1} + p_{3} = \frac{I−Φ^{2}}{2} Φ = a + ib, a = p_{0} − p_{2} = \frac{Φ+Φ̄}{2}, b = p_{1} − p_{3} = \frac{Φ−Φ̄}{2i} ab = ba = 0, a^{2} + b^{2} = I, a^{2} = p_{0} + p_{2}, b^{2} = p_{1} + p_{3}, a^{3} = a, b^{3} = b, a_{jk} = \frac{1}{\sqrt{n}} cos \frac{2πkj}{n} , b_{kj} = \frac{1}{\sqrt{n}} sin \frac{2πkj}{n} , k, j = 0, 1 …, n − 1.

Again the eigenvalues of a and b are 0, 1, −1 and their multiplicities m_{a}, m_{b} follows immediately from the formulas given below.

Let m_{0} = m(1), m_{1} = m(i), m_{2} = m(−1), m_{3} = m(−i) are the multiplicities corresponding to the eigenvalues 1, i, −1, −i of Φ. We obviously have the formulas m_{k} = Tr p_{k}. Hence taking into account the fact the formulas (3 ,16,17) we get for m_{k} the following explicit expressions :

m_{1} = \frac{1}{4} (n + 2Im TrΦ(n) − \frac{3+(−1)^{n}}{2} ) = [\frac{n+1}{4}] ,
m_{2} = \frac{1}{4} (n − 2Re TrΦ(n) + \frac{3+(−1)^{n}}{2} ) = [\frac{n+2}{4}] ,
m_{3} = \frac{1}{4} (n − 2Im TrΦ(n) − \frac{3+(−1)^{n}}{2} ) = [\frac{n+3}{4}] − 1,
m_{0} = \frac{1}{4} (n + 2Re TrΦ(n) + \frac{3+(−1)^{n}}{2} ) = [\frac{n}{4}] + 1.

In more detailed form the same formulas can be written as follows

\begin{matrix}n = 4m + 2 ⇒ & m_{1} = m & m_{2} = m + 1 & m_{3} = m, & m_{0} = m + 1 \\ n = 4m ⇒ & m_{1} = m & m_{2} = m & m_{3} = m − 1 & m_{0} = m + 1 \\ n = 4m + 1 ⇒ & m_{1} = m & m_{2} = m & m_{3} = m & m_{0} = m + 1 \\ n = 4m + 3 ⇒ & m_{1} = m + 1 & m_{2} = m + 1 & m_{3} = m & m_{0} = m + 1 \end{matrix}

3 The formulas above provide the following formulas for charachteristic polynomial P (z) of Φ and det Φ

P (z) = ∏_{k=0}^{k=3}(z − i^{k})^{m_{k}}, det F = ∏_{k=1}^{k=3} i^{km_{k}} = i^{\frac{n(n−1)}{2} +(n−1)^{2}} = i^{\frac{3n^{2}−5n}{2} +1},

(21)

valid for any value of n.

5 The complete systems of the eigenvectors of Φ(n) and the real orthogonal matrices O(n) diagonalizing DFT

The explicit formulas for spectral projectors p_{j} given above provide the complete set of eigenvectors of Φ: we have to take m_{0} first columns of p_{0}, m_{1} first nontrivial, (since first columns of p_{1} and p_{3} are formed by zeros), columns of p_{1}, m_{2} first columns of p_{2} and m_{3} first nontrivial columns of p_{3} to get it. The completeness follows from the relation ∑ p_{j} = I. The eigenvector v(k, m), equal to the m-th column of p_{k}, has the components v_{j}(m, k) (equal to the matrix elements p_{mj} = p_{jm} of p_{k}), :

4v_{j}(k, m) = δ_{jm} + (−1)^{k}δ_{n−j,m} + (−i)^{k} \frac{q^{jm}}{\sqrt{n}} + (−i)^{3k} \frac{q^{−jm}}{\sqrt{n}}  (22)

All these eigenvectors have real valued components and giving to k in (22) the values 0, 1, 2, 3 we get the following more detailed vision of them:

4v_{j}(0, m) = δ_{jm} + δ_{n−j,m} + \frac{2}{\sqrt{n}} cos (\frac{2πmj}{n} ) ,
4v_{j}(1, m) = δ_{jm} − δ_{n−j,m} + \frac{2}{\sqrt{n}} sin (\frac{2πmj}{n} ) ,
4v_{j}(2, m) = δ_{jm} + δ_{n−j,m} − \frac{2}{\sqrt{n}} cos (\frac{2πmj}{n} ) ,
4v_{j}(3, m) = δ_{jm} − δ_{n−j,m} − \frac{2}{\sqrt{n}} sin (\frac{2πjm}{n}) .

3the complete list of the spectral multiplicities concerning all values of n was first published by Carlitz [10] and later was rediscovered by many people. Calculation of the spectral multiplicities of Φ presented here seems to be the most simple.

Theorem 5.1 The following vectors

v(0, m), m = 0, 1, …, m(1);
v(1, m), m = 1, 2, …, m(i) + 1;
v(2, m), m = 0, 1, …, m(−1);
v(3, m), m = 1, 2, …, m(−i) + 1,

form the basis of C^{n}.

The proof of this nontrivial fact (in slightly different but equivalent formulation) was given in [12] by McLennan and Parks, using the technic of Chebyshev’s nets. It was also reproduced in a review article [16]. In the case n = 2, 3, the spectral multiplicities are 1 or 0. So, normalizing the eigenvectors belonging to the nontrivial eigenspaces, we get the real orthogonal matrix O reducing Φ to its diagonal form Λ, Λ = O^{−1}F O.

In the case n ≤ 4 so obtained system of vectors is no more ortogonal and in order to get the orthonormal basis of eigenvectors explicitly one can use Gram-Schmidt orthogonalization method [5], also leading to the explicit formulas for O. First step to realize the Gram-Schmidt method is to compute the Gram matrix formed by scalar products (v(k, m), v(k, j)). The scalar product of the two vectors in C^{n} is defined as usually:

(a, b) = ∑_{j=0}^{n−1} a_{j}b̄_{j},  (23)

Of course since the projectors p_{j} are real symmetric matrices , complex conjugation can be forgotten in what concerns the calculation of the scalar products of its columns . The later are very easy to compute since p_{k} are the real symmetric projector matrices, hence satisfying the relation p_{k}^{2} = p_{k} . Consequently we have the formula

(v(k, m), v(k, j)) = v_{j}(k, m).  (24)

It follows from (19) that in every subspace p_{k}C^{n} the ”big” (and degenerate) Gramian matrix Γ_{k} corresponding to the system of vectors v(k, m), m = 0, …, n−1 is just p_{k} itself : Γ_{k} = p_{k}. To get the orthogonal basis in p_{1}C^{n} we have to take the ”little” m_{k} ×m_{k} gramian matrices γ_{k},corresponding to the upper left corner m_{k} × m_{k} square block of p_{k}, in the case k = 0, 2. In the case k = 1, 3 we have to remove first line and first column from p_{k}, and take for γ_{k} the m_{k} × m_{k} square upper left corner block of so obtained matrix.

The sequence of the orthogonal vectors e_{j} spanning the eigenspace p_{k}C^{n} now is given, in the case k = 0, 2, by the following formulas:

e_{1}(k) = v(0, k), e_{2}(k) = | \begin{matrix}p_{00}(k) & v(0, k) \\ p_{10}(k) & v(1, k) \end{matrix} | , …,

e_{m(k)}(k) = | \begin{matrix}p_{00} & … & p_{0,m_{k}−1} & v(0, k) \\ ⋮ & … & … & ⋮ \\ p_{m_{k}−2,0} & … & p_{m(k)−2,m(k)−2} & v(m(k) − 2, k) \\ p_{m(k)−1} & … & p_{m(k)−1,m(k)−2} & v(m(k) − 1, k) \end{matrix} | .

The coordinates of the vectors in the LHS of these formulas are obtained by replacing the vectors in the last column by corresponding coordinates. The norms of the orthogonal vectors e_{j}(k) are given by the formulas:

||e_{j}|| = \sqrt{G_{j}G_{j−1}},  (25)

where G_{j}, G_{j−1} are the principal minors of p_{k} of the orders j − 1 and j respectively.

In the case k = 1, 3 the similar formulas are of the following form:

e_{1}(k) = v(1, k), e_{2}(k) = | \begin{matrix}p_{11}(k) & v(1, k) \\ p_{21}(k) & v(2, k) \end{matrix} | , …,

e_{m(k)}(k) = | \begin{matrix}p_{11} & … & p_{1,m_{k}} & v(1, k) \\ ⋮ & … & … & ⋮ \\ p_{m_{k}−1,1} & … & p_{m(k)−1,m(k)−1} & v(m(k) − 1, k) \\ p_{m(k)} & … & p_{m(k),m(k)−1} & v(m(k), k) \end{matrix} | .

It follows, from the formulas given above and from well known result of Gauss, that, in the case

n = 2^{m}g_{1}, …, g_{q}, g_{j} = 2^{k_{j}} + 1,

where m, k_{j} are nonnegative integers and all g_{j} are prime numbers, the real orthogonal matrix O_{n} diagonalizing Φ(n) can be expressed completely in terms of (nested) square radicals. ^{4}

4The prime numbers having this special form are called Fermat prime numbers. The

6 Orthogonal Matrices Diagonalizing Φ(n): n ≤ 8

Below we list some number of examples illustrating the general formulas given above in the cases n ≤ 8.

For n = 2 we have q = −1,

Φ = \frac{1}{\sqrt{2}} ( \begin{matrix}1 & 1 \\ 1 & −1 \end{matrix} ) , , F^{2} = I, p_{1} = p_{3} = 0.

The spectral projectors p_{0}, p_{2} are the following matrices:

p_{0} = \frac{1}{2\sqrt{2}} ( \begin{matrix}\sqrt{2} + 1 & 1 \\ 1 & \sqrt{2} − 1 \end{matrix} ) , p_{2} = \frac{1}{2\sqrt{2}} ( \begin{matrix}\sqrt{2} − 1 & −1 \\ −1 & \sqrt{2} + 1 \end{matrix} ) .

. In this case p_{2} = 0, p_{3} = 0. Hence it is easy to conclude that the orthogonal matrix O_{2} reducing F to the form diag[1, −1] = O^{−1}F O is

O_{2} = ( \begin{matrix}\frac{\sqrt{2}+1}{\sqrt{4+2\sqrt{2}}} & \frac{1−\sqrt{2}}{\sqrt{4−2\sqrt{2}}} \\ \frac{1}{\sqrt{4+2\sqrt{2}}} & \frac{−1}{\sqrt{4−2\sqrt{2}}} \end{matrix} ) .

In the case n = 3 the spectral projector p_{3} = 0 and nontrivial projectors are described by the following matrices

p_{0} = \frac{1}{2\sqrt{3}} ( \begin{matrix}\sqrt{3} + 1 & 1 & 1 \\ 1 & \frac{\sqrt{3}−1}{2} & \frac{\sqrt{3}−1}{2} \\ 1 & \frac{\sqrt{3}−1}{2} & \frac{\sqrt{3}−1}{2} \end{matrix} ) , p_{1} = \frac{1}{2} ( \begin{matrix}0 & 0 & 0 \\ 0 & 1 & −1 \\ 0 & −1 & 1 \end{matrix} ) ,

p_{2} = \frac{1}{2\sqrt{3}} ( \begin{matrix}\sqrt{3} − 1 & −1 & −1 \\ −1 & \frac{\sqrt{3}−1}{2} & \frac{\sqrt{3}−1}{2} \\ −1 & \frac{\sqrt{3}−1}{2} & \frac{\sqrt{3}−1}{2} \end{matrix} ) .

first of them are 3, 5, 17 = 2^{4} + 1, 257 = 2^{8} + 1, 65537 = 2^{16} + 1.To be prime it is necessary, but not sufficient that k_{j} will be a power of two: Euler discovered that 2^{32} + 1 is divisible by 641. It is still unknown if the number of Fermat primes is finite or not.

From thus it is easy to conclude that the orthogonal matrix O_{3} diagonalizing Φ in the case n = 3 has the form

O_{3} = ( \begin{matrix}\frac{\sqrt{3}+1}{\sqrt{6+2\sqrt{3}}} & 0 & \frac{\sqrt{3}−1}{\sqrt{6−2\sqrt{3}}} \\ \frac{1}{\sqrt{6+2\sqrt{3}}} & \frac{1}{\sqrt{2}} & −\frac{1}{\sqrt{6−2\sqrt{3}}} \\ \frac{1}{\sqrt{6+2\sqrt{3}}} & −\frac{1}{\sqrt{2}} & −\frac{1}{\sqrt{6−2\sqrt{3}}} \end{matrix} ) .

In the case n = 4 the Fourier matrix F is

F = \frac{1}{2} ( \begin{matrix}1 & 1 & 1 & 1 \\ 1 & i & −1 & −i \\ 1 & −1 & 1 & −1 \\ 1 & −i & −1 & i \end{matrix} )

, and we have p_{3} = 0 , since m(−i) = m_{3} = 0. Matrices of nontrivial projectors are looking as follows

p_{0} = \frac{1}{4} ( \begin{matrix}3 & 1 & 1 & 1 \\ 1 & 1 & −1 & 1 \\ 1 & −1 & 3 & −1 \\ 1 & 1 & −1 & 1 \end{matrix} ) , p_{1} = \frac{1}{2} ( \begin{matrix}0 & 0 & 0 & 0 \\ 0 & 1 & 0 & −1 \\ 0 & 0 & 0 & 0 \\ 0 & −1 & 0 & 1 \end{matrix} ) ,

p_{2} = \frac{1}{4} ( \begin{matrix}1 & −1 & −1 & −1 \\ −1 & 1 & 1 & 1 \\ −1 & 1 & 1 & 1 \\ −1 & 1 & 1 & 1 \end{matrix} ) .

Now it is obvious that the first two columns v_{1}, v_{2} of P_{0} together with the second columns of p_{1}, p_{2} form the basis of C^{4} and that the difference v_{2} − v_{1} is orthogonal to v_{2}. Hence, the real orthogonal matrix O_{4} : O_{4}^{−1}F O_{4} = diag[1, 1, −1, i] has the particularly simple form:

O_{4} = \frac{1}{2} ( \begin{matrix}1 & \sqrt{2} & −1 & 0 \\ 1 & 0 & 1 & \sqrt{2} \\ −1 & \sqrt{2} & 1 & 0 \\ 1 & 0 & 1 & −\sqrt{2} \end{matrix} ) .

For n = 5 first time all the spectral projectors of Φ are nontrivial. The spectral multiplicities are the following numbers: m_{0} = 2, m_{1} = m_{2} = m_{3} = 1. Let θ = \frac{2π}{5}. For the spectral projectors we have the following formulas

p_{0} = \frac{1}{2\sqrt{5}} ( \begin{matrix}\sqrt{5} + 1 & 1 & 1 & 1 & 1 \\ 1 & \frac{\sqrt{5}}{2} + cos θ & cos 2θ & cos 2θ & \frac{\sqrt{5}}{2} + cos θ \\ 1 & cos 2θ & \frac{\sqrt{5}}{2} + cos 4θ & \frac{\sqrt{5}}{2} + cos 4θ & cos 2θ \\ 1 & cos 2θ & \frac{\sqrt{5}}{2} + cos 4θ & \frac{\sqrt{5}}{2} + cos 4θ & cos 2θ \\ 1 & \frac{\sqrt{5}}{2} + cos θ & cos 2θ & cos 2θ & \frac{\sqrt{5}}{2} + cos θ \end{matrix} ) ,

p_{1} = \frac{1}{2\sqrt{5}} ( \begin{matrix}0 & 0 & 0 & 0 & 0 \\ 0 & \frac{\sqrt{5}}{2} + sin θ & sin 2θ & − sin 2θ & −\frac{\sqrt{5}}{2} − sin θ \\ 0 & sin 2θ & \frac{\sqrt{5}}{2} + sin 4θ & −\frac{\sqrt{5}}{2} − sin 4θ & − sin 2θ \\ 0 & − sin 2θ & −\frac{\sqrt{5}}{2} − sin 4θ & \frac{\sqrt{5}}{2} + sin 4θ & sin 2θ \\ 0 & −\frac{\sqrt{5}}{2} − sin θ & − sin 2θ & sin 2θ & \frac{\sqrt{5}}{2} + sin θ \end{matrix} ) ,

p_{2} = \frac{1}{2\sqrt{5}} ( \begin{matrix}\sqrt{5} + 1 & −1 & −1 & −1 & −1 \\ −1 & \frac{\sqrt{5}}{2} − cos θ & − cos 2θ & − cos 2θ & \frac{\sqrt{5}}{2} − cos θ \\ −1 & − cos 2θ & \frac{\sqrt{5}}{2} − cos 4θ & \frac{\sqrt{5}}{2} − cos 4θ & − cos 2θ \\ −1 & − cos 2θ & \frac{\sqrt{5}}{2} − cos 4θ & \frac{\sqrt{5}}{2} − cos 4θ & − cos 2θ \\ −1 & \frac{\sqrt{5}}{2} − cos θ & − cos 2θ & − cos 2θ & \frac{\sqrt{5}}{2} − cos θ \end{matrix} ) ,

p_{3} = \frac{1}{2\sqrt{5}} ( \begin{matrix}0 & 0 & 0 & 0 & 0 \\ 0 & \frac{\sqrt{5}}{2} − sin θ & − sin 2θ & sin 2θ & −\frac{\sqrt{5}}{2} + sin θ \\ 0 & − sin 2θ & \frac{\sqrt{5}}{2} − sin 4θ & −\frac{\sqrt{5}}{2} + sin 4θ & − sin 2θ \\ 0 & sin 2θ & −\frac{\sqrt{5}}{2} + sin 4θ & \frac{\sqrt{5}}{2} − sin 4θ & − sin 2θ \\ 0 & −\frac{\sqrt{5}}{2} + sin θ & sin 2θ & − sin 2θ & \frac{\sqrt{5}}{2} − sin θ \end{matrix} ) ,

The sine and cosine functions in the expressions above can be easily written in terms of radicals:

cos θ = \frac{\sqrt{5}−1}{4}, cos 2θ = −\frac{\sqrt{5}+1}{4},
cos \frac{mπ}{5} = (−1)^{[(m+2)/5]}^{\frac{\sqrt{5}+(−1)^{[n/2]}}{4}} , m ≠ 0 (mod 5),
sin θ = \frac{1}{4} \sqrt{10 + 2\sqrt{5}}, sin 2θ = \frac{1}{4} \sqrt{10 − 2\sqrt{5}},
sin \frac{mπ}{5} = (−1)^{[m/5]} \frac{1−(−1)^{[4m/5]}}{8} \sqrt{10 − (−1)^{[m/2]}2\sqrt{5}}, m = 2k.

Now it is easy to see that the matrix ˜0_{5} formed by the linearly independent orthogonal eigenvectors v_{j} of Φ(5) can be chosen as follows:

Õ_{5} = ( \begin{matrix}\sqrt{5} + 1 & 0 & 1 − \sqrt{5} & 0 & 0 \\ 1 & 1 & 1 & sin θ + \frac{\sqrt{5}}{2} & \frac{\sqrt{5}}{2} \\ 1 & −1 & 1 & sin 2θ & − sin 2θ \\ 1 & −1 & 1 & − sin 2θ & sin 2θ \\ 1 & 1 & 1 & − sin θ − \frac{\sqrt{5}}{2} & − sin θ + \frac{\sqrt{5}}{2} \end{matrix} ) .

The norms of the vectors v_{j} forming the columns of Õ_{5} are given by the formulas:

||v_{1}|| = \sqrt{10 + 2\sqrt{5}}  λ = 1 ||v_{2}|| = 2  λ = 1
||v_{3}|| = \sqrt{10 − 2\sqrt{5}}  λ = −1 ||v_{4}|| = \frac{1}{2} \sqrt{20 + 2\sqrt{50 + 10\sqrt{5}}} λ = i
||v_{5}|| = \frac{1}{2} \sqrt{20 − 2\sqrt{50 + 10\sqrt{5}}} λ = −i

Hence the real orthogonal matrix O_{5} satisfying the relation O_{5} : O_{5}^{−1}Φ(5) O = diag[1, 1, −1, i, −i] has the following form:

O_{5} = (e_{1}, e_{2}, e_{3}, e_{4}, e_{5}),  e_{j} = \frac{v_{j}}{||v_{j}||}.  (26)

. For n = 6 the real orthogonal matrix O_{6} diagonalizing

Φ(6) : O_{6}^{−1}Φ(6)O_{6} = diag[1, 1, i, −1, −1, −i]

can be obtained normalizing the columns of the matrix Õ_{6} = (v_{1}, v_{2}, …, v_{6}) , where v_{j} form the basis of orthogonal eigenvectors of Φ(6) constructed in a same way as before:

O_{6} = ( \begin{matrix}\sqrt{6} + 1 & 0 & 0 & 1 − \sqrt{6} & 0 & 0 \\ 1 & \sqrt{6} + \frac{5}{2} & \frac{\sqrt{6}+\sqrt{3}}{2} & 1 & \frac{5}{2} − \sqrt{6} & \frac{\sqrt{6}−\sqrt{3}}{2} \\ 1 & −\frac{3+\sqrt{6}}{2} & \frac{\sqrt{3}}{2} & 1 & \frac{\sqrt{6}−3}{2} & −\frac{\sqrt{3}}{2} \\ 1 & −\sqrt{6} − 2 & 0 & 1 & \sqrt{6} − 2 & 0 \\ 1 & −\frac{3+\sqrt{6}}{2} & −\frac{\sqrt{3}}{2} & 1 & \frac{\sqrt{6}−3}{2} & \frac{\sqrt{3}}{2} \\ 1 & \sqrt{6} + \frac{5}{2} & −\frac{\sqrt{6}+\sqrt{3}}{2} & 1 & \frac{5}{2} − \sqrt{6} & \frac{\sqrt{3}−\sqrt{6}}{2} \end{matrix} ) .

The list of the norms of v_{i} is written below :

\sqrt{12 + 2\sqrt{6}}, \sqrt{42 + 17\sqrt{6}}, \sqrt{6 + 3\sqrt{2}}, \sqrt{12 − 2\sqrt{6}}, \sqrt{18 − 17\sqrt{6}}, \sqrt{6 − 3\sqrt{2}}.

(27)

The case n = 7 differs from the previously considered in a sense that here the matrix elements of real orthogonal matrix O_{7} diagonalizing Φ(7) cannot be expressed in terms of square radicals but of course general formulas of the previous section are applicable. To describe O_{7} it is more convenient first to write the components of the vectors forming the orthogonal basis in a form of rows and next supply the list the list of the corresponding norms.

v_{1} = (\sqrt{7} + 1, 1, 1, 1, 1, 1, 1) v_{2} = ( (\sqrt{7} + 1) cos ϕ + \frac{5+\sqrt{7}}{2}, (\sqrt{7} + 1) cos 2ϕ − 1, (\sqrt{7} + 1) cos 3ϕ − 1, (\sqrt{7} + 1) cos 3ϕ − 1, (\sqrt{7} + 1) cos 2ϕ − 1, (\sqrt{7} + 1) cos ϕ + \frac{5+\sqrt{7}}{2}) v_{3} = (0, sin ϕ + \frac{\sqrt{7}}{2}, sin 2ϕ, sin 3ϕ, − sin 3ϕ, − sin 2ϕ, − sin ϕ − \frac{\sqrt{7}}{2}) v_{4} = (0, 0, \frac{1}{2}[\frac{3}{2} + \sqrt{7}(sin ϕ − sin 3ϕ) + 2 cos 3ϕ − cos 2ϕ], \frac{1}{2}[1 − cos 3ϕ − 2 cos 2ϕ − \sqrt{7} sin ϕ], −\frac{1}{2}[1 − cos 3ϕ − 2 cos 2ϕ − \sqrt{7} sin ϕ], −\frac{1}{2}[\frac{3}{2} + \sqrt{7}(sin ϕ − sin 3ϕ) + 2 cos 3ϕ − cos 2ϕ], 0) v_{5} = (−\sqrt{7} + 1, 1, 1, 1, 1, 1, 1) v_{6} = (−\frac{5}{2} + (\sqrt{7} − 1) cos ϕ, 1 + (\sqrt{7} − 1) cos 2ϕ, 1 + (\sqrt{7} − 1) cos 3ϕ, 1 + (\sqrt{7} − 1) cos 3ϕ, 1 + (\sqrt{7} − 1) cos 2ϕ, \frac{\sqrt{7}−5}{2} + (\sqrt{7} − 1) cos ϕ) v_{7} = (0, \frac{\sqrt{7}}{2} − sin ϕ, − sin 2ϕ, − sin 3ϕ, sin 3ϕ, sin 2ϕ, −\frac{\sqrt{7}}{2} + sin ϕ)

Vectors v_{j} are orthogonal and satisfy the relations

Φ(7)v_{1,2} = v_{1,2}, Φ(7)v_{3,4} = iv_{3,4}, Φ(7)v_{5,6} = −v_{5,6}, Φ(7)v_{7} = −iv_{7}.

The norms of the vectors v_{j} are listed below:

||v_{1}|| = \sqrt{14 + 2\sqrt{7}}, ||v_{2}|| = \sqrt{42 + 12\sqrt{7} + (16\sqrt{7} + 28) cos ϕ}, ||v_{3}|| = \sqrt{7 + 2\sqrt{7} sin ϕ}

||v_{4}|| = \frac{1}{2\sqrt{7}} \sqrt{(sin ϕ + \frac{\sqrt{7}}{2})^{2} (2\sqrt{7} sin 4ϕ + 7) − sin^{2} 2ϕ(2\sqrt{7} sin ϕ + 7)},

||v_{5}|| = \sqrt{14 − 2\sqrt{7}}, ||v_{6}|| = \sqrt{42 − 12\sqrt{7} + (16\sqrt{7} − 28) cos ϕ} ||v_{7}|| = \sqrt{7 − 2\sqrt{7} sin ϕ}

Our last example concerns the real orthogonal matrix O_{8} diagonalizing Φ(8) :

O_{8}^{−1}Φ(8)O_{8} = diag[1, 1, 1, i, i, −1, −1, −i].

As in the previous example we present the matrix Õ_{8} whose columns represent orthogonal non normalized eigenvectors , supplying next the list of the norms :

Õ_{8} = ( \begin{matrix}1 + \sqrt{8} & 0 & 5 + \frac{3}{\sqrt{2}} & 0 & 0 & 1 − \sqrt{8} & 0 & 0 \\ 1 & 5 + \frac{3}{\sqrt{2}} & 0 & \frac{3}{\sqrt{2}} & −1 & 1 & 1 − \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ 1 & −1 & \frac{11}{\sqrt{2}} − 4 & 1 & 0 & 1 & 1 & −1 \\ 1 & −3 − \frac{1}{\sqrt{2}} & −3 − \frac{14}{\sqrt{2}} & \frac{1}{\sqrt{2}} & −1 & 1 & 1 − \frac{1}{\sqrt{2}} & −\frac{1}{\sqrt{2}} \\ 1 & −2 − 2\sqrt{2} & 9 + \frac{3}{\sqrt{2}} & 0 & 0 & 1 & \sqrt{8} − 2 & 0 \\ 1 & −3 − \frac{1}{\sqrt{2}} & −3 − \frac{14}{\sqrt{2}} & −\frac{1}{\sqrt{2}} & 1 & 1 & 1 − \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ 1 & −1 & −4 + \frac{11}{\sqrt{2}} & −1 & 0 & 1 & −1 & 1 \\ 1 & 5 + \frac{3}{\sqrt{2}} & 0 & −\frac{3}{\sqrt{2}} & 1 & 1 & 1 − \frac{1}{\sqrt{2}} & −\frac{1}{\sqrt{2}} \end{matrix} )

The first 3 columns are the orthogonal eigenvectors corresponding to λ = 1, 4-th and 5-th columns correspond to λ = i, 6-th and 7-th columns correspond to λ = −1, and the last column corresponds to λ = −i. The norms of these vectors constitute the following list:

||v_{1}|| = 2\sqrt{4 + \sqrt{2}} ||v_{2}|| = 2\sqrt{46 + 22\sqrt{2}} ||v_{3}|| = 4\sqrt{7 − \sqrt{2}} ||v_{4}|| = 2\sqrt{3}
||v_{5}|| = 2  ||v_{6}|| = 2\sqrt{4 − \sqrt{2}}  ||v_{7}|| = 2\sqrt{5 − 3\sqrt{2}} ||v_{8}|| = 2

The explicit formulas for the real orthogonal matrix diagonalizing Φ(7) different from ours can be found in [22], containing also some general formulas, valid for odd values of n. In the case n = 8, different expression for the real orthogonal matrix diagonalizing Φ(8) is given at the end of article [21], but to put it in completely explicit form some further elementary calculations should be performed. Article [21] contains also general algorithms for diagonalizing Φ(n) depending somehow of the arithmetical properties of n. Another approach to the same problem was proposed recently by Gutzwiller [24]. His results are also valid only for odd values of n.

The formulas of the section 5 provide what can be called ”rough” diagonalisation of the DFT. Performing further rotations of the orthogonal repers corresponding to each of the four eigenspaces of Φ(n) it is possible to get for large values of n more sparse structure of the columns of the diagonalizing transformation. It seems that further progress in this direction is still possible.

It is also necessary to mention that different constructions of the real ortogonal matrices diagonalizing the DFT matrix, existing in the literature, have more complicated description but they might have an advantage from the point of veiw of the algebraic complexity of computations.

Of course, instead of the explicit formulas for the orthogonal basis given in the section 5, it is possible to construct the same orthonormal basis of the eigenvectors of Φ in a well known recursive way, which can be easily programmed.

7 The unitary equivalence of F (2n+1) and Φ(2n + 1)

The operator H defined by the formula

H = −\frac{d^{2}}{dx^{2}} + x^{2},  (28)

is the Hamiltonian of the quantum harmonic oscillator. Its eigenfunctions ψ_{k},

ψ_{k}(x) = a^{k}e^{− \frac{x^{2}}{2}} ,  a = x − \frac{d}{dx},  (29)

are orthogonal in L^{2}(R) metrics and satisfy the relations

Hψ_{k} = (2k + 1)ψ_{k},  F ψ_{k} = (i)^{k}ψ_{k},  (30)

showing also that F can be represented in a following form

F = e^{\frac{πi}{4} (H−I)}.  (31)

It is also well known that ψ_{k} = e^{− \frac{x^{2}}{2}} H_{n}(x) where H_{n} are the Hermite polynomials and that ψ_{k} form a complete system of the eigenfunctions in L^{2}(R). Below we use the notation F (n) for the restriction of F on the subspace L_{n} spanned by the first n functions ψ_{k}, k = 0, …, n − 1. Now it is trivial to compute the trace of F (4n + k):

Tr F (4m + k) = \frac{1 − (i)^{4m+k+1}}{1 − i} ,  (32)

and its spectral multiplicities μ(i^{j}):

\begin{matrix}k = 0 & μ(0) = m, & μ(i) = m, & μ(−1) = m, & μ(−i) = m, \\ k = 1 : & μ(0) = m + 1, & μ(i) = m, & μ(−1) = m, & μ(−i) = m, \\ k = 2 : & μ(0) = m + 1, & μ(i) = m + 1, & μ(−1) = m, & μ(−i) = m, \\ k = 3 : & μ(0) = m + 1, & μ(i) = m + 1, & μ(−1) = m + 1, & μ(−i) = m. \end{matrix}

Comparing the obtained result with the list of spectral multiplicities of Φ(4m + k) we see that in odd dimension they are the same and hence we have established the following result : Theorem 7.1 Their exists the isometric mapping Q : L_{2n+1} → C^{2n+1} intertwining Φ(2n + 1) and F (2n + 1):

Φ(2n + 1) Q = Q F (2n + 1).

Q obviously can be explicitly constructed by use of the orthonormal basis of eigenvectors of Φ presented above and the basis of L_{2n+1} formed by the eigenfunctions of the quantum harmonic oscillator.

In the next section we will present different (non isometric) intertwining relation between the whole Fourier transform and DFT.

8 Poisson summation formula and intertwining relation between FT and DFT

Let E be the space of the continuous functions absolutely integrable together with their Fourier transform. Than, it is easy to prove the following, well known, (generalized) Poisson summation formula

ab ∑_{r∈Z} f(b(ar + x)) = \sqrt{2π} ∑_{m∈Z} f̃(2πm(ab)^{−1})e^{− \frac{2πimx}{a}} .  (33)

The proof is obtained, taking into account that, LHS of (21) is a periodic function of x, with a period a. Expanding it in a Fourier series, it is easy to show that the associated Fourier coefficient a_{m} can be written modulo factor (ab)^{−1}\sqrt{2π} as a value of the Fourier transform of f at the point −2πmb^{−1}. Replacing f by f̃ we get the similar formula

ab ∑_{r=−∞}^{∞} f̃(b(ar + x)) = \sqrt{2π} ∑_{m∈Z} f(2πm(ab)^{−1})e^{\frac{2πimx}{a}} . (34)

Now, in order to create the DFT structure in the RHS of (33), we specify a and x and write m in appropriate form:

a = n, x = j, j = 0, …, n − 1, m = nr + k, r ∈ Z, k = 0, …, n − 1.

After this (33) takes the form

nb ∑_{r∈Z} f[b(nr + j)] = \sqrt{2π} ∑_{k=0}^{n−1} [∑_{r∈Z} f̃(\frac{2π}{bn} (nr + k))] q^{−kj}  (35)

Now taking in (35) b = \sqrt{\frac{2π}{n}} we obtain a following particular form of (33):

∑_{r∈Z} f (\sqrt{\frac{2π}{n}} (nr + j)) = \frac{1}{\sqrt{n}} ∑_{k=0}^{n−1} [∑_{r∈Z} f̃(\sqrt{\frac{2π}{n}} (nr + k))] q^{−jk}. (36)

Introducing the mapping

M : E → C^{n}, M(f) = v, v_{j} = ∑_{r∈Z} f (\sqrt{\frac{2π}{n}} (nr + j)) , j = 0, …, n−1

we can interpret (36) as an intertwining relation between FT and DFT. Hence we have the following statement. Theorem 8.1 The mapping M is intertwining F and Φ:

Φ M = M F.  (37)

The mapping M is surjective, ^{5} its kernel has the infinite dimension. Any continuous, absolutely integrable eigenfunction ψ of F generates the eigenvector M(ψ) of Φ:

F (ψ) = i^{k}ψ ⇒ Φ M(ψ) = i^{k} M(ψ)  (38)

5to justify this point it is enough to show that we can select the eigenfunctions f_{j}(x)

of F generating via relation (36) the complete system of eigenvectors (20), which is easy to do, (see the end of the section 9)

So far, we have established a very simple connection between the eigenfunctions of FT and eigenvectors of the DFT. ^{6}

9 Generation of the eigenvectors of DFT from any absolutely convergent series

Let

∑_{m∈Z} g_{m}

be any absolutely convergent series. The continuous periodic function g(x) and the periodic sequence f_{j} = f_{j+n}, are defined by the formulas:

g(x) = ∑_{m∈Z} g_{m}q^{mx}, f_{j} = ∑_{r∈Z} g_{rn+j}.

Than it is immediate to prove the following statement. ^{7} Proposition 9.1 (Discrete Poisson summation formula) :

∑_{j=0}^{n−1} q^{jl} ∑_{m∈Z} g_{nm+j} = ∑_{k∈Z} g_{k} q^{kl} = g(l), l = 0, …, n − 1; (39)

∑_{m∈Z} g_{nm+j} = \frac{1}{n} ∑_{l=0}^{n−1} g(l) q^{−lj},  q = e^{\frac{2πi}{n}} , j = 0, …, n − 1. (40)

Of course the second formula is immediate consequence of the first obtained by applying the inversion formula for DFT to the LHS of (39). To prove the first formula we set r = nm + j, which implies that j = r − nm, q^{jl} = q^{rl−lnm} = q^{rl}. Now it is clear that a double sum in the LHS of (39) can be written as a single sum which is exactly the same as the RHS of (39) which completes the proof.

6in special case, when f is any eigenfunction of H, this connection was found by Mehta [23]

7The particular case of the formula (40) written below, corresponding to j = 0, can be found in [11]

Theorem 9.2 Let ∑_{p∈Z} g_{p} is any absolutely converging series. Than the vector v(k) with the components v_{j}(k) ,

v_{j}(k) = ∑_{m∈Z}(g_{nm+j} + (−1)^{k}g_{nm−j}) + \frac{(−i)^{k}}{\sqrt{n}} ∑_{m∈Z}(g_{m} + (−1)^{k}g_{−m})e^{\frac{2πimj}{n}} ,

(41)

is an eigenvector of the DFT :

Φv = i^{k}v.  (42)

All the eigenvectors of the DFT can be constructed in this way.

In order to get the proof, we write in the second sum in (41) m = kn+r . Than, the second sum, for which we use the notation s_{2}, obviously can be represented in a following form:

s_{2} = (−i)^{k} \frac{1}{\sqrt{n}} ∑_{r=0}^{n−1} f_{r} e^{\frac{2πirj}{n}} + (−i)^{3k} \frac{1}{\sqrt{n}} ∑_{r=0}^{n−1} f_{r} e^{− \frac{2πirj}{n}} ,  (43)

where f_{r} is defined by the formula

f_{r} = ∑_{m∈Z} g_{mn+r}.  (44)

Obviously f_{j+n} = f_{j}. Now it is clear that (36) can be represented in the form

v_{j} = f_{j} + (−1)^{k}f_{−j} + (−i)^{k}f̃_{j} + (−i)^{3k}f̃_{−j},  (45)

and hence according to (18) really gives an eigenvector of Φ:

Φv = (i)^{k}v.

In other words formula (41) for the eigenvectors is immediate consequence of the discrete Poisson summation formula and the spectral theorem for the DFT.

In order to show that this construction gives all the eigenvectors of DFT it is enough to take

g_{m}(l) = δ_{lm}, l = 0, …, n − 1.

It is obvious, that this choice of g_{m} reproduces the complete system of eigenvectors (22), QED.

10 Functional identities

We can compare now the explicit expressions for the eigenvectors of Φ coming from spectral theorem with those obtained from the formula (41). Assuming that g_{n} are the functions depending on some parameters, we can expect that for the functions represented by the RHS of (44) we can get in this way some functional identities. ^{8} We will discuss here only the identities for generalized theta functions although there are many other applications which will be considered elsewhere.

We can generate the eigenvectors of Φ with components expressed in terms of the generalized theta functions with rational characteristics choosing for g_{m} in (36) the exponential function.

The generalized theta function θ(x, τ, ν), which we will shortly call νtheta function, is defined by the formula

θ(x, τ, ν) = ∑_{m=−∞}^{∞} e^{πiτm^{2ν}+2πimx},  ν ∈ Z^{+}, Im τ > 0  (46)

It is obvious that θ(x, τ, ν) is an entire function of x satisfying the relation

θ(x + 1, τ, ν) = θ(x, τ, ν).

θ(x, τ, ν) reduces to the usual theta function θ(x, τ) when ν = 1.

It is also evident that ν-theta function satisfies the following partial differential equation

2 (2π)^{2ν−1}(−1)^{ν} \frac{∂θ}{∂τ} = i \frac{∂^{2ν}θ}{∂x^{2ν}}  (47)

The ν-theta function θ_{a,b}(x, τ, ν) with characterstics [a, b] is introduced by the formulas

θ_{a,b}(x, τ, ν) = ∑_{n∈Z} exp[πiτ(n + a)^{2ν} + 2πi(n + a)(x + b)].  (48)

8Mehta [23] discussed the identities coming from (38) in the special case when ψ_{n} = H_{n}(x)e^{− \frac{x^{2}}{2}} i.e. the ψ_{n} are the eigenfunctions of H. Our formulation obviously provides more opportunities.

This function also gives the solution to (47 ). In the case ν = 1, θ_{a,b}(x, τ, ν) reduces to the usual theta function with characteristics θ_{a,b}(x, τ), simply connected with θ(x, τ):

θ(x, τ) = θ(x + aτ + b, τ) exp[πia^{2}τ + 2πia(x + b)].  (49)

Let now g_{m} in (36) is chosen in a following way

g_{m} = exp (\frac{πiτm^{2ν}}{n^{2ν}} + \frac{2πimx}{n}) .  (50)

We obviously have the formula

∑_{m∈Z} g_{mn+j} = θ_{\frac{j}{n} ,0}(x, τ, ν)  (51)

According to (36) and (43) we can formulate the following statement. Proposition 10.1

For any τ with Im τ > 0 vector v(τ, x, k, ν) with the components v_{j},

v_{j}(x, τ, k) = θ_{\frac{j}{n} ,0}(x, τ, ν) + (−1)^{k}θ_{\frac{−j}{n} ,0}(x, τ, ν)
+\frac{1}{\sqrt{n}} [(−i)^{k}θ (\frac{j + x}{n}, \frac{τ}{n^{2ν}} , ν) + (−i)^{3k}θ (\frac{x − j}{n} , \frac{τ}{n^{2ν}} , ν)] . (52)

is the eigenvector of the DFT :

Φ(n)v(k) = i^{k}v(k).  (53)

This result already contains interesting functional relations between the ν-theta functions.

Let e_{k} are the eigenvectors of Φ(n) : Φ(n)e_{k} = i^{k}e_{k}. We obviously have the relation:

Φ(n)(e_{0} + e_{1} + e_{2} + e_{3}) = e_{0} + ie_{1} − e_{2} − ie_{3}  (54)

Applying this relation to the eigenvectors of Φ(n) given by (54) we get the following statement:

Proposition 10.2 ^{9} The ν-theta functions θ (\frac{x+k}{n}, \frac{τ}{n^{2ν}} , ν) and θ_{j/n,0}(x, τ, ν), k, j = 0, …, n− 1 are connected by the discrete Fourier transform :

θ_{j/n,0}(x, τ, ν) = \frac{1}{n} ∑_{k=0}^{n−1} q^{−jk}θ (\frac{x + k}{n} , \frac{τ}{n^{2ν}} , ν) ,  (55)

θ (\frac{x + k}{n} , \frac{τ}{n^{2ν}} , ν) = ∑_{j=0}^{n−1} q^{jk}θ_{j/n,0}(x, τ, ν).  (56)

The independent proof of (55-56) is also very easy. The sum in the RHS of (56) can be written as

∑_{j=0}^{n−1} ∑_{m∈Z} exp [\frac{πiτ}{n^{2ν}} (mn + j)^{2ν} + 2πi(mn + j)\frac{x}{n} + \frac{2πik}{n} (j + mn)] (57)

Now taking into the account that the double sum above is the same as the sum over r ∈ Z, r = mn + j we see immediately that it is the same as the LHS of (56) which completes the proof.

In particular, taking j = 0 in (55) and k = 0 in (56) we get the following two formulas

\begin{matrix}θ(x, τ, ν) = \frac{1}{n} ∑_{k=0}^{n−1} θ (\frac{x+k}{n}, \frac{τ}{n^{2ν}} , ν) , \\ θ (\frac{x}{n}, \frac{τ}{n^{2ν}} , ν) = ∑_{j=0}^{n−1} θ_{j/n,0}(x, τ, ν) \end{matrix}

Unitarity of the discrete Fourier transform implies now the following relations between the ν-theta functions (Parcerval identity):

∑_{k=0}^{n−1} |θ (\frac{x + k}{n} , \frac{τ}{n^{2ν}} , ν)|^{2} = n ∑_{k=0}^{n−1} |θ_{k/n,0}(x, τ, ν)|^{2}  (58)

The relations (55-56) are in fact equivalent to the formula (52) for the eigenvectors. The reason for this is, that any time when we know how to calculate DFT of some vector, we can generate the eigenvectors of DFT via formula (20) in whole analogy with continuous case. We have shown above, that formula (52) for the eigenvectors imply the relations (55-56) which proves the aforementioned equivalence. But Proposition 10.1 , combined with knowledge of spectral multiplicities of DFT says a bit more with respect to (55-56). Namely, for a given value of n, taking the eigenvectors of the form (52) corresponding to the eigenvalue i^{k} with different values of a and t we can claim that only m(k) of them are linearly independent. In other words, all minors of order > m(k), composed from the components of the eigenvectors v(j, k), with x and τ chosen in arbitrary way, vanish. This gives the numerous nonlinear identities between ν-theta functions and, hence, between the usual theta functions. Somehow, we have no intention to discuss these nonlinear identities here.

9In the case ν=1 the result formulated below is well known [32] and describes the connection between two bases in the space of entire functions with prescribed quasi periodicity properties

11 Non-Abelian Z-circulants

Let A_{j}, j = 1, …, n and Z are some m × m complex matrices and Q is some matrix root of Z of degree n i.e. Q^{n} = Z . We call the non-Abelian Z-circulant the following matrix C_{z} = C_{z}(Z|A_{1}, A_{2}, …, A_{n}) :

C_{z} = ( \begin{matrix}A_{1} & A_{2} & … & A_{n} \\ A_{n}Z & A_{1} & … & A_{n−1} \\ ⋮ & … & ... & ⋮ \\ A_{2}Z & … & A_{n}Z & A_{1} \end{matrix} ) .

In the case Z = zI_{m}, z ∈ C, where I_{m} is the m × m unit matrix, C_{z} is a usual block z-circulant matrix with square blocks for which we use the notation C(z|A_{1}, …, A_{n}) Block z-circulant matrices are discussed in [14],[15]. In the case z = 1 the z-circulant reduces to a well known and having many applications block circulant matrix. In the case m = 1 , C_{z} is just usual (scalar) z-circulant matrix.Its eigenvectors are the columns of the Vandermonde matrix , formed by the powers of the nth roots of z and its spectrum, (see more general statement below) can also be found explicitly. Below we formulate and prove some statement concerning the non-Abelian Z-circulants which absorb automatically the most part of previously considered cases of m = 1 or Z = I_{m}z [14]. The fundamental property of the matrix C_{z} is described by the following

Theorem 11.1. To any matrix root Q of Z, i.e. to any Q : Q^{n} = Z corresponds the ”matrix eigenvector” of C_{z}, composed from powers of Q, and the associated ”matrix eigenvalue” is a matrix polynomial of Q with the coefficients A_{j} :

( \begin{matrix}A_{1} & A_{2} & … & A_{n} \\ A_{n}Z & A_{1} & … & A_{n−1} \\ ⋮ & … & ... & ⋮ \\ A_{2}Z & … & A_{n}Z & A_{1} \end{matrix} ) ( I ; Q ; ⋮ ; Q^{n−1} ) = (A_{1}+A_{2}Q+… A_{n}Q^{n−1}) ( I ; Q ; ⋮ ; Q^{n−1} ) .

The proof follows immediately from the relation

A_{k}Z + A_{k+1}ZQ + … + A_{n}ZQ^{n−k} + A_{1}Q^{n−k+1} + … + A_{k−1}Q^{n−1} = (A_{1} + A_{2}Q + … + A_{n}Q^{n−1})Q^{n−k+1}.

which is obvious since we have

QQ^{n−k+1} = Q^{n−k+2}, Q^{2}Q^{n−k+1} = Q^{n−k+3}, …, Q^{k−2}Q^{n−k+1}
= Q^{n−K+1}; Q^{k−1}Q^{n−k+1} = Q^{n} = Z.

Let P (Q) = A_{1}+A_{2}Q+… A_{n}Q^{n−1}, and Q_{j}, j = 1, …, n are n different matrix roots of Z having the property that the matrix U, whose block columns are the matrix eigenvectors of C_{z}, formed from the powers of Q_{j} as above, is invertible. We denote by Λ the block diagonal matrix

Λ = diag[Λ_{1}, Λ_{2}, …, Λ_{n}], Λ_{j} = P (Q_{j}).

Proposition 11.2 Matrix C_{z} is reduced to the block diagonal form by the similarity transformation and its determinant is a product of the determinants of Λ_{j} :

U^{−1}C_{z}U = Λ, det C_{z} = ∏_{j=1}^{n} det Λ_{j}.

Let Z is the block matrix equal to C_{z}(Z|0_{m}, I_{m}, 0_{m}, …, 0_{m}). It is easy to check that

Z^{n} = Z ⊗ I_{n} and

C_{z} = ∑_{j=0}^{n−1} A_{j} ∘ Z^{j}.

The multiplication ∘ in the last formula is understood in the sense that every block in Z^{j} is multiplied by A_{j} from the left. In general, the product of two non-Abelian Z-circulants is not the Zcirculant and C_{z} does not commute with Z, but any linear combination of Z-circulants is again the Z-circulant. In more particular case, where Z = zI_{m}, z ∈ C, the Z circulants form a non commutative subalgebra of the whole matrix algebra with respect to the usual matrix addition and multiplication. Its elements in the later case can be charachterised by the relation C_{z}Z = ZC_{z}, which is not satisfied in general non-Abelian case. In the most simple, but also most important case of the usual scalar circulants we get from the Theorem 11.1 the following classical result, [7, 14]: Proposition 11.3

All circulant matrices c(a⃗) = c(a_{1}, …, a_{n}) are diagonalized simultaneously by the discrete Fourier transform

Φ^{−1}(n)c(a_{1}, …, c_{n})Φ(n) = diag [λ_{1}, …, λ_{n}]

and their eigenvalues λ_{j} are given by the formula

λ⃗ = \sqrt{n} Φ(n)a⃗,  λ⃗ = (λ_{1}, …, λ_{n}).  (59)

The circulant matrix c can be reconstructed from its spectrum λ_{1}, … λ_{n} by means of the DFT inversion formula:

a⃗ = \frac{1}{\sqrt{n}} Φ^{−1}(n)λ⃗

12 Connection between DFT and Harper-Hofschtadter Hamiltonian

. Let c(a_{1}, …, a_{n}) is any hermitian circulant matrix and Λ is its diagonal form defined by the formula Λ = Φ(n)^{−1} c Φ(n) In the case of the simplest choice of c :

c = c(0, a, 0, …, ā), a = |a|e^{iϕ}

formula (55) leads ,obviously, to the following spectrum of c :

λ = 2|a| cos ϕ_{k}, ϕ_{k} = \frac{2πk}{n} + ϕ; k = 0, …, n − 1.  (60)

Hence in this case the hermitian matrix h(ϕ) = c+Λ is of the following form

h = ( \begin{matrix}2|a| cos ϕ & a & 0 & … & 0 & ā \\ ā & 2|a| cos ϕ_{1} & a & … & … & 0 \\ 0 & ā & 2|a| cos ϕ_{2} & ⋮ & 0 & … \\ 0 & 0 & ā & ⋮ & a & … \\ ⋮ & ⋮ & ⋮ & ⋮ & a & 0 \\ 0 & … & 0 & ā & 2|a| cos ϕ_{n−2} & a \\ a & 0 & … & 0 & ā & 2|a| cos ϕ_{n−1} \end{matrix} )

The so called Harper-Hofschtadter hermitian matrix corresponding to the difference Schrödinger equation with cyclic boundary conditions is obtained from the matrix above by replacing the phase ϕ in the last elements of the first row and first column by arbitrary phase γ. Taking a = 1 , ϕ = 0, γ = 0, we get the particular case of Harper-Hofstadter Hamiltonian corresponding to the periodic boundary condition.

The difference Schröedinger equation corresponding to the Harper-Hofschtadter problem is of the following form

H(ψ_{k}) = λ ψ_{k}, k = 0, ±1, ±2, …
H(ψ_{k}) = e^{iϕ}ψ_{k+1} + e^{−iϕ}ψ_{k−1} + 2 cos (\frac{2πk}{n} + ϕ) ψ_{k} = λψ_{k}, (61)

The continuous spectrum of H corresponds to the values of λ for which ψ_{k} is globally bounded.It can be shown that this spectrum coincides with a system of closed intervals formed by the union of spectrums of h(γ) ,when γ ∈ [0, 2 π]. Its boundaries, corresponding to the periodic or anti periodic solutions of (61),

ψ_{k±n} = ±ψ_{n} coincide with the eigenvalues of the matrix h(γ) with γ = 0 and γ = π respectively. Any difference Schrödinger equation with periodic potential u_{k} = u_{k+n} can be solved by the algebraic geometrical methods. The solutions (Baker-Akhiezer functions) are expressed by means of the hyperelliptic Riemann theta functions of the genus n − 1, [33]. The branch points of the associated spectral curve coincide with the boundaries of the continuous spectrum. This solution however is complicated enough. In the special case of the rational Harper-Hofschtadter potential (61) the associated problem allows more efficient solution by means of the Bethe ansatz technic, involving somehow the solution of some transcendental equations for determining the boundaries of the spectrum, [34].

In the case ϕ = 0, a = 1, γ = 0 the eigenvalues and eigenvectors of the matrix h corresponding to the purely periodic solutions of (61) commutes with the DFT matrix. More generally, taking into account that the DFT matrix Φ is symmetric, it is easy to show that, if c is a real symmetric circulant, the matrix h = c + Λ commutes with Φ(n).^{10} The proof is immediate:

Φ c = ΦΛ ⇒ cΦ = ΛΦ ⇒ Φ(c + Λ) = (c + Λ)Φ.  (62)

In particular, this means that the matrix h(0) commutes with Φ and its spectral projectors as well, in the case ϕ = 0, γ = 0, corresponding to the Harper-Hofschtadter problem with periodic boundary condition. This allows to find explicitly eigenvalues of h(0) and its eigenvectors for n ≤ 15, i.e. for the cases where spectral multiplicities m_{j} of Φ(n) satify the condition m_{j} ≤ 4. Comparing the so obtained results with theta functional formulas for the periodic eigenfunctions of H we get some interesting relations between the values of the Riemann theta functions of small genera at the special points. ^{11} For instance, in the case n = 3 , the eigenvalues of the matrices h(0), h(π) are the following numbersE_{j}: −2, \sqrt{3}, 1 + \sqrt{3}, for h(0), and −\sqrt{6}, 0, \sqrt{6} for h(π) . Hence the continuous specrtrum corresponding to the difference equation (61) consists of the three closed intervals [−\sqrt{6}, −2], [1−\sqrt{3}, 0] and [\sqrt{6}, 1 + \sqrt{3}]. The eigenvectors of h(0) can be identified with the eigenvectors of Φ(3). The correspondence between the eigenvalues of Φ(3) and h(0) for the common eigenvectors is the following :

10This observation belongs to Dickinson and Steglitz [13] 11Dickinson and Steglitz [13] proposed to use the h(0) matrix as a tool for constructing the orthogonal basis of the eigenvectors of Φ(n),by my opinion replacing the simpler problem, by more complicated . They also did not observed that the corresponding matrix was related to the Harper-Hofschtater problem. It seems to be more fruitful to explore the fact that DFT commutes with h(0) for spectral analysis of the later.

1 → \sqrt{3} + 1, i → −2, −1 → 1 − \sqrt{3}.

Let ψ_{k}(P (λ)) is a Baker-Akhiezer function, (see [33] ) solving (57) with n = 3, ϕ = 0. ψ_{k}(P) is defined on a hyperelliptic curve of the genus 2:

ω^{2} = ∏_{k=1}^{6}(λ − E_{k}), P = (ω, λ)

Its values at the points λ = E_{1}, E_{2}, E_{3} represent the solution of the periodic problem for (61) i.e ψ_{k+3} = ψ_{k} . Hence, vectors with the components ψ_{0}(E_{k}), ψ_{1}(E_{k}), ψ_{2}(E_{k}) are proportional to the corresponding eigenvectors of Φ(3). This gives the following relations :

ψ_{0}(1 − \sqrt{3}) = (1 − \sqrt{3})ψ_{1}(1 − \sqrt{3}),
ψ_{1}(1 − \sqrt{3}) = ψ_{2}(1 − \sqrt{3}),
ψ_{0}(−2) = 0, ψ_{1}(−2) = −ψ_{2}(−2),
ψ_{0}(1 + \sqrt{3} = (1 + \sqrt{3})ψ_{1}(1 + \sqrt{3}),
ψ_{1}(1 + \sqrt{3}) = ψ_{2}(1 + \sqrt{3})

Substituting the explicit expressions for ψ_{k}(P) in terms of the two dimensional Riemann theta functions in the formulas listed above we obtained the identities satisfied by the values of the Riemann theta functions at the points P = (0, E_{k}), k = 1, 2, 3. Similar considerations, including explicit expressions for the eigenvalues of h(0) in terms of radicals can be performed, as well for all n ≤ 15. Somehow, we have no intention to analyze here these relations in more details. We only wanted to illustrate by the simplest example the existing relations between the DFT and Riemann theta-functions.

13 Concluding remarks

Most part of the results of this article can be easily transfered to the multidimensional case. It is well known that the (unitary) Ndimensional Fourier transform F satisfies the relation F^{4} = I, where I is identity operator in L^{2}(R^{N}) and hence the same kind of the spectral decomposition as (9), holds in this case as well. Formula (10) is also valid in the N-dimensional case, modulo replacing x by x⃗, x⃗ ∈ R^{N}. The multidimensional discrete Fourier transform Φ(k⃗) k⃗ ∈ Z^{N} is by definition a finite tensor product of the usual DFT :

Φ(k⃗) = ⨂_{j=1}^{N} Φ(k_{j})

Hence we can generate its orthogonal eigenvectors taking the tensor products of the orthogonal eigenvectors of Φ(k_{j}). We also have the obvious relation

Φ^{4}(k⃗) = ⨂_{j=1}^{N} I_{k_{j}}, k = (k_{1}, …, k_{N}).

where I_{k_{j}} are the k_{j} × k_{j} identity matrices. So the spectral decomposition of the form (18) might be applied again together with all its consequences. Another important ingredient which was used - the Poisson summation formula is also well known in the multidimensional case. More detailed discussion of the multidimensional generalizations of the results of this article will be presented elsewhere.

The result of the section 7 proves for odd values of n the existence of the analogues of the creation-annihilation operators for the case of DFT, allowing to generate the orthogonal eigenvectors of DFT in a way similar to the use of the operators a, a^{∗} for the Fourier transform. Somehow it is not obvious how to find the realization comfortable enough to provide the advantage with respect to existing constructions of the orthonormal bases of eigenvectors of DFT. It will be interesting to get some progress in this direction, although the existing results on the Bethe-ansatz approach for the Harper-Hofschtadter problem are not very encouraging in this sense.

Aknowledgments

I am grateful to Max-Planck-Institut für Mathematik, where this work was written, for hospitality.

References

[1] Cooley nd Tukey ”An algorithm for the machine computation of the complex Fourier series ” Math. Comput. 19, 297-301 (1965)

[2] J.S.Walker ”The fast Fourier Transform ” CRS Press , p.1-437 (1996)

[3] F.Riesz et B.Sz. Nagy, ”Lecons d’Analyse fonctionnelle” Academiai Kiado, Budapest (1953)

[4] R.D. Richtmyer,” Principles of Advanced Mathematical Physics” v.1, Springer-Verlag ser. Texts and Monographs in Physics (1978)

[5] F.R. Gantmacher ”The Theory of Matrices ” Vol. 1, Chelsea Publ. Comp. New York (1990)

[6] B.C.Berndt , R.D. Evans ”The determination of the Gauss sums” J. of Amer. Math. Soc. v.5 n.2 ,p.107-129 (1981)

[7] L. Cremona Intorno ad un teorema di Abel . Annali di Scienze matematiche e fisiche (7) p.99-105 (1856)

[8] K.Conrad ”The origin of representation theory ” L’Enseignement Mathématique t.44 p.361-392 (1998)

[9] I.Schur Nachr. K. Gesell, Wiss. Göttingen, Math.-Phys. K1, p.147

[10] L.Carlitz,” Some cyclotomic matrices”, Acta Arithmetica p.293-308, V (1959)

[11] I.J.Good, ”Analogues of Poisson Summation Formula”, Amer. Math. Monthly v.69 p.259-266 (1962)

[12] J.H.McClennan , T.W.Parks, ”Eigenvalue and Eigenvector Decomposition of the Discrete Fourier Transform”, IEEE Trans Audio and Electroacoustics ,vol. AU-20 n.1, p. 66-74 March (1972)

[13] B.W. Dickinson , K.Steiglitz , ”Eigenvectors and Functions of the Discrete Fourier Transform” Trans. on Acoustics,Speech, and Signal Processing, vol. ASSP-30 n.1 , February 1982.

[14] P.D. Davis Circulant matrices , p. 1-300 ,Wiley -Interscience Pub. , New York-Toronto Brisban (1979)

[15] R.L. Smith, Moore-Penrose Inverses of Block k-circulant matrices, J. of Linear Alg. and Its Appl., 16, 237-245 (1977)

[16] L.Auslander , R.Tolimieri ”Is computing with the Finite Fourier Transform Pure or Applied Mathematics ?” Bull. Amer.Math.Soc. 1 p.847-897 (1979)

[17] L.Auslander , R.Tolimiery ”Abelian harmonic analysis , theta functions and function algebras on nilmanifolds” Lecture Notes in Math. v.436, Springer, (1975)

[18] P.Morton ”On the eigenvectors of Schur’s Matrix” J.of Number Theory 12 , 122-127 (1980)

[19] L.Auslander , R.Tolimiery ”Algebraic structures for ⨁ ∑_{n≥1} L^{2}(Z/n) compatible with the finite Fourier transform” Trans. Amer. Math. Soc. 244 p.263-272 (1978)

[20] L. Auslander, E.Feig, S.Winograd ”Abelian Semi-simple Algebras and Algorithms for the DFT” Adv. in Appl. Math. 5 31-55 (1984)

[21] R.Tolimiery ”The construction of Orthonormal Bases Diagonalising the DFT” , Advances in Applied Mathematics 5 56-86 (1984)

[22] R.Balian , C.Itzykson ”Observations sur la mécanique quantique finie” C.R.Acad.SC. Paris , v.303 , Serie I, n.16, p.773-778 (1986)

[23] M.L.Mehta ”Eigenvalues and Eigenvectors of the Finite Fourier Transform” J.Math.Phys. 28 (4) p.781-785 (1987)

[24] M.C . Gutzwiller ”Physics and Arithmetic Chaos in the Fourier Transform” in ” The Mathematical Beauty of Physics ” A memorial volume for Claude Itzykson Ed.by J.M. Drouffe and J.B.Zuber World Scientific, Advanced Series in Mathematical Physics v.24 , p.1-365, (1997) p.258-280 (1995)

[25] P.J.Harper, Proc.Roy.Soc. A 68 p.874 (1955)

[26] R.D. Hofstadter Phys.Rev.B (14) 2239 (1976)

[27] V.B.Matveev , A.O.Smirnov ”Some comments on the solvable chiral Potts model” Letters in Mathematical physics 19 : 179-185 , 1990

[28] E.G.Floratos ”A quantum mechanical analogue for the qoscillator” Phys. Lett. B 251 n.1 p. 163-166 (1990)

[29] A.Bobenko, N.Kutz, U.Pinkall ”The discrete quantum pendlum” Phys. Lett. A 177 p.399-404 (1993)

[30] V. Karimupur ”A solvable hamiltonian system:Integrability and action angle variables” J.Math. Phys 38 n.3 p.1577-1582 (1997)

[31] J. Weiss J.Math. Phys, Periodic fixed points of Backlund transformations 28n.9 2025-2038 (1987)

[32] D. Mumford ”Tata Lectures on Theta v.1”, Birkhauser, Basel (1983)

[33] I.M.Krichever , ”Peierls model” J. of Functional analysis and its applications ,16 n.4, 10-26 (1982)

[34] P.Wiegmann , A.Zabrodin, ”Quantum group and magnetic translations. Bethe ansatz for the Azbel-Hofschtadter problem” Nucl.Phys. B 422, 495-514, (1994)