Error Bounds for the Computation of Null Vectors with Applications to Markov Chains
Jesse L. Barlow · SIAM Journal on Matrix Analysis and Applications · 1993
This paper considers the solution of the homogeneous system of linear equations $Ap = 0$ subject to $c^H p = 1$ where $A \in {\bf C}^{n \times n} $ is a singular matrix of rank $n - 1$, $c, p \in {\bf C}^n$, and $c^H A = 0$. It is assumed that the vector c is known. An important applications context for this problem is that of finding the stationary distribution of a Markov chain. In that context, A is a real singular M-matrix of the form $A = I - Q^T $ where Q is row stochastic. In previous work by Barlow [SIAM J. Algebraic Discrete Methods, 7 (1986), pp. 414–424], it was shown that, for A an M-matrix, this problem could be solved by solving a nonsingular linear system B of degree $n - 1$ that was a principal submatrix of A. Moreover, this matrix B could always be chosen so that $\| B^{ - 1} \|_2 \approx \| A^\dag \|_2 $. Thus a stable algorithm to solve this problem could be developed for the Markov modeling problem using LU decomposition without pivoting and an update step that identified the correct submatrix. In this paper, that result is improved in several ways. First, it is shown that many of the results can be generalized to the case where A is any complex matrix of degree n with rank $n - 1$; thus they can be generalized to the case where $A = \lambda I - Q^H $ and $\lambda$ is a simple eigenvalue of $Q^H $. Second, it is shown that the update step is not necessary for the Markov modeling problem. For that problem, LU decomposition is used without pivoting. Finally, it is shown that a more elegant characterization and sharper error bounds are obtained for this algorithm in terms of the group inverse $A^# $. In fact, the error is shown to be bounded in terms of $\| A^{#} \|_1 \| | A | | p | \|_1 $, which is smaller than the more traditional condition number $\| A^# \|_1 \| A \|_1 $. These bounds show that the procedure is unconditionally stable.