Fredman’s reciprocity, invariants of abelian groups, and the permanent of the Cayley table

DOI 10.1007/s10801-010-0236-6

Fredman’s reciprocity, invariants of abelian groups, and the permanent of the Cayley table

Dmitri I. Panyushev

Received: 18 September 2009 / Accepted: 12 May 2010 / Published online: 4 June 2010

© Springer Science+Business Media, LLC 2010

Abstract Let Rbe the regular representation of a finite abelian group Gand let Cndenote the cyclic group of ordern. ForG=Cn, we compute the Poincaré series of allCn-isotypic components inS^·R⊗ ∧^·R(the symmetric tensor exterior algebra ofR). From this we derive a general reciprocity and some number-theoretic identities.

This generalises results of Fredman and Elashvili–Jibladze. Then we consider the Cayley table,MG, ofGand some generalisations of it. In particular, we prove that the number of formally different terms in the permanent ofMGequals(SⁿR)^G, wheren is the order ofG.

Keywords Molien formula·Poincaré series·Permanent·Ramanujan’s sum

1 Introduction

In the beginning of the 1970s, Fredman [7] considered the problem of computing the number of vectors(λ₀, λ₁, . . . , λ_n−1)with non-negative integer components that satisfy

λ0+ · · · +λn−1=m and

n−1

j=0

j λj≡imodn. (1.1) He denoted this number by S(n, m, i). Using generating functions, Fredman ob- tained an explicit formula forS(n, m, i), which immediately showed thatS(n, m, i)= S(m, n, i). The latter is said to be Fredman’s reciprocity. Using a necklace interpre- tation, he also constructed a bijection between the vectors enumerated byS(n, m, i)

D.I. Panyushev (

Independent University of Moscow, Bol’shoi Vlasevskii per. 11, 119002 Moscow, Russia e-mail:[email protected]

and those enumerated byS(m, n, i). However, these results did not attract attention and remained unnoticed.

Later, Elashvili and Jibladze [4,5] (partly with Pataraia [6]) rediscovered these results using Invariant Theory. LetCnZ/nZbe the cyclic group of ordernandR the space of its regular representation overC. Choose a basis(v0, v1, . . . , vn−1)for Rconsisting ofCn-eigenvectors. More precisely, ifγ∈Cnis a generator andζ=√ⁿ

1 a fixed primitive root of unity, thenγ·vi =ζⁱvi. Write χi for the linear character Cn→C^× that takesγ toζⁱ. The monomialv₀^λ1· · ·v_n−^λn−1₁ has degreemand weight χi if and only if(λ0, λ1, . . . , λn−1)satisfies (1.1). Thus,S(n, m, i)is the dimension of the space ofCn-semi-invariants of weightχ_i in themth symmetric powerS^mR.

This space can also be understood as theCn-isotypic component of typeχ_i inS^mR, denoted by(S^mR)_Cn,χi. To stress the connection with cyclic groups, we will write a_i(Cn, m) in place of S(n, m, i). The celebrated Molien formula provides a closed expression for the generating function (Poincaré series)

F

(S^·R)_Cn,χi;t

= ∞ m=0

a_i(Cn, m)t^m, where(S^·R)_Cn,χi =

m≥0(S^mR)_Cn,χi is the(Cn, χi)-isotypic component in S^·R. Then extracting the coefficient oft^m yields a formula fora_i(Cn, m), see (2.2). It is worth stressing that Molien’s formula is a very efficient tool that provides a uniform approach to various combinatorial problems and paves the way for further generali- sations; see, e.g. [12].

In this note, we elaborate on two topics. First, generalising results of Fredman and Elashvili–Jibladze, we compute the Poincaré series for eachCn-isotypic component in the bi-graded algebraS^·R⊗ ∧^·Rand then dim(S^pR⊗ ∧^mR)_Cn,χi for allp, m, i (Theorem3.2). From this we derive a more general reciprocity, see (3.5). As a by- product of these computations, we obtain some interesting identities, e.g.

exp z

1−z²

=^∞

d=1

1+z^dϕ(d)/d

,

whereϕ is Euler’s totient function. In Sect.4, several identities related to isotypic components in∧^·Rare given; some of them are valid for an arbitrary finite abelian groupG, see Theorem4.4. Second, in Sect.5, we study some properties of the Cay- ley table,MG, ofG. IfG= {x0, x1, . . . , xn−1}, thenMG can be regarded asn by nmatrix with entries inC[x₀, . . . , x_n−1] S^·R. ForG=Cn,MG is nothing but a generic circulant matrix. The permanent ofMG, per(MG), is a sum of monomials in x_i’s of degreen. Using [8], we prove that the number of different monomials occur- ring in this sum equals dim(SⁿR)^G. Then we introduce the extended Cayley table, MG (which is a matrix of ordern+1), and characterise the monomials occurring in per( MG)(Theorem5.8). This characterisation implies that the number of different monomials in per(MG)equals dim(Sⁿ⁺¹R)^G. Both per(MG)and det(MG)belong to SⁿR, and we prove that per(MG)isG-invariant, whereas det(MG)is a semi-invariant whose weight is the sum of all elements of the dual groupG. The latter means thatˆ in many cases det(MG)is invariant, too. In Sect.6, we discuss some open problems related to(S^·R)^Gand per(MG).

Notation #(M)is the cardinality of a finite set M; (n, m)is the greatest common divisor ofn, m∈N;Gis always a finite group.

2 Preliminaries 2.1 Ramanujan’s sums

Two important number-theoretic functions are Euler’s totient function ϕ and the Möbius functionμ. Recall that ϕ(n) is the number of all primitive roots of unity of ordern. Giveni, n∈N,n≥1, the Ramanujan’s sum,c_n(i), is the sum ofith pow- ers of the primitive roots of unity of ordern. In particular,cn(0)=ϕ(n). There are two useful expressions for Ramanujan’s sums:

c_n(i)=

d|(n,i)

μ n

d

d, c_n(i)= ϕ(n) ϕ(_(n,i)ⁿ )·μ

n (n, i)

,

see [9, Theorems 271 and 272]. These formulae also show thatcn(1)=μ(n),cn(i)= c_n(n−i), andc_n(i)is always a rational integer.

2.2 Molien’s formula for the symmetric algebra

LetGbe a finite group andV a finite-dimensionalG-module. The original Molien formula computes the Poincaré series of the graded algebra of invariants(S^·V )^G=

m≥0(S^mV )^G. More generally, there is a similar formula for the Poincaré series of anyG-isotypic component inS^·V. Letχ be an irreducible representation ofGand (S^·V )G,χthe isotypic component of typeχinS^·V. By definition, the Poincaré series of(S^·V )_G,χ is the power seriesF((S^·V )_G,χ;t ):=

m≥0dim((S^mV )_G,χ)t^m. Then F

(S^·V )_G,χ;t

=deg(χ )

#(G)

γ∈G

tr(χ (γ⁻¹)) detV(1−t γ ),

see, e.g. [12, Theorem 2.1]. Here 1 is the identity matrix in GL(V ). (The alge- bra of invariants corresponds to the trivial one-dimensional representation, i.e., if deg(χ )=1 andχ (γ )=1 for allγ∈G.)

Let R be the space of the regular representation of G. For the G-module R, Molien’s formula can be presented in a somewhat simpler form.

Proposition 2.1 [2, V.1.8] Letϕ_G(d)be the number of elements of order d inG.

Then

F

(S^·R)^G;t

= 1

#(G)

d≥1

ϕ_G(d) (1−t^d)^(#G)/d.

This can easily be extended to an arbitraryχ. If^ord(γ )is the order ofγ∈G, then F

(S^·R)_G,χ;t

=deg(χ )

#(G)

d|#G

γ:^ord(γ )=dtr(χ (γ⁻¹))

(1−t^d)^(#G)/d . (2.1) In fact, we prove below a more general formula (Lemma3.1).

2.3 Formulae of Fredman and Elashvili–Jibladze

Recall thata_i(Cn, m)=dimS^m(R)_Cn,χi or, equivalently, it is the number of vectors satisfying (1.1). In particular,a₀(Cn, m)=dimS^m(R)^Cn. If the elements ofCn are regarded as the roots of unity of ordern, thenχi is the characterξ →ξⁱ, ξ ∈Cn. Hereϕ_Cn(d)is almost Euler’s totient function. That is,ϕ_Cn(d)=ϕ(d), ifd|n; and ϕ_Cn(d)=0 otherwise. Using (2.1) withG=Cnandχ=χ_i, we see that deg(χi)=1 and

γ:^ord(γ )=dχ_i(γ⁻¹)=c_d(d−i). Then extracting the coefficient oft^myields a nice-looking formula (Fredman [7], Elashvili–Jibladze [5])

a_i(Cn, m)= 1 n+m

d|(n,m)

c_d(i)

n/d+m/d n/d

. (2.2)

Remark 2.2 Both Fredman’s approach, see (1.1), and cyclic group interpretation pre- suppose thata_i(Cn, m)is defined forn≥1 andm≥0. But (2.2) shows thata_i(Cn, m) is naturally defined for(n, m)∈N²,(n, m)=(0,0).

It follows from (2.2) thata_i(Cn, m)=a_i(Cm, n). In [4–6], this equality is named the “Hermite reciprocity”. As it has no relation to Hermite and was first proved by Fredman, the term Fredman’s reciprocity seems to be more appropriate.

From (2.2), one can derive the equality

(n,m)∈N², (n,m)=(0,0)

a_i(Cn, m)xⁿy^m= −^∞

d=1

cd(i) d log

1−x^d−y^d

. (2.3)

(Cf. [4, Remark 2], [6, Sect. 4].)

3 Symmetric tensor exterior algebra and Poincaré series

As above, letV be aG-module. We consider the Poincaré series of theG-isotypic components inS^·V⊗ ∧^·V. Let(S^·V⊗ ∧^·V )_G,χ denote the isotypic component cor- responding to an irreducible representationχ. It is a bi-graded vector space and its Poincaré series is the formal power series

F

(S^·V ⊗ ∧^·V )_G,χ;s, t

=

p,m≥0

dim

S^pV ⊗ ∧^mV

G,χs^pt^m.

(Clearly, it is a polynomial with respect tot.) It is known that F

(S^·V ⊗ ∧^·V )^G;s, t

= 1

#G

γ∈G

detV(1+t γ ) detV(1−sγ ),

see [1, Theorem 1.33]. A similar argument provides the formula for an arbitrary G-isotypic component:

F

(S^·V ⊗ ∧^·V )_G,χ;s, t

=deg(χ )

#G

γ∈G

tr χ

γ⁻¹detV(1+t γ )

detV(1−sγ ). (3.1)

For, in place of the Reynolds operator_#(G)¹

γ∈Gγ (the projection to the subspace ofG-invariants), one should merely exploit the operator ^{deg(χ )}_#(G)

γ∈Gtr(χ (γ⁻¹))γ (the projection to the isotypic component of typeχ).

Lemma 3.1 For the regular representationRofG, the right-hand side of (3.1) can be written as

deg(χ )

#G

d≥1 γ:^ord(γ )=d

tr χ

γ⁻¹

·

1−(−t )^d 1−s^d

(#G)/d .

Proof Ifγ∈Gis of orderd, thenγ Cdand each coset ofγinGis a cycle of lengthd with respect to the multiplication byγ. Hence, in a suitable basis ofR, the matrix ofγ inGL(R)consists of(#G)/ddiagonal blocks

⎛

⎜⎜

⎜⎜

⎜⎜

⎜⎝

0 1 0 . . . 0 0 0 1 . .. 0 0 0 . .. . .. 0 0 0 . .. . .. 1 1 0 0 . . . 0

⎞

⎟⎟

⎟⎟

⎟⎟

⎟⎠

of sized. Since

det

⎡

⎢⎢

⎢⎢

⎢⎢

⎢⎣

1 −s 0 . . . 0 0 1 −s . .. 0 0 0 . .. . .. 0 0 0 . .. . .. −s

−s 0 0 . . . 1

⎤

⎥⎥

⎥⎥

⎥⎥

⎥⎦

=1−s^d,

we obtain^det_det^{R(1+t γ )}

R(1−sγ )=(^{1−(−t )d)}

1−s^d )^(#G)/d, which proves the lemma.

Now, we apply this lemma to the regular representation of Cn. Recall that the number_a+b+c

a, b, c

is defined to be ^(a_a⁺_!^b_b⁺_!c^c)_!^!.

Theorem 3.2 The Poincaré series of the(Cn, χ_i)-isotypic component equals F

(S^·R⊗ ∧^·R)_Cn,χi;s, t

=1 n

d|n

cd(i)(1−(−t )^d)^n/d (1−s^d)^n/d

=1 n

d|n

c_d(i) _n/d

a=0

(−1)^(d+1)a n/d

a

t^ad

b≥0

(n/d)+b−1 (n/d)−1

s^bd

. (3.2)

Consequently, dim

S^pR⊗ ∧^mR

Cn,χ_i=(−1)^m p+n

d|n,p,m

(−1)^m/dc_d(i)

(n+p)/d m/d, p/d, (n−m)/d

.

(3.3) Proof This is a straightforward consequence of Lemma 3.1. If G =Cn, then deg(χi)=1 and

γ:^ord(γ )=dχ_i(γ⁻¹)=c_d(n−i)=c_d(i), which proves (3.2).

We leave it to the reader to extract the coefficient of t^ms^p in (3.2) and ob-

tain (3.3).

Lettingn=q+myields a more symmetric form of (3.3):

dim

S^pR⊗ ∧^mR

Cq+m,χi= (−1)^m p+q+m

d|p,q,m

(−1)^m/dc_d(i)

(m+p+q)/d m/d, p/d, q/d

.

(3.4) As the right-hand side is symmetric with respect topandq, we get an equality for dimensions of isotypic components related to the regular representations of two cyclic groups,(Cq+m,R)and(Cp+m,R˜):

dim

S^pR⊗ ∧^mR

Cq+m,χ_i=dim

S^qR˜ ⊗ ∧^mR˜

Cp+m,χ_i. (3.5) Form=0, this simplifies to Fredman’s reciprocity [7, (4)]. It would be interesting to have a combinatorial interpretation of this symmetry in the spirit of Fredman’s approach.

Remark 3.3

(1) Lettingt=0 in (3.2) orm=0 in (3.3), we get known formulae for the isotypic components in the symmetric algebra ofR, see [4,5]. Lettings=0 in (3.2) or n=0 in (3.3), we get interesting formulae for the isotypic components in the exterior algebra ofR, see the next section.

(2) Ifd is always odd (e.g. at least one ofm, p, q is odd), then(−1)^m+md =1 and the right-hand side of (3.4) becomes totally symmetric with respect top, q, m.

The following is a generalisation of (2.3):

Proposition 3.4

(p,q,m)∈N³, p+q+m≥1

dim

S^pR⊗ ∧^mR

Cq+m,χi·x^py^qz^m

= − ∞ d=1

c_d(i) d log

1−x^d−y^d+(−z)^d .

Proof By (3.4), the left-hand side equals

p+q+m≥1

(−1)^m p+q+m

d|p,q,m

(−1)^m/dc_d(i)

(p+q+m)/d p/d, q/d, m/d

x^py^qz^m.

Lettingp/d=α,q/d=β,m/d=γ, we rewrite it as ∞

d=1

c_d(i) d

α+β+γ≥1

(−1)^γ α+β+γ

α+β+γ α, β, γ

x^αdy^βd(−z)^{γ d}

= ∞ d=1

c_d(i) d

k≥1 α+β+γ=k

1 k

k α, β, γ

(x^d)^α(y^d)^β

−(−z)^dγ

=^∞

d=1

c_d(i) d

k≥1

(x^d+y^d−(−z)^d)^k

k = −^∞

d=1

c_d(i) d log

1−x^d−y^d+(−z)^d .

Specialising the equality of Proposition3.4, we get some interesting identities.

(A) Takingx =y =0 forces p=q=0 on the left-hand side, which leads to the equality

m≥1

dim

∧^mR

Cm,χ_iz^m= −^∞

d=1

cd(i) d log

1+(−z)^d .

Fori=0, we have

cd(0)=ϕ(d) and dim

∧^mR_Cm

=

1 modd;

0 meven.

That is, ₁₋^z

z² = −_∞

d=1 ϕ(d)

d log(1+(−z)^d).Replacingzwith−zand expo- nentiating, we finally obtain:

exp z

1−z²

=

d≥1

1+z^dϕ(d)/d

.

(B) Likewise, forx=z=0 (or justx=0 in (2.3)), we get

−^∞

d=1

c_d(i) d log

1−y^d

=

y/(1−y) i=0;

0 i=0.

In particular,

exp −y

1−y

=

d≥1

1−y^dϕ(d)/d

.

4 On the exterior algebra of the regular representation

In case of the exterior algebra of a G-module, the Poincaré series of an isotypic component is actually a polynomial int, which can be evaluated for anyt. Here we gather some practical formulae for the regular representations and for cyclic groups.

First, using (3.1) and Lemma3.1with trivialχands=0, we obtain F

(∧^·R)^G;t

= 1

#(G)

d≥1

ϕ_G(d)

1−(−t )^d#(G)/d

.

It follows thatF((∧^·R)^G;t )always has the factor 1+tand dim(∧^·R)^G= 1

#(G)

dodd

ϕ_G(d)2^#(G)/d. (4.1)

Note that hereGis not necessarily abelian!

Example 4.1 ForG=S3, we haveϕ_G(1)=1,ϕ_G(2)=3, andϕ_G(3)=2. Therefore, F

(∧^·R)^S3;t

=1 6

(1+t )⁶+3 1−t²3

+2

1+t³2

=1+t+t²+4t³+4t⁴+t⁵. ForG=Cn, there are precise assertions for all G-isotypic components in ∧^·R. Using Theorem3.2withs=0 andp=0, we obtain

F

(∧^·R)_Cn,χi;t

=1 n

d|n

cd(i)

1−(−t )^d_n/d

, (4.2)

dim

∧^mR

Cⁿ,χ_i

=(−1)^m n

d|n,m

(−1)^m/dc_d(i) n/d

m/d

=:b_i(Cn, m). (4.3)

Again, it is convenient to replacenwithq+min (4.3). Then b_i(Cq+m, m)=dim

∧^mR

Cq+m,χi

=(−1)^m q+m

d|q,m

(−1)^m/dc_d(i)

q/d+m/d m/d

.

From this we derive the following observation:

Proposition 4.2 If q or m is odd, then bi(Cq+m, m) = ai(Cq, m) and also bi(Cq+m, m)=bi(Cq+m, q).

Example 4.3 b_i(C2n−1, n−1)=a_i(Cn−1, n), and it is the(n−1)th Catalan number regardless ofi.

Remark Ifnis odd, then∧ⁿRis the trivialCn-module, and therefore∧^mR ∧^n−mR asCn-modules. This “explains” the equalitybi(Cn, m)=bi(Cn, n−m)fornodd.

Substitutingt=1 in (4.2) yields a nice formula for dimension of the whole iso- typic component:

dim

(∧^·R)_Cn,χi

=1 n

d|n, dodd

c_d(i)2^n/d. (4.4)

Fori=0, this becomes a special case of (4.1). There is a down-to-earth interpretation of (4.4) that does not invoke Invariant Theory. As in the introduction, choose a basis {v0, v1, . . . , vn−1}forRsuch thatvi has weightχi. Then

v_j1∧ · · · ∧v_jm∈

∧^mR

Cn,χi ⇐⇒ j₁+ · · · +j_m≡imodn.

Consequently, dim(∧^·R)_Cn,χiequals the number of subsetsJ⊂ {0,1, . . . , n−1}such that |J| ≡i mod n. (Here |J| stands for the sum of elements of J.) Hence our invariant-theoretic approach proves the following purely combinatorial fact:

#

J⊂ {0,1, . . . , n−1} | |J| ≡imodn

=1 n

d|n, dodd

c_d(i)2^n/d.

Fori=0, this is nothing but the number of subsets ofCn summing to the neutral element (in the additive notation). We provide a similar interpretation for any abelian group.

Theorem 4.4 For an abelian group G, let NG denote the number of subsets S of G such that |S| :=

γ∈Sγ =0∈ G. Then NG =dim(∧^·R)^G = _#(G)¹ ×

doddϕG(d)2^#(G)/d.

Proof In view of (4.1), only the first equality requires a proof. Let(z0, . . . , zn−1)be a basis forRconsisting ofG-eigenvectors,n=#(G). Here the weight ofziis a linear characterχ_i andGˆ = {χ₀, χ₁, . . . , χ_n−1}is the dual group ofG. One of theχ_i’s is the neutral element ofG, denoted byˆ 0 in the additive notation. Thenˆ

zj₁∧ · · · ∧zj_m∈

∧^mRG

⇐⇒ χj₁+ · · · +χj_m= ˆ0∈ ˆG.

Thus, dim(∧^·R)^G equals the number of subsets of Gˆ summing to0. However, theˆ groupsGˆ andG are (non-canonically) isomorphic, hence NG=N_Gˆ and we are

done.

5 On the permanent of the Cayley table of an abelian group

In this section,Gis an abelian group,G= {x₀, x₁, . . . , x_n−1}. The Cayley table ofG, denotedMG=(m_i,j), can be regarded asnbynmatrix with entries in the polynomial ringC[x0, x1, . . . , x_n−1] S^·R. To distinguish the addition in C[x0, x1, . . . , x_n−1] and the group operation in G, the latter is denoted by ‘’. By definition,mi,j = xi xj,i, j =0, . . . , n−1. HenceMG is a symmetric matrix. The permanent of MG, per(MG), is a homogeneous polynomial of degreen inx_i’s, and it does not depend on the ordering of elements ofG. Letp(G)denote the number of formally different monomials occurring in per(MG).

Remark 5.1 In place of the Cayley table, one can consider the matrixMˆGwith entries ˆ

m_i,j =x_ix_j(the difference inG). Clearly,MˆGis obtained fromMGby rearrang- ing the columns only (or, the rows only), using the permutation onGthat takes each

element to its inverse. Therefore, per(MˆG)=per(MG)and det(MˆG)= ±det(MG).

AlthoughMˆG is not symmetric in general, an advantage is that every entry on the main diagonal is the neutral elements ofG.

Example 5.2 ForG=Cnand the natural ordering of its elements (i.e., whenx_icorre- sponds toi), one obtains a generic circulant matrix (the latter means that the rows are successive cyclic permutations of the first row). More precisely,M_Cn (resp.,Mˆ_Cn) is a circulant matrix in Hankel (resp., Toeplitz) form. For instance,

M_C3=

⎛

⎝x0 x1 x2

x1 x2 x0

x2 x0 x1

⎞

⎠.

Here per(M_C3)=x₀³+x₁³+x₂³+3x0x1x2. Therefore,p(C3)=4.

The functionn→p(Cn)was studied in [3] where it was pointed out that the main result of Hall [8] shows thatp(Cn)equals the number of solutions to

λ0+ · · · +λ_n−1=n, _n−1

j=0j λj≡0 modn.

That is,p(Cn)=a0(Cn, n)in our notation. Because results of [8] apply to arbitrary finite abelian groups, one can be interested in p(G) in this more general setting.

Below, we give an invariant-theoretic answer using that result of Hall.

LetSndenote the symmetric group acting by permutations on{0,1, . . . , n−1}.

Accordingly,Snpermutes the elements ofGby the ruleπ(x_i):=x_π(i). Recall that per(mi,j)=

π∈Sn

n−1 i=0

mi,π(i).

For the matrixMG,

n−1 i=0

m_i,π(i)=

n−1 i=0

(x_ix_π(i))=

n−1

i=0

x_i^{ki(π )}=:x(π )

is a monomial inxi’s of degreen. Note that different permutations may result in the same monomial. The following is essentially proved by M. Hall.

Theorem 5.3 [8, n. 3] A monomialm=_n−1

i=0x_i^ki is of the form x(π ) for some π ∈ Sn (i.e., occurs in per(MG)) if and only if

iki =n and k0x0· · · kn−1xn−1=0∈G. [Of course, herekixistands forxi· · ·xi (ki times).]

The necessity of the conditions is easy; a non-trivial argument is required for the sufficiency, i.e., for the existence ofπ.

Theorem 5.4 p(G)=dimSⁿ(R)^G.

Proof Let(z₀, . . . , z_n−1)be a basis forRconsisting ofG-eigenvectors. Recall that the weight of zi is χi and Gˆ = {χ0, . . . , χn−1}is the dual group. The monomial z^k₀⁰· · ·z^k_n−ⁿ⁻₁¹ ∈S^·Ris a semi-invariant of Gof weightk₀χ₀· · ·k_n−1χ_n−1∈ ˆG.

It follows that dimSⁿ(R)^G=

(k0, . . . , k_n−1)

i

k_i=nandk0χ0· · ·k_n−1χ_n−1= ˆ0

.

Modulo the passage from G toG, these conditions coincide with those of Theo-ˆ

rem5.3. SinceG ˆG, we are done.

Our next goal is to extend these results to a certain matrix of ordern+1. We begin with two assertions on per(MG)which are of independent interest.

Proposition 5.5 There is a natural action∗ :G×Sn→Snsuch that, forγ∈Gand π∈Sn, sign(γ∗π )=sign(π )andx(γ∗π )=x(π ).

Proof Everyγ ∈Gdetermines a permutationσ_γ onGand thereby an element ofSn. Namely,

(x₀, . . . , x_n−1) →^σγ (γx₀, . . . , γx_n−1).

Equivalently,xσ_γ(i)=xiγ. Define theG-action onSn byγ∗π=σγπ σγ. Hence sign(γ∗π )=sign(π ). Recall thatx(π )=_n−1

i=0(xixπ(i)). Then x(γ∗π )=

n−1 i=0

(x_ix_{σγπ σγ(i)})=

n−1 j=0

(x_σ−1

γ (j )x_{σγπ(j )}), wherej=σγ(i). By definition,x_{σγπ(j )}=x_{π(j )}γ andxj=x_σ−1

γ (j )γ. Thus, the

linear factors ofx(γ∗π )remain the same.

Remark 5.6 Our action ‘∗’ can be regarded as a generalisation of Lehmer’s “operator S” for circulant matrices [11, p. 45], i.e., essentially, forG=Cn. Using that operator Lehmer proved that, forn=podd prime,

det(M_Cp)=x₀^p+ · · · +x_p^p₋₁+pF (x0, . . . , xp−1),

whereF ∈Z[x₀, . . . , x_p−1]. We note that Lehmer’s argument applies to per(M_Cp)as well.

Proposition 5.7 Suppose thatmis a monomial in per(MG)such thatxkoccurs inm.

Ifx_k=x_ix_j for somei, j, then there isσ∈Snsuch thatσ (i)=j andm=x(σ ).

Proof By the assumption on m, there is a π ∈Sn such that m=x(π )and x_k = x_αx_β for someα, β withπ(α)=β. If{α, β} = {i, j}, then we have to correctπ. Takeγ∈Gsuch thatx_iγ=x_α. Thenx_βγ=x_j and forσ =γ∗πwe have

σ (x_i)=σ_γπ σ_γ(x_i)=σ_γπ(x_α)=σ_γ(x_β)=x_βγ=x_j.

Thus,σ (i)=j and alsox(σ )=x(π )in view of Proposition5.5.

The Cayley table ofG is the “addition table” of all elements of G. Define the extended Cayley table as ann+1 byn+1 matrix that the “addition table” ofn+1 el- ements ofG, with the neutral element is taken twice. More precisely, we assume that x₀=x_n=0 is the neutral element ofGand consider the matrixMG=(m_i,j), where m_i,j =x_i x_j,i, j =0,1, . . . , n. In this context,Sn+1 is regarded as permutation group on{0,1, . . . , n}. Then per(MG)=

˜

π∈Sn+1x(π )˜ is a sum of monomials of degreen+1.

Example

M_C3=

⎛

⎜⎜

⎝

x0 x1 x2 x0

x1 x2 x0 x1

x2 x0 x1 x2

x0 x1 x2 x0

⎞

⎟⎟

⎠,

per(M_C3)=2x₀⁴+10x²₀x1x2+4x0x₁³+4x0x³₂+4x₁²x₂². Theorem 5.8 The monomialm=_n−1

i=0x_i^ki occurs in per(MG)if and only if

i

k_i=n+1 and k₀x₀· · ·k_n−1x_n−1=0∈G.

Proof “⇒”. Supposem=x(π )˜ for someπ˜∈Sn+1. Obviously, degm=n+1. Next, k₀x₀· · ·k_n−1x_n−1=(x₀x_{π (0)˜} )(x₁x_{π (1)˜} )· · ·(x_nx_{π (n)˜} )=0, since the multiset{x0, x1, . . . , xn−1, xn=x0}is closed with respect to taking inverses.

“⇐”. Supposemsatisfies the conditions of the theorem.

• k₀>0. Take m=x₀^k0−1x₁^k1· · ·x_n−^kn−₁¹. Then m satisfies the conditions of Theo- rem5.3. Therefore,mis a monomial of per(MG)and there is aπ∈Snsuch that m=x(π ). EmbedSnintoSn+1as the subgroup preserving the last elementn. Let

˜

πdenoteπconsidered as an element ofSn+1. Thenm=x(π ).˜

• k0=0. Choose any binomialx_ix_j inm and replace it with(x_ix_j)x0=x_kx0

(i.e.,xixj=xk). That is,m=mxixj is replaced withmxkx0=:mx0. By the previous argument, we can findπ ∈Sn such thatm=x(π )andmx₀=x(π ).˜ Sincex_k=x_ix_j occurs inx(π ), we can apply Proposition5.7and assume that π(i)=j and henceπ (i)˜ =j. Finally, we replaceπ˜ withπ τ˜ , where the transposi- tionτ∈Sn+1permutesiandn. One readily verifies thatx(π τ )˜ =mxixj=m.

Corollary 5.9 The number of different monomials in per( MG)equals dim(Sⁿ⁺¹R)^G.

The proof is almost identical to that of Theorem5.4and left to the reader.

It follows from Frobenius’ theory of group determinants (see, e.g. [10, Sect. 2]) that, for abelian groups, det(MG) is the product of linear forms in xi’s. In case of generic circulant matrices, this fact plays an important role in [11,13]. For fu- ture use, we provide a quick derivation. Recall that G= {x₀, x₁, . . . , x_n−1} and

Gˆ = {χ₀, χ₁, . . . , χ_n−1}. Consider thenbyncomplex matrixKG, with(KG)_i,j = (χj(xi)), and the vectorsvj=_n−1

i=0χj(xi)xi∈R,j=0,1, . . . , n−1.

Proposition 5.10 Under the above notation, we have:

(1) v_j is an eigenvector ofGcorresponding to the weightχ_j⁻¹;

(2) det(MG)·det(KG)=det(KG)v0v1· · ·vn−1, where ‘bar’ stands for the complex conjugation;

(3) det(KG)/det(KG)equals the sign of the permutationπ0∈Snthat takes eachxi

to its inverse. Hence det(MG)=sign(π0)v₀v₁· · ·v_n−1. Proof

(1) Obvious.

(2) It is easily seen that(MG·KG)_ij=χ_j(x_i)⁻¹v_j=χ_j(x_i)v_j=(KG)_i,jv_j. (3) Assuming thatx0is the neutral element, compare the coefficient ofx₀ⁿ in both

parts of the equality in (2).

Note thatMGhas equal columns and hence det(MG)=0.

Remark 5.11

1. The set of vectors{v_j}is closed with respect to complex conjugation, and letting zj=vj=

iχj(xi)xi one obtains the eigenvector corresponding toχj.

2. The orthogonality relations for the characters imply thatKG(KG)^t=n1n; that is,

√1

nKGis unitary and|det(KG)|²=nⁿ.

For the sake of completeness, we mention some other easy properties.

Proposition 5.12 Supposeγ∈Gandπ∈Sn.

(1) γ·x(π )=x(π σ_γ⁻¹), where ‘·’ stands for the naturalG-action onSⁿR;

(2) x(π )=x(π⁻¹);

(3) per(MG)∈(SⁿR)^G;

(4) IfGˆ has a unique element of order 2, sayψ, then det(MG)is a semi-invariant of weightψ. In all other cases, det(MG)∈(SⁿR)^G.

Proof

(1) γ·x(π )=γ·_n−1

i=0(x_ix_π(i))=_n−1

i=0(x_ix_π(i)γ )=_n−1

i=0(x_σγ(i)x_π(i))= x(π σ_γ⁻¹).

(2) Obvious.

(3) Follows from (1).

(4) Proposition5.10shows that det(MG)is a semi-invariant whose weight equals the sum of all elements ofG. The sum of all elements of an abelian group is knownˆ to be the neutral element unless the group has a unique element of order 2, in

which case the sum is this unique element.

Note that per( MG)is an element ofSⁿ⁺¹R, but it does not belong to(Sⁿ⁺¹R)^G.