Bordering method

A method for solving a system of linear algebraic equations $ Ax = b $ with a non-degenerate matrix by inverting a matrix and calculating a determinant, based on passing recursively from the solution of the problem with matrix

$$ A _ {k-1} = \left \| \begin{array}{ccc} a _ {1,1} &\cdots &a _ {1, k - 1 } \\ \vdots &\ddots &\vdots \\ a _ {k-1,1} &\cdots &a _ {k-1,k-1} \\ \end{array} \right \| , $$

to the solution of the problem with the matrix $ A _ {k} $, which can be considered as the result of bordering $ A _ {k-1} $.

The calculating scheme of the bordering method for the inversion of a matrix is as follows: Let $ A _ {k-1} $ be a non-degenerate matrix. In the inversion of the matrix $ A _ {k} $, the representation

$$ \tag{1 } A _ {k} = \left \| \begin{array}{cc} A _ {k-1} &u _ {k} \\ v _ {k} &a _ {kk} \\ \end{array} \right \| $$

is used, where $ u _ {k} = (a _ {1,k} \dots a _ {k+1,k} ) ^ {T} $ and $ v _ {k} = (a _ {k,1} \dots a _ {k,k-1} ) $. Then

$$ \tag{2 } A _ {k} ^ {-1} = \left \| \begin{array}{cc} A _ {k-1} ^ {-1} + \frac{A _ {k-1} ^ {-1} u _ {k} v _ {k} A _ {k-1} ^ {-1} }{\alpha _ {k} } & - \frac{A _ {k-1} ^ {-1} u _ {k} }{\alpha _ {k} } \\ - \frac{v _ {k} A _ {k-1} ^ {-1} }{\alpha _ {k} } & \frac{1}{\alpha _ {k} } \\ \end{array} \right \| , $$

$$ \alpha _ {k} = a _ {kk} - v _ {k} A _ {k-1} ^ {-1} u _ {k} . $$

Subsequent inversion of the matrices $ A _ {1} \dots A _ {n} $ by this scheme gives the matrix $ A ^ {-1} $.

The above scheme of the bordering method is only applicable to matrices with principal minors unequal to zero. Generally, a choice of the principal element is adopted. In this scheme, the bordering rows and columns used are those for which $ \alpha _ {k} = a _ {kk} -v _ {k} A _ {k-1} ^ {-1} u _ {k} $ has the maximum absolute value. The calculated matrix will then differ from $ A ^ {-1} $ only in the rearrangement of the rows and columns [1].

The bordering method is not the fastest of the direct methods of inversion of a matrix.

The bordering method permits an effective inversion of a triangular matrix. If $ A _ {k} $ is a right (upper-) triangular matrix, then in (1)

$$ v _ {k} = 0 \ \textrm{ and } \ A _ {k} ^ {-1} = \left \| \begin{array}{cc} A _ {k-1} ^ {-1} &- \frac{A _ {k-1} ^ {-1} u _ {k} }{a _ {kk} } \\ 0 & \frac{1}{a _ {kk} } \\ \end{array} \ \right \| . $$

The amount of calculation in this instance is reduced six-fold.

The bordering method is particularly effective when inverting Hermitian positive-definite matrices. For these matrices it is not necessary to use a scheme with a choice of a principal element. Moreover, they are determined by only half of their elements. The calculating scheme in this instance is simplified thus:

$$ A _ {k} ^ {-1} = \left \| \begin{array}{cc} A _ {k-1} ^ {-1} + \frac{P _ {k} P _ {k} ^ \star }{\alpha _ {k} } & - \frac{P _ {k} }{\alpha _ {k} } \\ - \frac{P _ {k} ^ \star }{\alpha _ {k} } & \frac{1}{\alpha _ {k} } \\ \end{array} \right \| , $$

$$ P _ {k} = A _ {k-1} ^ {-1} u _ {k} ,\ \alpha _ {k} = a _ {kk} - u _ {k} ^ \star P _ {k} . $$

The calculating scheme of the bordering method for the solution of a system is as follows. Let $ b ^ {(kp)} = (a _ {1p} \dots a _ {kp} ) ^ {T} $, $ k = 1 \dots n $; $ b ^ {(n,n+1)} = -b $. If $ A _ {k-1} $ is a non-degenerate matrix and $ x ^ {(k-1,p)} $ is the solution of the system $ A _ {k-1} x ^ {(k-1,p)} + b ^ {(k-1,p)} = 0 $, then the solution $ x ^ {(k,p)} $ of the system $ A _ {k} x ^ {(k,p)} + b ^ {(k,p)} = 0 $ is obtained from the representation

$$ \tag{3 } A _ {k} = \left \| \begin{array}{cc} A _ {k-1} &b ^ {(k-1,k)} \\ v _ {k} &a _ {kk} \\ \end{array} \right \| ,\ \ b ^ {(k,p)} = \left \| \begin{array}{c} b ^ {(k-1,p)} \\ a _ {kp} \\ \end{array} \right \| , $$

and from (2) as follows

$$ \tag{4 } x ^ {(k,p)} = - \left \| \begin{array}{cc} A _ {k-1} ^ {-1} & 0 \\ 0 & 0 \\ \end{array} \right \| \left \| \begin{array}{c} b ^ {(k-1,p)} \\ a _ {kp} \\ \end{array} \right \| + $$

$$ + \frac{1}{\alpha _ {k} } \left \| \begin{array}{c} -x ^ {(k-1,k)} v _ {k} x ^ {(k-1,p)} -x ^ {(k-1,k)} a _ {kp} \\ -v _ {k} x ^ {(k-1,p)} - a _ {kp} \\ \end{array} \right \| = $$

$$ = \ \left \| \begin{array}{c} x ^ {(k-1,p)} \\ 0 \\ \end{array} \ \right \| - \frac{v _ {k} x ^ {(k-1,p)} + a _ {kp} }{a _ {kk} + v _ {k} x ^ {(k-1,k)} } \left \| \begin{array}{c} x ^ {(k-1,k)} \\ 1 \\ \end{array} \right \| . $$

In this way, through the solutions $ x ^ {(k-1,p)} $ and $ x ^ {(k-1,k)} $ of the systems with the same matrix $ A _ {k-1} $ and with various right-hand sides, it is easy to obtain the solution of the system with the bordered matrix $ A _ {k} $. The solution of the initial system is $ x ^ {(n,n+1)} $. This can be obtained by the recurrent use of relation (4). This leads to the subsequent calculation of the set of vectors $ x ^ {(k,p)} $, $ k = 1 \dots n $, $ p > k $, that is

$$ \begin{array}{cccc} x ^ {(12)} , &x ^ {(13)} , &\dots, &x ^ {(1,n+1)} , \\ {} &x ^ {(23)} , &\dots, &x ^ {(2,n+1)} , \\ {} &{} &\dots, &\dots, \\ {} &{} &{} &x ^ {(n-1,n+1)} , \\ {} &{} &{} &x ^ {(n,n+1)} . \\ \end{array} $$

In the amount of calculation necessary, this bordering method is equivalent to the Gauss method, one of the fastest direct methods of solving systems.

The bordering method allows one to solve higher-order systems owing to the effective use of computer memory. This is caused by the fact that for the calculation of the vectors $ x ^ {(k,p)} $, $ p > k $, only the storage of the vectors $ x ^ {(k-1,p)} $, $ p > k-1 $, and the coefficients of a $ k $-th order system of equations is necessary, that is, a series of numbers of length $ f(k) = k(n-k+1) + (n+1) $. It is therefore sufficient to have a working capacity $ (n+1)(n+5)/4 \approx (n/2) ^ {2} $ to solve a system of order $ n $. Moreover, the elements of the matrix and of the right-hand side do not have to be put into the computer memory immediately but successively, row by row.

It is advisable to use the bordering method when solving systems for which a truncated system has already been solved. Relation (4) then immediately gives the required solution.

The scheme of the bordering method described can be used to calculate the determinant. It follows from (1) that

$$ | A _ {k} | = \ ( a _ {kk} -v _ {k} A _ {k-1} ^ {-1} u _ {k} ) \ | A _ {k-1} | . $$

Recurrent use of this relation gives $ | A | $.

As with the inversion of a matrix, the solution of a system and the calculation of the determinant by means of the bordering method is possible only for matrices with non-zero principal minors. It is generally also necessary here to use a scheme with a choice of a principal element.

References

[1]	V.V. Voevodin, "Numerical methods of algebra. Theory and algorithms" , Moscow (1966) (In Russian)
[2]	D.K. Faddeev, V.N. Faddeeva, "Computational methods of linear algebra" , Freeman (1963) (Translated from Russian)

Comments

The bordering method is a special case of more general partitioning procedures [a1].

The bordering method defined above is related to the Sherman–Morrison formula and its generalization the Sherman–Morrison–Woodbury formula. The Sherman–Morrison formula states that a non-singular $ (m \times m ) $-matrix $ M $ and vectors $ x $ and $ y $ are related by

$$ [ M + xy ^ {H} ] ^ {-1} = \ M ^ {-1} - M ^ {-1} xc ^ {-1} y ^ {H} M ^ {-1} ,\ c=1+y ^ {H} M ^ {-1} x , $$

provided that $ c \neq 0 $. The Sherman–Morrison–Woodbury formula replaces the vectors $ x $ and $ y $ by $ (m \times n ) $-matrices $ X $ and $ Y $. These formulas were developed in [a2]–[a5] (see also [a6]), and used for the construction of matrix inversion schemes resembling that of the bordering method. An excellent discussion of these schemes is given in [a7].

References

[a1]	J.R. Westlake, "A handbook of numerical matrix inversion and solution of linear equations" , Wiley (1968) pp. Sect. 2.6
[a2]	M.S. Bartlett, "An inverse matrix adjustment arising in discriminant analysis" Ann. Math. Stat. , 22 (1951) pp. 107–111
[a3]	J. Sherman, "Computations relating to inverse matrices" , Appl. Math. Ser. , 29 , Nat. Bur. Standards (1953) pp. 123–124
[a4]	J. Sherman, W.J. Morrison, "Adjustments of an inverse matrix corresponding to changes in the elements of a given column or a given row of the original matrix" Ann. Math. Stat. , 20 (1949) pp. 621
[a5]	M. Woodbury, "Inverting modified matrices" Memorandum Report Stat. Res. Group Princeton , 42 (1950)
[a6]	G.H. Golub, C.F. van Loan, "Matrix computations" , North Oxford Acad. (1983)
[a7]	A.S. Householder, "Principles of numerical analysis" , McGraw-Hill (1953)