The symmetric functions catalog

An overview of symmetric functions and related topics

2023-11-06

Permutation matrices

For permutations $\pi,\sigma \in \symS_n,$ we think of multiplication as composition of functions, so that

\[ (\pi \circ \sigma)(k) = \pi(\sigma(k)) \text{ for $k \in [n].$} \]

Given $\pi,$ we associate its permutation matrix,

\[ P_\pi = \left( \delta_{i, \pi(j)} \right)_{1 \leq i, j \leq n}. \]

The permutation matrix of the composition $\pi \circ \sigma$ is $P_{\pi} P_{\sigma}.$ We follow the convention in [Kit11] and illustrate permutation matrices by letting row indices start at the bottom, as in the figure below. From now on, this is the picture we have in mind when referring to permutation matrices.

Example.

The permutation matrix $P_\pi$ associated with $\pi = [1, 8, 5, 3, 7, 4, 6, 2]$ using conventional row/column coordinates, and the convention we use. The rightmost figure is simply the graph of the function $i \mapsto \pi(i)$ (using Cartesian coordinates).

$ P_\pi = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix} $
$ 8$$\,$$\bullet$$\,$$\,$$\,$$\,$$\,$$\,$
$ 7$$\,$$\,$$\,$$\,$$\bullet$$\,$$\,$$\,$
$ 6$$\,$$\,$$\,$$\,$$\,$$\,$$\bullet$$\,$
$ 5$$\,$$\,$$\bullet$$\,$$\,$$\,$$\,$$\,$
$ 4$$\,$$\,$$\,$$\,$$\,$$\bullet$$\,$$\,$
$ 3$$\,$$\,$$\,$$\bullet$$\,$$\,$$\,$$\,$
$ 2$$\,$$\,$$\,$$\,$$\,$$\,$$\,$$\bullet$
$ 1$$\bullet$$\,$$\,$$\,$$\,$$\,$$\,$$\,$
 $ 1$$ 2$$ 3$$ 4$$ 5$$ 6$$ 7$$ 8$

Permutation patterns

A permutation $\pi \in \symS_n$ is said to contain the pattern $\sigma \in \symS_k,$ if there is a subsequence of $\pi$ which is order-isomorphic to $\sigma.$ For example, $\pi = [1, 8, 5, 3, 7, 4, 6, 2]$ contains the pattern $[2,3,1]$ as the subsequence $3, 6, 2$ in $\pi$ have its elements in the same relative order.

Example.

The permutation matrices associated with $\pi = [1, 8, 5, 3, 7, 4, 6, 2]$ and $\sigma = [2,3,1].$ Here we see that $\pi$ contains the pattern $\sigma$ (there are other instances of this pattern in $\pi$).

$\,$$\bullet$$\,$$\,$$\,$$\,$$\,$$\,$
$\,$$\,$$\,$$\,$$\bullet$$\,$$\,$$\,$
$\,$$\,$$\,$$\,$$\,$$\,$$\odot$$\,$
$\,$$\,$$\bullet$$\,$$\,$$\,$$\,$$\,$
$\,$$\,$$\,$$\,$$\,$$\bullet$$\,$$\,$
$\,$$\,$$\,$$\odot$$\,$$\,$$\,$$\,$
$\,$$\,$$\,$$\,$$\,$$\,$$\,$$\odot$
$\bullet$$\,$$\,$$\,$$\,$$\,$$\,$$\,$
$\,$$\bullet$$\,$
$\bullet$$\,$$\,$
$\,$$\,$$\bullet$

The structure of a permutation matrix avoiding the pattern $132.$ The larger regions on the left and right are also $132$-avoiding.

Structure of a 132-avoiding permutation

In [Vat19], the author studies possible growth rates for pattern-avoiding permutations.

Direct sums and skew sums of permutations

Given $\pi \in \symS_m$ and $\sigma \in \symS_n,$ we define the direct sum and the skew sum of $\pi$ and $\sigma$ as

\begin{align} \pi \ast \sigma \coloneqq & [pi_1,\dotsc,\pi_m,\sigma_1+m,\dotsc,\sigma_n+m] \in \symS_{m+n} \\ \pi \times \sigma \coloneqq & [pi_1+n,\dotsc,\pi_m+n,\sigma_1,\dotsc,\sigma_n] \in \symS_{m+n} \end{align}

Note that these operations are not commutative, but they are associative.

Named sets of permutation

  • Up-down — in one-line notation, we have $\pi_1 \lt \pi_2 \gt \pi_3 \lt \pi_4 \dotsb.$ Down-up permutations are of the form $\pi_1 \gt \pi_2 \lt \pi_3 \gt \pi_4 \dotsb.$ Enumerated by the Euler numbers A000111.
  • André — Either up-down or down-up, A001250.
  • Derangements — permutations with no fixed point, A000166.
  • Dominant — 132-avoiding. Enumerated by the Catalan numbers, A000108.
  • Baxter — avoids $2-14-3$ and $3-14-2,$ see https://doi.org/10.1016/S0012-365X(97)00112-X.
  • Boolean — 123-avoiding and 3412-avoiding, see [Ten07GPRT22]. A permutation is boolean iff the order ideal it defines in the Bruhat order, is a Boolean lattice, see [Thm. 4.3, Ten07]. Enumerated by odd-indexed Fibonacci numbers, A001519.
  • Fully commutative — 123-avoiding, see [BJS93GPRT22]. Enumerated by the Catalan numbers, A000108.
  • A simsun permutation is a permutation such that restricting to entries $1,2,\dotsc,k,$ it does not have a double descent, i.e., $\pi(i)\gt \pi(i+1) \gt \pi(i+2),$ see [MY16]. The number of simsun permutations in $\symS_n$ is given by the Euler number $E_{n+1},$ see A000111.
  • A permutation is vexillary if it avoids the pattern 2143, see A005802.
  • A permutation is Grassmann if it has at most one descent. These are special cases of vexillary permutations. There are $2^n-n$ Grassman permutations in $\symS_n,$ see A000325.
  • A permutation $\pi$ is bi-Grassmann if both $\pi$ and $\pi^{-1}$ are Grassman. Equivalent with avoiding 2413. This set has size $1+\binom{n+1}{3}.$
  • Flattened permutations, where runs are in lex order. Enumerated by Bell numbers A000110, see [Prop. 16, NRB20].
  • Parity-alternating permutations are permutations which sends odd numbers to odd numbers, and even numbers to even, see [KR21a]. This can be generalized to mod-k-alternating permutations, where we demand that $\pi(i) \equiv i \mod k.$ For pattern-avoidance in mod-k-alternating permutations, see [AFGQ22].
  • The Richardson permutation with parameters $(k_1,k_2,\dotsc,k_m)$ is given by the following in two-line notation. \[ \begin{pmatrix} 1 & 2 & \dotsc & k_1 & k_1+1 & k_1+2 & \dotsc & k_1 + k2 & k_1+k_2+1 & \dotsc \\ k_1 & k_1-1 & \dotsc, 1 & k_1+k_2 & k_1+k_2-1 & \dotsc & k_1+1 & k_1+k_2+k_3 & \dotsc \\ \end{pmatrix} \] Basically, we take the unique longest permutation in each of the sets $\symS_{k_1},\dotsc,\symS_{k_m},$ and produce the direct sum of these.
  • Wachs permutationsA359039. These are the permutations in $\symS_n$ defined as \[ W_n \coloneqq \{ \sigma \in \symS_n : |\sigma^{-1}(i)-\sigma^{-1}(i^*)|\leq 1 \text{ for all } i \in [n-1] \}, \] where $i^*$ is defined as \[ i^* \coloneqq \begin{cases} i-1 &\text{if $i$ is even} \\ i+1 &\text{if $i$ is odd and $i+1 \leq n$} \\ n & \text{otherwise.} \end{cases} \] These permutations are studied in [BS22], and there are generalizations to other types.

Permutations of type B

The set of permutations of type $B,$ is defined as the permutations on $B_n \coloneqq \{\pm 1, \pm 2,\dotsc, \pm n\}$ with the property that $\pi(-i)=-\pi(i).$ This is also known as the hyperoctahedral group.

Stirling permutations

In [GS78], Gessel and Stanley introduced the set of Stirling permutations, $Q_n$. These are permutations of the multiset $\{1,1,2,2,3,3,\dotsc,n,n\}$ with the additional property that for between the two entries equal to $i \in [n],$ only entries larger than $i$ may appear. For example, $12234431$ is an element in $Q_n.$

We have that $|Q_n| = (2n-1)!!.$

References