¿Este tipo de matriz es siempre semidefinida positiva?

Question

Dejemos que $b\in[0,1]^n$ con $n\in\mathcal{N}^*$ . Consideremos la matriz simétrica $A=(a_{i,j})$ definido por $$ a_{i,j}=\begin{cases}\min\lbrace b_i,...,b_j\rbrace &\mbox{if } i<j\\ \min \lbrace b_j,...,b_i\rbrace &\mbox{if } j\leq i\end{cases} $$ Es $A$ ¿siempre es semidefinido positivo?

Por ejemplo, la matriz generada por el vector $[0. 1, 0.2, 0.3]$ es $$ \left(\begin{matrix} 0.1 & 0.1 & 0.1 \\ 0.1 & 0.2 & 0.2 \\ 0.1 & 0.2 & 0.3 \\ \end{matrix}\right) $$ mientras que la generada por el vector $[0. 2, 0.1, 0.3]$ es $$ \left(\begin{matrix} 0.2 & 0.1 & 0.1 \\ 0.1 & 0.1 & 0.1 \\ 0.1 & 0.1 & 0.3 \\ \end{matrix}\right)\text{.}$$ Hasta ahora, sólo he conseguido demostrar que $A$ es semidefinido positivo cuando $b$ está ordenado (en orden creciente o decreciente). La prueba es por inducción:

La afirmación es claramente válida si $n=1$ .

Paso de inducción: Denotemos $A(b)$ la matriz generada al seguir el procedimiento descrito anteriormente con un vector $b$ .

Dejemos que $n\in\mathcal{N}^*$ . Supongamos que todas las matrices $M\in\lbrace A(b), b\in [0,1]^{i}, i\in\lbrace 1,...n\rbrace, b \mbox{ sorted}\rbrace$ son semidefinidos positivos.

Consideremos entonces un vector ordenado $b$ con $n+1$ elementos y aplicar el criterio de Sylvester: todas las submatrices de $A(b)$ correspondientes a los menores principales pertenecen a $\lbrace A(b), b\in [0,1]^{i}, i\in\lbrace 1,...n\rbrace, b \mbox{ sorted}\rbrace$ por lo que el resultado se mantiene.

También he intentado generar contraejemplos en el caso de que $b$ no se clasifica, pero sin éxito.

Answer 1

Sí, es semidefinido positivo. Esto se puede demostrar fácilmente por inducción matemática sobre $n$ .

Para destacar su tamaño, así como su dependencia de los parámetros $b_i$ s, denotamos la matriz generada por $(b_1,\ldots,b_n)\in[0,1]^n$ como se describe en su pregunta como $A(b_1,\ldots,b_n)$ . En el paso inductivo, dejemos que $b_i=\min(b_1,\ldots,b_n)$ . Entonces \begin{aligned} A(b_1,\ldots,b_n) &=\left[\begin{array}{c|c|c} A(b_1,\,\ldots,\,b_{i-1}) &\begin{matrix}b_i\\ \vdots\\ b_i\end{matrix} & \begin{matrix}b_i&\cdots&b_i\\ \vdots&&\vdots\\ b_i&\cdots&b_i\end{matrix} \\ \N - Línea de flotación \begin{matrix}b_i&\cdots&b_i\end{matrix}&b_i&\begin{matrix}b_i&\cdots&b_i\end{matrix}\\ \hline \begin{matrix}b_i&\cdots&b_i\\ \vdots&&\vdots\\ b_i&\cdots&b_i\end{matrix} & \begin{matrix}b_i\\ \vdots\\ b_i\end{matrix} &A(b_{i+1},\,\ldots,\,b_n) \end{array}\right]\\N- &=\iquierda[ \begin{array}{c|c|c} A(b_1-b_i,\,\ldots,b_{i-1}-b_i)&0&0\\ \hline 0&0&0\\ \hline 0&0&A(b_{i+1}-b_i,\,\ldots,\,b_n-b_i) \end{array} \derecha]+b_iE \fin{alineado} donde $E$ denota la matriz todo-uno. Dado que $b_k-b_i\in[0,1]$ por cada $k$ vemos que $A(b_1,\ldots,b_n)$ es semidefinida positiva, por inducción.

Answer 2

La matriz es efectivamente semidefinida positiva. Para ver esto, mostraremos que hay una forma alternativa de formular esta matriz como una suma de matrices semidefinidas positivas.

Dejemos que $b=(b_1,\ldots,b_n)\in [0,1]^n$ sea el vector dado. Para simplificar, supongamos que todas las componentes son distintas y positivas; esto es sin pérdida de generalidad, ya que las componentes de $A$ son continuas y el conjunto de matrices semidefinidas positivas es cerrado, por lo que podemos perturbar las entradas para que sean distintas y positivas, y luego tomar los límites conservar la semidefinición positiva. Hagamos también la convención de que $b_0=b_{n+1}=0$ . Para cada $i=1,\ldots,n$ , dejemos que $l(i)\leq i\leq r(i)$ denotan el mayor rango de índices que contienen $i$ tal que $b_i$ es mínimo en este rango, es decir $$i= \arg\min_j\{b_{l(i)},b_{l(i+1)},\ldots,b_i,\ldots, b_{r(i)}\}\quad\land\quad b_{l(i)-1},b_{r(i)+1}<b_i.$$

Además, escribe $\tau(i)$ para $\max\{b_{l(i)-1},b_{r(i)+1}\}$ . Por último, para $1\leq i\leq j\leq n$ , dejemos que $J_{i:j}$ denotan el $n\times n$ matriz simétrica con todo- $1$ en las entradas cuyos índices de fila y columna están en el rango $[i,j]$ y $0$ en todos los demás lugares.

Entonces puede comprobar que \begin{equation} A=\sum_{i=1}^n (b_{i}-\tau(i))J_{l(i):r(i)}. \end{equation} Para entender por qué esto es correcto, supongamos $p\leq q$ sin pérdida y considerar el $(p,q)$ entrada de $A$ . Supongamos que $k= \arg\min\{b_p,\ldots,b_q\}$ y pensemos en qué términos de la suma tienen entradas no nulas en el $(p,q)$ entrada. Esto sucede para cada $i$ tal que $p,q\in [l(i),r(i)]$ . Esto no puede pasar por ningún $i$ tal que $b_k<b_i$ , como $[l(i),r(i)]$ no puede contener $k$ por lo que no puede contener ambos $p$ y $q$ . Evidentemente, el término correspondiente a $b_k$ es distinto de cero, ya que $b_k$ era la entrada mínima en el rango $[p,q]$ y contribuye $b_k-\tau(k)$ . Entonces el índice único $j$ cuyo valor corresponde a $\tau(k)$ también es tal que $p,q\in [l(j),r(j)]$ ya que su intervalo debe contener el de $k$ por construcción, por lo que también obtenemos el término $b_j-\tau(j)$ en este punto consideramos el índice correspondiente a $\tau(j)$ que de hecho debe ser el otro término considerado en nuestra construcción de $\tau(j)$ es decir $\min\{b_{l(i)-1},b_{r(i)+1}\}$ . Continuando de esta manera, la suma se telescopia para dar justo $b_k$ (Le dejo que compruebe los detalles; la forma en que construimos $\tau$ hace que el telescopio funcione). Esto muestra $A$ es realmente como se ha definido anteriormente.

La semidefinición positiva de $A$ es ahora inmediato, ya que $J_{i:j}$ es semidefinido positivo para cualquier $1\leq i\leq j\leq n$ ya que se puede escribir como $\mathbf{1}_{i:j}\mathbf{1}^T_{i:j}$ , donde $\mathbf{1}$ es el vector con $1$ s en las entradas de $i$ a $j$ y cero en el resto. Estas matrices de rango uno se multiplican por números no negativos y luego se suman, por lo que $A$ es semidefinido positivo.

Para dar un ejemplo, su primera matriz se escribe como \begin{align} (0.1-0) J_{1:3}+(0.2-0.1) J_{2:3}+(0.3-0.2)J_{3:3}&=0.1\begin{pmatrix} 1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1 \end{pmatrix} +.1 \begin{pmatrix} 0 & 0 & 0\\ 0 & 1 & 1\\ 0 & 1 & 1 \end{pmatrix} +.1 \begin{pmatrix} 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 1 \end{pmatrix} \\ &= \begin{pmatrix} .1 & .1 & .1\\ .1 & .2 & .2\\ .1 & .2 & .3 \end{pmatrix} , \fin mientras que su segundo ejemplo puede escribirse como \begin{align} (0.2-0.1)J_{1:1}+(0.1-0)J_{1:3}+(0.3-0.1)J_{3:3}&= .1\begin{pmatrix} 1 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0 \end{pmatrix}+0.1\begin{pmatrix} 1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1 \fin{pmatrix} +.2 \begin{pmatrix} 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 1 \end{pmatrix} \\ &= \begin{pmatrix} .2 & .1 & .1\\ .1 & .1 & .1\\ .1 & .1 & .3 \end{pmatrix} \end{align}