1
$\begingroup$

Is there any research on the structure/properties of permutation matrix/table with $(i,j)th$ entry as $\pi_j\circ \pi_i^{-1}$, where $\{\pi_1,\pi_2,...,\pi_{k!}\}=S_k$?

I know if we apply the function of taking the number of inversions onto above table entry-wisely to get a matrix, then the so-defined matrix is actually a conditionally positive semidefinite where it is refined to subspace $\{x|e^Tx=0\}$. This result is by Bapat and Raghavan in "Nonnegative Matrices and Applications".

But right now I am working on taking the longest increasing subsequence of that table and it turns out to be hard so that I am trying to dig out as many properties as I can.

Is there any advanced technique such as representation theory can be used here? Any general big-idea talk or specific advice are welcomed! Thanks!

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ How big are these matrices supposed to be? It looks to me like a $k! \times k!$ table of $k \times k$ matrices. Is that what you intend? $\endgroup$
    – Geoff Robinson
    Commented Jan 23, 2015 at 4:48
  • 3
    $\begingroup$ it's not clear what kind of order on permutations you are talking about, and, indeed, what the entries of these tables are. $\endgroup$
    – Dima Pasechnik
    Commented Jan 23, 2015 at 9:20
  • $\begingroup$ You might want to have a look at arxiv.org/abs/1102.2460. They study a-non-inversions on exactly that matrix; these are $w_{i_1} < \ldots < w_{i_a}$ for a permutation $w \in \mathcal{S}_n$. $\endgroup$
    – Christian Stump
    Commented Jan 23, 2015 at 17:49
  • $\begingroup$ @GeoffRobinson Yes, if you prefer using permutation matrices to represent permutations. $\endgroup$
    – user3760541
    Commented Jan 25, 2015 at 15:30
  • $\begingroup$ For now, I am using increasing order if you consider the dictionary as $\[n\]$. @DimaPasechnik $\endgroup$
    – user3760541
    Commented Jan 25, 2015 at 15:35

0

Reset to default

You must log in to answer this question.