Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This problem arises while studying the complexity of algorithms and I am quite unfamiliar with the subject.

Consider the set F of injective functions from {1..N} to {1..M}

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$.

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.

Q1: Has this association scheme ever been studied? What is its name?

Q2: Can this scheme be obtained by a combination (tensor product? suprema?) of the Johnson scheme and another quantity?

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.

Q3: How can we construct/characterize these eigenspaces?


Some background on Association Schemes.

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 )$

The matrices $A_i$ can be seen as adjency matrix for some graph (but I don't think it might help here)

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.


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$.


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$}.

$[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$.

share|improve this question
As an aid toward bringing many heads on the topic, perhaps you could add some background information. For example, listing the properties of an association scheme, providing the definition of a Johnson scheme, and including enough operational information on the 'Bose-Mesner Algebra point of view' so that we might see how it applies. Lacking any of this information, my guess is that clarity will come from comparison of the classes of both schemes. I don't yet know enough to see what will be matrix elements, much less eigenspaces. Gerhard "Ask Me About System Design" Paseman. 2010.07.24 –  Gerhard Paseman Jul 25 '10 at 2:51

1 Answer 1

up vote 3 down vote accepted

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.

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.

for what it's worth, I think there's a chance that getting the decomposition is actually doable, but it would not be quick :-(

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.