Bounds for codes and designs in complex subspaces

DOI 10.1007/s10801-009-0170-7

Bounds for codes and designs in complex subspaces

Aidan Roy

Received: 19 July 2008 / Accepted: 11 February 2009 / Published online: 27 February 2009

© Springer Science+Business Media, LLC 2009

Abstract We introduce the concepts of complex Grassmannian codes and designs.

LetGm,ndenote the set ofm-dimensional subspaces ofCⁿ: then a code is a finite subset ofGm,nin which few distances occur, while a design is a finite subset ofGm,n

that polynomially approximates the entire set. Using Delsarte’s linear programming techniques, we find upper bounds for the size of a code and lower bounds for the size of a design, and we show that association schemes can occur when the bounds are tight. These results are motivated by the bounds for real subspaces recently found by Bachoc, Bannai, Coulangeon and Nebe, and the bounds generalize those of Delsarte, Goethals and Seidel for codes and designs on the complex unit sphere.

Keywords Codes·Designs·Bounds·Grassmannian spaces·Complex subspaces· Linear programming·Delsarte·Association schemes

1 Introduction

In this paper, we introduce the concept of complex Grassmannian codes and designs:

codes and designs in the collection of fixed-rank subspaces of a complex vector space.

In the 1970’s, Delsarte [11] developed a series of excellent bounds for certain error-correcting codes by treating codewords as points in an association scheme and then applying linear programming. Shortly thereafter, Delsarte, Goethals and Sei- del [12] showed that the same technique could also be used on systems of points on the real or complex unit sphere, which they called spherical codes and spheri- cal designs; this resulted in important contributions to problems in sphere-packing

A. Roy (

Institute for Quantum Information Science & Department of Mathematics and Statistics, University of Calgary, Calgary, Alberta T2N 1N4, Canada

e-mail:[email protected]

[10, Chapter 9]. This linear programming technique, which is now known as “Del- sarte LP theory”, has proved surprisingly portable. Recently, Bachoc, Coulangeon and Nebe [4] and Bachoc, Bannai and Coulangeon [3] generalized the results of Del- sarte, Goethals and Seidel to real Grassmannian spaces, and Bachoc [2] pointed out that “the same game” can be played over the complex numbers. In this paper, we investigate more closely the case of complex Grassmannian codes.

The motivation for studying complex Grassmannians comes from the theory of quantum measurements. Roughly speaking, any complex Grassmannian 1-design (or any complex projective 1-design) defines a projective measurement in the theory of quantum mechanics [23, Section 2.2.6]. It has recently been discovered that complex projective 2-designs correspond to quantum measurements that are optimal for the purposes of nonadaptive quantum state tomography [26]. In fact, this is also true in the more general Grassmannian setting: complex Grassmannian 2-designs are the optimal choices of measurements for nonadaptive quantum state tomography when the observer only has access to measurements with a restricted number of outcomes.

More details will appear in a paper by Godsil, Rötteler, and the author [15]. Complex Grassmannians also play a role in certain wireless communication protocols [1].

DefineGm,nto be the set ofm-dimensional subspaces of ann-dimensional com- plex vector space. Without loss of generality, we always assumem≤n/2. Usually, we represent a subspacea by itsn×nprojection matrixP_a. The inner product on Gm,nis the trace inner product for projection matrices:

a, b :=tr(P_a^∗P_b)

=tr(PaP_b).

Sincea, b = b, a, the inner product is real. This is a measure of separation, or distance, between two subspaces—note that is not a distance metric per se: the in- ner product ofPawith itself is maximal rather than minimal. However, the chordal distance [9], defined by

d_c(a, b):=

m−tr(PaP_b),

is a monotonic function of the inner product. Given a finite set of inner product values A, anA-code is a subsetSofGm,nsuch that

A= {tr(PaP_b):a, b∈S, a=b}.

An s-distance set is an A-code with |A| =s. This generalizes the concept of an s-distance set on the complex unit sphere: ifuandvare unit vectors, then the distance betweenuandvon the unit sphere is a function of

u^∗v²=tr(uu^∗vv^∗).

We are interested in codes of maximal size for a fixedAors, and bounds on their size based on zonal polynomials. Table1in Section6gives a summary of the bounds for small|A|.

The outline of this paper is as follows. In Section2, we describe the orbits of pairs of subspaces inGm,nunder the action ofU (n): these orbits play a significant role in the bounds derived later on. In Sections3,4and5, we develop the necessary repre- sentation theory background needed for our LP bounds. In particular, we discuss the decomposition of the square-integrable functions onGm,ninto irreducible representa- tions ofU (n), and the zonal polynomials for these representations. The results in this section are all known, and the development is quite similar to that of Bachoc, Coulan- geon and Nebe for real Grassmannians. In fact, the complex case is actually easier than the real case, because representations of the unitary groupU (n)are easier to describe than representations of the orthogonal groupO(n). In Section6, we develop absolute and relative bounds forA-codes and for a more general type of code called anf-code. These bounds forGm,n reduce to known bounds for complex spherical codes whenm=1. We compare the bounds to other known bounds for subspaces in Section7, and in Section 8, we give examples in which the bounds are tight. In Section9, we consider Grassmannian designs. Complex Grassmannian codes enjoy a form of duality with Grassmannian designs, very similar to real Grassmannian codes or spherical codes. In many cases codes of maximal size or designs of minimal size have the structure of an association scheme, which we describe in Section10. Finally, in Section11, we show how a weighted version of a design can be constructed in any dimension.

2 Orbitals

In this section we describe the orbits of pairs of elements ofGm,nunder the action of U (n).

First, we claim thatGm,n can be identified with a quotient space of the unitary group,U (n)/(U (m)×U (n−m)). For, consider the firstmcolumns of a matrix of U (n)as the basis for a subspacea of dimension m inCⁿ, letting the lastn−m columns be a basis fora^⊥. Thenais invariant under the action ofU (m)on the first mcolumns, whilea^⊥is invariant underU (n−m).

As a result of this quotient space,U (n)acts onGm,nas follows: ifU is inU (n) andPais the projection matrix fora∈Gm,n, then

U:P_a →U P_aU^∗.

This action is an isometry, in that it preserves the trace inner product onGm,n. Unlike on the complex unit sphere, however,U (n)is not 2-homogeneous onGm,n:U (n)does not act transitively on pairs of subspaces with the same distance. In other words, the fact that tr(PaP_b)=tr(PcP_d)does not imply that there is a unitary matrix mapping atocandbtod. In order to use zonal polynomials, we need to understand the orbits of pairs inGm,nunder this isometry group, which requires principal angles.

GivenaandbinGm,n, the principal anglesθ₁, . . . , θ_mbetweenaandbare defined as follows: firstly,θ₁is the smallest angle that occurs between any two unit vectors a1∈aandb1∈b:

θ1:=min

a₁∈a b1∈b

arccosa^∗₁b1.

Secondly, θ₂ is the smallest angle that occurs between any two unit vectors a₂∈ a∩a₁^⊥ and b2∈b∩b₁^⊥. Similarly define θ3, . . . , θ_m. These principal angles are closely related to the eigenvalues of PaPb: the first m eigenvalues of PaPb are {cos²θ1, . . . ,cos²θm}. Because of this correspondence, for the remainder of this pa- per we simply refer to the eigenvalues y_i :=cos²θ_i (rather than the anglesθ_i) as the principal angles betweena andb. Note thatn−mof the eigenvalues ofP_aP_b are zero, so we need only consider the firstm eigenvalues. Conway, Hardin, and Sloane [9] accredit the following lemma to Wong [29, Theorem 2].

Lemma 1 The principal angles characterize the orbits of pairs of subspaces un- derU (n).

Proof SupposeU∈U (n)maps projection matricesPaandPbtoPcandPd respec- tively. Then by similarity, the eigenvalues of

PcPd=(U PaU^∗)(U PbU^∗)=U PaPbU^∗

are the same as the eigenvalues ofP_aP_b.

Conversely, we show that ifPaPbandPcPdhave the same eigenvalues, then some unitary matrixU mapsatocandbtod. We do this by unitarily mappinga andb into a canonical form that depends only on the eigenvalues ofP_aP_b.

LetM_abe ann×mmatrix whose columns[a1, . . . , a_m]are an orthonormal basis fora, so thatMaM_a^∗=PaandM_a^∗Ma=I. Similarly defineMb= [b1, . . . , bm]forb.

SupposeM_a^∗Mbhas singular value decompositionU DV^∗, whereUandV arem×m unitary andDism×mdiagonal. Then(M_aU )^∗(M_bV )=D. Since the columns of M_aU are another orthonormal basis fora, without loss of generality we replaceM_a byM_aUand likewise replaceM_bwithM_bV. In other words, we may assume without loss of generality thatM_a^∗Mb=D, whereDis a diagonal matrix of singular values.

Next, define the columns of N_a= [a_m+1, . . . , a_n] to be any orthonormal basis fora^⊥, so thatN_aN_a^∗=I−P_aandN_a^∗N_a=I. Further assume thatN_a^∗M_b=QR, whereQis(n−m)×(n−m)unitary andRis(n−m)×mupper triangular (the QR-decomposition ofN_a^∗Mb). ThenQ^∗N_a^∗Mb=R, and the columns ofNaQform another orthonormal basis fora^⊥. ReplacingN_a byN_aQ, we may assume without loss of generality thatN_a^∗M_bis upper triangular.

Finally, letUa:=M_a^∗ N_a^∗

; this is ann×nunitary matrix. Then

UaMa= Im

0

; UaMb= D

R

.

IfP_aP_bhas eigenvalues cos²θ_i, thenM_a^∗M_b=Dhas singular values cosθ_i. More- over, sinceUaMb has orthonormal columns, it follows thatR also has orthogonal columns. We may therefore assume thatR is not just upper triangular but diagonal, with diagonal entries sinθ_i. ThusU_ais a unitary matrix which mapsM_aandM_binto

the form

M_a → I_m

0

, M_b →

⎛

⎜⎜

⎜⎜

⎜⎜

⎜⎜

⎜⎜

⎝ cosθ₁

. ..

cosθ_m sinθ₁

. ..

sinθ_m 0

⎞

⎟⎟

⎟⎟

⎟⎟

⎟⎟

⎟⎟

⎠ .

Since any pair(Ma, Mb)with principal angles cos²θican be mapped to this canonical form, it follows that the eigenvalues ofPaPb characterize the orbits of pairs(a, b)

under the unitary group.

3 Representations

In this section and the next, we develop the representation theory needed for Grass- mannian LP bounds.

BecauseU (n)is a compact Lie group, up to normalization it has a unique invariant measure (the Haar measure). SinceU (n)acts transitively on Gm,n, this induces a unique invariant measure onGm,n, which we normalize so that

Gm,n

da=1.

With this measure, the square-integrable functionsL²(Gm,n)are those functionsf : Gm,n→Csuch that

|f (a)|²dais finite. As is standard for compact Lie groups, we work with square-integrable functions to find irreducible representations. The group U (n)acts onf ∈L²(Gm,n)as follows:

(Uf )(P_a):=f (U^∗P_aU ),

wherePa is the projection matrix fora∈Gm,n. It follows thatL²(Gm,n)is a repre- sentation ofU (n). There is a natural inner product on this space:

f, g :=

Gm,n

f (a)g(a) da.

Equivalently, we may write f, g :=

U (n)

f (U^∗P_aU )g(U^∗P_aU ) dU,

wheredUis the Haar measure onU (n)andPais some fixed projection matrix. As we will see, this representation can be decomposed into orthogonal, irreducible subrep- resentations, and the decomposition is multiplicity-free: no irreducible representation ofU (n)occurs more than once inL²(Gm,n).

Since U (n) is a compact Lie group, its irreducible representations are well- studied: see for example [7,13,17,27]. Every irreducible representation is indexed by a dominant weight [27, Theorem 7.34]. In the case ofU (n), we may take these weights to have the form [7, Theorem 38.3]

λ=(λ₁, . . . , λ_n):λ₁≥λ₂≥ · · · ≥λ_n, λ_i∈Z.

The dimension of the irreducible representationV_λindexed byλis given by Weyl’s character formula [27, Theorem 7.32]. In the case ofU (n), the formula reduces to:

dimV_λ=

1≤i<j≤n

λi−λj+j−i

j−i . (1)

For example, the standard representation of U (n)is indexed by λ=(1,0, . . . ,0), which gives

dimV(1,0,...,0)=n.

Note that there is more than one irreducible representation with the same dimension.

Each dominant weight may also be thought of as a form acting on a maximal torus of the Lie group. Hereλacts on the diagonal matrixd=diag(d1, . . . , d_n)∈U (n)as follows:

d^λ:=

n i=1

d_i^λi.

The next section describes exactly which of these forms contribute to the decompo- sition ofL²(Gm,n).

4 Symmetric spaces

The spaceU (n)/U (m)×U (n−m)is an example of a symmetric space: a quotient space G/K such that Gis a connected semisimple Lie group and K is the fixed point set of an involutive automorphism ofG. In this section, we use results from Goodman and Wallach [17] to explain how the decomposition of representations of Gm,nfollows from this structure.

Letsmdenote them×mmatrix with backwards diagonal entries of 1 and 0 else- where:

sm:=

⎛

⎜⎝

0 1

. ..

1 0

⎞

⎟⎠.

Also define

J_m,n:=

⎛

⎝ s_m I_n−2m s_m

⎞

⎠,

and consider the involutionθ (M):=J_m,nMJ_m,nonGL_n(C). The fixed points ofθ have the form

M=

⎛

⎝ a b c

d e dsm

smcsm smb smasm

⎞

⎠,

so the fixed point set inGL_n(C)is isomorphic toGL_m(C)×GL_n−m(C).

Lemma 2 The fixed point setKofθinG=U (n)is isomorphic toU (m)×U (n−m).

ThereforeGm,nis a symmetric space.

Proof Fora=(a₁, . . . , a_m), leta˘denote the reversal ofa, namely

˘

a:=s_ma=(a_m, . . . , a₁).

Ifa,b, andchave lengthm,n−2mandmrespectively, then we haveJm,n(a, b, c)^T = (˘c, b,a)˘ ^T. Therefore the 1 and −1 eigenspaces ofJm,n are V₊= {(a, b,a)}˘ and V₋= {(a,0,−˘a)}respectively. These spaces are orthogonal with respect to the form (x, y) →x^∗y.

NowKis the set of points inU (n)which commute withJ_m,n. So decomposing CⁿintoV₊⊕V₋, we have thatK is the set of points inU (n)which leave bothV₊ andV₋ invariant. In other words,K is the set of points which preserve the form (x, y) →x^∗y on the subspacesV₊andV₋. Thus

K∼=U (V₊)×U (V₋)∼=U (n−m)×U (m).

The fact thatKis the fixed point set ofθinGimplies ([17, Theorem 12.3.5]) that (G, K)is a spherical pair: for every irreducible representationVλofG, the subspace V_λ^K of points fixed byKsatisfies dimV_λ^K≤1. Those representations such thatV_λ^K has dimension exactly 1 are called spherical representations. The following theorem [18, Theorem V.4.3] explains how those representation relate toL²(G/K).

Theorem 1 LetG be a compact simply connected semisimple Lie group, and let K≤G be the fixed point group of an involutive automorphism of G. Further let GˆK denote the set of equivalence classes of spherical representationsVλofGwith respect toK. ThenL²(G/K)is a multiplicity-free representation ofG, and

L²(G/K)∼=

λ∈ ˆG_K

V_λ.

To describe which representations are spherical, we now consider diagonal sub- groups ofG andK. For d=(d₁, . . . , d_n), let diag(d) denote the diagonal matrix with diagonal entriesd₁, . . . , d_n. Firstly, note that diag(d)is in U (n)if and only if

|d_i| =1 for alli. Secondly, note that ifd=diag(a, b, c)witha andcof lengthm, thenθ (d)=(c, b,˘ a). It follows that the diagonal group˘

T := {diag(a1, . . . , a_m, b_m+1, . . . , b_n−m, a_m, . . . , a₁): |a_i| = |b_i| =1}

is contained inK. In fact, it is a maximal subgroup ofKisomorphic to(R/Z)^r: this is called a maximal torus ofK.

Recall that the irreducible representations of G are indexed by the dominant weightsλ=(λ1, . . . , λn), where λi ≥λi+1 andλi ∈Z. Now the spherical repre- sentations ofGwith respect toK are indexed by those particular dominant weights such thatt^λ=1 for allt=(t1, . . . , t_n)in the torusT (see Goodman and Wallach [17, p. 540]). So a dominant weightλis spherical if it has the form

λ=(λ₁, . . . , λ_m,0, . . . ,0,−λ_m, . . . ,−λ₁) withλ1≥ · · · ≥λm≥0 andλi∈Z. In other words:

Theorem 2 The irreducible representations ofU (n)occurring inL²(Gm,n)are in one-to-one correspondence with the integer partitions with at mostmparts.

For any partitionμ, we letH_μ(n), or simplyH_μ, denote the irreducible represen- tation inL²(Gm,n)isomorphic toV(μ,0,...,0,− ˘μ). The Weyl character formula (equa- tion (1)) now tells us the dimension of eachHμ. The first few dimensions are:

dimH(0)=dimV(0,...,0)=1 dimH(1)=dimV(1,0,...,0,−1)=n²−1

dimH₍₂₎=n²(n−1)(n+3) 4 dimH(1,1)=n²(n+1)(n−3)

4

dimH_(2,1)=(n²−1)²(n²−9) 9

dimH(k)=

n+k−2 k

2n+2k−1 n−1 dimH_(1,...,1

k

)= n+1

k 2

n−2k+1 n+1

Ifm=1, thenGm,nis the complex projective spaceCPⁿ⁻¹, and only the spaces H_(k)occur. In that caseH_(k)is isomorphic to the space Harm(k, k)of harmonic poly- nomials of homogeneous degreekin bothzandz, where¯ z=(z₁, . . . , z_n)is a point on the unit sphere inCⁿ. Those harmonic polynomials were used by Delsarte, Goethals, and Seidel in their LP bounds for codes and designs on the complex unit sphere [12].

We now record another representation ofU (n)inL²(Gm,n)that we need for our bounds on codes and designs. Given an nonincreasing sequence of nonnegative inte- gersμ=(μ1, μ2, . . .), we sayμhas sizekand write|μ| =kifμis a partition ofk;

that is,

iμ_i=k. We also sayμhas lengthland write len(μ)=lifμhaslnonzero entries. For example,(2,1,0, . . .)has size 3 and length 2. Then for fixedGm,n, define

H_k=H_k(m, n)as follows:

H_k(m, n):=

|μ|≤k len(μ)≤m

H_μ(n).

The spaceH₀has dimension 1 and consists of the constant functions onGm,n. For k >0, the representationH_k is reducible, andH_k−1is contained inH_k. Whenm=1, H_k is isomorphic to the space of homogeneous polynomials degreekin bothzandz¯ on the unit sphere inCⁿ. In the next section, we will see thatHkis also the span of the symmetric polynomials of degree at mostkon the principal angles betweenaandb inGm,n, for fixeda. Moreover, ifgandhare polynomials inH_kandH_krespectively, thenghis inH_k+k, and in factH_k+k is spanned by polynomials of that form.

We will also see in the next section thatHkis the space of polynomialsf (b)which are homogeneous of degreekin the entries ofP_b, the projection matrix ofb∈Gm,n. It follows that for fixeda∈Gm,n, the inner product functionb → a, b =tr(PaP_b) is inH1(n).

James and Constantine [20] further investigated the irreducible subspaces of L²(Gm,n), finding zonal polynomials for each irreducible representation. We describe those results in the following section.

5 Zonal polynomials

A zonal polynomial at a pointa∈Gm,nis a function on pointsb∈Gm,n which de- pends only on the principal angles betweenaandb. Given a symmetric polynomial f (x1, . . . , x_m)∈R[x1, . . . , x_m]of degreek, we define the zonal polynomial off ata as follows: ify(a, b)=(y1, . . . , ym)are the principal angles ofaandb, then

f_a(b):=f (y₁, . . . , y_m).

Sincef is a symmetric polynomial of degree at mostkin the principal angles, it is in Hk(m, n). IfPaandPbare the projection matrices foraandb, thenb →tr(PaPb)is an example of a zonal polynomial, since tr(PaP_b)=_m

i=1y_i, a symmetric polyno- mial of degree 1.

There is a particular set of zonal polynomials that play a special role in the theory of Delsarte bounds. LetHμbe an irreducible representation inL²(Gm,n). Then for eacha∈Gm,n, define the zonal orthogonal polynomial or zonal spherical polynomial Z_μ,a to be the unique element ofH_μsuch that for everyp∈H_μ,

Zμ,a, p

=p(a). (2)

From equation (2) it follows that the set{Z_μ, a:a∈Gm,n}spansH_μ. These zonal polynomials are invariant under the unitary group, in the following sense:

Zμ,b(a)=

U^∗Zμ,a, U^∗Zμ,b

=

Zμ,U a, Zμ,U b

=Zμ,U b(U a).

(ByU awe mean the actionU:P_a →U P_aU^∗.) The value ofZ_μ,b(a)depends on the U (n)-orbit of(a, b)and therefore depends on the principal angles ofaandb. With

this in mind we sometimes writeZ_μ,a(b)=Z_μ(a, b)orZ_μ,a(b)=Z_μ(y₁, . . . , y_m), where(y1, . . . , y_m)are the principal angles ofaandb.

Schur orthogonality [27, Theorem 3.3] for irreducible representations implies that Zμ,a andZν,bare orthogonal forμ=ν. So, we have

Z_μ,a, Z_ν,b

=δ_μ,νZ_μ(a, b).

Moreover,Z_μ,a(b)=Z_μ,b(a) is in fact real and symmetric ina andb. The zonal polynomials satisfy some other important properties, including the following positiv- ity condition:

Lemma 3 For any subsetS⊆Gm,n,

a,b∈S

Z_μ(a, b)≥0.

Equality holds if and only if

a∈SZμ,a=0.

Proof We have

a,b∈S

Z_μ(a, b)=

a,b∈S

Z_μ,a, Z_μ,b

=

a∈S

Z_μ,a,

b∈S

Z_μ,b

≥0.

Equality holds only when

a∈SZμ,a=0.

The second important condition the zonal polynomials satisfy is called the addi- tion formula:

Lemma 4 Lete1, . . . , e_N be an orthonormal basis for the irreducible subspaceH_μ. Then

N i=1

ei(a)ei(b)=Zμ(a, b).

Proof SinceZ_μ,a is inH_μ, we may write it as a linear combination ofe1, . . . , e_N: Z_μ,a=

N i=1

e_i, Z_μ,a e_i

=

i

ei(a)ei.

So, it follows thatZ_μ,a(b)=

ie_i(a)e_i(b).

James and Constantine give an explicit formula for the zonal orthogonal polyno- mials ofGm,nin terms of Schur polynomials, the irreducible characters ofSL(m,C).

Ify=(y₁, . . . , y_m)are variables andσ=(s₁, . . . , s_m)is an integer partition into at mostmparts, then the (unnormalized) Schur polynomial is defined as

X_σ(y):=det(y_i^sj+m−j)i,j

det(y_i^k−j)_i,j .

Each Schur polynomial is a symmetric polynomial in(y1, . . . , y_m). For more infor- mation about Schur polynomials, see Stanley [28, Chapter 7]. The normalized Schur polynomialX_σ^∗is the multiple ofX_σ such thatX_σ^∗(1, . . . ,1)=1.

To define the zonal orthogonal polynomials forGm,n, first define the ascending product

(a)s:=a(a+1)· · ·(a+s−1),

and given a partitionσ=(s₁, . . . , s_m), define complex hypergeometric coefficients [a]σ :=

m i=1

(a−i+1)si.

Further assume we have a partial order ≤ on partitions defined such that (s1, . . . , s_m)≤(k1, . . . , k_l)if and only if s_i ≤k_i for all i. Letting y+1:=(y1+ 1, . . . , ym+1), the complex hypergeometric binomial coefficients_κ

σ

are given by the formula

X_κ^∗(y+1)=

σ≤κ

κ σ

X^∗_σ(y).

We can now define the zonal orthogonal polynomials forGm,n. The following result is due to James and Constantine [20].

Theorem 3 Let

ρ_σ:=

m i=1

s_i(s_i−2i+1) and letσandκpartitionsandkrespectively. Also let

[c](κ,σ ):=

i

κ σi

σi

σ

(k−s) κ

σ

[c](κ,σ_i)

c+^ρκ_k⁻₋^ρ_s^σ!,

where the summation is over partitionsσ_i=(s1, . . . , s_i−1, s_i+1, s_i+1, . . .)that are nonincreasing. Then up to normalization, the zonal orthogonal polynomial forH_κis

Z_κ(y):=

σ≤κ

(−1)^s κ

σ

[c](κ,σ )

[a]σ

X_σ^∗(y),

wherey=(y₁, . . . , y_m)is the set of principal angles.

The first few normalized Schur polynomials are:

X^∗₍₀₎(y)=1 X^∗₍₁₎(y)= 1

m m i=1

y_i

X^∗_(1,1)(y)= 1 _m

2

i<j

y_iy_j

X^∗₍₂₎(y)= 1 _m+1

2

m i=1

y_i²+

i<j

y_iy_j

! .

Up to normalization by a constant, the first few zonal orthogonal polynomials are:

Z₍₀₎(y)=1

Z₍₁₎(y)=nX₍₁₎^∗ (y)−m

Z(1,1)(y)=(n−1)(n−2)X^∗_(1,1)(y)−2(n−1)(m−1)X^∗₍₁₎(y)+m(m−1) Z₍₂₎(y)=(n+1)(n+2)X^∗₍₂₎(y)−2(n+1)(m+1)X₍₁₎^∗ (y)+m(m+1).

The correct normalizations satisfy Z_μ,a, Z_μ,a

=Z_μ(1,1, . . . ,1)=dimH_μ.

With the exception of the caseμ=(0)(which is normalized correctly in the formula above), normalizations forZ_μdo not play a role in the results which follow.

From the result of James and Constantine, a few observations are apparent. Firstly, the zonal orthogonal polynomialsZ_μ(y), like the Schur polynomials, are symmetric polynomials iny₁, . . . , y_m, and the polynomials with|μ| ≤k form an orthonormal basis for the symmetric polynomials iny₁, . . . , y_mof degree at mostk. Secondly, we have the following useful description ofH_k.

Lemma 5 H_k(m, n)is the space of polynomialsGm,n→Cwhich are homogeneous of degreekin the entries of the projection matrices for the subspaces.

Proof For convenience, let Homk denote the space of polynomialsf (b)which are homogeneous of degreekin the entries ofP_b, forb∈Gm,n. First, we claim thatH_kis contained in Homk. Since the zonal polynomials{Z_μ,a:a∈Gm,n}spanH_μ, the zonal polynomials{Z_μ,a: |μ| ≤k, a∈Gm,n}spanH_k, and it suffices to show thatZ_μ,a is in Homk. ButZ_μ,a(b) is a symmetric polynomial of the principal anglesy(a, b), which are precisely the nonzero eigenvalues ofP_aP_b. Moreover, a standard theorem from linear algebra [19, Theorem 1.2.12] states that thej-th elementary symmetric function of the eigenvalues of a matrix is the sum of all j ×j principal minors.

Therefore every symmetric polynomial of degreekin the eigenvalues ofP_aP_bis also a homogeneous polynomial of degreek in the entries of P_aP_b, which is in turn a homogeneous polynomial of degreekin the entries ofPb.

Next we claim that Homk andHk are actually equal. To see this, consider the zonal polynomials in Homk: the degree-k polynomials f_a(b) in the entries of P_b which depend only on theU (n)-orbit of(a, b). These zonal polynomials are sym- metric functions of the principal anglesy(a, b)=y₁, . . . , y_m, which depend only on the projection of a basis ofbonto the subspacea. Therefore, it suffices to consider degree-kpolynomials in the entries ofP_aP_bP_a(which are also degree-kpolynomials in the entries ofPb). Now choose the unitary matrixUain the proof of Lemma1so that

U_aP_aU_a^∗=diag(1, . . . ,1,0, . . . ,0), U_aP_aP_bP_aU_a^∗=diag(y1, . . . , y_m,0, . . . ,0).

Since the zonal polynomials are symmetric functions ofy1, . . . , y_mand polynomials of degreekin the entries ofU P_aP_bP_aU^∗, they are symmetric polynomials of degree kiny₁, . . . , y_m. Thus every zonal polynomial of Homkis also a zonal polynomial of H_k. Since the two spaces have the same zonal polynomials, and the zonal polynomials

span the entire space, the two spaces are equal.

6 Bounds

Recall that an A-code is a collection S of subspaces in Gm,n such that a, b = tr(PaPb)∈Afor everya=binS. In this section, we find upper bounds on the size of anA-code in terms of either the cardinality ofAor the elements ofA. A summary of the results for|A| ≤2 is given in Table1.

Table 1 Upper bounds on|S|, whenS⊆Gm,nis anA-code

A {α} {α, β}

Absolute bound

n²

n² 2

(m >1)

Relative bound

n(m−α) m²−nα

n(m−α)(m−β) m²"_(m+1)2

2(n+1)+^(m−1)_2(n−1)²−(α+β)+^nαβ_m2

#

Relative bound conditions

α <m²

n α+β≤2(m²n−4m+n)

n²−4 , α+β−nαβ

m² <m²n−2m+n n²−1

IfA= {α₁, . . . , α_k}, then the annihilator ofAis the symmetric function

ann_A(y):=

k i=1

⎛

⎝^m

j=1

yj−αi

⎞

⎠.

The significance of the annihilator is that ifSis anA-code, then ann_A(y(a, b))=0 for anya=b inS. More generally, given any symmetric polynomial f satisfying f (1,1, . . . ,1)=0, anf-code is a collectionSof subspaces such that for everya=b inS, the principal anglesy(a, b)=(y₁, . . . , y_m)satisfyf (y₁, . . . , y_m)=0. IfAis any set of inner product values andf is the annihilator ofA, then anA-code is also anf-code.

Theorem 4 IfS⊆Gm,nis anf-code, with deg(f )=k, then

|S| ≤dim(Hk(m, n)).

In particular, ifSis ak-distance set, then the annihilator of the code has degreek, so|S| ≤dim(Hk(m, n)). Note that sinceH_k(m, n)is the space of homogeneous poly- nomials of degreekin then×nprojection matrices forGm,n, we have

dim(Hk(m, n))≤

n²+k−1 k

.

Proof IfS is anf-code, consider the zonal polynomialsf_a(b):=f (y(a, b)), for a ∈S. Since f_a(b) is a degree-k symmetric polynomial in y(a, b), it is an ele- ment ofH_k(m, n). Sincef_a(b)=0 for everyb∈S except a, andf_a(a)=0, the set{f_a:a∈S}is linearly independent. Thus the number of functions|S|is at most

the dimension of the spaceH_k(m, n).

If equality holds, then the functionsf_a form a basis for the space. Moreover, the spaceHk(m, n)is exactly the space of functions onS.

Corollary 1 IfSis a 1-distance set inGm,n, then

|S| ≤n².

IfSis a 2-distance set inGm,n(m >1), then

|S| ≤ n²

2

.

Proof Use Theorem4together with the facts that dim(H1(m, n))=n²and form >1, dim(H2(m, n))=_n²

2

.

Theorem 4 is called the absolute bound for Grassmannian codes, because the bound depends only on the number of different distances that occur inS. It is the

complex analogue of the bound for real Grassmannian spaces given by Bachoc, Ban- nai and Coulangeon [3, Theorem 9]. Whenm=1, it reduces to the absolute bound of Delsarte, Goethals and Seidel [12, Theorem 6.1]. There is also a relative bound, which depends on the actual values of the inner products and is sometimes tighter.

The relative bound for real Grassmannian spaces was given by Bachoc [2, Proposi- tion 2.3].

Theorem 5 Letf (x₁, . . . , x_m)∈R[x₁, . . . , x_m]be a symmetric polynomial such that f =

μcμZμ, whereZμis a zonal orthogonal polynomial, and eachcμ≥0. Fur- ther assume thatc₍₀₎ is strictly positive. IfSis a set of subspaces inGm,nsuch that f_a(b):=f (y1(a, b), . . . , y_m(a, b))is nonpositive for everya=binS, then

|S| ≤f (1, . . . ,1) c(0)

.

Proof Sincef_a(b)≤0 forb=a, summing over allb∈S, we have

b∈S

fa(b)≤fa(a)=f (1, . . . ,1).

Then averaging over alla∈S,

f (1, . . . ,1)≥ 1

|S|

a,b∈S

f_a(b)

= 1

|S|

μ

c_μ

a,b∈S

Z_μ(a, b).

By Lemma3, the inner sum is non-negative forμ=0. Ifμ=(0), thenZ₍₀₎(a, b)=1 for allaandb, and hence,

f (1, . . . ,1)≥ 1

|S|c₍₀₎

a,b∈S

1

=c₍₀₎|S|.

Equality holds if and only iff_a(b)=0 for everya=b∈Sand for eachμ=(0), we have eithercμ=0 or

a∈SZμ,a=0. (We will see in Section9that whencμ>0 for all|μ| ≤deg(f ), this implies that we have a Grassmanniant-design.)

By way of example, we consider the case of a single nontrivial distance in detail.

The following result is known as the complex Grassmannian simplex bound and can also be obtained from the real Grassmannian simplex bound by embeddingCⁿ into R²ⁿ: see Corollary4in Section7.

Corollary 2 LetSbe a subset ofGm,nsuch that tr(PaP_b)∈ [0, α]for alla=binS, andα < m²/n. Then

|S| ≤n(m−α) m²−nα.

Proof The first two zonal orthogonal polynomials areZ₍₀₎(y)=1 and (up to normal- ization)Z₍₁₎(y)=_m

i=1y_i−m²/n. The annihilator forαis the polynomial f (y1, . . . , ym)=

m i=1

yi−α,

and ify1, . . . , ymare the principal angles ofaandbinS, thenfa(b)=f (y(a, b))=0.

In terms of zonal polynomials, we have f (y1, . . . , y_m)=

m i=1

y_i−α

=Z(1)(y)+ m²

n −α

Z(0)(y).

Applying Theorem5, we get

|S| ≤f (1, . . . ,1)

c₍₀₎ = m−α

m²/n−α.

In particular, ifSis a 1-distance set with non-trivial inner productα, then Corol- lary2applies, and the bound is tighter than the bound in Corollary1provided that α <1/(n+1). Whenm=1, Corollary2reduces to Delsarte, Goethals and Seidel’s bound for a set of complex equiangular lines:

|S| ≤n(1−α) 1−nα .

Similarly, using the zonal orthogonal polynomialsZ₍₀₎, Z₍₁₎, Z_(1,1) andZ₍₂₎, we get a bound using the annihilator of two distances.

Corollary 3 LetSbe a subset ofGm,nsuch that tr(PaPb)∈ [α, β]for alla=binS.

Further assume that

α+β≤2(m²n−4m+n)

n²−4 , (3)

α+β−nαβ

m² <m²n−2m+n

n²−1 . (4)

Then

|S| ≤ n(m−α)(m−β) m²

"

(m+1)²

2(n+1) +^(m_2(n⁻₋¹⁾₁₎²−(α+β)+^nαβ_m2

#.

Whenm=1 this reduces to the Delsarte, Goethals and Seidel’s bound of

|S| ≤ n(n+1)(1−α)(1−β) 2−(n+1)(α+β)+n(n+1)αβ for 2-distance sets of lines in complex projective spaceCPⁿ⁻¹.

Proof The annihilator for{α, β}is f (y)=

$ _m

i=1

y_i−α

% $ _m

i=1

y_i−β

% ,

and is nonpositive ifa, b ∈ [α, β]. In terms of Schur polynomials, the annihilator is f (y)=

m+1 2

X₍₂₎^∗ (y)+ m

2

X^∗_(1,1)(y)−(α+β)mX₍₁₎^∗ (y)+αβ.

Writing each Schur polynomial in terms of zonal orthogonal polynomials, we get f (y)=c₍₂₎Z₍₂₎+c_(1,1)Z_(1,1)+c₍₁₎Z₍₁₎+m²

n

(m+1)²

n+2 +(m−1)²

n−2 −(α+β)

+αβ− m²(m+1)²

2(n+1)(n+2)− m²(m−1)² 2(n−1)(n−2),

for some constantsc₍₂₎,c_(1,1), andc₍₁₎. The resulting boundf (1,1, . . . ,1)/c(0)from Theorem5simplifies to

n(m−α)(m−β) m²

"

(m+1)²

2(n+1) +^(m_2(n−⁻¹⁾₁₎² −(α+β)+^nαβ_m2

#.

Conditions (3) and (4) arise from insisting thatc(1)≥0 andc(0)>0 respectively.

7 Other bounds

Certain cases of equality in Corollaries2 and3 also achieve equality for bounds on the size of the largest inner product that occurs in a set of subspaces. For real Grassmannians, Conway, Hardin and Sloane [9] call these bounds the simplex and orthoplex bounds. Here we give their complex analogues.

Recall that ifPais then×nprojection matrix fora∈Gm,n, thenP_ais Hermitian with tracem, soP_a =P_a−mI /n lies in a real space of dimensionn²−1. More- over||P_a||²:=tr(P_aP_a)=m(1−m/n), soP_a is embedded onto a sphere of radius

√m(1−m/n)inRⁿ²⁻¹. Further recall that the chordal distance onGm,nis defined by

d_c(a, b)²=m−tr(PaP_b)

=1

2||P_a−P_b||²=1

2||P_a−P_b||².

With this distance, the Grassmannians are isometrically embedded intoRⁿ²⁻¹. The

“Rankin bounds” given in Theorem6 below (see [5, Theorems 6.1.1 & 6.1.2]) are bounds on the minimum distance between points on a real sphere as a function of the number of points and the dimension of the space. An equatorial simplex refers to a