Sherman–Morrison formula

In mathematics, in particular linear algebra, the Sherman–Morrison formula, named after Jack Sherman and Winifred J. Morrison, computes the inverse of the sum of an invertible matrix A {displaystyle A} and the outer product, u v T {displaystyle uv^{T}} , of vectors u {displaystyle u} and v {displaystyle v} . The Sherman–Morrison formula is a special case of the Woodbury formula. Though named after Sherman and Morrison, it appeared already in earlier publications. Suppose A ∈ R n × n {displaystyle Ain mathbb {R} ^{n imes n}} is an invertible square matrix and u {displaystyle u} , v ∈ R n {displaystyle vin mathbb {R} ^{n}} are column vectors. Then A + u v T {displaystyle A+uv^{T}} is invertible iff 1 + v T A − 1 u ≠ 0 {displaystyle 1+v^{T}A^{-1}u eq 0} . In this case, Here, u v T {displaystyle uv^{T}} is the outer product of two vectors u {displaystyle u} and v {displaystyle v} . The general form shown here is the one published by Bartlett. ( ⇐ {displaystyle Leftarrow } ) To prove that the backward direction ( 1 + v T A − 1 u ≠ 0 ⇒ A + u v T {displaystyle 1+v^{T}A^{-1}u eq 0Rightarrow A+uv^{T}} is invertible with inverse given as above) is true, we verify the properties of the inverse. A matrix Y {displaystyle Y} (in this case the right-hand side of the Sherman–Morrison formula) is the inverse of a matrix X {displaystyle X} (in this case A + u v T {displaystyle A+uv^{T}} ) if and only if X Y = I {displaystyle XY=I} . We first verify that the right hand side ( Y {displaystyle Y} ) satisfies X Y = I {displaystyle XY=I} . ( ⇒ {displaystyle Rightarrow } ) Reciprocally, if 1 + v T A − 1 u = 0 {displaystyle 1+v^{T}A^{-1}u=0} , then letting x = A − 1 u {displaystyle x=A^{-1}u} , one has ( A + u v T ) x = 0 {displaystyle (A+uv^{T})x=0} thus ( A + u v T ) {displaystyle (A+uv^{T})} has a non-trivial kernel and is therefore not invertible. If the inverse of A {displaystyle A} is already known, the formula provides anumerically cheap wayto compute the inverse of A {displaystyle A} corrected by the matrix u v T {displaystyle uv^{T}} (depending on the point of view, the correction may be seen as a perturbation or as a rank-1 update).The computation is relatively cheap because the inverse of A + u v T {displaystyle A+uv^{T}} does not have to be computed from scratch (which in general is expensive),but can be computed by correcting (or perturbing) A − 1 {displaystyle A^{-1}} . Using unit columns (columns from the identity matrix) for u {displaystyle u} or v {displaystyle v} , individual columns or rows of A {displaystyle A} may be manipulatedand a correspondingly updated inverse computed relatively cheaply in this way. In the general case, where A − 1 {displaystyle A^{-1}} is a n {displaystyle n} -by- n {displaystyle n} matrixand u {displaystyle u} and v {displaystyle v} are arbitrary vectors of dimension n {displaystyle n} , the whole matrix is updated and the computation takes 3 n 2 {displaystyle 3n^{2}} scalar multiplications. If u {displaystyle u} is a unit column, the computation takes only 2 n 2 {displaystyle 2n^{2}} scalar multiplications. The same goes if v {displaystyle v} is a unit column. If both u {displaystyle u} and v {displaystyle v} are unit columns, the computation takes only n 2 {displaystyle n^{2}} scalar multiplications.