Conditioning of the entries in the stationary vector of a Google-type matrix (Q855557)

Given a stationary vector \(\alpha^T\) of a stochastic matrix of the form \(cA + (I - c)B\), where \(c \in(0, 1)\) is a scalar, and \(A\) and \(B\) are stochastic matrices, with rank \(B\) = 1, condition bounds for \(\alpha^T\) are given. Based on combinatorial and analytic techniques the conditioning bounds considered include normwise, absolute componentwise, and relative componentwise bounds. The bounds depend on \(c\), and on quantities such as the number of dangling nodes (which correspond to rows of \(A\) having all entries equal), or the lengths of certain cycles in the directed graph associated with \(A\). If a vertex is on only long cycles in that directed graph, then the corresponding entry in \(\alpha^T\) exhibits better conditioning properties, and that for dangling nodes, the sensitivity of the corresponding entries in \(\alpha^T\) decreases as the number of dangling nodes increases. Conditions are given that are sufficient to ensure that an iterate of the power method accurately reflects the relative ordering of two entries in \(\alpha^T\).