Una forma práctica de comprobar si una matriz es definida positivamente

Question

Dejemos que $A$ sea una simetría $n\times n$ matriz.

He encontrado un método en la web para comprobar si $A$ es positivo definido :

$A$ es positivo-definido si todas las entradas diagonales son positivas, y cada entrada diagonal es mayor que la suma de los valores absolutos de todas las demás entradas de la fila/columna correspondiente.

No he podido encontrar una prueba para esta afirmación. Tampoco pude encontrar una referencia en mis libros de álgebra lineal.

Tengo algunas preguntas.

1. ¿Cómo se demuestra la afirmación anterior?

2. Es lo siguiente ligeramente más débil ¿es cierta la afirmación?

Una matriz simétrica $A$ es positivo-definido si todas las entradas diagonales son positivas, cada entrada diagonal es mayor que o igual a la suma de los valores absolutos de todas las demás entradas de la fila/columna correspondiente, y existe una entrada diagonal que es estrictamente mayor que la suma de los valores absolutos de todas las demás entradas de la fila/columna correspondiente.

Answer 1

Estas matrices se denominan (estrictamente) dominante en diagonal . La forma estándar de demostrar que son definidos positivos es con la Teorema del círculo de Gershgorin . Su condición más débil no da definición positiva; un contraejemplo es $\left[ \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{matrix} \right]$ .

Answer 2

Antes de continuar, permítanme añadir la advertencia de que una matriz simétrica puede violar sus reglas y seguir siendo positiva definida, dame un minuto para comprobar los valores propios

$$H \; = \; \left( \begin{array}{rrr} 3 & 2 & 0 \\ 2 & 3 & 2 \\ 0 & 2 & 3 \end{array} \right) .$$ Esto es positivo por la Ley de Inercia de Sylvester, https://en.wikipedia.org/wiki/Sylvester%27s_law_of_inertia

Se ofrece una prueba aquí como consecuencia del teorema del círculo de Gershgorin. Para más información, véase http://en.wikipedia.org/wiki/Diagonally_dominant_matrix y http://mathworld.wolfram.com/DiagonallyDominantMatrix.html o simplemente buscar en Google "simétrico diagonalmente dominante"

Metodología posterior, que equivale a completar repetidamente el cuadrado:

$$\bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc$$

$$P^T H P = D$$

$$\left( \begin{array}{rrr} 1 & 0 & 0 \\ - \frac{ 2 }{ 3 } & 1 & 0 \\ \frac{ 4 }{ 5 } & - \frac{ 6 }{ 5 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 3 & 2 & 0 \\ 2 & 3 & 2 \\ 0 & 2 & 3 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & - \frac{ 2 }{ 3 } & \frac{ 4 }{ 5 } \\ 0 & 1 & - \frac{ 6 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 3 & 0 & 0 \\ 0 & \frac{ 5 }{ 3 } & 0 \\ 0 & 0 & \frac{ 3 }{ 5 } \\ \end{array} \right)$$

$$Q^T D Q = H$$

$$\left( \begin{array}{rrr} 1 & 0 & 0 \\ \frac{ 2 }{ 3 } & 1 & 0 \\ 0 & \frac{ 6 }{ 5 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 3 & 0 & 0 \\ 0 & \frac{ 5 }{ 3 } & 0 \\ 0 & 0 & \frac{ 3 }{ 5 } \\ \end{array} \right) \left( \begin{array}{rrr} 1 & \frac{ 2 }{ 3 } & 0 \\ 0 & 1 & \frac{ 6 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 3 & 2 & 0 \\ 2 & 3 & 2 \\ 0 & 2 & 3 \\ \end{array} \right)$$

$$\bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc$$

Algoritmo discutido en referencia para libros de álgebra lineal que enseñan el método de Hermite inverso para matrices simétricas
https://en.wikipedia.org/wiki/Sylvester%27s_law_of_inertia
$$H = \left( \begin{array}{rrr} 3 & 2 & 0 \\ 2 & 3 & 2 \\ 0 & 2 & 3 \\ \end{array} \right)$$ $$D_0 = H$$ $$E_j^T D_{j-1} E_j = D_j$$ $$P_{j-1} E_j = P_j$$ $$E_j^{-1} Q_{j-1} = Q_j$$ $$P_j Q_j = Q_j P_j = I$$ $$P_j^T H P_j = D_j$$ $$Q_j^T D_j Q_j = H$$

$$H = \left( \begin{array}{rrr} 3 & 2 & 0 \\ 2 & 3 & 2 \\ 0 & 2 & 3 \\ \end{array} \right)$$

\==============================================

$$E_{1} = \left( \begin{array}{rrr} 1 & - \frac{ 2 }{ 3 } & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right)$$ $$P_{1} = \left( \begin{array}{rrr} 1 & - \frac{ 2 }{ 3 } & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{1} = \left( \begin{array}{rrr} 1 & \frac{ 2 }{ 3 } & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{1} = \left( \begin{array}{rrr} 3 & 0 & 0 \\ 0 & \frac{ 5 }{ 3 } & 2 \\ 0 & 2 & 3 \\ \end{array} \right)$$

\==============================================

$$E_{2} = \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & - \frac{ 6 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right)$$ $$P_{2} = \left( \begin{array}{rrr} 1 & - \frac{ 2 }{ 3 } & \frac{ 4 }{ 5 } \\ 0 & 1 & - \frac{ 6 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{2} = \left( \begin{array}{rrr} 1 & \frac{ 2 }{ 3 } & 0 \\ 0 & 1 & \frac{ 6 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{2} = \left( \begin{array}{rrr} 3 & 0 & 0 \\ 0 & \frac{ 5 }{ 3 } & 0 \\ 0 & 0 & \frac{ 3 }{ 5 } \\ \end{array} \right)$$

\==============================================

$$\bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc$$

$$P^T H P = D$$

$$\left( \begin{array}{rrr} 1 & 0 & 0 \\ - \frac{ 2 }{ 3 } & 1 & 0 \\ \frac{ 4 }{ 5 } & - \frac{ 6 }{ 5 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 3 & 2 & 0 \\ 2 & 3 & 2 \\ 0 & 2 & 3 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & - \frac{ 2 }{ 3 } & \frac{ 4 }{ 5 } \\ 0 & 1 & - \frac{ 6 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 3 & 0 & 0 \\ 0 & \frac{ 5 }{ 3 } & 0 \\ 0 & 0 & \frac{ 3 }{ 5 } \\ \end{array} \right)$$

$$Q^T D Q = H$$

$$\left( \begin{array}{rrr} 1 & 0 & 0 \\ \frac{ 2 }{ 3 } & 1 & 0 \\ 0 & \frac{ 6 }{ 5 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 3 & 0 & 0 \\ 0 & \frac{ 5 }{ 3 } & 0 \\ 0 & 0 & \frac{ 3 }{ 5 } \\ \end{array} \right) \left( \begin{array}{rrr} 1 & \frac{ 2 }{ 3 } & 0 \\ 0 & 1 & \frac{ 6 }{ 5 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 3 & 2 & 0 \\ 2 & 3 & 2 \\ 0 & 2 & 3 \\ \end{array} \right)$$

$$\bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc$$

Answer 3

Esta es otra forma de ver esto. Definir $R_i = A_{ii} - \sum_{j\neq i} \lVert A_{ij} \rVert$ . Su condición es que $R_i>0$ para todos $i$ .

Dejemos que $s_{ij} = \frac{A_{ij}}{\lVert A_{ij}\rVert}$ sea el signo de $A_{ij}$ . Entonces se puede comprobar algebraicamente (sólo hay que hacer coincidir los coeficientes) que para todo $x\in\mathbb{R}^n$ \N-[x^T A x = \N-suma_{i=1}^n R_ix_i^2 + \N-suma_{i=1}^n \N-suma_{j>i} \lVert A_{ij}\rVert (x_i + s_{ij} x_j)^2. \] Como los cuadrados son no negativos y la $R_i$ se suponen positivos, todos los sumandos son no negativos para todo $x\in\mathbb{R}^n$ . Además, si $x\neq 0$ entonces $x_i\neq 0$ para algunos $i$ Así que $x^TAx\geq R_ix_i^2>0$ . Por lo tanto, $A$ es positiva definida.

Esta expresión para $x^TAx$ puede considerarse alternativamente como la expresión de $A$ como una suma ponderada $A = \sum_k c_k v_kv_k^T$ donde cada $c_k>0$ y cada $v_k\in\mathbb{R}^n$ es un vector con soporte (número de entradas no nulas) a lo sumo dos, cada uno de los cuales es $\pm 1$ . Pero $v_kv_k^T$ es siempre semidefinido positivo para $v_k\in\mathbb{R}^n$ y las combinaciones positivas de matrices semidefinidas positivas son semidefinidas positivas. Dado que cada $R_i>0$ podemos disminuir algunos de los $c_k$ ligeramente (los que corresponden a la $v_k$ que son vectores unitarios estándar) y en su lugar escribir $A = cI + \sum_k c_k v_kv_k^T$ para $c>0$ lo que demuestra que $A$ es de hecho positiva definida.

Una cosa buena de esta prueba: Toda matriz definida positiva (o semidefinida) puede escribirse como una combinación positiva de matrices $vv^T$ pero esta prueba muestra que para las matrices diagonalmente dominantes podemos tomar todas las $v$ para tener apoyo como máximo $2$ . Esto permite intuir por qué la "mayoría" de las matrices definidas positivas no son diagonalmente dominantes. Por ejemplo, si $v$ es cualquier vector con un tamaño de soporte de al menos tres, entonces para un tamaño suficientemente pequeño $c$ , $cI + vv^T$ es positiva definida pero no es diagonalmente dominante.

Answer 4

Esto es, en parte, un refrito de la respuesta de Noah Stein, sin demasiado lío. Lo más importante es que te da una forma algorítmica de determinar qué tipo de matriz tienes.

Es fácil si sigues Método Cholesky en aquí .

Una matriz cuadrada es definida positiva si es simétrica (!) y $x^TAx>0$ para cualquier $x\neq0$ . Entonces, por el teorema de descomposición de Cholesky $A$ puede descomponerse exactamente de una manera en un producto

$$A = R^TR$$

donde $R$ es triangular superior y $r_{ii}>0$ .

Si esto es cierto, entonces (¡véase la referencia!), los elementos diagonales de $R$ debe cumplir

$$r_{ii} = +\sqrt{a_{ii}-\sum_{k=1}^{i-1}r_{ki}^2}\; j=i+1,\dots,n,$$

donde $n$ es la dimensión real del espacio vectorial. Si en algún momento esta raíz cuadrada es compleja o cero, entonces $A$ no puede ser positiva definida.

¡Bonito y limpio! Sólo hay que elevar al cuadrado, tomar la diferencia y la raíz cuadrada para encontrar si $A$ es positivo. Es incluso fácil programar este método incluso para un $n$ .

Answer 5

En el caso de las dos afirmaciones mencionadas, la primera es cierta sólo con el teorema del círculo de Gershgorin. Pero en realidad, la segunda afirmación es cierta si se añade una condición más a A: la matriz A es irreducible. Entonces el contraejemplo proporcionado a continuación ya no tiene sentido, ya que son reducibles.