2
$\begingroup$

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

  • 0
    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$?2012-12-15
  • 0
    What did you try?2012-12-15
  • 0
    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.2012-12-15
  • 0
    before I editted it, this expression resulted in a matrix. it should (as now) result in a scalar2012-12-15
  • 0
    @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.)2012-12-15
  • 0
    ok you're very right!! my mistake. what I need is D to remain diagonal, so I just change its diagonal elements. I'll edit the q now.2012-12-15
  • 0
    let me tell you how I got this question: this is the expectation over all total-orders of a Gram matrix generated by $n$ vectors. I'd like to "boost" this n! estimators, in a machine learning manner. it's gonna turn into a paper and the answerer will get his acknowledges2012-12-15
  • 0
    Thanks for that information, but I'm afraid I don't understand it in that condensed form; perhaps you could elaborate on that in an edit to the question? Regarding the central factor, I think $PDP^T$ would have been clearer than $\operatorname{diag}(Pd)$. By the way, note that when you write out a name like "diag", it gets interpreted as a juxtaposition of variable names and formatted accordingly (e.g. italicized); you can get the right formatting using `\operatorname{diag}`. Also, please consider writing fewer and longer comments; the many short ones make the comment thread look daunting.2012-12-15
  • 0
    partial solution: $\mathbb E[x^TP^TL PDP^T L^TPy] = \mathbb x^T E[P^TL PDP^T L^TP] y = \mathbb x^T E[D P^T L^T P P^T L^T P] y = \mathbb x^T D E[P^T L^T P P^T L^T P] y $2012-12-15
  • 0
    Why can you replace $P^TLPD$ by its transpose $DP^TL^TP$? It's not a symmetric matrix. If the result does happen to be valid, note that $PP^T=I$.2012-12-15
  • 0
    right. fixed while you typed2012-12-15

1 Answers 1

1

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

  • 0
    man you're good! please send me your details so I'll put it in the paper2012-12-15
  • 0
    i opened 10minutemail temp account: hk4902@zoaxe.com please contact me through there2012-12-15
  • 0
    seems like when putting $=1\cdot x/n$ then the result reduces to $(n/(n-1))*x^T(D+)*y$2012-12-15
  • 0
    Nice calculation.2012-12-16