# Expectation Involving Permutation Matrices

Let $L$ be $n\times n$ bidiagonal matrix such that its diagonal is all $1$ and its subdiagonal is all $-1$ (and zero elsewhere). Let $D$ be any diagonal matrix and $x,y$ be any $n$-dimensional column vectors.

What is the expectation:

$\mathbb E[x^TP^TL PDP^T L^TPy]$

where the expectation is taken over $P$ which runs over all $n!$ permutation matrices of $n\times n$?

-
You've edited the post once to remove an unexpected asymmetry, so I wonder whether the remaining asymmetry is intended. Is there really no $P^T$ after the $D$? – joriki Dec 15 '12 at 13:43
What did you try? – Did Dec 15 '12 at 13:43
I don't think there should be an asymmetry here. Let me explain in English: look at $x^T LDL^T y$. Now, we change the order of the elements of x, at the very same way we change the order of elements of y, at the very same way we change the order of the rows of D. – Troy McClure Dec 15 '12 at 13:45
before I editted it, this expression resulted in a matrix. it should (as now) result in a scalar – Troy McClure Dec 15 '12 at 13:46
@Troy: The asymmetry lies in only changing the order of the rows of $D$, not the columns. $PD$ isn't a diagonal matrix, whereas $PDP^T$ is, with rows and columns reordered by the same permutation. Perhaps you could tell us something about how this question arose? (That might also increase the motivation for answering it.) – joriki Dec 15 '12 at 13:48

The permutations are perhaps best understood as permuting $L$, that is, we want $\mathbb E[x^TL'DL'^Ty]$ with $L'=P^TLP$. We can write $L=I-A$, where $I$ is the identity and $A$ has $1$s on the subdiagonal and $0$ elsewhere. The identity is invariant under the permutation, and where $A$ has $1$s in off-diagonal elements along a chain of indices from $1$ to $n$, $A'=P^TAP$ has them along any of the $n!$ possible chains. Thus

\begin{align} \mathbb E[x^TP^TIPDP^TI^TPy]&=x^TDy\;, \\ \\ \mathbb E[x^TP^TIPDP^TA^TPy] &=\mathbb E[x^TDA'^Ty] \\ &=\frac1{n!}\sum_{\sigma\in S_n}\sum_{i=1}^nx_iD_{ii}y_{\sigma^{-1}(\sigma(i)+1)} \\ &=\sum_{i=1}^nx_iD_{ii}\frac1{n-1}\sum_{j\ne i}y_j \\ &=\frac n{n-1}x^TD\langle y\rangle-\frac1{n-1}x^TDy\;, \\ \\ \mathbb E[x^TP^TAPDP^TI^TPy] &= \frac n{n-1}\langle x\rangle^TDy-\frac1{n-1}x^TDy\;, \\ \\ \mathbb E[x^TP^TAPDP^TA^TPy] &= \mathbb E[x^TA'DA'^Ty] \\ &= \frac1{n!}\sum_{\sigma\in S_n}\sum_{i=1}^nx_{\sigma^{-1}(\sigma(i)+1)}D_{ii}y_{\sigma^{-1}(\sigma(i)+1)} \\ &=\sum_{i=1}^n\frac1{n-1}\sum_{j\ne i}x_jD_{ii}y_j \\ &=\sum_{j=1}^n\frac1{n-1}\sum_{i\ne j}x_jD_{ii}y_j \\ &=\frac n{n-1}x^T\langle D\rangle y-\frac1{n-1}x^TDy\;, \end{align}

so

$$\mathbb E[x^TP^TLPDP^TL^TPy]=\frac n{n-1}\left(x^TDy-\langle x\rangle^TDy-x^TD\langle y\rangle+x^T\langle D\rangle y\right)\;,$$

where $\langle x\rangle$ and $\langle y\rangle$ are constant vectors whose entries are the average of the entries of $x$ and $y$, respectively, and $\langle D\rangle$ is a multiple of the identity whose diagonal entries are the average of the diagonal entries of $D$.

-
man you're good! please send me your details so I'll put it in the paper – Troy McClure Dec 15 '12 at 15:41
i opened 10minutemail temp account: hk4902@zoaxe.com please contact me through there – Troy McClure Dec 15 '12 at 15:58
seems like when putting $<x>=1\cdot x/n$ then the result reduces to $(n/(n-1))*x^T(D+<D>)*y$ – Troy McClure Dec 15 '12 at 16:20
Nice calculation. – user1551 Dec 16 '12 at 0:58