Матрична тотожність Вудбурі

Матрична тотожність Вудбері

(A + U C V)^{- 1} = A^{- 1} - A^{- 1} U {(C^{- 1} + V A^{- 1} U)}^{- 1} V A^{- 1},

де матриці A розміру n×n, U розміру n×k, C розміру k×k і V розміру k×n.

Доведення через систему матричних рівнянь

Розв'язуючи систему матричних рівнянь

[\begin{matrix} A & U \\ V & - C^{- 1} \end{matrix}] [\begin{matrix} X \\ Y \end{matrix}] = [\begin{matrix} I \\ 0 \end{matrix}]

Отримаємо систему з двох рівнянь $A X + U Y = I$ та $V X - C^{- 1} Y = 0$ , вилучимо Y з першого рівняння: $(A + U C V) X = I$ .

Перетворимо перше рівняння так $X = A^{- 1} (I - U Y)$ , і підставимо його в друге рівняння $V A^{- 1} (I - U Y) = C^{- 1} Y$ .

Отримаємо $V A^{- 1} = (C^{- 1} + V A^{- 1} U) Y$ , чи $(C^{- 1} + V A^{- 1} U)^{- 1} V A^{- 1} = Y$ .

Підставимо Y в $A X + U Y = I$ , і отримаємо $A X + U (C^{- 1} + V A^{- 1} U)^{- 1} V A^{- 1} = I$ . Отримаємо

(A + U C V)^{- 1} = X = A^{- 1} - A^{- 1} U {(C^{- 1} + V A^{- 1} U)}^{- 1} V A^{- 1} .

В матриці

[\begin{matrix} A & U \\ V & C \end{matrix}]

для обнулення елемента під A (дано що A невироджена) домножимо зліва на ліву трикутну матрицю,

а для обнулення елемента над C домножимо справа на праву трикутну матрицю.

Отримаємо LDU розклад блочної матриці

[\begin{matrix} I & 0 \\ - V A^{- 1} & I \end{matrix}] [\begin{matrix} A & U \\ V & C \end{matrix}] [\begin{matrix} I & - A^{- 1} U \\ 0 & I \end{matrix}] = [\begin{matrix} A & 0 \\ 0 & C - V A^{- 1} U \end{matrix}]

Проінвертуємо обидві сторони і перенесемо трикутні матриці направо

${[\begin{matrix} A & U \\ V & C \end{matrix}]}^{- 1}$	$= {[\begin{matrix} I & A^{- 1} U \\ 0 & I \end{matrix}]}^{- 1} {[\begin{matrix} A & 0 \\ 0 & C - V A^{- 1} U \end{matrix}]}^{- 1} {[\begin{matrix} I & 0 \\ V A^{- 1} & I \end{matrix}]}^{- 1}$
	$= [\begin{matrix} I & - A^{- 1} U \\ 0 & I \end{matrix}] [\begin{matrix} A^{- 1} & 0 \\ 0 & (C - V A^{- 1} U)^{- 1} \end{matrix}] [\begin{matrix} I & 0 \\ - V A^{- 1} & I \end{matrix}]$
	$= [\begin{matrix} A^{- 1} + A^{- 1} U (C - V A^{- 1} U)^{- 1} V A^{- 1} & - A^{- 1} U (C - V A^{- 1} U)^{- 1} \\ - (C - V A^{- 1} U)^{- 1} V A^{- 1} & (C - V A^{- 1} U)^{- 1} \end{matrix}] (1)$

Також можна записати UDL розклад блочної матриці (дано що C невироджена)

[\begin{matrix} I & - U C^{- 1} \\ 0 & I \end{matrix}] [\begin{matrix} A & U \\ V & C \end{matrix}] [\begin{matrix} I & 0 \\ - C^{- 1} V & I \end{matrix}] = [\begin{matrix} A - U C^{- 1} V & 0 \\ 0 & C \end{matrix}]

Знову проінвертуємо обидві сторони і перенесемо трикутні матриці направо

${[\begin{matrix} A & U \\ V & C \end{matrix}]}^{- 1}$	$= {[\begin{matrix} I & 0 \\ C^{- 1} V & I \end{matrix}]}^{- 1} {[\begin{matrix} A - U C^{- 1} V & 0 \\ 0 & C \end{matrix}]}^{- 1} {[\begin{matrix} I & U C^{- 1} \\ 0 & I \end{matrix}]}^{- 1}$
	$= [\begin{matrix} I & 0 \\ - C^{- 1} V & I \end{matrix}] [\begin{matrix} (A - U C^{- 1} V)^{- 1} & 0 \\ 0 & C^{- 1} \end{matrix}] [\begin{matrix} I & - U C^{- 1} \\ 0 & I \end{matrix}]$
	$= [\begin{matrix} (A - U C^{- 1} V)^{- 1} & - (A - U C^{- 1} V)^{- 1} U C^{- 1} \\ - C^{- 1} V (A - U C^{- 1} V)^{- 1} & C^{- 1} V (A - U C^{- 1} V)^{- 1} U C^{- 1} + C^{- 1} \end{matrix}] (2)$

Порівняємо елементи (1,1) матриць (1) та (2) і отримаємо тотожність Вудбері:

(A - U C^{- 1} V)^{- 1} = A^{- 1} + A^{- 1} U (C - V A^{- 1} U)^{- 1} V A^{- 1} .

Якщо n = k та U = V = I_n, тоді

{(𝐀 + 𝐂)}^{- 1} = 𝐀^{- 1} - 𝐀^{- 1} 𝐂 {(𝐂 + {𝐂 𝐀}^{- 1} 𝐂)}^{- 1} {𝐂 𝐀}^{- 1} .

Якщо k = 1 та C = I_k, тоді U буде вектором-стовпцем u, та V буде вектором-рядком v^T. Тоді

{(𝐀 + {𝐮 𝐯}^{T})}^{- 1} = 𝐀^{- 1} - \frac{𝐀^{- 1} {𝐮 𝐯}^{T} 𝐀^{- 1}}{1 + 𝐯^{T} 𝐀^{- 1} 𝐮}

— має назву формули Шермана — Моррісона.

Якщо A = I_n та C = I_k, тоді

{(𝐈_{n} + 𝐔 𝐕)}^{- 1} = 𝐈_{n} - 𝐔 {(𝐈_{n} + 𝐕 𝐔)}^{- 1} 𝐕,

зокрема, справедливо

{(𝐈 + {𝐮 𝐯}^{T})}^{- 1} = 𝐈 - \frac{{𝐮 𝐯}^{T}}{1 + 𝐯^{T} 𝐮} .