Positive semidefinite matrix problem This is a simple question, at least, looks like.
Let $x\in\mathbb{R}^n$ and consider the matrix $C$ such that $C_{ij}=|x_i|+|x_j|-|x_i-x_j|$, show that $C$ is positive semidefinitive. 
I could prove it for some special cases, but the general case is not coming, any help is welcome. Thanks in advance.
 A: Let us first prove two side-results.
Lema 1. let $x_1 \ge \dots \ge x_n \ge 0$ and let $A = [a_{ij}]$ such that $a_{ij} = x_{\max\{i,j\}}$, i.e., $A$ has the form
$$A = \begin{bmatrix}
x_1 & x_2 & x_3 & \dots \\
x_2 & x_2 & x_3 & \dots \\
x_3 & x_3 & x_3 & \dots \\
\vdots & \vdots & \vdots & \ddots
\end{bmatrix}.$$
Then $A$ is positive semidefinite.
Proof. It is fairly obvious that the matrix and all its leading principal submiatrices can be reduced via row eliminations to upper triangular matrices with the nonnegative diagonal elements. Hence, its determinant and all its leading principal minors are nonnegative.
Lema 2. let $0 \le x_1 \le \dots \le x_n$ and let $B = [b_{ij}]$ such that $b_{ij} = x_{\min\{i,j\}}$.
Proof. Note that $B = P A P^T$, where $P$ is a symmetric involutory permutation ($p_{ij} = \delta_{n+1-i,j}$) and $A$ has a from from Lemma 1.
Proof of the OP's statement. Note that $A$ is positive semidefinite if and only if $P A P^T$ is positive semidefinite, for any permutation $P$. This means that we can assume $x_1 \le x_2 \le \cdots x_n$, without the loss of generality.
It is easy to see (left as an exercise to the reader :-P) that such $x$ produces a blockdiagonal matrix $A = A_1 \oplus A_2$, where $A_1$ conforms to Lemma 1, and $A_2$ conforms to Lemma 2, so $A$ is positive semidefinite. Block $A_1$ is induced by negative and $A_2$ is induced by positive elements of $x$ (zero just creates zero row and column, so it can be included in either $A_1$ or $A_2$).
