Parabolic double cosets and block permutations

The Bruhat index. For every $x\in G$ there is exactly one $\sigma (x)\in S_n$ with $x\in B{P}_{\sigma (x)}B$, and then $x=b_1{P}_{\sigma (x)}{b}_2$ with $b_1,b_2\in B$; in particular $\sigma (P_{\tau })=\tau$ for every $\tau \in S_n$, because $P_{\tau }\in B{P}_{\tau }B$ while $P_{\tau }\mathrm{\notin }B{P}_{\sigma }B$ for $\sigma \mathrm{\ne }\tau$.

The dimension identity. Fix $x\in G$ and put $C_{ij}(x):={\dim }_{{\mathbb{F}}_q}(V_{d_i}\cap x{V}_{e_j})$ for $1\le i\le r$ and $1\le j\le s$; these intersections are finite-dimensional by [L9], and computing with [L4] and [L5] for $\sigma =\sigma (x)$ gives $C_{ij}(x)=e_j-r_{d_i+1,e_j}(x)=e_j-\mathrm{\#}\{k\le e_j:\sigma (k)\ge d_i+1\}=\mathrm{\#}\{k\le e_j:\sigma (k)\le d_i\}={\sum }_{i^{\mathrm{\prime }}\le i}{\sum }_{j^{\mathrm{\prime }}\le j}M(\sigma (x){)}_{i^{\mathrm{\prime }}{j}^{\mathrm{\prime }}},$ where the third equality uses $\sigma (k)\le n$ for all $k$ and the last one splits $k\le e_j$ according to the $\beta$-blocks $J_1,\dots ,J_j$ and the $\alpha$-blocks $I_{i^{\mathrm{\prime }}}$ containing $\sigma (k)$.

The margins of a block-count matrix. For every $\tau \in S_n$ the block-count matrix has row sums ${\sum }_{j}M(\tau {)}_{ij}=\mathrm{\#}\{v:\tau (v)\in I_i\}=\mathrm{\mid }{I}_i\mathrm{\mid }=a_i$ and column sums ${\sum }_{i}M(\tau {)}_{ij}=\mathrm{\mid }{J}_j\mathrm{\mid }=b_j$; in particular $M(\tau )$ is a matrix with nonnegative integer entries, row sums $a_1,\dots ,a_r$ and column sums $b_1,\dots ,b_s$.

Invariance of block counts under the two parabolic actions. One has $M(u\tau v)=M(\tau )$ for all $u\in W_{\alpha }$, $v\in W_{\beta }$ and $\tau \in S_n$: for $u$ this is $M(u\tau {)}_{ij}=\mathrm{\#}\{v\in J_j:u(\tau (v))\in I_i\}=M(\tau {)}_{ij}$, because $u(I_i)=I_i$ for every $i$; for $v$ it is $M(\tau v{)}_{ij}=\mathrm{\#}\{x\in J_j:\tau (v(x))\in I_i\}=M(\tau {)}_{ij}$, because $v$ permutes each block $J_j$.

The monotone matching. Let $m=(m_{ij})$ be any matrix with nonnegative integer entries, row sums $a_i$ and column sums $b_j$. For all $i,j$ let $A_{ij}:=\{t\in I_i:{\sum }_{j^{\mathrm{\prime }}<j}{m}_{i{j}^{\mathrm{\prime }}}<t-d_{i-1}\le {\sum }_{j^{\mathrm{\prime }}\le j}{m}_{i{j}^{\mathrm{\prime }}}\},$ the set of the next $m_{ij}$ elements of $I_i$ after those already allocated to $J_1,\dots ,J_{j-1}$; the $A_{ij}$ for fixed $i$ partition $I_i$ into consecutive pieces of sizes $m_{ij}$, and every element of $A_{i^{\mathrm{\prime }}j}$ is smaller than every element of $A_{ij}$ whenever $i^{\mathrm{\prime }}<i$. Define ${\sigma }_m$ by requiring, for each $j$, that ${\sigma }_m$ maps $J_j$ increasingly onto the increasing list of ${\bigcup }_{i\le r}{A}_{ij}$; this is a well-defined bijection because each $J_j$ has ${\sum }_i{m}_{ij}=b_j$ elements, the target has the same number, and the targets for distinct $j$ are disjoint with union ${\bigcup }_i{I}_i=\{1,\dots ,n\}$. By construction ${\sigma }_m(J_j)\cap I_i=A_{ij}$, so $M({\sigma }_m{)}_{ij}=\mathrm{\mid }{A}_{ij}\mathrm{\mid }=m_{ij}$; and ${\sigma }_m$ is increasing on each $\beta$-block, while ${\sigma }_m^{-1}$ is increasing on each $\alpha$-block because for fixed $i$ the sets $A_{i1},A_{i2},\dots ,A_{is}$, each listed increasingly, occur in this order in $I_i$ and are the images of $J_1,\dots ,J_s$. Thus ${\sigma }_m$ is $(\alpha ,\beta )$-block-increasing with $M({\sigma }_m)=m$.

The normal form of an arbitrary permutation. Let $\sigma \in S_n$ and put $m:=M(\sigma )$. For all $i,j$ the sets $S_{ij}:=\{x\in J_j:\sigma (x)\in I_i\}$ and $T_{ij}:=\{x\in J_j:{\sigma }_m(x)\in I_i\}$ satisfy $\mathrm{\mid }{S}_{ij}\mathrm{\mid }=\mathrm{\mid }{T}_{ij}\mathrm{\mid }=m_{ij}$, and $S_{1j},\dots ,S_{rj}$ as well as $T_{1j},\dots ,T_{rj}$ partition $J_j$. Let $v\in S_n$ be the permutation which maps each $S_{ij}$ increasingly onto $T_{ij}$; it is well defined, and $v\in W_{\beta }$ because $v^{-1}(J_j)=J_j$ for every $j$. Let $u:=\sigma \circ v^{-1}\circ {\sigma }_m^{-1}$. Then $u\circ {\sigma }_m\circ v=\sigma$, and $u\in W_{\alpha }$: for $y\in I_i$ write $y={\sigma }_m(w)$ with $w\in J_j$, so that $w\in T_{ij}$, hence $v^{-1}(w)\in S_{ij}$, hence $u(y)=\sigma (v^{-1}(w))\in I_i$. Therefore every $\sigma \in S_n$ satisfies $\sigma =u{\sigma }_{M(\sigma )}v$ with $u\in W_{\alpha }$ and $v\in W_{\beta }$.

A length formula for products. For a two-element subset $P=\{x,y\}\subseteq \{1,\dots ,n\}$ with $x<y$ and a permutation $w$ write ${\delta }_w(P):=1$ if $w(x)>w(y)$ and ${\delta }_w(P):=0$ otherwise, so that $\mathrm{\ell }(w)={\sum }_P{\delta }_w(P)$ over all two-element subsets. For $\rho ,{\rho }^{\mathrm{\prime }}\in S_n$ and such a $P$ put $Q:={\rho }^{\mathrm{\prime }}(P)=\{{\rho }^{\mathrm{\prime }}(x),{\rho }^{\mathrm{\prime }}(y)\}$. If ${\delta }_{{\rho }^{\mathrm{\prime }}}(P)=0$ then $({\rho }^{\mathrm{\prime }}(x),{\rho }^{\mathrm{\prime }}(y))$ is the natural labelling of $Q$, so ${\delta }_{\rho {\rho }^{\mathrm{\prime }}}(P)=1$ exactly when ${\delta }_{\rho }(Q)=1$; if ${\delta }_{{\rho }^{\mathrm{\prime }}}(P)=1$ then ${\rho }^{\mathrm{\prime }}(y)<{\rho }^{\mathrm{\prime }}(x)$, so ${\delta }_{\rho {\rho }^{\mathrm{\prime }}}(P)=1$ exactly when ${\delta }_{\rho }(Q)=0$. Since $\delta$-values are $0$ or $1$ and $a+b-2ab$ is $1$ exactly when $a\mathrm{\ne }b$ for such $a,b$, this gives ${\delta }_{\rho {\rho }^{\mathrm{\prime }}}(P)={\delta }_{{\rho }^{\mathrm{\prime }}}(P)+{\delta }_{\rho }({\rho }^{\mathrm{\prime }}(P))-2{\delta }_{{\rho }^{\mathrm{\prime }}}(P){\delta }_{\rho }({\rho }^{\mathrm{\prime }}(P)),$ and summing over all $P$, using that $P\mapsto {\rho }^{\mathrm{\prime }}(P)$ is a bijection of the set of two-element subsets, yields $\mathrm{\ell }(\rho {\rho }^{\mathrm{\prime }})=\mathrm{\ell }(\rho )+\mathrm{\ell }({\rho }^{\mathrm{\prime }})-2N(\rho ,{\rho }^{\mathrm{\prime }}),N(\rho ,{\rho }^{\mathrm{\prime }}):=\mathrm{\#}\{P:{\delta }_{{\rho }^{\mathrm{\prime }}}(P)={\delta }_{\rho }({\rho }^{\mathrm{\prime }}(P))=1\}\mathrm{.}$ In particular $\mathrm{\ell }(\rho {\rho }^{\mathrm{\prime }})\le \mathrm{\ell }(\rho )+\mathrm{\ell }({\rho }^{\mathrm{\prime }})$.

The map $\mathrm{\Psi }$ is well defined. Let $u\in W_{\alpha }$ and $v\in W_{\beta }$. By [L2], $P_u$ and $P_v$ are monomial matrices with $u(I_i)=I_i$ for all $i$ and $v(J_j)=J_j$ for all $j$, hence $P_u\in P_{\alpha }$ and $P_v\in P_{\beta }$ by [L1]; therefore $P_{\alpha }{P}_u{P}_{\sigma }{P}_v{P}_{\beta }=P_{\alpha }{P}_{\sigma }{P}_{\beta }$. Since $P_u{P}_{\sigma }{P}_v=P_{u\sigma v}$ by [L2] and [L6], the value $\mathrm{\Psi }(W_{\alpha }{w}_{\sigma }{W}_{\beta })=P_{\alpha }{P}_{\sigma }{P}_{\beta }$ does not depend on the chosen representative of the double coset $W_{\alpha }{w}_{\sigma }{W}_{\beta }$.

Second differences. Taking second differences of the identity of step 1.2, with the conventions $C_{0,j}=C_{i,0}=0$ coming from $V_0=\{0\}$ and $d_0=e_0=0$, gives $M(\sigma (x){)}_{ij}=C_{ij}(x)-C_{i-1,j}(x)-C_{i,j-1}(x)+C_{i-1,j-1}(x)$ for all $i,j$; hence the dimension matrix $C(x)=(C_{ij}(x))$ alone determines $M(\sigma (x))$.

Invariance of the dimension matrix. Let $p\in P_{\alpha }$ and $q\in P_{\beta }$. By [L1], $p$ stabilises the standard partial flag of type $\alpha$ and $q$ that of type $\beta$, so $p[V_{d_i}]=V_{d_i}$ and $q[V_{e_j}]=V_{e_j}$. By [L7] the restriction of the linear map $v\mapsto pv$ to a linear subspace $A\le V$ is a linear map $A\to V$, and by [L8] this map $v\mapsto pv$ is injective; an injective map satisfies $p[A\cap B]=p[A]\cap p[B]$ for any two subsets $A,B$: the inclusion $\subseteq$ is clear, and $p(a)=p(b)$ with $a\in A$ and $b\in B$ forces $a=b\in A\cap B$. Therefore $V_{d_i}\cap pxq{V}_{e_j}=V_{d_i}\cap p[x{V}_{e_j}]=p[V_{d_i}]\cap p[x{V}_{e_j}]=p[V_{d_i}\cap x{V}_{e_j}],$ using $q[V_{e_j}]=V_{e_j}$ in the first step and $p[V_{d_i}]=V_{d_i}$ in the second, and applying ${\dim }_{{\mathbb{F}}_q}p[U]={\dim }_{{\mathbb{F}}_q}U$ from [L8] to $U=V_{d_i}\cap x{V}_{e_j}$ gives $C_{ij}(pxq)=C_{ij}(x)$ for all $i,j$.

The double coset of $x$. For every $x\in G$ one has $P_{\alpha }x{P}_{\beta }=P_{\alpha }{P}_{\sigma (x)}{P}_{\beta }$. One inclusion holds because $x=b_1{P}_{\sigma (x)}{b}_2$ with $b_1\in B\le P_{\alpha }$ and $b_2\in B\le P_{\beta }$ by [L1] and [L3], so $P_{\alpha }x{P}_{\beta }\subseteq P_{\alpha }{P}_{\sigma (x)}{P}_{\beta }$; conversely $P_{\sigma (x)}=b_1^{-1}x{b}_2^{-1}\in P_{\alpha }x{P}_{\beta }$, so $P_{\alpha }{P}_{\sigma (x)}{P}_{\beta }\subseteq P_{\alpha }x{P}_{\beta }$.

Block counts classify double cosets. If $\sigma ,{\sigma }^{\mathrm{\prime }}\in S_n$ satisfy $M(\sigma )=M({\sigma }^{\mathrm{\prime }})$, then step 1.6 applied to both gives $\sigma ,{\sigma }^{\mathrm{\prime }}\in W_{\alpha }{\sigma }_{M(\sigma )}{W}_{\beta }$, so ${\sigma }^{\mathrm{\prime }}$ lies in the same $(W_{\alpha },W_{\beta })$-double coset as $\sigma$; conversely step 1.4 shows that all elements of one double coset share one block-count matrix. Since step 1.5 produces for every matrix $m$ with the prescribed margins a permutation ${\sigma }_m$ with $M({\sigma }_m)=m$, the assignment $\tau \mapsto M(\tau )$ induces a bijection from $W_{\alpha }\mathrm{\backslash }W\mathrm{/}{W}_{\beta }$ onto the set of all matrices with nonnegative integer entries whose row sums are $a_1,\dots ,a_r$ and whose column sums are $b_1,\dots ,b_s$.

Length is additive along $\beta$-block permutations. If $\rho$ is increasing on each $\beta$-block and ${\rho }^{\mathrm{\prime }}\in W_{\beta }$, then $N(\rho ,{\rho }^{\mathrm{\prime }})=0$ in step 1.7 and hence $\mathrm{\ell }(\rho {\rho }^{\mathrm{\prime }})=\mathrm{\ell }(\rho )+\mathrm{\ell }({\rho }^{\mathrm{\prime }})$. Indeed, if ${\delta }_{{\rho }^{\mathrm{\prime }}}(P)=1$ for $P=\{x<y\}$, then ${\rho }^{\mathrm{\prime }}(x)>{\rho }^{\mathrm{\prime }}(y)$; since ${\rho }^{\mathrm{\prime }}$ maps each block $J_j$ onto itself and maps the blocks in increasing order, $x$ and $y$ lie in a common block $J_j$, so also ${\rho }^{\mathrm{\prime }}(x),{\rho }^{\mathrm{\prime }}(y)\in J_j$; as $\rho$ is increasing on $J_j$ and ${\rho }^{\mathrm{\prime }}(y)<{\rho }^{\mathrm{\prime }}(x)$, we get $\rho ({\rho }^{\mathrm{\prime }}(y))<\rho ({\rho }^{\mathrm{\prime }}(x))$, that is ${\delta }_{\rho }({\rho }^{\mathrm{\prime }}(P))=0$, so no $P$ contributes to $N(\rho ,{\rho }^{\mathrm{\prime }})$.

Simple reflections. For every $\rho \in S_n$ and every $1\le i<n$, where $s_i$ is the adjacent transposition of $i$ and $i+1$, one has $\mathrm{\ell }(\rho s_i)=\mathrm{\ell }(\rho )+1-2[\rho (i)>\rho (i+1)]$ and $\mathrm{\ell }(s_i\rho )=\mathrm{\ell }(\rho )+1-2[{\rho }^{-1}(i)>{\rho }^{-1}(i+1)]$. For the first identity, $s_i$ reverses exactly one two-element set, namely $\{i,i+1\}$, and fixes it, so in step 1.7 the sum defining $N(\rho ,s_i)$ has the single term ${\delta }_{s_i}(\{i,i+1\}){\delta }_{\rho }(s_i(\{i,i+1\}))=[\rho (i)>\rho (i+1)]$, while $\mathrm{\ell }(s_i)=1$. The second identity follows from the first applied to ${\rho }^{-1}$: using $\mathrm{\ell }(s_i\rho )=\mathrm{\ell }((s_i\rho {)}^{-1})$ and $(s_i\rho {)}^{-1}={\rho }^{-1}{s}_i^{-1}={\rho }^{-1}{s}_i$ together with $\mathrm{\ell }({\rho }^{-1})=\mathrm{\ell }(\rho )$ gives $\mathrm{\ell }(s_i\rho )=\mathrm{\ell }(\rho )+1-2[{\rho }^{-1}(i)>{\rho }^{-1}(i+1)]$.

Uniqueness of the block-increasing element with given block counts. Suppose $\sigma ,{\sigma }^{\mathrm{\prime }}\in S_n$ are both $(\alpha ,\beta )$-block-increasing with $M(\sigma )=M({\sigma }^{\mathrm{\prime }})=m$. For fixed $i$ put $A_{ij}:=\{t\in I_i:{\sigma }^{-1}(t)\in J_j\}$; then $\mathrm{\mid }{A}_{ij}\mathrm{\mid }=m_{ij}$ and the $A_{ij}$ partition $I_i$. If $t\in A_{ij}$ and $t^{\mathrm{\prime }}\in A_{i{j}^{\mathrm{\prime }}}$ with $j<j^{\mathrm{\prime }}$, then ${\sigma }^{-1}(t)\in J_j$ and ${\sigma }^{-1}(t^{\mathrm{\prime }})\in J_{j^{\mathrm{\prime }}}$, and every element of $J_j$ is smaller than every element of $J_{j^{\mathrm{\prime }}}$, so ${\sigma }^{-1}(t)<{\sigma }^{-1}(t^{\mathrm{\prime }})$, and ${\sigma }^{-1}$ increasing on $I_i$ gives $t<t^{\mathrm{\prime }}$; so the sets $A_{i1},\dots ,A_{is}$ occur in $I_i$ in this increasing order and, having sizes $m_{ij}$, they are exactly the sets of step 1.5. Fix now $j$: the restriction of $\sigma$ to $J_j$ is increasing and has image ${\bigcup }_{i\le r}{A}_{ij}$, so that restriction is the increasing bijection of $J_j$ onto that union, and listing the union increasingly presents it as $A_{1j},A_{2j},\dots ,A_{rj}$ with each $A_{ij}$ increasing. This is exactly the prescription defining ${\sigma }_m$ in step 1.5; the same computation applies to ${\sigma }^{\mathrm{\prime }}$, so $\sigma ={\sigma }^{\mathrm{\prime }}={\sigma }_m$.

Block counts are constant on $(P_{\alpha },P_{\beta })$-double cosets. For all $p\in P_{\alpha }$, $q\in P_{\beta }$ and $x\in G$ one has $M(\sigma (pxq))=M(\sigma (x))$ by steps 2.2 and 2.1; equivalently $M\circ \sigma$ is constant on $(P_{\alpha },P_{\beta })$-double cosets.

Minimal elements are block-increasing. Let $\rho \in S_n$ be an element of minimal length in its $(W_{\alpha },W_{\beta })$-double coset. If $\rho$ is not increasing on some $\beta$-block, there are $i,i+1$ in a common block $J_j$ with $\rho (i)>\rho (i+1)$; then $s_i\in W_{\beta }$, so $\rho s_i$ lies in the same double coset, and $\mathrm{\ell }(\rho s_i)=\mathrm{\ell }(\rho )-1$ by step 2.6, contradicting minimality. If $\rho$ is increasing on every $\beta$-block but ${\rho }^{-1}$ is not increasing on some $\alpha$-block, there are $i,i+1$ in a common block $I_{i^{\mathrm{\prime }}}$ with ${\rho }^{-1}(i)>{\rho }^{-1}(i+1)$; then $s_i\in W_{\alpha }$, so $s_i\rho$ lies in the same double coset, and $\mathrm{\ell }(s_i\rho )=\mathrm{\ell }(\rho )-1$ by step 2.6, again contradicting minimality. Hence every minimal-length element is $(\alpha ,\beta )$-block-increasing.

$\mathrm{\Psi }$ is surjective. For $x\in G$ step 1.1 gives $\sigma (P_{\sigma (x)})=\sigma (x)$, so $\mathrm{\Psi }(W_{\alpha }{w}_{\sigma (x)}{W}_{\beta })=P_{\alpha }{P}_{\sigma (x)}{P}_{\beta }=P_{\alpha }x{P}_{\beta }$ by step 2.3; every $(P_{\alpha },P_{\beta })$-double coset therefore lies in the image of $\mathrm{\Psi }$.

$\mathrm{\Psi }$ is injective. Suppose $P_{\alpha }{P}_{\sigma }{P}_{\beta }=P_{\alpha }{P}_{\tau }{P}_{\beta }$ for $\sigma ,\tau \in S_n$. Then $P_{\tau }\in P_{\alpha }{P}_{\sigma }{P}_{\beta }$, say $P_{\tau }=p{P}_{\sigma }q$ with $p\in P_{\alpha }$ and $q\in P_{\beta }$; steps 2.2 and 2.1 applied to the pair $p{P}_{\sigma }q$ give $M(\sigma (P_{\tau }))=M(\sigma (P_{\sigma }))$, that is $M(\tau )=M(\sigma )$ because $\sigma (P_{\rho })=\rho$ for every $\rho$ by step 1.1. Step 2.4 then gives $W_{\alpha }\sigma W_{\beta }=W_{\alpha }\tau W_{\beta }$: distinct $(W_{\alpha },W_{\beta })$-double cosets have distinct images under $\mathrm{\Psi }$.

The unique minimal representative in a double coset. Let $D=W_{\alpha }\sigma W_{\beta }$ be a $(W_{\alpha },W_{\beta })$-double coset and put $m:=M(\sigma )$. By step 1.6, $\sigma \in W_{\alpha }{\sigma }_m{W}_{\beta }$, so ${\sigma }_m\in D$ and $D=W_{\alpha }{\sigma }_m{W}_{\beta }$; by step 1.4 every element $\rho \in D$ has $M(\rho )=m$; by step 2.7 every $(\alpha ,\beta )$-block-increasing element of $D$ equals ${\sigma }_m$; and by step 3.2 every element of $D$ of minimal length is $(\alpha ,\beta )$-block-increasing. Hence ${\sigma }_m$ is the unique element of $D$ of minimal length, every other element of $D$ has strictly larger length, and ${\sigma }_m$ is the monotone matching of step 1.5.

Claim 3. By step 4.1 every $(W_{\alpha },W_{\beta })$-double coset contains exactly one $(\alpha ,\beta )$-block-increasing permutation, it is the unique element of the coset of minimal length, and it is the monotone matching ${\sigma }_M$ determined by the block-count matrix $M$ through the allocation rule of step 1.5; this is claim 3 of the statement.

Boundary cases. For $n=1$ we have $\alpha =\beta =(1)$, $r=s=1$, $W_{\alpha }=W_{\beta }=\{1\}$, $\mathrm{\ell }(\mathrm{i}\mathrm{d})=0$ and $M(\mathrm{i}\mathrm{d})=(1)$: there is one double coset and its unique block-increasing element is $\mathrm{i}\mathrm{d}$, the monotone matching. For $r=1$, that is $\alpha =(n)$ and $P_{\alpha }=G$, the parabolic Weyl subgroup is $W_{\alpha }=S_n$ by [L2], since the single block is preserved by every permutation; every $\tau$ then has the same block-count matrix, namely the row $(b_1,\dots ,b_s)$ of column sums, the double-coset set $W_{\alpha }\mathrm{\backslash }W\mathrm{/}{W}_{\beta }$ consists of one class, and step 1.5 assigns to that row the permutation $\mathrm{i}\mathrm{d}$, which is increasing on every $\beta$-block with ${\mathrm{i}\mathrm{d}}^{-1}=\mathrm{i}\mathrm{d}$ increasing on $I_1=\{1,\dots ,n\}$. The case $s=1$, that is $\beta =(n)$ and $P_{\beta }=G$, is analogous: every $\tau$ has the single-column block-count matrix of row sums, there is one double coset, and its unique block-increasing representative is $\mathrm{i}\mathrm{d}$. All formulas above are stated for arbitrary compositions and require no separate treatment of these extremes.

Claims 1 and 2, and conclusion. Steps 1.8, 3.3 and 3.4 exhibit $\mathrm{\Psi }$ as a well-defined bijection, which is claim 1, and step 5.1 is claim 3. For claim 2 let $x,y\in G$: if $M(\sigma (x))=M(\sigma (y))$, then step 2.4 gives $W_{\alpha }\sigma (x)W_{\beta }=W_{\alpha }\sigma (y)W_{\beta }$ and step 2.3 gives $P_{\alpha }x{P}_{\beta }=P_{\alpha }{P}_{\sigma (x)}{P}_{\beta }=P_{\alpha }{P}_{\sigma (y)}{P}_{\beta }=P_{\alpha }y{P}_{\beta }$; conversely if $P_{\alpha }x{P}_{\beta }=P_{\alpha }y{P}_{\beta }$, then $y=pxq$ with $p\in P_{\alpha }$ and $q\in P_{\beta }$, so $M(\sigma (y))=M(\sigma (x))$ by step 3.1; and $W_{\alpha }\sigma (x)W_{\beta }=W_{\alpha }\sigma (y)W_{\beta }$ is equivalent to $M(\sigma (x))=M(\sigma (y))$ by step 2.4 together with step 1.4. The bijection onto matrices with the prescribed margins is step 2.4, and the boundary cases are step 5.2. ∎