Contents
Context
Group Theory
group theory
Classical groups
Finite groups
Group schemes
Topological groups
Lie groups
Super-Lie groups
Higher groups
Cohomology and Extensions
Related concepts
Analysis
Contents
- Idea
- Definition
- Examples
- Properties
- Some lemmas
- Eigenvectors
- Positivity
- Indefiniteness for
- Semi-definiteness for
- Definiteness for
- Definiteness for
- Cayley state on the group algebra
- Entropy of the Cayley state
- Related concepts
- References
Idea
For and for some parameter (“inverse temperature”) the function on pairs Sym(n) of permutations of elements which assigns the exponentiated Cayley distance between them, weighted by :
may naturally be called the Cayley distance kernel (though it does not seem to have a standard name in existing literature).
This is different from but akin to other kernels used in geometric group theory, notably the more widely studied Mallows kernel, which is of the same form but using the Kendall distance instead of the Cayley distance. While these two distance functions are superficially similar (where the Cayley distance counts the minimum number of transpositions needed to turn one permutation into another, the Kendall distance counts minimum numbers of adjacent transpositions) the two resulting kernels behave qualitatively differently:
Where the Mallows kernel is positive definite for all (Jiao-Vert 18, Thm. 1), the Cayley distance kernel becomes indefinite, for sufficiently small non-integer values of , see Example and Prop. below.
We prove below (following CSS21) that for integer values of the Cayley distance kernel is always positive (semi-)definite, see Example . At exactly these values the Cayley distance kernel equals (CSS21) the fundamental -Lie algebra weight system on horizontal chord diagrams (for the general linear Lie algebra regarded as a metric Lie algebra with the trace in its defining fundamental representation, as in Bar-Natan 95) under the monoid-homomorphism
that sends the chord to that permutation of elements (strands) which is given by the transposition of the th with the th strand.
Definition
Definition
(Cayley distance kernel) For a natural number, with denoting the symmetric group on elements, and
denoting its Cayley distance-function, the corresponding Cayley distance kernel for
(1)
is the exponential of the Cayley distance, weighted by .
This may and often is regarded as a square matrix over the real numbers and as such often conflated with the corresponding bilinear form on the linear span of .
Examples
Properties
Some lemmas
Sum over one row
We give a useful expression (Lemma below) for the sum over the first row of the Cayley distance kernel. This appears both in the expression for its Gershgorin radius (Prop. ) as well as being the eigenvalue of the kernel on the homogeneous distribution (Example ).
Lemma
For , with denoting the symmetric group on elements, and for any variable , we have (as an equation between polynomials in ):
In
Stanley 11, Prop. 1.3.7 are offered four proofs of this lemma, see also discussion at
MO:q/245005; we now spell out the proof idea given in
Math.SE:a/92051:
Proof
Notice that every permutation has a unique representative in cycle notation
(4)
with the property that the following two conditions hold:
-
heads are smallest in their cycle: ,
-
cycles are ordered by their heads: .
This yields a bijection between the set of permutations and the set of sections of the following indexed family of sets
(5)
as follows:
To a given section , assign the permutation whose normalized cycle notation (4) has underlying it (forgetting the bars “”) the list obtained by setting
and then recursively adding the element to the list at stage by
-
either appending it on the right, if ;
-
or inserting it after the -st element already in the list:
The resulting , with a bar “” inserted right before each element with , is a normalized cycle notation (4) for a permutation, and every such arises this way, uniquely.
Via this bijection, the number of cycles of a permutation equals the number of times that the corresponding section (5) takes the value 0. Therefore we have:
An immediate variant of Lemma :
Lemma
For , with denoting the symmetric group on elements, and for any variable , we have (as an equation between polynomials in ):
where denotes the signature of a permutation.
This is mentioned, without proof, at
MO:q/245010.
Proof
We compute as follows:
Here the second step is Lemma .
To see the fourth step, notice that if is even/odd there must be an even/odd number of permutations of odd length. Therefore plus the number of odd-length permutations cancels out in signs and thus leaves the sign of the number of even permutations.
The last step is the observation that the signature of a permutation is the sign of its number of even-length permutations, since for each cycle there is one less transposition than elements in the cycle (see here).
Another immediate consequence of Lemma is this:
Lemma
(sum over first row of Cayley distance kernel)
For , the sum over the first row of the Cayley distance kernel (Def. ) equals
Proof
We compute as follows:
where:
Gershgorin radius
We discuss the Gershgorin radius of the Cayley distance kernel, in Prop. below.
Proposition
(Gershgorin radius of Cayley distance kernel) For , the Gershgorin radii of the Cayley distance kernel (Def. ) are all equal to
(6)
Proof
By right invariance of the Cayley distance (this Prop.) the sum over entries of any row is equal to that of the first row. Since moreover
-
all entries are real and non-negative, hence equal to their absolute value,
-
the diagonal elements are all equal to ,
it follows that this sum over the first row equals the Gershgorin radius plus 1 (by its defining formula here). Therefore the statement follows by Lemma .
Eigenvectors
We discuss some eigenvectors of the Cayley distance kernel.
The homogeneous distribution
(by Lemma
)
The signature distribution
Proposition
A further eigenvector of the Cayley distance kernel is with corresponding eigenvalue
(7)
Proof
That this is an eigenvector follows from the following calculation:
The component of the image of this vector is
This follows from the right invariance of the Cayley distance (here) and the fact that is a multiplicative character, . Thus is an eigenvector and the corresponding eigenvalue equals the signed sum of, in particular, the first row of the Cayley distance kernel. This is as claimed by Lemma .
Lemma
(signed sum over first row of Cayley distance kernel)
For , the sum over the first row of the signed Cayley distance kernel (Def. ) equals
Proof
We compute as follows:
where:
Lemma
The sign of the eigenvalue (7) of the signature distribution is as follows:
(8)
Proof
Since the prefactor in (7) is always positive, we need to equivalently discuss the sign of the polynomial
Here the first two statements are immediate. For the last last statement, observe that all roots of the polynomial appear with unit multiplicity, so that the polynomial must change sign as crosses over any of its zeros. Therefore the value which is positive for , by the first statement, must become negative as drops below , then positive again as it drops below the next zero at , and negative once more as drops below , and so on.
General eigenvectors
The general eigenvectors and eigenvalues of the Cayley distance kernel are given as explicit expressions in the irreducible characters of the symmetric group, by the character formula of Cayley graph spectra:
To be able to apply this formula, one just has to observe that the exponentiated Cayley distance in a single variable
is a class function for all , which is immediate by Cayley’s observation that .
It thus follows from the general character formula and the representation theory of the symmetric group (here) that:
We further characterize these eigenvalues (Prop. below) at the special inverse temperatures of the form . First we need some notation and a lemma:
Definition
(notation for sets of semistandard Young tableaux)
For , write
for the set of semistandard Young tableau
-
with boxes, and
-
all labels .
Moreover for write
for the subset on those tableau whose underlying Young diagram corresponds to the partition .
This is the statement of Gnedin, Gorin & Kerov 11, Prop. 2.4 (with notation from Prop. 2.1).
Proposition
(Eigenvalues of Cayley distance kernel at count semistandard Young tableaux)
For and , the th eigenvalue (9) of the Cayley distance kernel at on is proportional to the number of semistandard Young tableaux (Def. )
(12)
Proof
We compute as follows:
Here
Alternatively, using Lemma we may compute as follows:
Here the first line is the character expression (10) of the eigenvalues from Prop. . The second line passes to the complex conjugation using that all eigenvalues are real (the Cayley distance kernel being a real symmetric matrix). The fourth step inserts the character formula from Lemma . The last step follows with Schur orthogonality (this equation).
As a corollary we obtain:
Proposition
(non-negativity of Cayley distance kernel at log-integer inverse temperature)
For the Cayley distance kernel at with :
-
all eigenvalues (9) are non-negative
-
zero is an eigenvalue for
-
all eigenvalues are positive if :
Proof
By (12) in Prop. the eigenvalues at count possible numbers of colorings of Young diagrams to semistandard Young tableaux (ssYT). This gives the first statement.
Since in a ssYT the labels must strictly increase downwards, there is no possible ssYT-coloring if there are fewer labels than rows. This gives the second claim.
But conversely, since in an ssYT the labels may be constant horizontally, there is at least one coloring once there never are more rows than labels. This gives the last claim.
We give further combinatorial expressions of the eigenvalues of the Cayley distance kernel, using the hook length formula and the hook-content formula:
Proposition
(Eigenvalues of Cayley distance kernel via hook-content formula)
The eigenvalues (10) of the Cayley distance kernel for all may be expressed as:
The following proof was pointed out by
Abdelmalek Abdesselam.
Proof
By Prop. the th eigenvalue at integer values
is a positive multiple of the number of semi-standard Young tableau, and hence is given by the hook-content formula, as follows:
We may regard this set of equations as the specialization of the following more general equation
to all integer values of . But since both sides of this equation are polynomials in – the right hand manifestly so, the left hand side by (10) – the fact that the equation holds at infinite many distinct points implies that in fact it holds for all .
In fact:
Proposition
(Eigenvalues if Cayley distance kernel in terms of just box content)
The Eigenvalues (10) of the Cayley distance kernel for all may be expressed as:
This is essentially, the result of
Jucys 71, see at
Jucys-Murphy element.
Proof
The point is that the hook length formula (see here) also gives the dimension of the irreps of the symmetric group:
Using this, we compute as follows:
Here the first line is Prop. and the second step inserts (13).
Dual basis
We make explicit the inner product with respect to which the Cayley distance kernel is a hermitian matrix:
Definition
(Cartesian inner product)
Let
denote the sesquilinear form induced by the canonical linear basis of the linear span .
Proposition
(dual eigenvector basis)
With respect to the Cartesian inner product from Def. , the eigenvectors (11) from Prop. have a dual basis given by
(14)
Beware that the original eigenvector basis
(11) already involves the
complex conjugate of component entries.
Proof
This is a restatement of the Schur orthogonality relation for irreps, here for the Specht modules :
We compute as follows:
Here the first step unwinds the definitions (using (14) and (11) in Def. ), and the last step is the grand Schur orthogonality relation (?).
Positivity
We discuss at which values of the inverse temperature , the Cayley distance kernel on is, as a bilinear form, indefinite or positive (semi-)definite.
Indefiniteness for
Proposition
For all and all , the Cayley distance kernel fails to be positive semi-definite on .
Proof
By Example the statement holds for . But the kernel for this case is a principal submatrix of the kernels in all other cases (see this Prop.), and positivity fails as soon as it fails on any principal submatrix. (This is immediate from the definition, but also a direct consequence of Cauchy's interlace theorem.)
More generally:
Proposition
The Cayley distance kernel (Def. ) on is indefinite for all
or equivalently:
For the Cayley distance kernel is indefinite except possibly at integer values.
Proof
With the third statement in Lemma the claim follows for every second open unit interval between 0 and . But by the same argument the analogous statement is then true on every other of these unit intervals for the kernel on . Now since the kernel on is a principal submatrix of that for (see this Prop.), the Cauchy interlace theorem implies that the kernel on must have a negative eigenvalue as soon as that on does.
Semi-definiteness for
Lemma
For all the eigenvalues of the Cayley distance kernel on are non-negative and for they are all positive.
Proof
We observe that the eigenvalues at these particular values of appear, up to a positive multiple, as coefficients of monomials in Schur polynomials, but all such coefficients are non-negative integers (this Prop.).
Concretely, for any partition of , with corresponding Schur polynomial and irreducible Specht character , consider the following computation:
(15)
Here we used:
-
the Frobenius formula for Schur functions (this Prop.);
-
some evident re-arrangements;
-
the character formula for the eigenvalues (this Prop).
This shows the first part of the statement. Finally, that the eigenvalues for are in fact positive follows since in this case all the arguments on the top left of (15) are non-vanishing, so that none of the monomials contributing to vanishes.
Proposition
For the Cayley distance kernel is positive semi-definite.
For it is positive definite.
Proof
By Lemma the eigenvalues at all these values are non-negative and positive for the special case , while by Lemma they do contain 0 away from this special case.
Alternatively, this follows from Prop. .
Definiteness for
Proposition
The Cayley distance kernel on is positive definite for all .
Proof
By Prop. the CD kernel on is positive definite at , which holds for all . But the CD kernel in question is a principal submatrix of this positive one (see this Prop.), and hence cannot be less than positive itself, by the Cauchy interlace theorem.
Alternatively, this follows from the third clause of Prop.
Definiteness for
Proposition
The Cayley distance kernel on is positive definite for .
Proof
With the th eigenvalue expressed either via Prop. or Prop. , it is manifest that a sufficient condition for their positivity is clearly that
for all that appear in the product, hence that
for all that appear. But the index labels the rows of Young diagrams of boxes, and hence the condition is that
The following is an alternative proof of a much weaker lower bound, not relying on the hook-content formula from combinatorics, but on the Gershgorin circle theorem from analysis:
Proposition
A sufficient condition for the Cayley distance kernel (Def. ) on to be positive definite is that its inverse temperature satisfies the following inequality:
(16)
Proof
By the Gershgorin circle theorem and using Prop. , all the eigenvalues of the kernel are within a distance (6) from its diagonal values, which are all equal to . Since, moreover, all eigenvalues are real, the condition
(17)
implies that all eigenvalues are contained in the interval and hence in particular that they are positive.
Proof
First consider the case of :
In the given case (18) the Gershgorin bound (16) for positive semi-definity of the Cayley distance kernel reads
and hence may equivalently be expressed as
(19)
With the evident bound
the condition (19) is satisfied as soon as
Now to improve this to : Since we may assume that at least , we know that the eigenvalues of the homogeneous distribution (Example ) and of the signature distribution (Prop. ) are non-negative (by Lemma ). But by the character formula for Cayley graph spectra (this Prop) these are precisely the two eigenvalues with unit multiplicity. Therefore a strengthening of the Gershgorin circle theorem applies to all the remaining eigenvalues, saying (this Prop.) that these are in fact within half the Gershgorin radius (6). This allows us to put a factor of 1/2 on the left hand side of the first row of (17), which amounts to replacing the “2” by a “3” on the right of the second row.
Cayley state on the group algebra
under construction
We observe that for integral or greater than , the Cayley distance kernel defines a quantum state (in the sense of state on a star-algebra)
on the group algebra canonically regarded as a star algebra. Then we exhibit it as a mixed state given by a probability distribution on pure states which are labeled by standard Young tableaux.
unpolished notes
The algebra
We regard the linear span as equipped with the sesquilinear form given by
We regard any linear endomorphism on the linear span as a matrix with respect to the canonical linear basis
We denote matrix multiplication by “”, so that
Next, with regarded as the group algebra, we will write the algebra product as .
This way, for and with any element of the group algebra conflated with the endomorphism of left multiplication by this element, we have
Notice that in this notation
reflecting that is a cyclic vector.
Finally, we consider as a complex star-algebra via
Noticing
we see that
and so that
is a homomorphism of complex star-algebras.
The state
For
a state on this algebra is given by sending any
to
This is indeed a state, because
by left-invariance and by positive (semi-)definity of the Cayley distance kernel at the given .
Idempotent decomposition
Regarding as the regular representation of it decomposes into irreps (Specht modules) with multiplicity their dimension.
For and write
for the linear projection onto the linear span of
Thus
Notice that each is a left ideal of the group algebra:
Hence
is a decomposition into left ideals.
In fact, this is a decomposition into minimal ideals:
The minimal left ideals of any complex group algebra are labeled by pairs consisting of an irrep and a left ideal in the linear endomorphism algebra (by this Prop.). The latter is isomorphic to a matrix algebra and hence its left minimal ideals are the -many single-column matrixes. Therefore minimal ideals in are labeled by pairs consisting of an irrep and a postitive natural number no larger than the dimension of the irrep. This is the same number/cardinality of ideals we found above, hence they must already be minimal.
(It’s also the same number of primitive idempotents as used in the discussion of Jucys-Murphy elements, see there.)
This decomposition of the group algebra into left ideals implies that for all we have
Moreover, we have
by the fact that the are eigenvectors of the Cayley distance kernel.
Finally, we have
hence
(by grand Schur orthogonality, see this Prop.).
The mixture
Using the above properties of the projectors , we observe that each
is still a state:
It follows that we have decomposed our state into a convex combination of other states as follows:
(20)
where
Claim. The are pure states.
This must hold because the are minimal ideals, by the discussion above, whence the projectors are given by left multiplication with primitive idempotents in the group algebra. Under the GNS construction, these correspond to projectors onto 1-dimensional subspaces, hence to pure states.
But this means that (20) exhibits our state as a mixture in which the th pure state appears with probability .
The probability distribution
Now to express these probabilities more explicitly:
First observe the expansion of the neutral element in our eigenvector basis, evident from Schur orthogonality:
But this means that
and so the probabilities are:
As a sanity check, we have unit total probability:
In fact, by (12) in Prop. this is the probability distribution on Young diagrams with boxes proportionate to their number of semistandard Young tableaux with labels bounded by :
(21)
If follows that the pushforward of this probality distribution along the forgetful function
(22)
is
This is the Schur-Weyl measure.
Since the Cayley measure is constant on the fibers of (22) it is exactly that probability distribution on standard Yound tableaux which maximizes the entropy subject to the condition that the pushforward to Young diagrams is the Schur-Weyl measure.
Entropy of the Cayley state
Now to compute the von Neumann entropy of the Cayley state, hence the Shannon entropy of the above probability distribution:
as a function of .
Recall the bounds
Hartley entropy Shannon entropy min-entropy.
Hartley entropy
Observe that a Young diagram (partition) admits a decoration to at least one semi-standard Young tableau with labels bounded by if and only if it has at most rows.
Therefore the Hartley entropy of the probability distribution (21) is the logarithm of the number of standard Young tableaux with boxes and at most rows:
For discussion of these numbers see there.
(…)
References
Mentioning of the Cayley distance kernel:
-
Michael A. Fligner, Joseph S. Verducci, Section 4 of: Distance Based Ranking Models, Journal of the Royal Statistical Society. Series B (Methodological) Vol. 48, No. 3 (1986), pp. 359-369 (jstor:2345433)
-
Persi Diaconis, Phil Hanlon, Section 4 of: Eigen Analysis for Some Examples of the Metropolis Algorithm, in Donald Richards (ed.) Hypergeometric Functions on Domains of Positivity, Jack Polynomials, and Applications, Contemporary Mathematics Vol. 138, AMS 1992 (doi:10.1090/conm/138, EFS NSF 392, pdf)
-
Michael A. Fligner, Joseph S. Verducci (eds.), p. xx of: Probability Models and Statistical Analyses for Ranking Data, Lecture Notes in Statistics 80, Springer 1993 (doi:10.1007/978-1-4612-2738-0)
The above discussion of the positivity of the Cayley distance kernel in dependence of the inverse temperature follows:
Further computations in:
Related discussion in:
- Iskander Azangulov, Viacheslav Borovitskiy, Andrei Smolensky On power sum kernels on symmetric groups [arXiv:2211.05650]
Supplementary references:
-
Petteri Kaski, Eigenvectors and spectra of Cayley graphs, 2002 (pdf, pdf)
-
Richard Stanley, Enumerative combinatorics – Volume 1, Wadsworth & Brooks/Cole Mathematics Series book series 1986, 1997 (doi:10.1007/978-1-4615-9763-6) reprinted in: Cambridge Studies in Advanced Mathematics, Cambridge University Press 2011 (ISBN:9781107602625, pdf)
-
Alexander Gnedin, Vadim Gorin, Sergei Kerov, Block characters of the symmetric groups, Journal of Algebraic Combinatorics, 38, no. 1 (2013), 79-101 (arXiv:1108.5044, doi:10.1007/s10801-012-0394-9)