Sometimes, it is required to solve the following problem: having matrix *A* which we have already inverted (and got *A ^{ -1}*). Then, we have changed some elements of

Of course, this problem can generally be solved by inverting the modified matrix. However, there is a more effective way which takes into account the fact that we already have *A ^{ -1}* and the input matrix was modified slightly.

The Sherman-Morrison formula serves as the basis of an algorithm:

Here *A* is a square NxN matrix whose inverse matrix we know, *u* and *v* are the columns of height N defining the matrix modification, (*u _{i }v_{j }* is added to

Depending on *u* and *v*, there are different types of matrix *A* modifications and matrix *A ^{ -1}* update with different time complexity. Let's consider the main cases:

- If only
*u*and_{i }*v*are non-zero,_{j }*u*is added to_{i }v_{j }*a*._{i,j } - If
*u*and other components of the vector equal 0, vector_{i }= 1*v*is added to the row number i in matrix*A*. - If
*v*and other components of the vector equal 0, vector_{j }= 1*u*is added to the column number j in matrix*A*. - If
*u*and*v*are arbitrary vectors, row*v*(column*u*) is added to different rows (columns) with different multipliers.

These cases have a different computational complexity. The fastest is an inverse matrix update where only one element of the source matrix is changed. We'll take it as a unit. The inverse matrix update by row or column is only 2 times slower (thus, if three or more elements of one row or column were modified, it would better to use this algorithm than the previous one). The inverse matrix update with arbitrary vectors *u* and *v* is three times slower than the simple update.

**Note #1**

The algorithm stability is in question. At least, one step is stable enough if *A* and *B* are well-conditioned.

The module contains several subroutines which update *A ^{ -1}* both in the general case and in the special cases described above.

The **RMatrixInvUpdateSimple** subroutine updates *A ^{ -1}* when adding

The subroutines **RMatrixInvUpdateRow** and **RMatrixInvUpdateColumn** update the matrix when adding a vector to the matrix row or column.

The subroutine **RMatrixInvUpdateUV** updates an inverse matrix in the general case which is defined by vectors **U** and **V**.

*This article is licensed for personal use only.*

ALGLIB Project offers you two editions of ALGLIB:

**ALGLIB Free Edition**:

delivered for free

offers full set of numerical functionality

extensive algorithmic optimizations

no low level optimizations

non-commercial license

**ALGLIB Commercial Edition**:

flexible pricing

offers full set of numerical functionality

extensive algorithmic optimizations

high performance (SMP, SIMD)

commercial license with support plan

Links to download sections for Free and Commercial editions can be found below:

C++ library.

Delivered with sources.

Monolithic design.

Extreme portability.

Delivered with sources.

Monolithic design.

Extreme portability.

Delivered with sources.

VB.NET and IronPython wrappers.

Extreme portability.

Delphi wrapper around C core.

Delivered as precompiled binary.

Compatible with FreePascal.

Delivered as precompiled binary.

Compatible with FreePascal.

CPython wrapper around C core.

Delivered as precompiled binary.

Delivered as precompiled binary.