Permutations

Many tensors possess symmetry such that swapping two (or more modes) results in the same tensor. For example, consider the matrix \(A\) given by:

\[\begin{split}A = \begin{pmatrix} 1 & 2\\ 2 & 3 \end{pmatrix}\end{split}\]

If we declare another matrix, \(B\), such that rows of \(B\) were the columns of \(A\) we get:

\[\begin{split}B = \begin{pmatrix} 1 & 2\\ 2 & 3 \end{pmatrix}\end{split}\]

i.e., \(A=B\) and we say that \(A\) (or \(B\)) is symmetric with respect to permuting modes 0 (the rows) and 1 (the columns). Permutations are a key component of describing tensor symmetry and this page reviews the math behind them.

Terminology

Many of these definitions rely on the algorithm needed to reorder a set of objects \(I\) into \(I'\). Assuming there are \(n+1\) elements in \(I\) the algorithm is:

  1. Set \(i\) to 0.

  2. If \(i\) is \(n+1\) terminate.

  3. If \(I_i\) (the \(i\)-th element of \(I\)) is in the correct spot increment \(i\) and return to step 2.

  4. Let \(j\) be the correct position for \(I_i\), swap \(I_i\) and \(I_j\). The element which was previously \(I_i\) is now in its correct spot. Return to step 3 with the realization that the current \(I_i\) is now the element which was \(I_j\).

cycle

A “cycle” is a series of transpositions needed to get each element in a given orbit into its correct position. Cycles involving more than two elements are not unique as the transposes can be done in different orders.

cyclic permutation

A permutation which can be written as a single cycle. All permutations can be decomposed into one or more cyclic permutations.

noncyclic permutation

A permutation which can not be written as a single cycle.

orbit

For a given \(i\) the algorithm above will cause one or more elements to be labeled as \(I_i\). The set of elements which can be labeled as \(I_i\) defines the orbit of \(I_i\).

permutation

A particular ordering of a set of objects. “Permuting” is the act of going from one permutation to another.

transposition

Swapping two objects.

Notation

Having to write “permute mode 0 with mode 1” is already tedious and becomes more tedious when more modes are involved. One common notation for writing a permutation is “cycle notation”. For a cyclic permutation involving \(n+1\) objects the cycle is written like \((e_0, e_1,..., e_n)\) where \(e_i\) is the index of the \(i\)-th object BEFORE the permutation and \(e_{i+1}\) is the index of \(e_{i}\) AFTER the permutation (except for \(e_{n}\) which becomes \(e_0\)).