Association scheme on injective functions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T17:33:44Z http://mathoverflow.net/feeds/question/32999 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/32999/association-scheme-on-injective-functions Association scheme on injective functions Loick 2010-07-22T20:15:27Z 2010-07-28T12:49:31Z <p>This problem arises while studying the complexity of algorithms and I am quite unfamiliar with the subject.</p> <p>Consider the set F of injective functions from {1..N} to {1..M}</p> <p>we can define an association scheme on F x F by (f,f') and (g,g') are in the same class if there is a permutation $\pi\in S_M$ and a permutation $\tau \in S_N$ such that $g = \pi \circ f \circ \tau$ and $g' = \pi \circ f' \circ \tau$.</p> <p>I checked that this really defines an association scheme. In a way it is an "ordered" version of the Johnson scheme. It seems to me that it is a natural extension of the Johnson scheme, but I did not find any reference about it.</p> <blockquote> <p>Q1: Has this association scheme ever been studied? What is its name?</p> <p>Q2: Can this scheme be obtained by a combination (tensor product? suprema?) of the Johnson scheme and another quantity?</p> </blockquote> <p>More precisely, I am interested in the "Bose-Mesner Algebra" point of view on this scheme. It is known that all the matrices in the algebra defined by this association scheme diagonalize in the same basis.</p> <blockquote> <p>Q3: How can we construct/characterize these eigenspaces? </p> </blockquote> <p>--</p> <p>Some background on Association Schemes.</p> <p>An association scheme is a set of symmetric boolean matrices $A_1, \dots , A_S$ such that 1) $\sum_{i=1}^s A_i =J$ the all-one-matrix 2) $A_1 = I$ the identity matrix 3) $\forall i,j \; A_iA_j \in {\rm span} ( A_i )$</p> <p>The matrices $A_i$ can be seen as adjency matrix for some graph (but I don't think it might help here)</p> <p>The span{$A_i$} defines an algebra called the Bose-Mesner Algebra. Condition (3) implies that all matrices commute so they diagonalize in the same basis.</p> <p>--</p> <p>In the case I'm considering here, the dimension of the $A_i$ is ${M \choose N}N!\times {M \choose N}N!$. The $A_i$ are not explicitly defined but we know that $[A_i]_{fg}=[A_i]_{f'g'}$ if there is a permutation $\pi\in S_M$ and a permutation $\tau \in S_N$ such that $g = \pi \circ f \circ \tau$ and $g' = \pi \circ f' \circ \tau$.</p> <p>--</p> <p>About the Johnson scheme: The $A_i$ have size ${M \choose N}$. The rows and the columns of the matrices are labeled by subsets of size $N$ of {$1,\dots,M$}. (in my case, the labels are injective functions, ie. ordered sets of subsets of size $N$ of {$1,\dots,M$}.</p> <p>$[A_i]_{ab}=[A_i]_{a'b'}$ if there is a permutation $\pi\in S_M$ such that $\pi(a) = a'$ and $\pi(b) = b'$. (where $\pi(a)$ denotes the subset of {$1,\dots,M$} obtained by applying the permutation $\pi$ to the elements of the sets $a$.</p> http://mathoverflow.net/questions/32999/association-scheme-on-injective-functions/33651#33651 Answer by Chris Godsil for Association scheme on injective functions Chris Godsil 2010-07-28T12:49:31Z 2010-07-28T12:49:31Z <p>I don't think this scheme has a particular name, and am not aware of any study of it. Its Bose-Mesner algebra is the commutant of a multiplicity-free representation of the wreath product of $S_m$ by $S_n$. To get the eigenspaces you need to find the decomposition of the representation into irreducibles.</p> <p>The most useful reference I know is "Harmonic Analysis on Finite Groups: Representation Theory, Gelfand Pairs and Markov Chains" by Ceccherini-Silberstein, Scarabotti and Tolli.</p> <p>for what it's worth, I think there's a chance that getting the decomposition is actually doable, but it would not be quick :-(</p>