Positivo semidefiniteness de una matriz

Question

No está claro cómo probar que la matriz $(\min(i,j))_{i,j=1,\dots,n}$ es (o no es) positivo semidefinite. Hay algunos hechos de Cuerno y Johnson del libro Análisis de la Matriz: si $A \in M_n$ es positivo semidefinite, a continuación, $a_{ii}a_{jj} \ge a_{ij}^2, i,j=1,2,\dots, n$ (fuente). Parece que esta condición no es suficiente para que la matriz a sea positivo semidefinite. Hay técnicas para comprobar que todos los valores propios de la matriz son positivos, o que el menor de edad son los factores determinantes de la no-negativos?

Answer 1

Para ampliar mi comentario: tenemos el teorema de "una matriz es simétrica positiva definida si y sólo si posee una descomposición de Cholesky". Es decir, cualquier simétrica positiva definida la matriz de $\mathbf A$ posee una factorización de la $\mathbf A=\mathbf G\mathbf G^\top$, donde el triangular inferior de la matriz $\mathbf G$ se llama Cholesky triángulo.

Ahora, me dicen que si $a_{ij}=\min(i,j)$, $g_{ij}=[i\geq j]$ donde $[p]$ es una Iverson soporte, igual a $1$ si $p$ es cierto, y $0$ si $p$ es falso. Como un ejemplo, ($n=6$),

$$\begin{pmatrix}1 & 1 & 1 & 1 & 1 & 1 \\1 & 2 & 2 & 2 & 2 & 2 \\1 & 2 & 3 & 3 & 3 & 3 \\1 & 2 & 3 & 4 & 4 & 4 \\1 & 2 & 3 & 4 & 5 & 5 \\1 & 2 & 3 & 4 & 5 & 6\end{pmatrix}=\begin{pmatrix}1 & 0 & 0 & 0 & 0 & 0 \\1 & 1 & 0 & 0 & 0 & 0 \\1 & 1 & 1 & 0 & 0 & 0 \\1 & 1 & 1 & 1 & 0 & 0 \\1 & 1 & 1 & 1 & 1 & 0 \\1 & 1 & 1 & 1 & 1 & 1\end{pmatrix}\cdot\begin{pmatrix}1 & 0 & 0 & 0 & 0 & 0 \\1 & 1 & 0 & 0 & 0 & 0 \\1 & 1 & 1 & 0 & 0 & 0 \\1 & 1 & 1 & 1 & 0 & 0 \\1 & 1 & 1 & 1 & 1 & 0 \\1 & 1 & 1 & 1 & 1 & 1\end{pmatrix}^\top$$

Esto es equivalente a probar que

$$\min(i,j)=\sum_{k=1}^n [i\geq k][k\leq j]$$

o, desde la $[p][q]=[p\text{ and }q]$,

$$\min(i,j)=\sum_{k=1}^n [i\geq k\text{ and }j\geq k]$$

y que la identidad de hecho, sostiene que ahora es un poco más fácil de ver.

Answer 2

A partir de un comentario de J. M. de la respuesta - considero que éste es esencialmente equivalente a su respuesta, pero:

Considere la posibilidad de un arbitrario ${\bf x}=(x_1, x_2 \cdots x_n)^T$. Ahora,

$$\sum_{i=1}^N \left(\sum_{j=i}^N x_j\right)^2 \ge0$$

con la igualdad iff ${\bf x}={\bf 0}$. Pero la expansión de las sumas, y calculando el coeficiente de la $x_i x_j$ plazo, tenemos que:

• al $i=j$: el plazo $x_i^2$ aparece $i$ veces.

• al $i\ne j$: el plazo $x_i x_j$ aparece $2 \min(i,j)$ veces.

Entonces, por encima de la suma puede ser escrito como

$$\sum_{i=1}^N \sum_{j=1}^N \min(i,j) x_i x_j = {\bf x^T A x}$$

por lo tanto, debido a que esto es positivo, ${\bf A}$ es (estrictamente) positiva definida.

Answer 3

Otra solución alternativa: se puede demostrar que la inversa de la min-matriz es la perturbado Toeplitz de la matriz tridiagonal

$$\begin{pmatrix}2&-1&&&\\-1&2&-1&&\\&-1&\ddots&\ddots&\\&&\ddots&2&-1\\&&&-1&1\end{pmatrix}$$

cuyo polinomio característico es

$$(-1)^n\left((x-1)U_{n-1}\left(\frac{x-2}{2}\right)-U_{n-2}\left(\frac{x-2}{2}\right)\right)$$

(donde $U_n(x)$ es el polinomio de Chebyshev de la segunda clase), y tiene los autovalores

$$\mu_k=2+2\cos\left(\frac{2k\pi}{2n+1}\right),\qquad k=1\dots n$$

Por lo tanto, los valores propios de la min-matriz son los recíprocos de los $\mu_k$,

$$\lambda_k=\frac14\sec^2\left(\frac{k\pi}{2n+1}\right)$$

y estos son fáciles de ver para ser positivo, mostrando así que el min-matriz es positiva definida.

Answer 4

La matriz de todo es positiva semidefinite (es $n$ veces una proyección ortogonal). Si $A$ es positivo semidefinite, entonces también lo es $\begin{bmatrix}0&0\\0&A\end{bmatrix}$. Por lo tanto la matriz es una suma de $n$ positivo semidefinite matrices, y por lo tanto es positiva semidefinite. Ya es invertible (para cada una de las $k\in\{1,2,\ldots,n\}$, $k^\text{th}$ fila no es en el lapso de la primera $k-1$ filas, debido a que el $k^\text{th}$ $(k-1)^\text{st}$ entradas diferentes), incluso es positiva definida.

---

Más explícitamente, el min de la matriz es $P_1+P_2+\cdots+P_n$ donde $P_k$ $(n-k+1)\times (n-k+1)$ bloque de $1$s en la parte inferior derecha, y el resto $0s$. Tenga en cuenta que cada una de las $P_k$ es simétrica, y $P_k=\dfrac{1}{n-k+1}P_k^2$, lo que hace que sea fácil de comprobar que $P_k$ es positivo semidefinite.

Answer 5

De menor importancia son los factores determinantes computable: denotan como $A_n$ la matriz que estamos tratando. Tenga en cuenta que el $j$-ésimo menor de $A_n$$A_j$. Así que tenemos que demostrar que $\det A_j > 0$ todos los $j$. A ver, considere a la última línea de la matriz, y de do $L_j\leftarrow L_j-L_{j-1}$. Esto muestra que $\det A_j=\det A_{j-1}$, lo $\det A_j=1$ para todo entero $j$, y por Sylvester criterio que estamos hecho.