On a result of S. Delsarte

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 92. Number I. September 19K4 SHORTERNOTES The purpose of this department is to publish very short papers of unusually elegant and polished character, for which there is no other outlet. ON A RESULT OF S. DELSARTE GREGORY CONSTANTINE1 AND RAVI S. KULKARNI2 Abstract. For an isomorphism type of a finite abelian ¿»-group X it is shown that the matrix (p<s(DUIK») is nonsingular; D, Y e [S\S « X and S * X}. the set of all proper isomorphism type of subgroups of X. Here s{ Y) denotes the signature of Y. This completes the proof of a result of S. Delsarte which gives explicit formulas for the number of automorphisms of X, the number of subgroups of X isomorphic to Y (and the number of homomorphisms from Y into X) in terms of signatures. 1. Preliminaries. In [1], S. Delsarte generalizes the classical Möbius function in number theory and uses it to establish explicit formulas for the number of automorphisms of a (finite) abelian group x, and the number of subgroups of x of a given isomorphism type. These formulas are given in terms of signatures of the groups. Since a finite abelian group decomposes canonically into its p-primary parts it suffices to prove the result for abelian p-groups only. Establishing the nonsingularity of a certain coefficient matrix ( p^J<D)î( r» ) is a crucial step in Delsarte's proof [1, p. 607]. A reference is given in [1] to account for the claim on nonsingularity; we have, however, not been successful in completing the proof based on this reference. The purpose of this note is to prove that the aforementioned coefficient matrix ( p^ J<D)J<yi>) is indeed nonsingular (positive definite, in fact). Let x be a (finite) abelian p-group. By X we denote the isomorphism type of x. Also, v < x means y is a subgroup of x and Y < X means that X admits a subgroup of isomorphism type Y. Assume x = Zpmx © • • ■ © Zpmk; m, > 1. Let xx = [g g x: order of g divides p). Then xx < x. Let \xx\ = pr[ (rx = k, in fact). Repeat this process in x/xx, i.e., look at (x/xx)x and denote its order by pr'-. Continuing this process we associate a sequence of nonnegtive integers (ending in 0's) (r,, r2, r3,... ,0,0,...) which satisfies r, > r2 ^ r3 > ■■• and which we call the signature of x. Observe that, in fact, rn = |{/: m, > n}\. Conversely, a given signature rx > r2 ^ /-3 > • • • determines uniquely the isomorphism type of an abelian p-group as (Zp)r^r'- © (Zp)r2~r^ © • • • ®(Zpy>-°, where r„ = 0 for n > / + 1. ((Z*)'2-'3 means Zj © • • • © Z], a direct sum of r2 - r3 factors.) Denote by s(X) the signature of X. (For example, if Received by the editors July 29, 1983. 1980 Mathematics Subject Classification. Primary 05A15; Secondary 20B25. Key words and phrases. Signature of a finite abelian/»-group, Möbius inversion, generating function. 1This research has been supported bv a summer research fellowship grant from Indiana University (1983). : Supported by an NSF grant MCS 83-01614. 149 License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use 150 GREGORY CONSTANTINE AND R. S. KULKARNI x= z then. s(X) = (4,3,1,0,...); conversely, (4,3,1,0,...) Z = X.) and s(D) = (/,,.. .,/'fe,0...); then Zp • Zp leads uniquely to (Zp)4~3 © (Z,2)3"1 © (Z3)1' Let D ^ X. Assume s(X) = (r,,.. .,^,0...) i, < r1,...,ik < r^. In fact, for £mj>sequence of nonincreasing nonnegative integers there exists a ending in zeros (ix,...,iA,0...) and satisfying i1 < /-,,.. ■.»*<*; A-' subgroup D < ATwith signature (z'i,..., t'¿, 0... ). For a direct sum A' © F we have s(X © 7) = s( A') + s(F) with usual (componentwise) addition of sequences. We shall also denote by (s(X), s(Y)) the usual inner product of two sequences, i.e., if s(X) = (/-,, r2,...) and s(Y) = (sx, s2,...) then(s(X),s(Y))=Lr=iV,- We can now state Delsarte's result. Theorem (S. Delsarte). For finite abelian p-groups x and y with signatures s(x) = (rx,...,rk,0...) and s(y) = (sx,...,slt0...) satisfying r, < sx,.. ,,rk < sk we have (i) the number of automorphisms of x equals Fx(pri,...,prk), (ii) the number of subgroups of y isomorphic to x equals Fx{p\...,f*)/Fx{p\...,p'>) where ri-1 Fx{zx,,..,zky-z?z2 X • zi n(z2-Ph) n(*i i,=r2 rk~l '2 = r} (iii) the number of homomorphisms from x into y equals (p (s(x),s(y)) The proof is contained in [1], the original work of S. Delsarte. It can also be found in [3], rewritten in the more contemporary notation on Möbius inversion. For a complete proof it is necessary to establish the following Lemma. Let X be (an isomorphism type of) a finite abelianp-group. Let«y= {S: S < X and S # X). Order í^in some way. Let C be the symmetric matrix (^/s(D'-í(y)>)) where D and Y run over y ; the numbering of rows and columns in C comes from the order of 6f. Lemma. C is nonsingular. 2. Proof of the Lemma. Let the signature of X be (rlf r2,...,rk,0...). The rows and columns of C are labeled by the (isomorphism types of) proper subgroups of X; think, instead, of its rows and columns being labeled by the corresponding signature sequences. A block of C is a set of signatures (s, s2,...,sk,0...) with s2,...,sk fixed and s varying, s2 < i < rx. The block (s, s2,... ,sk, 0...) is said to be larger or of the same magnitude as the block (/, l2,...,lk,0...) if l2 > s2. Arrange the rows and columns of C by blocks in their order of magnitude (larger to smaller—blocks of the same magnitude can be arranged among themselves in any order). Now write C = (C,j) as a partitioned matrix with CtJ = (p<s<.D)'s(Y)))twith s(D) running through block i and s(Y) running through block j. License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use ON A RESULT OF S. DELSARTE 151 Let block 1 be(s, s2,.. .,sk,0.. .),s2 < s < r,, and let block 2 be (/, l2,.. .,lk,0...), l2 < I < ri (with /2 > s2). The signatures in blocks 1 and 2 (written as columns and truncated at the /cth entry for simplicity) are, respectively, s-, + 1 s-, + 2 //, and /2 + 1 l2 + 2 u u h u Tl\ Let a = EJL2s,2,y = E?L2/,2and /3 = I,rL2 J,//Note that Cmn = VnnDmn, 1 < m, n < 2, where K,, (resp. F22) is a square matrix with r, - s2 + 1 (resp. rx - l2 + 1) rows and (/, y)th entry p(/_1X*2+y-i) (resp. ,(i-iX/2+y-D ), and Dn = padiag{p^+l-^)i^ri.S2+1; ö12=p%ag(p^+'-1»)1</<ri_/2+1; £)21 =p^diag(p /2(i2+/-i) )im r,-i2 + l» A The significance of this rearrangement is that Vu and V22 are Vandermonde matrices and hence nonsingular. Since l2 > s2 each column of C12 appears also as a column of Cn. Multiplying the (/ + z')th column of Cu by pß~a and subtracting it from the zth column of C12 we reduce C12 to the zero matrix (1 < i < rx — l2 + 1). This process changes C22into (Py - P2ß-")C22= p-a(p"+a - p2ß)C22 {=C22,say). We thus reduce by column operations the matrix C21 12 -22 to Cn C21 C22 Note that py+a - p2ß > 0, since y + a - 2/3 = E,rL2(/, - s,)2 > 0; y + a - 2/3 is strictly positive since the two blocks in question are not identical, i.e., /, # s¿ for some i, 2 < i < rx. This shows that C22is also nonsingular. We now repeat the process to make all C¡j = 0, for i < j. C will be reduced to a lower block-triangular matrix with nonsingular diagonal blocks of Vandermonde type. This proves the nonsingularity of C and completes the proof of S. Delsarte's result. Remark. C is, in fact, positive definite. One way to see this is to recall a result of I. Schur [2]. It states that if A = (atJ) and B = (bu) are positive semidefinite then License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use 152 GREGORY CONSTANTINE AND R. S. KULKARNI A° B = (üjjbjj) (componentwise multiplication) is again positive semidefinite. Clearly, the matrix A = ((s(D), s(Y))) is positive semidefinite (it is an inner product matrix). Then (lnp)"A"/n\ is positive semidefinite by Schur's result. (A" = A° ■■■ ° A, n times). So then is our matrix C- t^{lnp)"A" »1= 0 as a sum of positive semidefinite matrices. Starting with a positive semidefinite matrix, one is, in general, led only to a positive semidefinite matrix by this process. We just established the nonsingularity of C, however, and can now conclude that C is positive definite. References 1. S. Delsarte, Fonctions de Möbius sur les groupes abeliens finis, Ann. of Math. (2) 3 (1948), 600-609. 2. I. Schur, Bemerkungen zur Theorie der beschränkten Bilinearformen suit unendlich vielen Veränderlichen. J. Reine Angew.Math. 140 (1911),1-28. 3. G. Constantine, Topics in combinatorics. Unpublished Manuscript. Indiana University, 1982. Department of Mathematics, Indiana University, Bloomington, Indiana 47405 License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use