Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
for completeness, to go alongside Mallows kernel
added statement and proof (here) that the Gershgorin radii of the Cayley distance kernel are all equal to
Things about other rows need saying, e.g., how is a homomorphism, etc., but I see that Urs is on the page now.
Thanks! I am done editing. Have just given it a Prop-environment and added some words on the proof.
By the way, I got stuck with understanding the “quite nice proof” (according to one MO contributor) on math.se (here) of that Lemma.
It starts out sounding really plausible, but when trying to write out this proof idea formally as a nested sum of permutations with increasing lower bound on their numbers of cycles, I got stuck.
Stanley, in contrast, offers no less than four different proofs for this Lemma, none of which is as easy-looking as the “quite nice proof” on math.se . Makes me wonder if it’s maybe too nice to be true.
A bit heuristic, but maybe it does work. Imagine doing this for
1 is placed in the first cycle:
2 either starts a new cycle or is placed in the same cycle as 1:
3 either starts a new cycle or is fitted in an existing cycle. Either option from 2, there are 2 ways to place 3:
and so on.
When adding a new element to existing cycles, one has to see that there are choices, however the previous construction has gone.
E.g if (12)(3) or (1)(2)(3) or (123), etc. then there are 3 places to add 4.
So that’s what the math.se author says. I see the logic in what he says, but not how this proves the lemma at hand:
First: we are counting acual permutations, not their conjugacy classes.
Second: You follow them in the vague “this gives ”, or even just “colon ”, which is not a formalizable instruction.
Maybe these two ways of waving our hands somehow cancel out, but I don’t see it yet.
The actual problem at hand is to manipulate the sum
One way I can see to start out following the proof idea is to say: Every permutation has at least one permutation, so we can pull out a factor and write
And then the idea would be to iterate this process on the first inner sum (pull out another factor of , get a sum over permutations with strictly more than 2 cycles and a constant number of permutations with strictly 2 cycles).
This is beginning to roughly look like the kind of expression we are after. But not quite.
Anyway, we don’t have to worry about this, as we have four good alternative proofs by Stanley.
The point ’First’ is wrong. Hand-waving it may be, but it’s counting actual permutations.
Maybe one way to go is to look at the expansion of taking it as .
Claim, any term in the polynomial expansion corresponds to a unique permutation.
Any such term is a sequence of s and s, where the latter appearing in the th place are indexed by a natural number between and .
Each of these is a recipe to form a unique permutation on elements. If appears times, there are cycles.
E.g., for , given , we form (132)(45).
In the other direction, given any permutation, arrange it so that for each cycle the lowest element heads it. Arrange cycles in order of the first entry.
Then passing through to , build a term of s and indexed s, according to whether a given heads a new cycle, , or occurs in the th available spot, . There are such available spots.
Sorry, I still need to ask: Why is your example not ?
What’s an “available slot”? If an element doesn’t start a new cycle, then we need to know (a) which of the existing cycles it is part of, and (b) in which position it occurs there.
Oh, I think I see it. Let me try to write it out as a proof…
The math.se answer puts it well enough. Placing the number , then look at the th term. If , start a new cycle; if , place in the cycle containing to the right of it.
I was missing that we are looking at the underlying list obtained from normalized cycle notation by forgetting the brackets. I am writeing a proof that makes this explicit in usual mathematical proof style, so that even a dense person can follow it.
with that issue out of the way, further towards the question of positivity, I have added expression of the resulting sufficient Gershgorin bound for the Caylest distance kernel on to be positive at inverse temperature :
If I see correctly, the (sufficient) condition is that:
Still need to prove that this has a solution for all ….
Maybe better to express this as follows, which makes it more manifest that this always has a solution for large enough :
Stirling approximations come to mind.
Or, pottering about
is which is certainly less than .
Which clearly would be fine for . If that’s right.
Thanks. I am feeling dizzy. I”ll better call it quits and get some sleep.
Sleep well.
I feel sure there’s something clever to say about the eigenvalues of this kernel. Seems close to the character theory of . But maybe if Carlo achieves a symbolic computation for that will be enough to show the pattern.
I thought you’d gone to bed! I need to tweak my proof but you’ve locked the page. So later, unless you do it first.
Just spotted a typo from my phone, over dinner. :-)
I added something
Since this result relies on being a multiplicative character, and the only multiplicative characters of a symmetric group are the trivial one and the sign, the other eigenvectors must be found by other means.
other eigenvectors then. Looking at the WolframAlpha calculation for , it seems clear that these other eigenvectors will be sparse, in this case pairs of points in the Cayley graph equidistant from every other point.
If we want more results as in #31, then from section 4, knowing that in the case of , is an eigenvalue means that semi-positive definiteness fails in the range , and indeed for .
Hmm, but then why can’t we replay your principal submatrix idea?
If for , this eigenvalue is negative , and for , it’s and , doesn’t the carry through from the former case to the latter?
Is that completely obvious this result about preserving distances. Yes, one doesn’t need to use transpositions from outside , but still it might be quicker to do so.
But then of course we know from the formula that distances are preserved since as increases by , one more cycle is added under .
Re #33, #34: Good point, I have now changed the proof as you suggest, here
Continuing #32, that must be right: for , positive semi-definiteness fails for , except for integral values of .
Yes, with Carlo we just had a similar discussion, from looking more at the fomulas for the eigenvalues:
Apparently something really interesting happens in between the two bounds for the Cayley distance kernel that we established:
We know
it’s indefinite for
it’s positive definite for
so it might be tempting to speculate that this is a monotonic situation. But far from it: Beyond these two extremes, apparently the Cayley distance kernel oscillates between indefniteness and positive definiteness, passing through positive semi-definity exactly (apparently) at the first few integer values of .
Well, according to #36, it’s touching positive semi-definiteness at integer values, and then reverting to indefiniteness, never achieving positive definiteness untli after . (Well, strictly I don’t even know that, but it’s at least as bad as that.)
Okay, I see, I was looking at another eigenvalue, thinking for a while it’s the smallest one. But yeah, that’s a good point worth recording…
Good. So the first two are no surprise, here.
What can we learn from the others? Low integer solutions.
no surprise
I am impressed by how you are doing this. You should record/explain that in the entry?
Can you see why these would necessarily have multiplicity 1, apparently?
Namely if we knew that (as seems to be the case) it is exactly these two types of eigenvalues that appear with unit multiplicity, then we could use the enhanced Gershgorin theorem of arXiv:1609.07439 to constrain away the rest in a smaller Gershgorin disc, and thus possibly get a tighter lower bound on at which the kernel becomes positive for good.
Okay, I checked out a table of conjugacy classes of (here) in order to decypher your lists of numbers.
So I suppose the conjecture is that the first eigenvalue with multiplicity 1 is always given by the polynomial:
times
sum over conjugacy classes of
number of elements in each class
times to the power of
the product of the lengths of its cycles
?
And the second with multiplicity one by the corresponding alternating sum.
Ah, no, that’s not the rule.
I am stuck: What’s the rationale behind the item “8/4” in your string here?
The number in that conjugacy class, , so along with the 3 elements in class , that’s 11 elements at distance 2 from the identity.
Anyway, the multiplicity 1 eigenvalues, are those we know for the trivial eigenvector and . The former is always positive, a product with roots at negative integers; the latter is a product with roots at the first positive integers. So this gives alternating intervals as in #32.
I should think that then the other eigenvalues kick in to make the complementary intervals be non-positive definite. From what you found for , it seems the other eigenvalues are also products with roots at low integers, including a negative one.
Presumably the multiplicities are to do with the squares of the representations sizes, so for , .
There’s perhaps a way to go from a representation to a collection of eigenvectors all with the same eigenvalues.
I understand that you are adding the 3 elements of one conjugacy class to the 8 elements of another. What I am trying to ask is: Why, by which rule?
Could you just say what your rule is? In the form of #44. How do you determine which conjugacy class contributes to which power in the polynomial?
The distance to , so (n - #cycles). Of course, is a pair of cycles , so at distance from .
All due to Lemmas 4.2. and 4.10.
Maybe I have been chasing a shadow. You are just restating these Lemmas? I thought your symbols meant to hint at a conjectural pattern not yet captured by these. Okay, never mind then.
What more could you want? We know that the left hand sides of those lemmas are eigenvalues, we know for which eigenvectors, and we know how to factorise them in the right hand sides. So then we know for which values of they are negative.
What you need now is something similar for the other eigenvalues. It seems pretty clear that two of them will be products of for various integer values of . In the case we’re seeing and . I
It’s pretty clear that for positive until , positive semi-definiteness is achieved at integral values up to , otherwise non-positive definite. Then it turns positive definite thereafter.
I perfectly understand these lemmas, but was just trying to understand what seemed additional remarks you made that seemed mysterious to me. It might have added to the confusion that you mostly gave me verbless quarter-sentences as replies. But okay, that’s the perils of online communication. Glad it got clarified.
I am to bed now. Hoping to see you tomorrow in further unravelling this curious story.
Is the assumption still that ? Otherwise the plots show that is to be included in points of positive semi-definiteness.
Then, how to approach the eigenvectors other than the trivial one and sign? Did the calculation mentioned in #40 give the eigenvectors?
With one is just choosing pairs of points in the graph such that they are equidistant from the other four points.
Is the assumption still that ?
I haven’t changed it. And indeed, it still says so in the file (above (1)).
But it’s sure interesting to think about including the infinite-temperature case.
It remains to find proof of that equation
Probably best to multiply both side by , thus changing to on the right. Then the previous form of the Lemma applies with weight for each cycle and gives that the left hand side should be that sum with a prefactor of to the number of cycles plus (or minus) . Finally, if is even/odd, it must have an even/odd number of odd-length permutations, so that this last sign is equal to or minus the sign of to the number of even permutations, which is the signature.
I guess that should work. Will write out a clean proof…
Some random thoughts:
I seems suggestive that the lower bound for positivity we found is
while the actual lowest bound which is suggested by the explicit examples we have is
Maybe that similarity is just “symbology”, but it might suggest that the existing lower bound argument is on the right track and could be enhanced further.
If we knew that the two special eigenvalues, the homogeneous distribition and the sign distribution, were the only two of multiplicity 1, then we could use the improved Gershgorin circle theorem of arXiv:1609.07439 to reduce the Gershgorin disc radius by half.
Inserted into the previous argument this would give the bound
which is not much of an improvement. Instead of “3” we’d want . (They give a stronger reduction of the Gershgorin radius in their equation (3), but I am not sure if this can be put to use in our case.)
But then, the worst part of the estimate may not be the size of the Gershgorin radius, but the step where we approximate
because that approximation is good when is much larger than , while close to our expected actual bound, , both are comparable.
Maybe we need a more sophisticated estimate at this step.
My hunch is that one should pursue what is special about the combinatorics of , whatever it is that gives rise to results such as Lemma 4.1.
We have two eigenvectors based on multiplicative characters, which give rise to very neat factorisations of polynomials with low integer roots.
It look like the other eigenvectors are also connected to the representation theory of , looking at the multiplicities as squares of the representation sizes, and these seem to give rise again to neat factorisations of polynomials, with slightly shifted integer roots.
I think the eigenvalues expressed as polynomials in will have roots generalizing the pattern for of
.
This might even be construed as containing additional entries of ’0’, so
.
This tallies with the case with roots
which with the missing s is really
.
In sum, roots of eigenvalues will be sequences of integers as above.
Oh, why not just run the argument of Proposition 4.6, but instead of , choose a representation of dimension represented as an matrix. Then taking any of the components will give you an eigenvector.
That would explain the eigenvalue multiplicities so far, for , , for , .
I don’t think #63 quite works, but there should be something in this vicinity.
But off to do other things now - some metaphysics to supervise.
That seems a good observation about group representations!
It reminds me that the non-abelian Fourier transformation also involves casting Fourier dual data in terms of irreps, and then the non-abelian Bochner theorem applies to extract a condition for positive definite kernels from this. (I have so far only glanced over references for this non-abelian Bochner theorem, recordered here).
In total this may suggest that the answers we seek will be revealed under non-abelian Fourier transform.
But, me too I need to go slower on this now. Am still working on equivariant infinity-bundles on the side.
I have a feeling this is all worked out somewhere. How about this?
We’re dealing with what they call the adjacency matrix of a Cayley color graph (p.17). is a class function in our case, so Corollary 5.4 applies.
Ex 5.3 deals with symmetric groups and transpositions, but there of the adjacency matrix of Cayley graph rather than Cayley color graph.
The clues should all be in this paper.
Yes, Corollary 5.4 gives you all the eigenvalues if you know the characters:
A quick look at using #67, and it all seems to be working as predicted in #62.
Oh, wow. That would be the solution.
Googling for “eigenvalues Cayley graphs” gives various similar references, for instance
where the result you point to (their Theorem 2.1) is attributed to
No, their Theorem 2.1 is only for abelian groups where reps are 1-dimensional.
Theorem 2.2 concerns general finite groups.
We want Theorem 2.6.
The note after is relevant too. [Perhaps not so relevant since it concerns largest eigenvalue.]
Thanks, right. I should take time now to actually read this…
The discussion and proof in Section 4.1 of
is nice (clear and concise). For what it’s worth, they confirm (p. 40) the relation to the non-abelian Fourier transform as guessed in #65, even if they don’t expand on it.
Maybe we should record this in an entry Cayley graph spectra.
For what it’s worth, I have used the character formula for Cayley graph spectra to improve the lower bound on positivity (this Prop.) from to .
(Did this by appending a paragraph to the previous proof. Not the most elegant way to write this, but it should work.)
I think the next step is into the world of symmetric functions meets characters for . Some course notes are here.
the characters of irreducible representations correspond to Schur polynomials
So something like: for , the Schur function corresponding to rep is ,
where , for the cycle lengths in , and .
Then setting each as ,
So .
The RHS is close to what’s needed, so we just need to have a nice simple factorization.
Hmm, that only seems to allow as exponentiated by .
Anyway, something in this vicinity is right. But I have to something else now.
Oh, but why not then look at , the first entries being .
Then .
Thanks, looks promising!
So the idea now is that the Schur functions know the eigenvalues of the Cayley distance kernel at just those magical integer values (and at ) for which we still want to show that they are all non-negative (which will imply that they are all zero, by what we already know).
But wait, that’s the proof: The Schur polynomial is homogeneous, so your expressions in #79 vanish.
Hmm, but the example here has such that .
But certainly there will be plenty of 0 eigenvalues around, and the rest positive.
Oh, I see my mistake. Right. Need to spell this out for myself with more patience.
But let’s see:
It should be sufficient to know that the minimal eigenvalues at are non-negative to deduce that they vanish:
Because we already know that for they are negative, so by continuity they can at most become zero in between.
But we know that the character gives at these integers from Lemma 4.2. Presumably the associated Schur polynomial involves mononomials such as .
Not sure what then “but” refers to. I just meant to say that your argument seems to give the desired proof already even without needing to know anything further about the values of the polynomials, not needing my broken argument in #82.
True.
And that’s right about eigenvalues being non-negative at isn’t it? We just need the coefficient of the monomial to be non-negative, and that’s assured by the form of Schur polynomials as sums of terms as here.
I have now typed out (here) in full detail (with all lemma material behind hyperlinks) this proof that is positive semi-definite on for (and at least not indefinite for ).
This is great.
It is curious that, when we started this discussion last year, there was the worry that might not work for large , and now it’s instead the low values of for which we have proof that they work for all , while we have a gap of intermediate values for which we don’t know anything for sure yet.
Looking good!
Don’t we know that it’s positive definite for ? The Schur polynomial must be , for some positive integer .
Our suspicion is surely that it’s positive definite for .
My hunch is that where the eigenvalues for and are and , that the others are .
What about the principal submatrix idea?
Say for a given , I’m wondering about definiteness for , where . But if it were other than positive definite there, then for , it wouldn’t be positive definite at . But we know that this isn’t the case. So for , the kernel is positive definite for integer values .
Good point! Yes.
With that out of the way (!), it’s time to look again at Bar-Natan’s proof that all horizontal weight systems are partitioned Lie algebra weight systems (arXiv:q-alg/9607001), where he uses the fundamental -weight systems (which we now know are positive-semi definite) to build all other weight systems on horizontal chord diagrams.
The construction he uses is deeply permutation-theoretic, so your geometric group theory expertise might just keep applying if we now ask: Can we characterize the convex space of all semi-positive weight systems?
We now know that the convex span of the fundamental -weight systems is a convex subspace, and we know from Bar-Natan that the ambient linear space may neatly be expressed through just fundamental -weight systems (with bells and whistles added), so it is not out of the question that some geometric group theory keeps applying in this more ambitious question.
Sounds like this will need quite a lot more preparation.
We now know that the convex span of the fundamental -weight systems is a convex subspace
Is this written out somewhere?
This was the starting point of the note that got our discussion started here last year. But I’ll send you a polished update.
Let’s consider my hunch from above:
Just as the eigenvalues for and are and , the others are .
I guess in Lemma 4.12, we might as well use rather than , and so have .
So we know that and .
There’s plenty of structure on the Schur polynomials, when considering them as decategorified Schur functors.
There must be things to consider about how to combine reps, e.g., a partition of and a partition of combine to a partition of .
If my hunch is right then we’d be interested in how .
So for some , .
Come to think of it, the hunch wasn’t supposed to be precise, just some factors without their constants.
To try one out: in the rep corresponding to gives for : .
Looks good with a factor. Perhaps it’s a Littlewood–Richardson rule thing.
Thanks, interesting. How did you “try out” that example, though? Could you explain how you computed that eigenvalue polynomial for ?