# How to (dis-)prove that this symmetric matrix is P.S.D.?

for two random $n$-vectors $(X_1,X_2)$ define

$$f(X_1,X_2)=\text{med}((X_1+X_2)^2)-\text{med}((X_1-X_2)^2)$$

Now define the matrix $U$ with entries

$$U_{ij}=\frac{n}{4}f(X_i,X_j)$$

Based on a large number of computer simulations using many nearly collinear matrices $X=(X_1,\ldots,X_p)\in\mathbb{R}^{n\times p}$ with $n>p=100$, I've come to suspect that if the members of $X$ are in general linear position, then $U$ is P.S.D..

To put the matter to rest, I'm trying to prove this statement (or find a counter example). My question is how would you go about attacking this problem?

I've been trying to prove that $U$ is diagonally dominant (it is easy to show that $U_{ii}>U_{ij}\forall i\neq j$, but I have not been able to make any statement about the sum of the absolute values of the off-diagonal elements).

• By $\operatorname{med}((X_1+X_2)^2)$, do you mean you're squaring each component of the vector $X_1+X_2$ separately and then taking the median of those squares? And why do you use lower-case $x_1,x_2$ in $f(x_1,x_2)$ and then capital $X_1,X_2$ on the other side? (Capital means, presumably, referring to the things you called (capital) $X_1,X_2$ on the previous line.) – Michael Hardy Mar 24 '13 at 15:49
• yes, med((X1+X2)^2) means I'm squaring each component of the vector X1+X2 separately and then taking the median of those squares. I tried to edit the question for the second suggestion. Let me know if this fails to solve the problem. Thanks for taking the time. – user1963 Mar 24 '13 at 16:12

(This is too long for a comment.) I don't have an answer to your question. All I can say is that your conjecture is not true in general. For a counterexample, consider the case where $n=3,\,p=2$ and $$(X_1, X_2) = \begin{bmatrix} 1+\varepsilon&1-\varepsilon\\ 1-\varepsilon&1+\varepsilon\\ 1-\varepsilon&1-\varepsilon \end{bmatrix}$$ where $\varepsilon>0$ is a small number. Then \begin{align*} f(X_1,X_1) &= f(X_2,X_2) = 4(1-\varepsilon)^2,\\ f(X_1,X_2) &= 4 - 4\varepsilon^2 = 4(1-\varepsilon^2) \end{align*} and the resulting $U$ has a negative determinant and hence is not positive semidefinite.
Yet this counterexample does not generalize well for larger $n$ and $p$, and your statement is perhaps true in an overwhelming number of cases for some good statistical reasons, but I am totally clueless about them.