Matrix inversion lemmas are extremely useful formulae that allow to efficiently compute how simple changes in a matrix affect its inverse.
One of the simplest changes that can be performed on a matrix is a so-called rank one update.
Definition Let be a matrix and and two column vectors. Then, the transformationis called a rank one update to .
The reason why the transformation is called rank one is that the rank of the matrix is equal to (because a single vector, , spans all the columns of ).
The first inversion lemma we present is for rank one updates to identity matrices.
Proposition Let be the identity matrix and and two column vectors. The matrixis invertible if and only ifWhen it is invertible, its inverse is
Let us first prove the "if" part. The assumption ensures that the ratioand the proposed inverseare well-defined. Moreover, the latter satisfies the definition of inverse (a matrix multiplied by its inverse gives the identity matrix):Let us now prove the "only if" part. Suppose orThe latter equality implies . Post-multiply the matrixby :Thus, the linear combination of the columns of with coefficients taken from the non-zero vector gives the zero vector. As a consequence, the columns of are not linearly independent, the matrix is not full-rank, hence not invertible.
Note the dimensions of the matrix products involved in this inversion lemma:
the rank one update, that is, the productis ;
the invertibility condition is based on the productwhose dimension is ; in other words, it is a scalar.
The Sherman-Morrison formula, shown in the next proposition, generalizes the previous inversion lemma by considering rank one updates to a generic invertible matrix (instead of only considering rank one updates to the identity matrix).
Proposition Let be a invertible matrix and and two column vectors. The rank one updateis invertible if and only ifWhen it is invertible, its inverse is
Note thatIn other words, we can write a rank one update to as the product of and a rank one update to the identity matrix (the update is performed with the column vectors and ). Thus, by the standard result on the inverse of a product, we have that is invertible if and only if the two factors of the product, that is,and are invertible. But is invertible by assumption, and the condition for the invertibility of a rank one update to the identity matrix has been derived in the previous proposition: the rank one update is invertible if and only ifWhen it is invertible, its inverse isAs a consequence,
The Sherman-Morrison formula is very useful not only because rank one updates are found in many theorems in matrix algebra, but also because it can be a computationally efficient way of calculating the inverse when has already been calculated. The number of arithmetic operations needed to compute from scratch is proportional to , while the number of operations needed to update the inverse with Sherman-Morrison formula is proportional to . Even if in the latter case the constant of proportionality is higher than in the former, when is sufficiently large, the computational cost of the update is much lower.
Another useful matrix inversion lemma goes under the name of Woodbury matrix identity, which is presented in the following proposition.
Proposition Let be a invertible matrix, and two matrices, and an invertible matrix. If is invertible, then is invertible and its inverse is
The condition thatexists ensures that the proposed inverse is well-defined. We need to check that the proposed inverse satisfies the definition of inverse (a matrix multiplied by its inverse gives the identity matrix):
Note that when and , the Woodbury matrix identity coincides with the Sherman Morrison formula. Therefore, the latter is a special case of the former.
The reasons why this inversion lemma is worth knowing are similar to those we have explained for the Sherman Morrison formula: it is often used in matrix algebra, and it saves computations when is already known (and is significantly smaller than ).
Most of the learning materials found on this website are now available in a traditional textbook format.