It is well-known how to count all possible distinct patterns of an one-dimensional array arising upon permutations of its elements. The number is given by the multinomial coefficient: $$ \binom{n}{n_1,n_2,\dots,n_k}\tag1 $$ where $n_i$ are number of (indistinguishable) elements of type $i$ and $n=\sum_i n_i$ is the overall number of elements in the array. For simplicity we will assume that the element types are numbered and an element of a type is just the number assigned to the type.

It is often required to compute an additive function of a vector (aka one-dimensional array) which is invariant with respect to a permutation of the vector components. The recipe in this case is clear:

  1. choose a representative for the set of similar vectors;

  2. compute the function for the representative;

  3. multiply the result by $(1)$.

Probably the simplest representative in one-dimensional case is the ordered set of elements: $$ a_1\le a_2\le\dots\le a_n\tag2. $$ The "$<$" signs separate the groups of identical elements, so that $(1)$ can be easily applied to compute the number of the arrays similar to $(2)$.

The story becomes however more complicated for multidimensional arrays of dimension $$\underbrace{n\times n\times\cdots \times n}_{k\text{ times}}\equiv n^k. $$ The arrays are assumed to be symmetric, i.e. $a_{\sigma(i_1,i_2,\dots,i_k)}=a_{i_1,i_2,\dots,i_k}$, where $\sigma$ is any permutation of the indices. Further it will be assumed that all elements with repeating indices are identical ($=0$). Otherwise the problem can be easily reduced to corresponding subspaces.

Two arrays are considered to be permutationally similar (or simply similar) if there is a permutation of indices that maps one array onto the other. In general every permutation of indices will produce a new array. However in some cases the number of similar arrays will be reduced. The most extreme case is the array with all elements being equal, so that any permutation results in the same array. In all other cases the reduction of the number of similar arrays will be only partial (if any).

To visualize the issue let us consider the two-dimensional case, which corresponds to symmetric matrices with zero diagonal elements. To obtain the same matrix two indices can be permuted only if both rows (columns) contain the same elements. If the order of the elements in both rows is not the same, an additional permutation of the columns containing the mixed up elements is needed which is however not always possible as demonstrated by the following example: $$ A:\begin{pmatrix} 0&1&2&3&4\\ 1&0&2&4&3\\ 2&2&0&5&5\\ 3&4&5&0&6\\ 4&3&5&6&0 \end{pmatrix},\quad B:\begin{pmatrix} 0&1&2&3&4\\ 1&0&2&4&3\\ 2&2&0&5&7\\ 3&4&5&0&6\\ 4&3&7&6&0 \end{pmatrix}. $$

Whereas the matrix $A$ maps onto itself by permutation $\{1\leftrightarrow2, 4\leftrightarrow5\}$, there is no (distinct from identity) permutation mapping $B$ onto itself. Therefore, the number of matrices similar to $A$ and $B$ are $N_A=\dfrac{5!}2=60$ and $N_B=5!=120$, respectively.

And now come my questions (motivated by the one-dimensional case):

  1. Is there a simple way to find the number of all permutations of indices which map a matrix onto itself?

  2. Is there a simple and unique way to choose a representative for any set of similar matrices?

  3. Can the representative be chosen in a way that facilitate the finding the answer to the first question?

The aim is to generate the complete list of representatives (with known degeneracies) for any external rule of generating the array elements. The rule is assumed to be permutationally symmetric (i.e. if an array satisfies the rule any similar array does it as well).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.