Completion method

2020 Mathematics Subject Classification: Primary: 65F05 [MSN][ZBL]

A method for calculating the inverse of a matrix, based on a recurrent transition which involves the calculation of a matrix $(C+uv)^{-1}$, where $u$ is a column vector, $v$ is a row vector, by the formula $$ (C + uv)^{-1} = C^{-1} - \frac{1}{\gamma} C^{-1} u v C^{-1} \ ,\ \ \ \gamma = 1 + v C^{-1} u \ . $$

The computational scheme of the method is as follows. Let $A = (A_{ij})$ be a given matrix of order $n$. Consider a sequence $A_0 = I, A_1, \ldots, A_n$, where $A_k = A_{k-1} + e_k a_k $ and $e_k$ is the $k$-th column of the identity matrix $I$, $a_k = (a_{k1},\ldots,a_{k,k-1},a_{kk}-1,a_{k,k+1},\ldots,a_{kn})$. Then $A_n = A$ and the matrix $A^{-1}$ is obtained by applying the above-described procedure $n$ times. The computational formulas in this case are the following: If $a_j^{(k)}$ is the $j$-th column of $A_k$, then for $k=1,\ldots,n$, $$ a_j^{(k)} = a_j^{(k-1)} - \frac{ a_ka_j^{(k-1)} }{ 1+a_ka_k^{(k-1)} } a_k^{(k-1)} \ ,\ \ j=1,\ldots,n\,. $$

It is sufficient to compute the elements of the first $k$ rows of the matrix $A_k^{-1}$, since all subsequent rows coincide with the rows of the identity matrix.

Other possibilities of arranging the computations in the completion method based on certain modifications of (*) are known, e.g. the so-called Ershov method (see [1]).

References

[1]	D.K. Faddeev, V.N. Faddeeva, "Computational methods of linear algebra" , Freeman (1963) (Translated from Russian)

Comments

This method is also called the bordering method (cf. [1]). See, however, also Bordering method.