Pruebas reveladoras de la fórmula de Sherman-Morrison y del lema del determinante matricial

Question

Hay dos afirmaciones sobre una matriz bajo actualizaciones de rango uno que te agradecería que me dieras alguna prueba perspicaz.

Supongamos que $A$ sea un no singular $n \times n$ matriz y $\mathbf{u},\mathbf{v}$ sean vectores.

En primer lugar, el Sherman-Morrison fórmula establece que:

$$ \left( A + \mathbf{u} \mathbf{v}^T \right)^{-1} = A^{-1} - \frac{A^{-1}\mathbf{u} \mathbf{v}^TA^{-1}}{1 + \mathbf{v}^TA^{-1}\mathbf{u}}.$$

(Podemos demostrarlo mediante verificando que el RHS multiplicado por $A + \mathbf{u} \mathbf{v}^T$ es $I$ .)

En segundo lugar, el lema determinante de la matriz establece que:

$$\det\left(A+\mathbf{u}\mathbf{v}^T\right) = \det(A) \left( 1 + \mathbf{v}^T A^{-1}\mathbf{u} \right).$$

(En la prueba de wikipedia Sólo tenemos que verifique alguna identidad de nuevo).

Es fácil verificar estas pruebas, pero no me queda claro cómo llegar a la identidad. ¿Existen otras pruebas que no sean simplemente multiplicación de matrices y que nos den alguna idea? ¿O alguna explicación informal?

Answer 1

Debo hacer una aclaración previa. Puede que no sea el tipo de conocimiento que estás buscando y ciertamente no tan profundo como las respuestas anteriores, pero es una derivación muy directa que sólo requiere los conocimientos más básicos de álgebra lineal.

Supongamos que desea resolver lo siguiente para $\mathbf{x}$ :

$$\left(A+\mathbf{uv}^T\right)\mathbf{x}=\mathbf{y}$$ $$A\mathbf{x}=\mathbf{y}-\mathbf{uv}^T\mathbf{x}$$ $$\mathbf{x}=A^{-1}\mathbf{y}-A^{-1}\mathbf{uv}^T\mathbf{x}$$

Observe que $\mathbf{v}^T\mathbf{x}$ es un escalar, llamémoslo $s$ .

Así que la solución para $\mathbf{x}$ en términos de $s$ es:

$$\mathbf{x}=A^{-1}\mathbf{y}-A^{-1}\mathbf{u}s$$

Y resolviendo para $s$ :

$$s=\mathbf{v}^T\mathbf{x}=\mathbf{v}^TA^{-1}\mathbf{y}-\mathbf{v}^TA^{-1}\mathbf{u}s$$ $$\left(1+\mathbf{v}^TA^{-1}\mathbf{u}\right)s=\mathbf{v}^TA^{-1}\mathbf{y}$$ $$s=\frac{\mathbf{v}^TA^{-1}\mathbf{y}}{1+\mathbf{v}^TA^{-1}\mathbf{u}}$$

Sustituyendo por $s$ en la solución para $\mathbf{x}$ : $$\mathbf{x}=A^{-1}\mathbf{y}-\frac{A^{-1}\mathbf{uv}^TA^{-1}\mathbf{y}}{1+\mathbf{v}^TA^{-1}\mathbf{u}}$$

O:

$$\mathbf{x}=\left(A^{-1}-\frac{A^{-1}\mathbf{uv}^TA^{-1}}{1+\mathbf{v}^TA^{-1}\mathbf{u}}\right)\mathbf{y}$$

Así que..:

$$\left(A+\mathbf{uv}^T\right)^{-1}=A^{-1}-\frac{A^{-1}\mathbf{uv}^TA^{-1}}{1+\mathbf{v}^TA^{-1}\mathbf{u}}$$

Answer 2

Mire primero $I + \mathbf{u}\mathbf{v}^\top$ . Para ello puede ser necesario factorizar $A + \mathbf{u}\mathbf{v}^\top = A\left(I + A^{-1}\mathbf{u}\mathbf{v}^\top\right)$ lo que puede ayudar a intuir el término $A^{-1}\mathbf{u}$ en las fórmulas.

Considere cómo $I + \mathbf{u}\mathbf{v}^\top$ actúa sobre el vector $\mathbf{u}$ : $$\left(I + \mathbf{u}\mathbf{v}^\top\right)\mathbf{u} = \mathbf{u} + \mathbf{u}\mathbf{v}^\top\mathbf{u} = \left(1+\mathbf{v}^\top\mathbf{u}\right)\mathbf{u}$$

Esto demuestra que $\mathbf{u}$ es un vector propio derecho con valor propio de $1+\mathbf{v}^\top\mathbf{u}$ . La inversa debe tener el mismo vector propio pero con valor propio $(1+\mathbf{v}^\top\mathbf{u})^{-1}$ . (Si $\mathbf{v}^\top\mathbf{u}=-1$ entonces la matriz es singular). El resto de los valores propios son unos, ya que cualquier $\mathbf{b}$ tal que $\mathbf{v}^\top\mathbf{b} = 0$ da $\left(I + \mathbf{u}\mathbf{v}^\top\right)\mathbf{b}=\mathbf{b}$ . Esto completa todo el espectro ( siempre que $\mathbf{v}^\top\mathbf{u} \ne -1$ ), que muestra los valores eignevalues de ones y el valor de $1 + \mathbf{v}^\top\mathbf{u}$ .

A partir de aquí obsérvese que cualquier matriz con dicho espectro debe ser de la forma $I+\mathbf{u}g\mathbf{v}^\top$ (tras la factorización de $A$ mencionado anteriormente) donde $g$ es cualquier escalar. Esta es la forma general de matriz que tiene tal espectro, con todos excepto uno de los valores propios como unos, el otro valor propio con los vectores propios derecho e izquierdo de $\mathbf{u}$ y $\mathbf{v}^\top$ (que tiene valor propio paramétrico en la variable $g$ ).

Una vez comprendida la necesidad de esa forma, el resto es álgebra, encontrar el valor para $g$ que resuelve las ecuaciones. Por ejemplo, la inversa:

\begin{align} \left(I+ \mathbf{u}\mathbf{v}^\top\right) \left(I+ \mathbf{u}\mathbf{v}^\top\right)^{-1} &= I \\ \left(I+ \mathbf{u}\mathbf{v}^\top\right) \left(I+ \mathbf{u}g\mathbf{v}^\top\right) &=I \\ I+ \mathbf{u}g\mathbf{v}^\top+ \mathbf{u}\mathbf{v}^\top + \mathbf{u}\mathbf{v}^\top\mathbf{u}g\mathbf{v}^\top&=I \\ I+ \mathbf{u}\left(g+ 1 + \mathbf{v}^\top\mathbf{u}g \right)\mathbf{v}^\top&=I \\ \Rightarrow g+ 1 + \mathbf{v}^\top\mathbf{u}g &= 0 \\ g(1+\mathbf{v}^\top\mathbf{u}) &= -1 \\ g = \frac{-1}{1+\mathbf{v}^\top\mathbf{u}} \\ \end{align}

Para que tengamos $$\left(I+ \mathbf{u}\mathbf{v}^\top\right)^{-1} = \left(I+ \mathbf{u}\frac{-1}{1+\mathbf{v}^\top\mathbf{u}}\mathbf{v}^\top\right)$$

Answer 3

Obsérvese que basta con demostrar la fórmula de Sherman-Morrison para $A = I$ . Supongamos que lo probamos para $A=I$ entonces \begin{align*} (A+\mathbf{u}\mathbf{v}^T)^{-1} &= (A(I+(A^{-1}\mathbf{u})\mathbf{v}^T))^{-1} = \left(I - \frac{(A^{-1}\mathbf{u})\mathbf{v}^T}{1+\mathbf{v}^T(A^{-1}\mathbf{u})}\right)A^{-1} \\ &= A^{-1} - \frac{A^{-1}\mathbf{u}\mathbf{v}^TA^{-1}}{1+\mathbf{v}^TA^{-1}\mathbf{u}}. \end{align*}

He aquí una derivación de la fórmula de Sherman-Morrison para el caso $A=I$ cuando $\|u\| < 1$ y $\|v\| < 1$ . \begin{align*} (I+\mathbf{u}\mathbf{v}^T)^{-1} &= \sum_{k=0}^{\infty} (-1)^k (\mathbf{u}\mathbf{v}^T)^k = I + \sum_{k=1}^{\infty} (-1)^k (\mathbf{u}\mathbf{v}^T)^k\\ &= I + \mathbf{u}\left(\sum_{k=1}^{\infty} (-1)^{k} (\mathbf{v}^T\mathbf{u})^{k-1} \right)\mathbf{v}^T = I - \mathbf{u} \times \frac{1}{1 + \mathbf{v}^T\mathbf{u}} \times \mathbf{v}^T\\ &=I - \frac{\mathbf{u} \mathbf{v}^T}{1 + \mathbf{v}^T\mathbf{u}} \end{align*}

Answer 4

La idea de Sherman Morrison es ver cómo una perturbación de bajo rango afecta a la inversa, es decir, si escribimos $$\left(A + uv^T \right)^{-1} - A^{-1} = B$$ queremos saber si se puede decir algo sobre $B$ . $$\left(A + uv^T \right) \left( A^{-1} + B\right) = I$$ Por lo tanto, $$I + uv^T A^{-1} + AB + uv^T B = I$$ Por lo tanto, esto demuestra que $$AB = -uv^T\left(A^{-1} + B \right)$$ es un rango $1$ matriz. Dado que $A$ es una matriz de rango completo, vemos que $B$ debe ser rango $1$ . Este es el principal mensaje de Sherman-Morrison, es decir, un rango $r$ se mantiene bajo inversión. Una vez realizado esto, la fórmula exacta para $B$ puede obtenerse a partir de manipulaciones algebraicas.

Answer 5

Se puede obtener una fórmula general (Sherman-Morrison-Woodbury) a partir del cálculo de la inversa de una matriz de bloques $M=\begin{pmatrix} A &B\\ C&D \end{pmatrix} $ con $A\in\mathrm{GL}_n(\mathbb{F}),~D\in\mathrm{M}_m(\mathbb{F}),~B\in\mathrm{M}_{n\times m}(\mathbb{F})$ y $C\in\mathrm{M}_{m\times n}(\mathbb{F})$ . Uno tiene $$M\in\mathrm{GL}_{n+m}(\mathbb{F})\iff \mathrm{det}(D-CA^{-1}B)\neq0\quad(*)$$ desde $$ M=\begin{pmatrix} I_n &0\\ CA^{-1}&I_m \end{pmatrix}\begin{pmatrix} A &0\\ 0&D-CA^{-1}B \end{pmatrix}\begin{pmatrix} I_n &A^{-1}B\\ 0&I_m \end{pmatrix}$$ Entonces, a partir de dos representaciones de la matriz de bloques $M$ se obtiene \begin{align*} M^{-1}&=\begin{pmatrix} I_n &-A^{-1}B\\ 0&I_m \end{pmatrix}\begin{pmatrix} A^{-1} &0\\ 0&(D-CA^{-1}B)^{-1} \end{pmatrix} \begin{pmatrix} I_n &0\\ -CA^{-1}&I_m \end{pmatrix} &\\ &= \begin{pmatrix} I_n &0\\ -D^{-1}C&I_m \end{pmatrix}\begin{pmatrix} (A-BD^{-1}C)^{-1} &0\\\\N 0&D^{-1} \end{pmatrix} \begin{pmatrix} I_n &-BD^{-1}\\ 0&I_m \end{pmatrix} & \end{align*} Un cálculo sencillo muestra que $$(A-BD^{-1}C)^{-1}=A^{-1}+A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1}\quad (**)$$ Ahora, para las fórmulas de Shermann-Morrison, una sustitución : $D=1, B=-u\in\mathrm{M}_{n\times1}(\mathbb{F})$ y $C=v^{T}\in\mathrm{M}_{1\times n}(\mathbb{F})$ induce:

De $(*)$ , \begin{align*}A+uv^{T}\in\mathrm{GL}_n(\mathbb{F})&\iff \mathrm{det}(v^{T}A^{-1}u)\neq0\\&\iff (v^{T}A^{-1}u)\neq0\end{align*} y de $(**)$ , $$(A+uv^{T})^{-1}=A^{-1}-\dfrac{A^{-1}uv^{T}A^{-1}}{1+v^{T}A^{-1}u}$$