Matrix determinant lemma

In mathematics, in particular linear algebra, the matrix determinant lemma^[1]^[2] computes the determinant of the sum of an invertible matrix A and the dyadic product, u v^T, of a column vector u and a row vector v^T.

Statement

Suppose A is an invertible square matrix and u, v are column vectors. Then the matrix determinant lemma states that

\det({\mathbf {A}}+{\mathbf {uv}}^{{\mathrm {T}}})=(1+{\mathbf {v}}^{{\mathrm {T}}}{\mathbf {A}}^{{-1}}{\mathbf {u}})\,\det({\mathbf {A}})\,.

Here, uv^T is the outer product of two vectors u and v.

The theorem can also be stated in terms of the adjugate matrix of A:

\det({\mathbf {A}}+{\mathbf {uv}}^{{\mathrm {T}}})=\det({\mathbf {A}})+{\mathbf {v}}^{{\mathrm {T}}}{\mathrm {adj}}({\mathbf {A}}){\mathbf {u}}\,,

in which case it applies whether or not the square matrix A is invertible.

Proof

First the proof of the special case A = I follows from the equality:^[3]

{\begin{pmatrix}{\mathbf {I}}&0\\{\mathbf {v}}^{{\mathrm {T}}}&1\end{pmatrix}}{\begin{pmatrix}{\mathbf {I}}+{\mathbf {uv}}^{{\mathrm {T}}}&{\mathbf {u}}\\0&1\end{pmatrix}}{\begin{pmatrix}{\mathbf {I}}&0\\-{\mathbf {v}}^{{\mathrm {T}}}&1\end{pmatrix}}={\begin{pmatrix}{\mathbf {I}}&{\mathbf {u}}\\0&1+{\mathbf {v}}^{{\mathrm {T}}}{\mathbf {u}}\end{pmatrix}}.

The determinant of the left hand side is the product of the determinants of the three matrices. Since the first and third matrix are triangle matrices with unit diagonal, their determinants are just 1. The determinant of the middle matrix is our desired value. The determinant of the right hand side is simply (1 + v^Tu). So we have the result:

\det({\mathbf {I}}+{\mathbf {uv}}^{{\mathrm {T}}})=(1+{\mathbf {v}}^{{\mathrm {T}}}{\mathbf {u}}).

Then the general case can be found as:

{\begin{aligned}\det({\mathbf {A}}+{\mathbf {uv}}^{{\mathrm {T}}})&=\det({\mathbf {A}})\det({\mathbf {I}}+({\mathbf {A}}^{{-1}}{\mathbf {u}}){\mathbf {v}}^{{\mathrm {T}}})\\&=\det({\mathbf {A}})(1+{\mathbf {v}}^{{\mathrm {T}}}({\mathbf {A}}^{{-1}}{\mathbf {u}})).\end{aligned}}

Application

If the determinant and inverse of A are already known, the formula provides a numerically cheap way to compute the determinant of A corrected by the matrix uv^T. The computation is relatively cheap because the determinant of A+uv^T does not have to be computed from scratch (which in general is expensive). Using unit vectors for u and/or v, individual columns, rows or elements^[4] of A may be manipulated and a correspondingly updated determinant computed relatively cheaply in this way.

When the matrix determinant lemma is used in conjunction with the Sherman-Morrison formula, both the inverse and determinant may be conveniently updated together.

Generalization

Suppose A is an invertible n-by-n matrix and U, V are n-by-m matrices. Then

\operatorname {det}({\mathbf {A}}+{\mathbf {UV}}^{{\mathrm {T}}})=\operatorname {det}({\mathbf {I_{m}}}+{\mathbf {V}}^{{\mathrm {T}}}{\mathbf {A}}^{{-1}}{\mathbf {U}})\operatorname {det}({\mathbf {A}}).

In the special case ${\mathbf {A}}={\mathbf {I_{n}}}$ this is Sylvester's theorem for determinants.

Given additionally an invertible m-by-m matrix W, the relationship can also be expressed as

\operatorname {det}({\mathbf {A}}+{\mathbf {UWV}}^{{\mathrm {T}}})=\det({\mathbf {W}}^{{-1}}+{\mathbf {V}}^{{\mathrm {T}}}{\mathbf {A}}^{{-1}}{\mathbf {U}})\det({\mathbf {W}})\det({\mathbf {A}}).

References

↑ Harville, D. A. (1997). Matrix Algebra From a Statistician’s Perspective. Springer-Verlag.
↑ Brookes, M. (2005). "The Matrix Reference Manual (online)".
↑ Ding, J., Zhou, A. (2007). "Eigenvalues of rank-one updated matrices with some applications". Applied Mathematics Letters. 20 (12): 1223–1226. doi:10.1016/j.aml.2006.11.016. ISSN 0893-9659.
↑ William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling (1992). Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press. p. 73. ISBN 0-521-43108-5.

This article is issued from Wikipedia - version of the 5/12/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.