ON CIRCULANT MATRICES

DARYL GELLER, IRWIN KRA, SORIN POPESCU AND SANTIAGO SIMANCA

1. Introduction

Fix a positive integer n ≥ 2, and let

v = (v_{0}, v_{1}, …, v_{n−1})

be a row vector in ℂ^{n}. Define the shift operator T : ℂ^{n} → ℂ^{n} by

T (v_{0}, v_{1}, …, v_{n−1}) = (v_{n−1}, v_{0}, …, v_{n−2}) .

The circulant matrix associated to v is the n×n matrix whose rows are given by iterations of the shift operator acting on v, that is to say, the matrix whose k-th row is given by T^{k−1}v, k = 1, …, n. Such a matrix will be denoted by

V = circ{v} = circ{v_{0}, v_{1}, …, v_{n−1}} .

Special cases of this type of matrices (see Theorem 3) appeared in one of the authors’ recent work [7] based on [3]. They seem to be prevalent in certain parts of mathematics (see, for example, [5]). For reference purposes, we point the reader to the elegant treatment given in [4, §5.2], and the monograph [1] devoted to the subject.

Our work was originally motivated by the need to derive a specific result (Theorem 3) to be applied in the investigation of theta constant identities. Recently, our Theorem 3 has also been applied, in [6], to the theory of optimization in the field of management and information sciences.

Many facts about these matrices can be proven using only basic linear algebra. This makes the area quite accessible to undergraduates looking for “research problems.” Our note presents a general view of these type of matrices, and hopes to illustrates the latter point by including in it a number of problems that may be of interest to students.

In our presentation, we concentrate on the discussion of necessary and sufficient conditions for circulant matrices to be nonsingular. This single goal allows us to lay out a rich mathematical structure surrounding these matrices, though this is by no means, an exhaustive treatment of all the properties they have. We have tried to make the note accessible to a wide audience by supplying rather full details in most of the arguments. When faced with the possibility of presenting a short argument or a longer one that requires less prerequisites, we have chosen the latter approach. At times the shorter, more elegant, argument is outlined in a remark.

The paper is organized as follows. We begin in §2 by evaluating the determinant of a circulant matrix, and computing some of its invariants. In §3, we discuss the space of such matrices, and show that it has the structure of a finite dimensional commutative algebra. Symmetries of circulant matrices are discussed briefly in §4. All this material is well known. Not so readily found in the literature is the remaining material. In §5, we determine necessary and sufficient conditions for a circulant matrix to be nonsingular provided n is prime. The case of real matrices is discussed in §6. We end our note by establishing, in §7, a relationship between the determinant of a circulant matrix and the rational normal curve in complex projective space. This material is not as elementary as the rest of our note, but illustrates the fact that circulant matrices have a strong presence in various parts of modern (and classical) mathematics. The interested reader may find a simpler illustration of this fact in [8].

It is a pleasure for Irwin Kra to thank Yum-Tong Siu, with whom he had enlightening conversations during a recent visit to Vietnam. Siu brought to his attention another, more elementary, proof of formula (1), and helped generate interest in the further study of circulant matrices. He also thanks Paul Fuhrmann for bringing to his attention a number of references, and for the helpful criticism of an earlier draft of this manuscript.

2. The general case

Theorem 1. Let v = (v_{0}, v_{1}, …, v_{n−1}) be a vector in ℂ^{n}, and V = circ{v}. If ϵ is a primitive n-th root of unity, then

(1) det V = det [ \begin{matrix}v_{0} & v_{1} & ⋯ & v_{n−2} & v_{n−1} \\ v_{n−1} & v_{0} & ⋯ & v_{n−3} & v_{n−2} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ v_{2} & v_{3} & ⋯ & v_{0} & v_{1} \\ v_{1} & v_{2} & ⋯ & v_{n−1} & v_{0} \end{matrix} ] = ∏_{l=0}^{n−1} (∑_{j=0}^{n−1} ϵ^{jl}v_{j}) .

Proof. We view the matrix V = circ{v_{0}, v_{2}, …, v_{n−1}} as a self map (linear operator) of ℂ^{n}. For each integer l, 0 ≤ l ≤ n − 1, let x_{l} ∈ ℂ^{n} be the transpose of the row vector \frac{1}{\sqrt{n}}(1, ϵ^{l}, ϵ^{2l}, …, ϵ^{(n−1)l}) and^{1}

λ_{l} = v_{0} + ϵ^{l}v_{1} + ⋯ + ϵ^{(n−1)l}v_{n−1}.

A calculation shows that

[ \begin{matrix}v_{0} & v_{1} & ⋯ & v_{n−2} & v_{n−1} \\ v_{n−1} & v_{0} & ⋯ & v_{n−3} & v_{n−2} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ v_{2} & v_{3} & ⋯ & v_{0} & v_{1} \\ v_{1} & v_{2} & ⋯ & v_{n−1} & v_{0} \end{matrix} ] [ 1 ; ϵ^{l} ; ϵ^{2l} ; ⋮ ; ϵ^{(n−1)l} ] = λ_{l} [ 1 ; ϵ^{l} ; ϵ^{2l} ; ⋮ ; ϵ^{(n−1)l} ] .

Thus λ_{l} is an eigenvalue of V with normalized eigenvector x_{l}. Since {x_{0}, x_{1}, …, x_{n−1}} is a linearly independent set, we conclude that

det V = ∏_{l=0}^{n−1} λ_{l} .

□

Problem 1. Investigate the connection of the above result to the spectral mapping theorem.

Corollary 1. The characteristic polynomial of V is

p_{V} (x) = det (xI − V) = ∏_{l=0}^{n−1}(x − λ_{l}).

Corollary 2. The nullity of V is the number of zero eigenvalues λ_{l}.

Corollary 3. We have ∑_{l=0}^{n−1} λ_{l} = nv_{0}.

Proof. Since

∑_{l=0}^{n−1} e^{il} = \{ \begin{matrix}n & for i = 0 \\ 0 & for i = 1, ..., n − 1 \end{matrix} ,

we see that

∑_{l=0}^{n−1} λ_{l} = ∑_{l=0}^{n−1} ∑_{i=0}^{n−1} e^{li}v_{i} = ∑_{i=0}^{n−1} (∑_{l=0}^{n−1} e^{li}) v_{i} = nv_{0}.

□

1We reserve the symbols λ_{l} and x_{l} for this eigenvalue and eigenvector throughout the manuscript. We use the convention, unless otherwise specified, that all vectors are column matrices. However, we will often write them as row matrices without mentioning that we are considering the transpose of the column vector. This identification should not cause any confusion. In a sense, it was already used in defining the shift operator T. In line with this convention, matrices, when viewed as linear operators, multiply column vectors on the left.

Remark 1. The last corollary also follows from the identity ∑_{l=0}^{n−1} λ_{l} = trace V.

3. The space of Circulant matrices

Definition 1. We define Circ(n) to be the set of all n × n complex circulant matrices.

We record a number of consequences of the last theorem.

Corollary 4. Circ(n) is an n-dimensional commutative subalgebra of the algebra of n × n matrices with the usual matrix operations of addition and multiplication. Furthermore, transposes of circulant matrices and inverses of nonsingular circulant matrices are also circulant. All elements of Circ(n) are simultaneously diagonalized by the same unitary matrix.

Proof. Let C be the n×n matrix that represents the linear transformation sending the l-th unit vector e_{l} (this is the vector (0, ..., 0, 1, 0, ..., 0) with the 1 in the l-th slot) to x_{l}:

C := \frac{1}{\sqrt{n}} [ \begin{matrix}1 & 1 & ⋯ & 1 & 1 \\ 1 & ϵ & ⋯ & ϵ^{n−2} & ϵ^{n−1} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 1 & ϵ^{n−2} & ⋯ & ϵ^{(n−2)^{2}} & ϵ^{(n−1)(n−2)} \\ 1 & ϵ^{n−1} & ⋯ & ϵ^{(n−2)(n−1)} & ϵ^{(n−1)^{2}} \end{matrix} ] ,

and let D_{V} be the diagonal matrix with diagonal entries λ_{0}, λ_{1}, …, λ_{n−2}, λ_{n−1}, respectively. Then

C^{−1}V C = D_{V} .

The remaining conclusions of the corollary follow readily now. □

If we let

W = circ{0, 1, 0, …, 0},

then it is seen easily that

circ{v_{0}, v_{1}, …, v_{n−1}} = ∑_{i=0}^{n−1} v_{i}W^{i}.

Remark 2. With respect to the standard basis of ℂ^{n}, the shift operator T is represented by the transpose of the matrix W; that is, by circ{0, 0, …, 0, 1}.

Corollary 5. The map that sends W to the indeterminate X establishes an isomorphism of algebras between Circ(n) and ℂ[X]/(X^{n} − 1).

Definition 2. Given a circulant matrix V = circ{v_{0}, v_{1}, …, v_{n−1}}, we define its representer as the polynomial P_{V} (X) = ∑_{i=0}^{n−1} v_{i}X^{i}.

Corollary 6. For l = 0, …, n − 1, we have that λ_{l} = P_{V} (e^{\frac{2πı}{n} l}).

Corollary 7. Let V be a circulant matrix with representer P_{V} (X). The following are equivalent:

(a) The matrix V is singular.

(b) P_{V} (e^{\frac{2πı}{n} l}) = 0 for some l ∈ ℤ.

(c) The polynomials P_{V} (X) and X^{n} − 1 are not relatively prime.

Remark 3. The nullity of a circulant matrix V with representer P_{V} (X) is the degree of the greatest common divisor of P_{V} (X) and X^{n} − 1.

Remark 4. For each n×n circulant matrix V, we have two polynomials: its representer P_{V} of degree ≤ n − 1 and its characteristic polynomial p_{V} of degree n. We can describe these polynomials rather explicitly in terms of the eigenvalues λ_{l} of V.

The characteristic polynomial p_{V} is the unique monic polynomial of degree n that vanishes at λ_{l}, l = 0, 1, …, n − 1. The representer P_{V} is the unique polynomial of degree ≤ n − 1 whose value at e^{\frac{2πıl}{n}} is λ_{l} for l = 0, 1, …, n − 1.

The roots of the characteristic polynomial of an arbitrary n × n matrix V (these are the eigenvalues of the matrix V) are obtained by solving a monic n-degree polynomial equation. However, in the case of circulant matrices, the roots of p_{V} are easily calculated using the auxiliary companion polynomial P_{V}. Thus if a given polynomial p is known to be the characteristic polynomial of a known circulant matrix V, its zeroes can be readily found. This remark is the basis of [5]. It is thus of considerable interest to determine which monic polynomials are characteristic polynomials of circulant matrices. Further, if we are given that p = p_{V} for some circulant matrix V, can we determine V, or equivalently P_{V}, directly from p?

We can obviously recover V from its representer. If λ = (λ_{0}, …, λ_{n−1}) is an ordered set of eigenvalues, then there is a unique circulant matrix V = circ{v} = circ{v_{0}, v_{1}, …, v_{n−1}} whose ordered eigenvalues are λ:

v = \sqrt{n}C^{−1}λ .

Thus there are at most (n − 1)! (see Corollary 3) circulant matrices V with characteristic polynomial p_{V}. In particular, every monic polynomial p is the characteristic polynomial of some circulant matrix V.

But the argument above avoids completely the issue of finding the roots of p, as the given construction of V from p started by assuming we had the roots of the polynomial. So the more difficult question is the construction of V (or equivalently, it representer P_{V}) in terms of the coefficients of the polynomial p.

Problem 2. Describe the finite set of circulant matrices with fixed characteristic polynomial.

Problem 3. Let 𝒫 be the space of polynomials of degree ≤ n − 1. We have seen that 𝒫 is canonically isomorphic to Circ(n) and thus, for each p ∈ 𝒫, there exists a unique V ∈ Circ(n) such that p = p_{V}. Let ℳ be the space of monic polynomials of degree n. We obtain a map λ : 𝒫 ↦ ℳ by sending p to p_{V}.

We know that λ is surjective. The last problem asked for a description of λ^{−1}(p) for arbitrary p ∈ ℳ. We now want to study the induced differential map dλ.

We have shown that for q ∈ ℳ,

q(x) = ∏_{i=0}^{n−1}(x − λ_{i}) = x^{n} + ∑_{i=0}^{n−1} a_{i}x^{i} ,

and if for p ∈ λ^{−1}(q),

p(x) = ∑_{i=0}^{n−1} v_{i}x^{i} ,

we must have

nv_{0} = ∑_{i=0}^{n−1} λ_{i} = a_{n−1} .

We can represent an arbitrary p ∈ 𝒫 by its coordinates v ∈ ℂ^{n} as in Definition 2. We represent a point in ℳ by its roots as in Corollary 1. In these coordinates, the differential of λ is given by

dλ = [\frac{∂λ_{l}}{∂v_{j}} ] = [e^{\frac{2πılj}{n}} ] = \sqrt{n}C.

It is constant and invertible. Thus the map λ is always a local homeomorphism. But it is not globally injective.

Does λ have a splitting map σ? In other words, is there a map σ : ℳ ↦ 𝒫 such that λ ∘ σ is the identity?

Corollary 8. If for some k, |v_{k}| > ∑_{j≠k} |v_{j}|, then the circulant matrix V = circ{v_{0}, …, v_{n−1}} is nonsingular.

Proof. Let P_{V} (X) be the representer of V. If P_{V} (e^{\frac{2πı}{n} l}) = 0 for some

l ∈ ℤ, then for η = e^{\frac{2πı}{n} l},

v_{k}η^{k} = − ∑_{j≠k} v_{j}η^{j}.

In particular

|v_{k}| ≤ ∑_{j≠k} |v_{j}|,

which contradicts the hypothesis. □

Corollary 9. Let d|n, d ≥ 1, and assume that the vector v consists of \frac{n}{d} identical blocks (that is, v_{i+d} = v_{i} for all i, where indices are calculated modulo n). Then λ_{l} = 0 whenever dl is not a multiple of n; hence V is singular and its nullity is ≥ n − d.

Proof. For all l,

λ_{l} = ∑_{i=0}^{n−1} ϵ^{li}v_{i} = ∑_{j=0}^{\frac{n}{d} −1} ∑_{i=0}^{d−1} ϵ^{ldj} (ϵ^{li}v_{i}) = \frac{1 − ϵ^{nl}}{1 − e^{dl}} ∑_{i=0}^{d−1} ϵ^{li}v_{i},

provided dl is not a multiple of n. In particular, λ_{l} = 0 for 1 ≤ l < \frac{n}{d}. In general there are n − d integers l such that 0 ≤ l < n and dl is not a multiple of n. □

Remark 5. In this case

P_{V} (X) = (∑_{i=0}^{d−1} v_{i}X^{i}) (\frac{X^{n} − 1}{X^{d} − 1})

and the polynomial \frac{X^{n}−1}{X^{d}−1} of degree n−d divides both P_{V} (X) and X^{n}−1 (see Corollary 7).

Corollary 10. Let d|n, d ≥ 2, and assume that the vector v consists of \frac{n}{d} consecutive constant blocks of length d (that is, v_{id+j} = v_{id} for i = 0, 1, … \frac{n}{d} − 1 and j = 0, 1, …, d − 1). Then λ_{l} = 0 whenever l ≠ 0 and l ≡ 0 mod \frac{n}{d}, hence V is singular and its nullity is ≥ d − 1.

Proof. In this case

λ_{l} = ∑_{i=0}^{n−1} ϵ^{li}v_{i} = ∑_{j=0}^{\frac{n}{d} −1} ϵ^{ldj}v_{dj} ∑_{i=0}^{d−1} ϵ^{li} = \frac{1 − ϵ^{ld}}{1 − ϵ^{l}} ∑_{j=0}^{\frac{n}{d} −1} ϵ^{ldj}v_{dj},

provided l > 0. In particular, λ_{l} = 0 for all l = α\frac{n}{d}, with α = 1, 2, …, d − 1. □

Remark 6. In this case

P_{V} (X) = (∑_{i=0}^{\frac{n}{d} −1} v_{i}X^{id}) (\frac{X^{d} − 1}{X − 1})

and the polynomial \frac{X^{d}−1}{X−1} of degree d−1 divides both P_{V} (X) and X^{n}−1 (see Corollary 7).

4. Symmetries of Circ(n)

It is easy to see that

det circ{v_{0}, v_{1}, …, v_{n−1}}
= (−1)^{k(n−1)} det circ{v_{k}, v_{k+1}, …, v_{n−1}, v_{0}, …, v_{k−1}} .

We also have that

det circ{v_{0}, v_{1}, …, v_{n−1}} = (−1)^{n−1} det circ{v_{n−1}, v_{n−2}, …, v_{1}, v_{0}} .

However, there is no obvious general relation between

det circ{v_{0}, v_{1}, …, v_{n−1}} and det circ{v_{σ(0)}, v_{σ(1)}, …, v_{σ(n−1)}} in the case where σ is an arbitrary permutation of n elements.

Given an invertible scalar a, we also have the relation

det circ{v_{0}, v_{1}, …, v_{n−1}} = a^{−n} det circ{av_{0}, av_{1}, …, av_{n−1}} .

Problem 4. Investigate the action of the permutation group on n letters on Circ(n).

5. The case of n prime

Theorem 2. Let n ∈ ℤ_{>0} be a prime. Assume that V has entries in ℚ^{n}. Then

det V = det [ \begin{matrix}v_{0} & v_{1} & ⋯ & v_{n−2} & v_{n−1} \\ v_{n−1} & v_{0} & ⋯ & v_{n−3} & v_{n−2} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ v_{2} & v_{3} & ⋯ & v_{0} & v_{1} \\ v_{1} & v_{2} & ⋯ & v_{n−1} & v_{0} \end{matrix} ] = 0

if and only if either λ_{0} = 0 or all the v_{i} are equal.

Proof. If all the v_{i}’s are equal, then λ_{l} = 0 for all l > 0. We already know that the vanishing of some λ_{l} implies that det V = 0. Conversely assume that det V = 0 and that λ_{0} ≠ 0. Then λ_{l} = 0 for some positive integer l < n.

Again we take ϵ = e^{2πi/n}. By our formula for λ_{l}, we see that ϵ^{l} is a root of the polynomial

p(x) = ∑_{i=0}^{n−1} v_{i}x^{i}.

However, since n is prime, ϵ^{l} is a primitive n-th root of unity, so the minimal polynomial of ϵ^{l} over the rationals is the cyclotomic polynomial

q(x) = ∑_{i=0}^{n−1} x^{i}.

Therefore p is a constant multiple of q. Consequently all v_{i} are equal, as desired. □

6. Real points

Theorem 3. If {v_{j}}_{0≤j≤n−1} is a weakly monotone sequence (that is, a nondecreasing or nonincreasing sequence) of nonnegative or nonpositive real numbers, then the matrix V = circ{v_{0}, v_{1}, ..., v_{n−1}} is singular if and only if for some integer d|n, d ≥ 2, the vector v = (v_{0}, v_{1}, …, v_{n−1}) consists of \frac{n}{d} consecutive constant blocks of length d. In particular, if the sequence {v_{j}}_{0≤j≤n−1} is strictly monotone and nonpositive or nonnegative, then V is non-singular.

Proof. If the matrix V were singular, then its representer P_{V} (X) = ∑_{i=0}^{n−1} v_{i}X^{i} would vanish at an n-th root of unity, say ϵ. We can easily see that it is sufficient to prove the theorem in the case when {v_{j}}_{0≤j≤n−1} is a nonincreasing sequence of nonnegative real numbers; all other cases reduce to this one, by replacing ϵ with \frac{1}{ϵ} or by appropriately changing the signs of all the v_{i}’s (see also the symmetries discussed in §4). We may thus assume in the sequel that

v_{0} ≥ v_{1} ≥ … v_{n−1} ≥ 0.

Now P_{V} (λ) = 0 means that

v_{0} + v_{1}ϵ + ⋯ + v_{n−1}ϵ^{n−1} = 0

and hence also

v_{0}ϵ + v_{1}ϵ^{2} + ⋯ + v_{n−1}ϵ^{n} = 0,

which yields

(2) v_{0} − v_{n−1} = (v_{0} − v_{1})ϵ + (v_{1} − v_{2})ϵ^{2} + ⋯ + (v_{n−2} − v_{n−1})ϵ^{n−1}.

Observe that if z_{1}, …, z_{m} are complex numbers such that

(3)  ∑_{i=1}^{m} z_{i} = |∑_{i=1}^{m} z_{i}| = ∑_{i=1}^{m} | z_{i} |,

then z_{i} ≥ 0 for all i = 1, …, m. Since |ϵ| = 1, it follows from (2) that z_{k} = (v_{k−1} − v_{k})ϵ^{k}, k = 1, …, n − 1 satisfy (3), and thus for each k either v_{k−1} = v_{k}, or ϵ^{k} = 1. The latter holds only if ϵ is actually a d-th root of unity, for some divisor d ≥ 2 of n, while k is a multiple of d, and the conclusions of the theorem follow easily now.

Indeed, to be specific, choose the smallest positive integer d such that ϵ^{d} = 1. Then d ≥ 2, d|n and ϵ^{k} = 1 for 1 ≤ k ≤ n if and only if k = d, 2d, … or n = \frac{n}{d}d. It follows that v_{k} = v_{k−1} = … = v_{k−(d−1)}. □

Remark 7. (a) With an argument similar to the one in the proof above, one can show that if the sequence {v_{j}}_{j=0}^{n−1} is non-increasing and v_{n−1} > 0, then P (X) = ∑_{i=0}^{n−1} v_{i}X^{i} is non-zero for any X on the unit complex disk |X| < 1. This result can be applied to show that if P (X) = ∑_{i=0}^{n−1} v_{i}X^{i} is a polynomial whose coefficients v_{i} are positive, then its zeros λ all lie in the annulus m ≤ |λ| ≤ M, where

m = min \{\frac{v_{i}}{v_{i+1}} ; i = 0, 1, …, n − 2\}

and

M = max \{\frac{v_{i}}{v_{i+1}} ; i = 0, 1, …, n − 2\} .

(b) The circulant matrices formed from the vectors (−3, −1, 0, 2, 2) and (−4, −1, 0, 2, 3) show that certain parts of the hypothesis cannot be weakened.

(c) For a real circulant matrix, λ_{l} = 0 if and only if λ_{n−l} = 0.

Problem 5. Investigate generalizations of the last theorem to the complex case.

We end this section with the related

Problem 6. Let 𝒱 = ℂ^{n} and let G be a finite group of order n that acts by permutations on the coordinates of ℂ^{n}; that is, for v = (v_{1}, ..., v_{n}) ∈ 𝒱 and g ∈ G,

g(v_{1}, ..., v_{n}) = (v_{g(1)}, ..., v_{g(n)}).

Then the fixed point set

𝒱^{G} = {v ∈ 𝒱; g(v) = v for all g ∈ G}

is a nontrivial subspace of 𝒱 since it contains the vector (1, ..., 1). It is reasonable to conjecture that

(4)  dim 𝒱^{G} |G .

• Construct an example to show that the conjecture as it stands is false.

• Can one add some hypotheses concerning the action of G on 𝒱 so that the divisibility property (4) holds?

• Let V = {y_{1}, y_{2}, ..., y_{r}} be a finite collection of vectors in 𝒱 and let G(V) be the span of the vectors {g(y_{i}); g ∈ G, i = 1, 2, ..., r}. Can one compute the dimension of G(V) in terms of invariants of the group G and collection V?

• In particular, if r = 1, viewing y = y_{1} as a row vector and ordering the elements of G as {g_{1}, ..., g_{n}}, we form an n × n matrix M whose k-th row is g_{k}(y). Under what conditions is M nonsingular?

7. Circulant matrices and rational normal curves

There is an alternative, more complicated but more geometric, proof of Theorem 1. We present it in this section, which also shows the usefulness of circulant matrices in algebraic geometry, and that one can also study other invariants, besides the determinant, of (generic) circulant matrices; for example, their lower order minors.

Let us begin by recalling that complex projective n-space ℙ^{n} is the set of one-dimensional subspaces of ℂ^{n+1}. A point p ∈ ℙ^{n} is usually written as a homogeneous vector [z_{0} : …: z_{n}], by which is meant the complex line spanned by (z_{0}, …, z_{n}) ∈ ℂ^{n+1} \ {0}.

A polynomial f ∈ ℂ[z_{0}, …, z_{n}] does not in general descend to a function on ℙ^{n}. However, if f is a homogeneous polynomial of degree d, we can perfectly talk about the zeroes of f in ℙ^{n} because we have the relation f(λz_{0}, …, λz_{n}) = λ^{d}f(z_{0}, …, z_{n}). The rational normal curve C_{d} ⊂ ℙ^{d} of degree d is defined to be the image of the map ℙ^{1} → ℙ^{d}, given by

[z_{0} : z_{1}] ↦ [z_{0}^{d} : z_{0}^{d−1}z_{1} : …: z_{0}z_{1}^{d−1} : z_{1}^{d}] = [Z_{0} : …: Z_{d}] .

This set is easily seen to be the common zero locus of the polynomials p_{ij} = Z_{i}Z_{j} − Z_{i−1}Z_{j+1} for 1 ≤ i ≤ j ≤ d − 1. The ideal of C_{d}, I(C_{d}) := {f ∈ ℂ[Z_{0}, …, Z_{n}] | f ≡ 0 on C_{d}} is actually generated by this family of polynomials.

In general, an algebraic subset X ⊂ ℙ^{n} is defined to be the zero locus of a collection of homogeneous polynomials, and its ideal I(X) consists of the set of polynomials that vanish on X.

Let us now think of {v_{0}, …, v_{n−1}, …, v_{2n−2}} as a set of 2n − 1 independent variables, and consider the matrix (beloved by invariant theorists) with constant antidiagonals given by

M := [ \begin{matrix}v_{0} & v_{1} & ⋯ & v_{n−2} & v_{n−1} \\ v_{1} & v_{2} & ⋯ & v_{n−1} & v_{n} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ v_{n−2} & v_{n−1} & ⋯ & v_{2n−4} & v_{2n−3} \\ v_{n−1} & v_{n} & ⋯ & v_{2n−3} & v_{2n−2} \end{matrix} ] .

This matrix is called the (generic) n × n catalecticant matrix. By the above observations, the 2×2-minors of M define the ideal of the rational normal curve C = C_{2n−2} ⊂ ℙ^{2n−2} of degree 2n − 2,

ℙ^{1} ∋ [z_{0} : z_{1}] ↦ [z_{0}^{2n−2} : z_{0}^{2n−3}z_{1} : z_{0}^{2n−4}z_{1}^{2} : …: z_{1}^{2n−2}] ∈ ℙ^{2n−2} .

The other ideals of minors of M have geometric significance too. Since the sum of m matrices of rank one has rank at most m, it follows that for each k ∈ {2, …, n} the ideal I_{k} of k × k-minors of M vanishes on the union of the (k − 1)-secant (k − 2)-planes to the rational normal curve C ⊂ ℙ^{2n−2}. Actually, it turns out that the ideal I_{k} of k×k-minors of M defines the (reduced) locus of these (k − 1)-secant (k − 2)-planes to C (Raymond Wakerling, unpublished Ph.D. thesis, Berkeley 1939; see [2] for a modern complete proof).

Note that the restriction of the matrix M to the (n − 1)-dimensional linear subspace Λ ⊂ ℙ^{2n−2} defined by

Λ = {v_{n} − v_{0} = v_{n+1} − v_{1} = ⋯ = v_{2n−2} − v_{n−2} = 0}

coincides up to row permutations with the (generic) circulant matrix

V = circ{v_{0}, v_{1}, …, v_{n−1}}.

(Here we say that a circulant matrix V is generic if {v_{0}, …, v_{n−1}} are considered independent variables.)

On the other hand the intersection Λ ∩ C, consists of the n points whose coordinates [z_{0} : z_{1}] ∈ ℙ^{1} satisfy the equations

(z_{0}^{n−2}, z_{0}^{n−3}z_{1}, …, z_{1}^{n−2}) · (z_{0}^{n} − z_{1}^{n}) = 0 ,

or equivalently z_{0}^{n} − z_{1}^{n} = 0. If ϵ is as above a primitive n-th root of unity, these n points have coordinates in Λ[v_{0} : …: v_{n−1}]

p_{i} = [1 : ϵ^{i} : ϵ^{2i} : ⋯: ϵ^{(n−1)i}], i ∈ {0, …, n − 1}.

It follows that the restriction of I_{k} to Λ vanishes on the union of (k−2)- planes

⋃_{i_{1},i_{2},...,i_{k−1}∈{0,...,n−1}} span(p_{i_{1}}, p_{i_{2}}, …, p_{i_{k−1}}).

In particular, the determinant of the generic circulant matrix V vanishes on the union of the n distinct hyperplanes

⋃_{i∈{0,...,n−1}} span(p_{0}, p_{1}, …, p̂_{i}, …, p_{n−1}),

where (as usual) in the last union, the symbol p̂_{i} denotes that p_{i} does not appear. But the union of the above n distinct hyperplanes is defined by a single polynomial of degree n (product of linear forms vanishing on each of the hyperplanes), while the determinant of the generic circulant matrix V is also a polynomial of degree n. Thus, by degree reasons these polynomials must agree up to a non-zero scalar, ans hence the hypersurface {det V = 0} ⊂ Λ must coincide with this union of hyperplanes. Since span(p_{0}, p_{1}, …, p̂_{i}, …, p_{n−1}) is the zero-locus of

λ_{n−i} = v_{0} + ϵ^{−i}v_{1} + ⋯ + ϵ^{−i(n−1)}v_{n−1},

we deduce that det(V) factors as in the statement of Theorem 1.

A similar but slightly more involved argument shows that for all k ∈ {2, …, n}, the ideal of k ×k-minors of the generic circulant matrix V = circ{v_{0}, v_{1}, …, v_{n−1}} defines the (reduced) union of (k − 2)-planes

⋃_{i_{1},i_{2},...,i_{k−1}∈{0,...,n−1}} span(p_{i_{1}}, p_{i_{2}}, …, p_{i_{k−1}})

(in contrast with case of the generic catalecticant matrix, where all ideals of minors are prime).

References

[1] P.J. Davis, Circulant Matrices, John Wiley and Sons, 1979.

[2] D. Eisenbud, Linear Sections of Determinantal Varieties, Amer. J. Math. 110 (1988), 541–575.

[3] H.M. Farkas and I. Kra, Theta Constants, Riemann Surfaces and the Modular Group, Graduate Studies in Mathematics, vol. 37, American Mathematical Society, 2001.

[4] P.A. Fuhrmann, A Polynomial Approach to Linear Algebra, Universitext, Springer, 1996.

[5] D. Kalman and J.E. White, Polynomial equations and circulant matrrices, Amer. Math. Monthly 108 (2001), 821–840.

[6] G.J. Koehler, Those Pesky No Free Lunch Theorems for Optimization, preprint 2004.

[7] I. Kra, Product identities for θ-constants and θ-constant derivatives, in preparation.

[8] H.R. Parks & D.C. Wills, An Elementary Calculation of the Dihedral Angle of the Regular n-Simplex, Amer. Math. Monthly 109 (2002), 756-758.

State University of New York at Stony Brook Stony Brook, NY 11794