Error Bounds for the Computation of Null Vectors with Applications to Markov Chains

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 s...