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