1
$\begingroup$

My question emerges from the permutation representation of the determinant. In my case the matrix has some special symmetries which I want to use. In order to do so, I need a better understanding of how permutations can be split into different "sub-permutations". I thought of a simple splitting of the definition space of the permutations, but wasn't jet able to proof the necessary statements. What I managed so far, was to write the problem down in the following form:

Let $M$ be the set and $\mathcal{P}_M$ the set of all permutations on $M$: $$M:=\{1,2,...,N\},~~N\in\mathbb{N}$$ $$\mathcal{P}_M:=\{\pi:M\rightarrow M~|~\pi\text{ bijective}\}$$ Now let $L:=\{1,2,...,n\}$ and $R:=\{n+1,n+2,...,N\}$, $\mathbb{N}\ni n \le N$, and define $\mathcal{P}_L$ and $\mathcal{P}_R$ in the same way. Now we have the sets of permutations on $M$ and its subsets $L$ and $R$. Additinally define a set of functions which interchange elements of $R$ and $L$ only: $$\mathcal{X}_{LR}:=\{\pi:M\rightarrow M~|~id\ne\pi=\hat\pi_{i_1,j_1}\circ\hat\pi_{i_2,j_2}\circ ... \circ \hat\pi_{i_m,j_m}, i_k\in L, j_k\in R, i_k\ne i_l, j_k\ne j_l,~k,l\in\{1,...m\}, 1\le m\le \min(n, N-n+1)\}$$ where $\hat\pi_{i,j}$ interchanges the number $i$ with $j$ in some expression, hence it's another way to write a permutation, $i\in L$, $j\in R$. So any function in $\mathcal{X}_{LR}$ pics $m$ numbers of $L$ and $m$ numbers of $R$ and interchanges them in some way, e.g. $L=\{1,2,3\}, R=\{4,5\}$, then $\pi_{1,4}\circ\pi_{3,5}\in\mathcal{X}_{LR}$, but $\pi_{1,4}\circ\pi_{4,1}=id\notin\mathcal{X}_{LR}$, $\pi_{1,3}\circ\pi_{2,5}\notin\mathcal{X}_{LR}$, $\pi_{1,5}\circ\pi_{2,5}\notin\mathcal{X}_{LR}$. I hope this explaines what I mean what $\mathcal{X}_{LR}$ should be.

  1. statement $$\forall \pi\in\mathcal{P}_M:\exists\pi_L\in\mathcal{P}_L, \pi_R\in\mathcal{P}_R, \pi_X\in\mathcal{X}_{LR}, \tilde{\pi}_X\in\mathcal{X}_{LR}\text{: }\\\pi=\pi_L\circ\pi_R\circ\pi_X=\pi_R\circ\pi_L\circ\pi_X\\\pi=\tilde{\pi}_X\circ\pi_L\circ\pi_R=\tilde{\pi}_X\circ\pi_R\circ\pi_L$$

  2. statement $$ \sum_{\pi\in\mathcal{P}}A(\pi)=\sum_{\pi_X\in\mathcal{P}_X}\sum_{\pi_L\in\mathcal{P}_L}\sum_{\pi_R\in\mathcal{P}_R} A(\pi_L\circ\pi_R\circ\pi_X)$$

In my opinion the first statement must be true, since the splitting of the permutations is reversed by the interchange-functions in $\mathcal{X}_{LR}$ and it also doesn't matter if I do the interchange between $L$ and $R$ first and sort in $L$ or $R$ afterwards or vice versa.

I doubt the second expression - not in principle but in detail. My intuition tells me that I take to many elements of $\mathcal{X}_{LR}$ into account in the sum, represent some permutations twice and hence there should be some factor one over something, which divides through some "power" of $\mathcal{X}_{LR}$. On the other side: If the first statement is true, then $\mathcal{P}$ should be a subset of the set of all $\pi_L\circ\pi_R\circ\pi_X$. But since there are no more permutations of $M$ than in $\mathcal{P}$, it should follow that $\mathcal{P}="\{\pi_L\circ\pi_R\circ\pi_X\}"$. The question would be, whether I do the counting in the summation right or not.

I do not have the mathematical background knowlegde to proof these statements, since I am "only" a physicist. Up to now I don't even know how to start the proof.

To give that question a little more explicitness: In my case $A(\pi)$ is invariant under permutations from $\mathcal{P}_R$ and $\mathcal{P}_L$, hence the expression $A(\pi_X\circ\pi_L\circ\pi_R)$ would simplify to $A(\pi_X)$

Is there anybody out there willing to think about this and give me not necessarily a proof, but some hints (although a proof would be very nice)?

$\endgroup$
  • $\begingroup$ Although the question is written down quiet formally, it reduces to a simple picture. From another point of view one could argue with permutation matrices, and the 1. statement would be equivalent to the question if there is a (unique?) decomposition of a permutation matrix into blockmatrices of the form DIAGONAL-OFFDIAGONAL. $\endgroup$ – zufall May 26 '17 at 9:53

Your Answer

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

Browse other questions tagged or ask your own question.