Rank modification method for certain singular systems of linear equations

This dissertation is mainly concerned with a general purpose algorithm for computing a solution to the consistent system of linear equations

Aw = f

where A is a real matrix of order n, with rank n - 1, and f is a real n-dimensional vector. The algorithm, called the Rank Modification Method, is based upon the transformation of A into a nonsingular matrix by a rank one modification, followed by the solution of an associated nonsingular system of linear equations. When the Rank Modification Method is applied to the consistent system of linear equations Aw = f, it results in a solution w such that v^Tw = τ , where v is an n-dimensional vector and τ is a real number. The vector v is any vector such that y^T ≠ where y is a right null vector of A. The value of τ may be specified arbitrarily. Therefore the proposed method can be used to compute a solution to the constrained system of linear equations Aw = f such that v^Tw = τ, if a solution exists.

The primary application of this research is the computation of a solution w to the homogeneous system of linear equations Aw = 0, where A is a singular irreducible M-matrix. This vector w is unique up to scalar multiples and it is important in many areas of the mathematical sciences, including queueing networks, input-output economic models, and in compartmental analysis tracer models.

The Rank Modification Method is developed and a complete error analysis is also given. Also developed is a special algorithm, called the Partition Factorization Method, which involves a simple direct LU-decomposition of an n - 1 dimensional submatrix of A. It is shown that the Partition Factorization Method can be considered a variation of the Rank Modification Method. A simple updating method is developed for the Partition Factorization Method. Also investigated are tridiagonal irreducible M-matrices.

These methods are applied to the problem of computing the stationary distribution vector p of an ergodic finite Markov chain C with associated rate transition matrix Q. Computational results for several test problems are reported, they show that the Partition Factorization Method should be considered the preferred direct method for computing p.