Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
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
up vote 1 down vote accepted

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} $$


$$ \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$.

share|cite|improve this answer
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: 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.