6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Apr 30 '19 at 16:11
  • $\begingroup$ $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). $\endgroup$ – H A Helfgott Apr 30 '19 at 16:28
  • $\begingroup$ I see now, thanks. It looks like I switched an inequality in reading. Gerhard "Right Turn At Greater Than" Paseman, 2019.04.30. $\endgroup$ – Gerhard Paseman Apr 30 '19 at 16:38
  • $\begingroup$ 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. $\endgroup$ – Martin Rubey May 1 '19 at 20:56
  • $\begingroup$ I don't quite understand how that is the same problem (as part (a) or (b)?). Can you explain? $\endgroup$ – H A Helfgott May 2 '19 at 7:02
0
$\begingroup$

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}$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.