1
$\begingroup$

This question originates from an engineering problem, which I am solving. Any related references are highly appreciated.

Let $M_k(T)=\prod_{t=1}^T P_t S_k$ over some field (finite or reals), where $P_t$ is a random (uniform, i.i.d. over $t$) $n\times n$ permutation matrix, and $S_k$ is a fixed idempotent matrix of rank $n-1$ of the following form

$$ S_1=\begin{pmatrix} 1 & 0 & 0 \cdots \\ 1 & 0 & 0 \cdots \\ 0 & 0 & \\ \vdots & \vdots & \huge{I_{n-2}} \\ 0 & 0 & \end{pmatrix}, S_2=\begin{pmatrix} 1 & 0 &0 & 0 \cdots \\ 0 & 1 &0& 0 \cdots \\ 1 & 1 &0& 0 \cdots \\ 0 & 0 &0& \\ \vdots &\vdots & \vdots & \huge{I_{n-3}} \\ 0 & 0 &0& \end{pmatrix}, \\ S_k=\begin{pmatrix} & &&0 & \\ & \huge{I_k} &&\vdots& \huge{0} \\ & &&0& \\ 1 & \cdots &1&0& 0 \cdots \\ & & &0& \\ & \huge{0}& & \vdots & \huge{I_{n-k-1}} \\ &&&0& \end{pmatrix}.$$

Essentially, each additional multiplication by $P_t S_k$ replaces some row of $M_k(t-1)$ with a linear combination of $k$ other rows. It is not hard to see that $\mbox{rank } M_k(t)$ is non-increasing in $t$, and $\lim_{T\to \infty} \mbox{rank } M_k(T) \leq k$ almost surely. I am looking into the rate of this convergence.

Question: find $E[\mbox{rank } M_k(T)]$ or the CDF of $\mbox{rank } M_k(T)$ for $T\gg n$.

One approach to this is to track the number $N_0(M(t))$ of zero-columns or the number $N(M(t))$ of rows $r$, s.t. $r$ contains the first row of $M(1)$ in its linear decomposition. These numbers follow the Markov property, and one can construct corresponding linear Markov chains with $n+1$ states to find their long-term behavior and bound

$$\mbox{rank } M(T) \leq n-N_0(M(T)) \\ E[\mbox{rank } M(T)] \leq n \Pr[N(M(T))>0] $$

Although the bounds are tight for $k=1$, they are very loose for $k>1, T\gg n$. In fact for $k=1$ the rank drops to $1$ rather quickly in $T = O(n^2)$, but for $k>1$, the decay seems to be exponentially slow, e.g. $E[\mbox{rank } M_3(10^5)]\approx E[\mbox{rank } M_3(10^7)] \approx 5$ for $n=20$ (numerically).

Another numerical observation shows that for $n\ge 10$ the resulting $E[\mbox{rank } M(T)]$ does not depend much on the field size once it is prime and larger than $7$.

Any reference to studying the long products like $M(t)$ of random permutations with a fixed matrix $S$ would be also appreciated.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.