Problema matriz semidefinite positiva

Question

Esta es una pregunta sencilla, por lo menos, parece.

Que $x\in\mathbb{R}^n$ y tener en cuenta el % de matriz $C$tal que $C_{ij}=|x_i|+|x_j|-|x_i-x_j|$, muestran que el $C$ es semidefinitive positivo.

Podría resultar para algunos casos especiales, pero no viene el caso general, cualquier ayuda es bienvenida. Gracias de antemano.

Answer 1

Primero vamos a probar dos de lado los resultados.

Lema 1. deje $x_1 \ge \dots \ge x_n \ge 0$ y deje $A = [a_{ij}]$ tal que $a_{ij} = x_{\max\{i,j\}}$, es decir, $A$ tiene la forma

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

A continuación, $A$ es positivo semidefinite.

Prueba. Es bastante obvio que la matriz y todas sus líderes principales submiatrices puede ser reducido a través de la fila de las eliminaciones a triangular superior matrices con el positivo de la diagonal de los elementos. Por lo tanto, su determinante y todos sus líderes principales de los menores de edad son no negativos.

Lema 2. deje $0 \le x_1 \le \dots \le x_n$ y deje $B = [b_{ij}]$ tal que $b_{ij} = x_{\min\{i,j\}}$.

Prueba. Tenga en cuenta que $B = P A P^T$ donde $P$ es simétrica involutory permutación ($p_{ij} = \delta_{n+1-i,j}$) y $A$ tiene de Lema 1.

La prueba de la OP de la instrucción. Tenga en cuenta que $A$ es positivo semidefinite si y sólo si $P A P^T$ es positivo semidefinite, para cualquier permutación $P$. Esto significa que podemos suponer $x_1 \le x_2 \le \cdots x_n$, sin pérdida de generalidad.

Es fácil ver (se deja como ejercicio para el lector :-P) que tal $x$ produce un blockdiagonal matriz $A = A_1 \oplus A_2$ donde $A_1$ cumple Lema 1, y $A_2$ cumple Lema 2, por lo $A$ es positivo semidefinite. Bloque $A_1$ es inducida por la negativa y $A_2$ es inducida por los elementos positivos de $x$ (cero sólo crea cero de la fila y de la columna, por lo que puede ser incluido en cualquiera de las $A_1$ o $A_2$).