Contractions for consensus processes

Many distributed control algorithms of current interest can be modeled by linear recursion equations of the form x(t + 1) = M(t)x(t), t ≥ 1 where each M(t) is a real-valued “stochastic” or “doubly stochastic” matrix. Convergence of such recursions often reduces to deciding when the sequence of matrix products M(1), M(2)M(1), M(3)M(2)M(1), ... converges. Certain types of stochastic and doubly stochastic matrices have the property that any sequence of products of such matrices of the form S₁, S₂S₁, S₃S₂S₁, ... converges exponentially fast. We explicitly characterize the largest classes of stochastic and doubly stochastic matrices with positive diagonal entries which have these properties. The main goal of this paper is to find a “semi-norm” with respect to which matrices from these “convergability classes” are contractions. For any doubly stochastic matrix S such a semi-norm is identified and is shown to coincide with the second largest singular value of S.