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?