I have recently proven the following (at least, so I believe):

Theorem. Given a permutation group $\Sigma\subseteq\mathrm{Sym}(\Omega)$ on the set $\Omega:=\{1,...,n\}$, the following are equivalent:

  1. the permutation character of $\Sigma$ is multiplicity-free, that is, it decomposes into distinct irreducible characters.
  2. the (self-paired) 2-orbits of $\Sigma$ (that is, its orbits on $\Omega\times \Omega$) define an association scheme.

I believe that this is known (if true). Has this result a name? Can someone point me to the literature proving/discussing/using this result? I am also grateful for a vague direction.


As pointed out by Tom De Medts, an alternative formulation is the following:

Theorem. Given a permutation group $\Sigma\subseteq\mathrm{Sym}(\Omega)$, the following are equivalent:

  1. the permutation character of $\Sigma$ is multiplicity-free.
  2. the association scheme formed by the 2-orbits of $\Sigma$ is commutative.

This claim can also be found in the beginning of Section 3 of Commutative Association Schemes by William J. Martin & Hajime Tanaka.


1 Answer 1


This is indeed known, and can be found, for instance, in the book "Algebraic combinatorics. I. Association schemes" by Bannai and Ito (1984), Section II.2, Example 2.1 (p. 53).

enter image description here

  • $\begingroup$ Thank you! I do not have access to the book right away, so let me ask: is this still true when the 2-orbits are not necessarily self-paired? $\endgroup$
    – M. Winter
    Feb 24, 2021 at 14:06
  • $\begingroup$ That is strange. On the one page available here, Example 2.3 states that the 2-orbits form an association scheme if $\Sigma$ acts transitively, no matter whether it is multiplicity-free. Isn't this in contradiction to what I claim in the question? $\endgroup$
    – M. Winter
    Feb 24, 2021 at 15:01
  • $\begingroup$ I assume that the difference lies in your definition of association scheme: Bannai and Ito consider not necessarily commutative association schemes, whereas other sources assume commutativity as part of the definition. Does this help? $\endgroup$ Feb 25, 2021 at 16:34
  • 1
    $\begingroup$ @M.Winter My apologies for being somewhat imprecise. I have now included a screenshot of the relevant 2 half pages of the book. In particular, you can see how both conditions come into play: commutativity corresponds to the permutation character being multiplicity-free, whereas symmetry corresponds to the 2-orbits being self-paired. $\endgroup$ Feb 28, 2021 at 10:29
  • 1
    $\begingroup$ Thank you! This was incredibly helpful! $\endgroup$
    – M. Winter
    Feb 28, 2021 at 10:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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