Rank and frequency of permutations

Question

(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<i$ 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.

Answer 1

Here is a (sketch of) a solution to (a) (with no pretenses to optimality).

We start by simplfying the problem by elementary row-and-column operations. We define a matrix $A'$ whose $i$th row ($1\leq i<n$) 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)<j<i$. 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<n$ 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}$.