# Rank and frequency of permutations

(a) Let $$[n] = \{1,\dotsc,n\}$$, and let $$\pi:[n]\to [n]$$ be a permutation. Define an $$n$$-by-$$n$$ matrix $$A=A(\pi)$$ as follows: $$A_{i,j}=1$$ if $$j>i$$ and $$\pi(j)>\pi(i)$$, $$A_{i,j}=-1$$ If $$j and $$\pi(j)<\pi(i)$$, $$A_{i,j}=0$$ otherwise.

For $$\pi$$ generic, we expect the rank of $$A(\pi)$$ to be $$n$$ or close to $$n$$. At the same time, the rank of $$A(\pi)$$ can be $$0$$: it is $$0$$ if (and only if) $$\pi$$ is the reflection $$\pi(k) = n+1-k$$.

What sort of upper bound can one give on the number of permutations $$\pi$$ such that the rank of $$A(\pi)$$ is small (say, at most $$\delta n$$, where $$0<\delta<1$$)?

(b) More generally (in a way), we may consider words $$w$$ of length $$2n$$ containing exactly one instance each of $$x_i$$ and $$x_i^{-1}$$ for each $$1\leq i\leq n$$. Define an $$n$$-by-$$n$$ matrix $$A=A(w)$$ as follows: $$A_{i,j}=s$$ if exactly one power $$x_j^s$$, $$s=\pm 1$$, appears between $$x_i$$ and $$x_i^{-1}$$ (or $$A_{i,j}=-s$$ for $$x_j^s$$ appearing between $$x_i^{-1}$$ and $$x_i$$, if they are in that order); $$A_{i,j}=0$$ otherwise.

The number of words $$w$$ such that the rank of $$A(w)$$ is $$0$$ is relatively small (roughly $$8^n$$): the rank of $$A(w)$$ can be $$0$$ only if $$w$$ reduces to the trivial word. (Here "relatively small" means "small compared to $$n!$$.)

What sort of upper bound can one give on the number of words $$w$$ of the kind we are considering such that the rank of $$A(w)$$ is small (say, at most $$\delta n$$, where $$0<\delta<1$$)?

Remark: in both parts of the question, $$A$$ is an antisymmetric matrix, and its determinant is thus the square of a Pfaffian. It is also clear that $$A$$ can be seen as the adjacency matrix of an oriented graph. However, the orientation is not Pfaffian, so $$A$$ can be singular even if there is a perfect matching. Incidentally, $$A$$, being antisymmetric, is of rank at least $$r$$ iff it has a principal r-by-r minor. That corresponds to take a subword by ignoring some of the letters.

td;lr Some headway on (b) ought to be possible.

• Since the matrix A(pi) is a zero matrix only when n=1, I do not see how its rank can be zero for large n. Can you explain why it is? Gerhard "Took Left Turn At Adjoint" Paseman, 2019.04.30. – Gerhard Paseman Apr 30 '19 at 16:11
• $A(\pi)$ is in fact the zero matrix when $\pi(k)=n+1-k$ for all $1\leq k\leq n$, as then $j-i$ and $\pi(j)-\pi(i)$ always have opposite signs (or are both zero). – H A Helfgott Apr 30 '19 at 16:28
• I see now, thanks. It looks like I switched an inequality in reading. Gerhard "Right Turn At Greater Than" Paseman, 2019.04.30. – Gerhard Paseman Apr 30 '19 at 16:38
• It appears that this was studied already quite a bit: for a permutation of $n$, the statistic findstat.org/St000696 is $n+1$ minus the rank of your matrix of the reversal of the permutation, if I am not mistaken. – Martin Rubey May 1 '19 at 20:56
• I don't quite understand how that is the same problem (as part (a) or (b)?). Can you explain? – H A Helfgott May 2 '19 at 7:02

We start by simplfying the problem by elementary row-and-column operations. We define a matrix $$A'$$ whose $$i$$th row ($$1\leq i) is the $$(i+1)$$th row of $$A$$ minus the $$i$$th row of $$A$$. Then $$a'_{i,j}$$ equals $$-1$$ at every $$j>i$$ for which $$\pi(i)\le \pi(j)\le \pi(i+1)$$; if $$\pi(i+1)<\pi(i)$$, $$a'_{i,j}$$ equals $$1$$ at every $$j$$ for which $$\pi(i+1)< \pi(j)<\pi(i)$$. Now we permute both rows and columns by $$\pi^{-1}$$, and obtain a matrix $$A''$$ described as follows: if $$\pi(\pi^{-1}(i)+1)>i$$, then $$a''_{i,j}=-1$$ for every $$i\le j\le \pi(\pi^{-1}(i)+1)$$; otherwise, we let $$a''_{i,j}=1$$ for every $$\pi(\pi^{-1}(i)+1). Lastly, we define a matrix $$A^{(3)}$$ whose $$j$$th column is the $$(j-1)$$th column of $$A''$$ minus the $$j$$th column of $$A''$$. Then $$a^{(3)}_{i,i}=1$$ and $$a^{(3)}_{i,\pi(\pi^{-1}(i)+1)+1}=-1$$, unless $$\pi(\pi^{-1}(i)+1)+1=i$$, in which case $$a_{i,i}^{(3)}=0$$. In other words, $$A^{(3)} = I - B$$, where $$B$$ is the permutation matrix corresponding to the permutation $$\phi:i\mapsto \pi(\pi^{-1}(i)+1)+1$$. (I'm ignoring edge effects; think of $$+1$$ as being $$\mod n$$ if you wish.) The rank of $$A^{(3)}$$ is no greater than the rank of $$A$$ (and in fact is at least $$\textrm{rank}(A)-2$$).
It is easy to see that, in general, for $$B$$ a permutation matrix, $$\textrm{rank}(I-B)$$ equals the sum of the lengths of the cycles of the permutation. Thus, $$\textrm{rank}(I-B) \geq ((n-1)-k)/2$$, where $$k$$ is the number of fixed points of $$\phi$$.
Saying that $$i$$ is a fixed point of $$\phi$$ is the same as saying that $$\pi^{-1}(i)+1 = \pi^{-1}(i-1)$$. In other words, $$k$$ is the number of $$j$$ for which $$\pi(j+1)=\pi(j)-1$$. It is clear that the number of $$\pi$$ for which this is true for almost all $$j$$ is small.
More precisely: if we want the rank of $$A$$ to be at most $$r$$, then the rank of $$A^{(3)}$$ has to be at most $$r$$, and so there can be at most $$2 r$$ (or $$2 r - 2$$ or so; I am not keeping count) indices $$1\leq j for which it is not true that $$\pi(j+1)=\pi(j)+1$$. Thus, the number of $$j$$ for which $$\pi(j)$$ is chosen freely is at most $$4 r$$. The number of permutations $$\pi$$ for which $$\textrm{rank}(A)\leq r$$ is thus at most (about) $$\binom{n}{4 r}$$.