\documentclass[12pt]{article} \usepackage{latexsym} %\usepackage{showkeys} \newtheorem{theorem}{Theorem}[section] %\renewcommand{\thetheorem}{\thesection.\arabic{theorem}} \newtheorem{cor}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{remark}[theorem]{Remark} \newtheorem{defin}[theorem]{Definition} \newtheorem{observation}[theorem]{Observation} \newtheorem{prop}[theorem]{Proposition} \newtheorem{example}[theorem]{Example} \renewcommand{\thetheorem}{\thesection.\arabic{theorem}} %\newcommand{\beq}{\addtocounter{theorem}{1}\begin{equation}} \setcounter{page}{0} \def\reff#1{{\rm (\ref{#1})}} %\def\R{\mathbb{R}} %\def\C{\mathbb{C}} %\def\F{\mathbb{F}} \def\R{{\rm I\kern-.25em R}} \def\F{{\rm I\kern-.25em F}} \def\C{{\rm \kern.24em \vrule width.02em height1.4ex depth-.05ex \kern-.26em C}} \newcommand{\ms}{\nu_e} %* \newcommand{\leqs}{ \ \leq \ } \newcommand{\geqs}{ \ \geq \ } \newcommand{\n}{\nu_{H}^{o} } \newcommand{\CC}{{\bf (C)}} \newcommand{\DD}{{\bf (D)}} \newcommand{\NN}{{\bf (N)}} \newcommand{\PO}{\{1,2,\ldots\}} \newcommand{\be}{\begin{equation}} \newcommand{\ee}{\end{equation}} \newcommand{\bd}{\begin{displaymath}} \newcommand{\ed}{\end{displaymath}} \newcommand{\bp}{\underline{\bf Proof}:\ } \newcommand{\ep}{{\hfill $\Box$}\\} \newcommand{\ba}{\begin{array}} \newcommand{\ea}{\end{array}} \newcommand{\e}{ \ = \ } %\renewcommand{\theequation} {\thesection.\arabic{equation}} \newcommand{\wt}{\widetilde} \newcommand{\wh}{\widehat} \newcommand{\tA}{\tilde{A}} \newcommand{\tnu}{\tilde{\nu}} \newcommand{\tsi}{\tilde{\sigma}} \newcommand{\tx}{\tilde{x}} \newcommand{\te}{\tilde{e}} \newcommand{\w}{ \omega } \newcommand{\A}{{\bf \cal A}} \newcommand{\Are}{{\bf R}} \newcommand{\Cee}{{\bf C}} \newcommand{\Ceehat}{{\bf \hat C}} \newcommand{\Sea}{{\cal C}} \newcommand{\Dee}{{\bf D}} \newcommand{\Em}{{\bf \cal M}} \newcommand{\Ef}{{\bf \cal F}} \newcommand{\intt}{\int\limits} \newcommand{\Oh}{{\bf \cal O}} \newcommand{\ftild}{\skew5\tilde f} \newcommand{\Res}{{\rm Res}} \newcommand{\Stild}{\skew4\tilde S} \newcommand{\Mtild}{\skew4\tilde M} \newcommand{\xtild}{\skew4\tilde x} \newcommand{\Tee}{{\bf T}} \newcommand{\aych}{{\bf H}} \newcommand{\Zee}{{\bf Z}} \newcommand{\Aut}{{\bf Aut\ }} \newcommand{\See}{{\bf \cal C}} \newcommand{\dg}{\delta} \newcommand{\noi}{\noindent} \newcommand{\la}{\lambda} \def\RR{\cal R} \def\NN{\cal N} \newcommand{\gla}{\gamma_{\lambda}} \newcommand{\ala}{\alpha_{\lambda}} \begin{document} \title{THE CONVERGENCE OF GENERAL PRODUCTS OF MATRICES AND THE WEAK ERGODICITY OF MARKOV CHAINS} \author{Michael Neumann\thanks{Work supported by NSF Grant DMS--9306357.} \\Department of Mathematics \\University of Connecticut \\ Storrs, CT 06268, USA \and Hans Schneider \footnote {Research supported in part by NSF Grant DMS--9424346. This research was partly performed during a visit by this author to the University of Bielefeld, Germany, supported by the Sonderforschungsbereich ``Diskrete Strukturen in der Mathematik'', Universit\"at Bielefeld.} \\Department of Mathematics \\University of Wisconsin \\ Madison, WI 53706, USA} \date{13 September 1998} \maketitle \begin{center} {\bf Dedicated to our good friend and valued colleague Ludwig Elsner\\ on the occasion of his sixtieth birthday} \end{center} \bigskip \noindent \begin{abstract} We determine a sufficient condition for the convergence to $0$ of general products formed from a sequence of real or complex matrices. Our result is applied to obtain a condition for the weak ergodicity of an inhomogeneous Markov chain. We make some remarks comparing coefficients of ergodicity and we give a method for constructing these. \end{abstract} \thispagestyle{empty} \newpage \section{Introduction} \label{sec1} \setcounter{equation}{0} Recently there has been much interest in conditions for the convergence of infinite products of real or complex matrices. Several investigations have concentrated on products taken in one direction -- left or right, see for example the recent papers by Beyn and Elsner \cite{BeEl97} and Hartfiel and Rothblum \cite{HaRo97}. However, in this paper, we are concerned with {\it general products} formed from a given infinite sequence of matrices. These are defined further on in the paper and they have previously been considered for nonnegative and stochastic matrices by Seneta in \cite[Chapters 3.1 and 4.6]{Sene81}. Such products include products taken in one direction.\\ Our principal result is a sufficient condition for the convergence to $0$ of an infinite general product of matrices. Our hypothesis is on the norms of the matrices of the given sequence, and our proof uses classical results on the convergence and divergence of products of positive real numbers.\\ Our result is motivated by the theory of inhomogeneous Markov chains. We are here concerned with the weak ergodicity of such chains, see \cite{Sene73} and \cite[Chapter 4]{Sene81} for references to the early history of this topic and for background material, see also \cite{Hajn56}, \cite{Mott57}, \cite{MoSc57} and \cite{Hajn58}.\\ Weak ergodicity of an inhomogeneous Markov chain is equivalent to the convergence to $0$ of a sequence of stochastic matrices considered as operators on a common invariant space of codimension 1. The corresponding operator norms are called coefficients of ergodicity. Thus by applying our result on the convergence to $0$ of a product of matrices to ergodicity coefficients, we obtain a sufficient condition for weak ergodicity.\\ The $\ell_1$ coefficient of ergodicity due to Bauer, Deutsch, and Stoer \cite{BaDeSt69} plays a special role in the theory of Markov chains as it is the only ergodicity coefficient associated with a norm that is less than or equal to $1$ for all stochastic matrices, see \cite{KuRh90} or \cite{Lesa90}. However, we shall define coefficients of ergodicity associated with norms that are less than the $\ell_1$ coefficient for many stochastic matrices, see \cite{Rhod93} for a different technique for finding such coefficients. Thus it appears to be useful to prove results on weak ergodicity, such as ours, which allow ergodicity coefficients to exceed $1$. \section{Convergence of Infinite Products} \label{sec3} %\setcounter{equation}{0} In this paper $\F$ will stand for the real field $\R$ or the complex field $\C$.\\ In this section we develop our main results concerning the convergence of products of complex matrices taken in an arbitrary order from an infinite sequence of matrices. Such products were considered (in a slightly less general form) in Seneta \cite[Section 4.6]{Sene81} in the case of stochastic matrices, see also \cite{Leiz92} and \cite{Rhod97}.\\ Let $A_1,A_2, \ldots$ be a sequence of complex matrices. We shall consider products of matrices obtained from the sequence in the following manner: First choose some permutation of the given infinite sequence to obtain a sequence $B_1,B_2,\ldots$. Then form the products $C_{p,r}$ of the matrices $B_{p+1}, \ldots, B_{p+r}$ in some order. We shall call $C_{p,r}$ a {\em general product} from the sequence $A_1,A_2,\ldots$ and we shall consider the existence of $\lim_{r\rightarrow\infty} C_{p,r}$. If this limit is $0$, for all permutations of $A_1, A_2, \ldots $ and all $p, \ p \geq 0$, then we shall say that all general products from the the sequence $A_1,A_2,\ldots$ converge to $0$.\\ As an example of a sequence of general product suppose the chosen order is $A_{43}, A_9, A_7, A_5$, $A_{14}, A_2, \ldots$. Then the sequence of $(C_{2,1}, C_{2,2}, \ldots)$ may begin thus: $ C_{2,1} = A_7, \ C_{2,2} = A_7 A_5, \ C_{2,3} = A_5 A_2 A_7 ,\ C_{2,4} = A_2 A_7 A_{14} A_5$. %\bd % \begin{array}{l} % C_{2,1} \e A_7, \ \\ % \ \\ % C_{2,2} \e A_7 A_5, \ \\ % \ \\ % C_{2,3} \e A_5 A_2 A_7 ,\ \\ % \ \\ % C_{2,4} \e A_2 A_7 A_{14} A_5. % \end{array} %\ed Note that, for a given sequence $C_{p,1}, C_{p,2}, \ldots$ of general products each factor of $C_{p,r}$ occurs in $C_{p,r+1}$, but the order in which the factors occur in $C_{p,r}$ is arbitrary.\\ Let $\mu$ be a matrix norm (viz. a submultiplicative norm on $\F^{nn}$) and denote \bd \mu^+(P) \e \max (\mu(P), 1) \;\;\;\;\;\; \mbox{and}\;\;\;\;\;\; \mu^-(P) \e \min (\mu(P), 1). \ed Now let $A_1,A_2,\ldots$ be a sequence of matrices in $\F^{nn}$ and let $\mu$ be a matrix norm. We now define two conditions:\\ \begin{description} \item[{\fbox{Condition (C)}}]: We say that the sequence $A_1,A_2,\ldots,$ satisfies Condition\\ {\bf (C)} for the norm $\mu$ if \be \label{condC} \sum_{i=1}^{\infty} (\mu^+(A_i)-1) \ {\rm converges}. \ee \item[{\fbox{Condition (D)}}]: We say that the sequence $A_1,A_2,\ldots$ satisfies Condition\\ {\bf (D)} for the norm $\mu$ if \be \label{condD} \sum_{j=1}^{\infty} (1-\mu^-(A_i)) \ {\rm diverges. } \ee \end{description} We are now ready to prove the following result:\\ \begin{prop} \label{prop.bdd} Let $A_1,A_2,\ldots$ be a sequence of matrices in $\F^{nn}$. Let $\mu$ be a matrix norm on $\F^{nn}$. Suppose that the sequence $A_1,A_2,\ldots$ satisfies Condition \CC \ for the norm $\mu$. Then all general products from $A_1,A_2,\ldots$ are bounded. \end{prop} \bp Let $B_1,B_2, \ldots$ be a permutation of $A_{1}, A_2, \ldots $ and let $C_{p,r}$ be a product of $B_{p+1}, \ldots, B_{p+r}$ in some order. By Condition \ \CC \ and \cite[Theorem 14]{Hysl45}, $\sum_{i=1}^{\infty}(\mu^+(B_i)-1)$ converges and hence $\sum_{i=1}^{\infty}(\mu^+(B_{p+i})-1)$ also converges. Thus, by \cite[Theorem 51]{Hysl45}, the product $\prod_{i=1}^{\infty} \mu^+(B_{p+i})$ converges and so there exists a positive constant $M$ such that $\prod_{i=1}^r \mu^+(B_{p+i})\leq M$, for each $r \in \{1,2,\ldots\}$. It follows that \begin{equation} \label{eqn1} \begin{array}{lll} \mu\left(C_{p,r}\right ) & \leq & \mu\left( B_{p+1} \right) \cdots \mu\left(B_{p+r}\right) \\ & \ & \ \\ & = & \left[\prod_{i=1}^{r} \mu^-\left(B_{p+i}\right)\right] \left[\prod_{i=1}^{r} \mu^+\left(B_{p+i}\right)\right] \\ \ & \ & \ \\ & \leq & M \left[\prod_{i=1}^{r} \mu^-\left(B_{p+i}\right)\right] \\ \ & \ & \ \\ & \ \leq & M. \end{array} \end{equation} \ep The above proposition allows us to prove a stronger result under an additional condition. Note that in the theory of infinite products of nonnegative numbers it is customary to speak of {\it divergence} to $0$, see e.g. \cite[p. 93]{Hysl45}. \\ \begin{theorem} \label{theorem.conv} Let $A_1,A_2,\ldots$ be a sequence of matrices in $\F^{nn}$. Let $\mu$ be a matrix norm on $\F^{nn}$. Suppose that the sequence $A_1,A_2,\ldots$ satisfies Conditions \CC \ and \DD \ for the norm $\mu$. Then all general products from $A_1,A_2,\ldots$ converge to $0$. \end{theorem} \bp Let $B_1,B_2, \ldots$ be a permutation of $A_{1}, A_2, \ldots $ and let $C_{p,r}$ be a product of $B_{p+1}, \ldots, B_{p+r}$ in some order. As in the proof of Proposition(\ref{prop.bdd}), we have that \begin{equation} \label{eqn2} \mu\left(C_{p,r}\right ) \ \leq \ M \left[\prod_{i=1}^{r} \mu^-\left(B_{p+i}\right)\right]. \end{equation} By Condition \DD, the sum $\sum_{i=1}^{\infty} (1-\mu^-(A_i))$ diverges and so, by \cite[Theorem 14]{Hysl45}, $\sum_{i=1}^{\infty} (1-\mu^-(B_i))$ diverges. Thus $\sum_{i=1}^{\infty} (1-\mu^-(B_{p+i}))$ also diverges. %Hence by %\cite[Theorem 14]{Hysl45}, $\sum_{i=1}^{\infty} (1-\mu^-(B_{i})$ %diverges. We again apply \cite[Theorem 51]{Hysl45} to obtain that $\prod_{i=1}^{\infty} \mu^-(B_{p+i})$ diverges. But since $\mu^-(B_i) \leq 1$, the last product must diverge to $0$ and the proof is done. \ep \section{Applications to Stochastic Matrices} \label{sec4} %\setcounter{equation}{0} In this section we apply the foregoing results to stochastic matrices. In order to be consistent with our previous section we consider {\em column} stochastic matrices. Thus ``stochastic matrix'' will mean ``column stochastic matrix''.\\ Let $e = (1,\ldots,1)^T \in \R^n$ and let \be \label{partic.H} H \e \{x \in \R^n \ : \ e^Tx= 0 \}. \ee If $A$ is a stochastic matrix in $\R^{n,n}$, then $H$ is invariant under $A$. If $\nu$ is a norm on $\R^n$ and $A$ is a stochastic matrix, then corresponding {\em coefficient of ergodicity} is defined by \be \label{Hcond} \nu_e(A) \ = \ \sup_{0 \neq x\in H}\frac{\nu(Ax)}{\nu(x)}, \ee as is usual in the literature on Markov chains, see for example \cite{Rhod97}. We may extend the definition of $\nu_e$ to all matrices $A$ in $\R^{nn}$ which leave $H$ invariant. Evidently $\nu_e$ is the (submutliplicative) operator norm induced by $\nu$ on the algebra of matrices which leave $H$ invariant.\\ The $\ell_1$ norm on $\R^n$ plays a special role in the theory of Markov chains and we shall denote it henceforth by $\w$. The corresponding coefficient of ergodicity was apparently first computed in Bauer, Deutsch, and Stoer \cite{BaDeSt69}, see also Zenger \cite{Zeng72}, and equals \bd \w_e(A) \e (1/2) \max_{i,k \in \{1,\dots,n\}} \sum_{j=1}^n |a_{ij}-a_{kj}|. \ed However, this quantity appeared previously in the equivalent form \bd 1 - \min_{i,k} \sum_{j=1}^n \min(a_{ij},a_{kj}). \ed in \cite{Hajn58}, see \cite[Theorem 2.10]{Sene81} for a proof of the equality of the two expressions. It is known that $\w_e(A) \leq 1$ for all stochastic matrices $A$ and $\w_e$ is the only coefficient of ergodicity that satisfies this inequality, \cite{KuRh90} and \cite{Lesa90}, but see also \cite{Rhod97}.\\ \begin{defin} \label{weak} {\rm Let $P_1,P_2,\ldots$ be a sequence of $n \times n$ stochastic matrices. We shall say that all general products formed from this sequence are {\em weakly ergodic} if for all general products $B_{p,1}, B_{p,2}, \ldots$, we have that \be \label{weak.con} \lim_{r \rightarrow \infty}B_{p,r}x \e 0, \ \ {\rm for \ all} \ \ x \in H. \ee } \end{defin} Since every $x \in H$ can be written $x = c(u - v)$, where $u,v \in \R^n$ are nonnegative and $e^Tu = e^Tv = 1$ and $c \in \R$, it is easily seen that, for each product considered, our definition is equivalent to that in \cite{Hajn58}, \cite{MoSc57}, or \cite[Defn. 3.3]{Sene81}.\\ By Theorem \ref{theorem.conv} we now immediately obtain:\\ \begin{theorem} \label{wkerg} Let $\nu$ be a norm on $\R^n$ and let $\ms$ be the corresponding coefficient of ergodicity. Let $P_1,P_2,\ldots$ be a sequence of $n \times n$ stochastic matrices. Then all general products formed from this sequence are weakly ergodic if \be \label{condCW} \sum_{i=1}^{\infty} ({\ms}^+(P_i)-1) \ {\rm converges} \ee and \be \label{condDW} \sum_{i=1}^{\infty} (1-{\ms}^-(P_{i})) \ {\rm diverges} \ee \end{theorem} Note that (\ref{condCW}) is automatically satisfied if $\nu = \w$, the $\ell_1$--norm. This special case of Theorem \ref{wkerg} is contained in \cite[Theorem 3]{Hajn58}, see also \cite[Exercise 4.36]{Sene81}. By means of an inequality found in \cite[(4.6)]{Sene81}, this result in turn implies \cite[Theorem 3]{Mott57}, see also \cite[Theorem 4.9]{Sene81}. Further results related to the special case $\nu = \w$, of Theorem \ref{wkerg} (and which therefore involve only (\ref{condDW}) explicitly) are to be found in \cite[Theorem 1]{Sene73} and in \cite{MoSc57}. The theorem in the latter paper is there illustrated by an example of a sequence of stochastic matrices that satisfies (\ref{condDW}) for the norm $\w$, see \cite[p. 333]{MoSc57}.\\ The following corollary to Theorem \ref{wkerg} is due to Rhodius \cite[Thm. 3, Part I]{Rhod97} in the case of $\nu = \w$, see Leizarowitz \cite[Thm A (i)]{Leiz92} for a related result. \begin{cor} \label{accum} Let $P_1, P_2, \ldots$ be a sequence of stochastic matrices. If $\ \nu_e(P_i)$ \ $\leq 1$ for all $i, \ i = 1,2, \ldots$, and there exists a point of accumulation $c$ of the sequence $\nu_e(P_1),\nu_e(P_2), \ldots$ such that $c < 1$, then all general products of the sequence are weakly ergodic. \end{cor} \bp Clearly condition \reff{condCW} holds and there is an infinite subsequence of indices $j_1, j_2, \ldots$ such that $\nu_e(P_{i_j}) < (1+c)/2 < 1$, $j = 1,2, \ldots$. Then condition \reff{condDW} holds for this subsequence. The result follows from Theorem (\ref{wkerg}). \ep Another corollary of Theorem \ref{wkerg} is \cite[Thm A (ii)]{Leiz92}: \begin{cor} \label{accum2} Let $P_1, P_2, \ldots$ be a sequence of stochastic matrices and let $\nu$ be a norm on $\R^n$. If all points of accumulation $c$ of the sequence $\nu_e(P_1)$, \ $\nu_e(P_2), \ldots$ satisfy $c < 1$, then all general products of the sequence are weakly ergodic. \end{cor} \bp The sequence $\nu_e(P_1),\nu_e(P_2), \ldots$, is bounded, since all elements of the stochastic matrices $P_j, \ j = 1,2,\ldots$, are bounded above by $1$. Since the set of accumulation points of a bounded sequence is compact, there exists $d < 1$ such that only a finite number of terms of the above sequence of ergodicity coefficients exceed $d$. Hence \reff{condCW} and \reff{condDW} hold for this sequence and the corollary follows from Theorem \ref{wkerg}. \ep \section{Comparisons of ergodic coefficients} \label{sec5} %\setcounter{equation}{0} Detailed comparison of of our results above to some results in \cite[Chapter 4]{Sene81} is difficult since in the latter the coefficient of ergodicity is defined in \cite[Definition 4.6]{Sene81} as a continuous function $\tau$ on the set of stochastic matrices satisfying $0 \leq \tau \leq 1$, and theorems there require the hypothesis that this function is submutliplicative, see also \cite{Sene73} for a similar approach. On the other hand we define the coefficient in terms of a norm. It may be noted that in our proofs we have not used the subadditive property of a matrix norm, only its submultiplicative property.\\ The $\ell_1$ coefficient of ergodicy $\w_e$ is advantageous for obtaining theoretical results since $\w_e(A) \le 1$ for all stochastic matrices $A$. However, as we pointed out in the introduction, there are natural and useful coefficients of ergodicity $\nu_e$ associated with a norm $\nu$ such that $\nu_e(A) > 1$ for some stochastic matrix $A$. In order to provide a class of such examples, we state and prove a proposition. \begin{prop} \label{last} Let $n > 1$ and let $1 \le k \le n$. For any $A \in \R^{nn}$ which leaves $H$ invariant, let $\tA_k \in \R^{n-1,n-1}$ be defined by \begin{equation} \label{A.tilde} \tilde{a}_{ij} \e a_{ij} - a_{ik},\ i,j = 1, \ldots, n, \ i,j \ne k . \end{equation} Let $\tnu$ be any norm on $\R^{n-1}$. Then there exists a norm $\nu$ on $\R^n$ such that the corresponding coefficient of ergodicity satifies $\nu_e(A) = \tnu^0(\tA_k)$ for all stochastic matrices $A \in \R^{nn}$, where $\tnu^0$ is the operator norm on $\R^{n-1,n-1}$ induced by $\tnu$. \end{prop} \bp Without loss of generality, we may assume that $k = 1$ and we put $\tA_1 = \tA$. For $x \in \R^n$ define $\tx = (x_2,\ldots,x_n)^T \in \R^{n-1}$. Note that $\te = (1,\ldots,1)^T \in \R^{n-1}$ and define the norm $\nu$ on $\R^n$ by \be \label{normdef} \nu(x) \e |x_1 + \te^T\tx| + \tnu(\tx), \ x \in \R^n. \ee Let $x \in H$. Then $x_1 = -\te^T \tx$ and hence $\nu(x) = \tnu(\tx)$. If $A$ leaves $H$ invariant (and, in particular if A is stochastic) we therefore have $\nu(Ax)/\nu(x) = \tnu(\wt{Ax})/\tnu(\tx)$ when $x \ne 0$. But it easily checked that $(\wt{Ax}) = \tA\tx$ for $x \in H$ since $x^T = (-\te^T\tx, \tx^T)$. The result follows. \ep\\ The special case of Proposition \ref{last}, where $\tnu$ is the $\ell_1$ norm on $\R^{n-1}$ may be found in \cite[Example 1]{Rhod93} with a different proof. Observe that the coefficient of ergodicity so obtained is in general {\em not} equal to $\w_e$.\\ If we wish to find examples of ergodicity coefficients, it follows from the above proposition that we do not need to start with a norm on $\R^n$ and use the definition (\ref{Hcond}) to compute the coefficient. Instead, we may pick $k,\ 1 \le k \le n$, and a norm $\tilde{\nu}_k$ on $\R^{n-1}$ and compute $\tnu^0(\tilde{A}_k)$. Also, for many purposes, it is possible to consider $\beta = \min_{k = 1,\ldots,n}\tnu^0(\tA_k)$, for example when finding upper bounds on the moduli of eigenvalues of $A$ which do not equal $1$, and our MATLAB experiments using the {\bf rand} function show that in most cases $\beta < \w_e(A)$ when $\tnu$ is the $\ell_2$ norm.\\ We end with the easily proved remark that the mapping $x \rightarrow \tx$ of $\R^n$ onto $\R^{n-1}$ in the proof of Proposition \ref{last} is a vector space homomorphism whose restriction to $H$ is an isomorphism. The mapping $A \rightarrow \tA_k$ onto $\R^{n-1,n-1}$ from the algebra of matrices in $\R^{nn}$ that map $H$ into itself is a homomorphism whose kernel consists of all matrices in the algebra of rank $r, \ r \le 1$.\\ \bigskip \centerline{{\bf Acknowledgment}} \vspace{.15in} We would like to thank Wenchao Huang for some helpful remarks. We thank Olga Holtz for her careful reading of the manuscript.\\ \bibliographystyle{plainxe} \begin{thebibliography}{0} \bibitem{BaDeSt69} F. L. Bauer, Eck. Deutsch, and J. Stoer. \newblock Absch\"{a}tzungen f\"{u}r die Eigenwerte positiver linearer Operatoren. \newblock {\it Lin. Alg. Appl.}, 2:275--301, 1969. \bibitem{BeEl97} W. J. Beyn and L. Elsner. \newblock Infinite products and paracontracting matrices. \newblock {\it Elec. J. Lin. Alg.}, 2:1--8, 1997. \bibitem{Hajn56} J. Hajnal. \newblock The ergodic properties of non--homogeneous finite Markov chains. \newblock {\it Proc. Cambridge Phil. Soc.}, 52:67--77, 1956. \bibitem{Hajn58} J. Hajnal. \newblock Weak ergodicity in non--homogeneous Markov chains. \newblock {\it Proc. Cambridge Phil. Soc.}, 54:52--67, 1958. \bibitem{HaRo97} D.J. Hartfiel and U.G. Rothblum. \newblock Convergence of inhomogeneous products of matrices and coefficients of ergodicity. \newblock {\it Lin. Alg. Appl.}, 277:1--9, 1998. \bibitem{Hysl45} J. M. Hyslop. \newblock Infinite Series. \newblock {\it Oliver and Boyd}, Edinburgh, 1945. \bibitem{KuRh90} R. K\"uhne and A. Rhodius. \newblock A characterization of Dobrushin's coefficient of ergodicity. \newblock {\it Z. Anal. Anw.} 9(2):187--188, 1990. \bibitem{Leiz92} A.Leizarowitz. \newblock On infinite products of stochastic matrices. \newblock {\it Lin. Alg. Appl.} 168:189--219, 1992. \bibitem{Lesa90} A. Le\v{s}anovsk\'{y}. \newblock Coefficients of ergodicity generated by non--symmetrical vector norms. \newblock {\it Czechoslovak Math. J.} 40 (115):284--294, 1990. \bibitem{Mott57} J. L. Mott. \newblock Conditions for the ergodicity of non--homogeneous finite Markov chains. \newblock {\it Proc. Roy. Soc, Edinburgh}, Section A, 64:369--380, 1957. \bibitem{MoSc57} J. L. Mott and H. Schneider. \newblock Matrix norms applied to weakly ergodic Markov chains. \newblock {\it Arch. Math.}, 8:331--333, 1957. \bibitem{Rhod93} A. Rhodius. \newblock On explicit forms of ergodicity coefficients. \newblock {\it Lin. Alg. Appl.}, 194:71--83, 1993. \bibitem{Rhod97} A. Rhodius. \newblock On the maximum ergodicity coefficient, the Dobrushin coefficient and products of stochastic matrices. {\it Lin. Alg. Appl.}, 253:141--157, 1997. \bibitem{Sene73} E. Seneta. \newblock On the historical development of the theory of finite inhomogeneous Markov chains. \newblock{\it Proc. Cambridge Phil. Soc}, 74:507--513, 1973. \bibitem{Sene81} E. Seneta. \newblock Non--negative Matrices and Markov Chains, Second Edition. \newblock {\it Springer Verlag}, New--York, 1981. \bibitem{Zeng72} C. Zenger. \newblock A comparison for some bounds for the nontrivial eigenvalues of stochastic matrices. \newblock {\it Numer. Math.}, 19:209--211, 1972. \end{thebibliography} \end{document} Date: Mon, 7 Sep 1998 11:21:35 -0500 (CDT) From: Hans Schneider To: "Neumann, Michael (Miki) -- Miki Neumann" Subject: ns980906.tex Mime-Version: 1.0 ----------------------------------------------------------------- ------------- Hans Schneider hans@math.wisc.edu. Department of Mathematics 608-262-1402 (Work) Van Vleck Hall 608-271-7252 (Home) 480 Lincoln Drive 608-263-8891 (Work FAX) University of Wisconsin-Madison 608-271-8477 (Home FAX) Madison WI 53706 USA http://www.math.wisc.edu/~hans (URL) ----------------------------------------------------------------- ------------- \documentclass[12pt]{article} \usepackage{latexsym} %\usepackage{showkeys} \newtheorem{theorem}{Theorem}[section] %\renewcommand{\thetheorem}{\thesection.\arabic{theorem}} \newtheorem{cor}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{remark}[theorem]{Remark} \newtheorem{defin}[theorem]{Definition} \newtheorem{observation}[theorem]{Observation} \newtheorem{prop}[theorem]{Proposition} \newtheorem{example}[theorem]{Example} \renewcommand{\thetheorem}{\thesection.\arabic{theorem}} %\newcommand{\beq}{\addtocounter{theorem}{1}\begin{equation}} \setcounter{page}{0} \def\reff#1{{\rm (\ref{#1})}} %\def\R{\mathbb{R}} %\def\C{\mathbb{C}} %\def\F{\mathbb{F}} \def\R{{\rm I\kern-.25em R}} \def\F{{\rm I\kern-.25em F}} \def\C{{\rm \kern.24em \vrule width.02em height1.4ex depth-.05ex \kern-.26em C}} \newcommand{\ms}{\nu_e} %* \newcommand{\leqs}{ \ \leq \ } \newcommand{\geqs}{ \ \geq \ } \newcommand{\n}{\nu_{H}^{o} } \newcommand{\CC}{{\bf (C)}} \newcommand{\DD}{{\bf (D)}} \newcommand{\NN}{{\bf (N)}} \newcommand{\PO}{\{1,2,\ldots\}} \newcommand{\be}{\begin{equation}} \newcommand{\ee}{\end{equation}} \newcommand{\bd}{\begin{displaymath}} \newcommand{\ed}{\end{displaymath}} \newcommand{\bp}{\underline{\bf Proof}:\ } \newcommand{\ep}{{\hfill $\Box$}\\} \newcommand{\ba}{\begin{array}} \newcommand{\ea}{\end{array}} \newcommand{\e}{ \ = \ } %\renewcommand{\theequation} {\thesection.\arabic{equation}} \newcommand{\wt}{\widetilde} \newcommand{\wh}{\widehat} \newcommand{\tA}{\tilde{A}} \newcommand{\tnu}{\tilde{\nu}} \newcommand{\tsi}{\tilde{\sigma}} \newcommand{\tx}{\tilde{x}} \newcommand{\te}{\tilde{e}} \newcommand{\w}{ \omega } \newcommand{\A}{{\bf \cal A}} \newcommand{\Are}{{\bf R}} \newcommand{\Cee}{{\bf C}} \newcommand{\Ceehat}{{\bf \hat C}} \newcommand{\Sea}{{\cal C}} \newcommand{\Dee}{{\bf D}} \newcommand{\Em}{{\bf \cal M}} \newcommand{\Ef}{{\bf \cal F}} \newcommand{\intt}{\int\limits} \newcommand{\Oh}{{\bf \cal O}} \newcommand{\ftild}{\skew5\tilde f} \newcommand{\Res}{{\rm Res}} \newcommand{\Stild}{\skew4\tilde S} \newcommand{\Mtild}{\skew4\tilde M} \newcommand{\xtild}{\skew4\tilde x} \newcommand{\Tee}{{\bf T}} \newcommand{\aych}{{\bf H}} \newcommand{\Zee}{{\bf Z}} \newcommand{\Aut}{{\bf Aut\ }} \newcommand{\See}{{\bf \cal C}} \newcommand{\dg}{\delta} \newcommand{\noi}{\noindent} \newcommand{\la}{\lambda} \def\RR{\cal R} \def\NN{\cal N} \newcommand{\gla}{\gamma_{\lambda}} \newcommand{\ala}{\alpha_{\lambda}} \begin{document} \title{THE CONVERGENCE OF GENERAL PRODUCTS OF MATRICES AND THE WEAK ERGODICITY OF MARKOV CHAINS} \author{Michael Neumann\thanks{Work supported by NSF Grant DMS--9306357.} \\Department of Mathematics \\University of Connecticut \\ Storrs, CT 06268, USA \and Hans Schneider \footnote {Research supported in part by NSF Grant DMS--9424346. This research was partly performed during a visit by this author to the University of Bielefeld, Germany, supported by the Sonderforschungsbereich ``Diskrete Strukturen in der Mathematik'', Universit\"at Bielefeld.} \\Department of Mathematics \\University of Wisconsin \\ Madison, WI 53706, USA} \date{6 September 1998} \maketitle \begin{center} {\bf Dedicated to our good friend and valued colleague Ludwig Elsner\\ on the occasion of his sixtieth birthday} \end{center} \bigskip \noindent \begin{abstract} We determine a sufficient condition for the convergence to $0$ of general products formed from a sequence of real or complex matrices. Our result is applied to obtain a condition for the weak ergodicity of an inhomogeneous Markov chain. We make some remarks comparing coefficients of ergodicity. \end{abstract} \thispagestyle{empty} \newpage \section{Introduction} \label{sec1} \setcounter{equation}{0} Recently there has been much interest in conditions for the convergence of infinite products of real or complex matrices. Several investigations have concentrated on products taken in one direction -- left or right, see for example the recent papers by Beyn and Elsner \cite{BeEl97} and Hartfiel and Rothblum \cite{HaRo97}. However, in this paper, we are concerned {\it general products} formed from a given infinite sequence of matrices. These are defined further on in the paper and they have previously been considered for nonnegative and for stochastic matrices by Seneta in \cite[Chapters 3.1 and 4.6]{Sene81}. Such products include products taken in one direction.\\ Our principal result is a sufficient condition for the convergence to $0$ of an infinite general product of matrices. Our hypothesis is on the norms of the matrices of the given sequence, and our proof uses classical results on the convergence and divergence of products of positive real numbers.\\ Our result is motivated by the theory of inhomogeneous Markov chains. We are here concerned with the weak ergodicity of such chains, see \cite{Sene73} and \cite[Chapter 4]{Sene81} for references to the early history of this topic and for background material, see also \cite{Hajn56}, \cite{Mott57}, \cite{MoSc57} and \cite{Hajn58}.\\ Weak ergodicity of an inhomogeneous Markov chain is equivalent to the convergence to $0$ of a sequence of stochastic matrices considered as operators on a common invariant space of codimension 1. The corresponding operator norms are called coefficients of ergodicity. Thus by applying our result on the convergence to $0$ of a product of matrices to ergodicity coefficients, we obtain a sufficient condition for weak ergodicity.\\ The $\ell_1$ coefficient of ergodicity due to Bauer, Deutsch, Stoer \cite{BaDeSt69} plays a special role in the theory of Markov chains as it is the only ergodicity coefficient associated with a norm that is less than or equal to $1$ for all stochastic matrices, see \cite{KuRh90} or \cite{Lesa90}. However, we shall define coefficients of ergodicity associated with norms that are less than the $\ell_1$ coefficient for many stochastic matrices, see \cite{Rhod93} for a different technique for finding such coefficients. Thus it appears to be useful to prove results on weak ergodicity, such as ours, which allow ergodicity coefficients to exceed $1$. \section{Convergence of Infinite Products} \label{sec3} %\setcounter{equation}{0} In this paper $\F$ will stand for the real field $\R$ or the complex field $\C$.\\ In this section we develop our main results concerning the convergence of products of complex matrices taken in an arbitrary order from an infinite sequence of matrices. Such products were considered (in a slightly less general form) in Seneta \cite[Section 4.6]{Sene81} in the case of stochastic matrices, see also \cite{Leiz92} and \cite{Rhod97}.\\ Let $A_1,A_2, \ldots$ be a sequence of complex matrices. We shall consider products of matrices obtained from the sequence in the following manner: First choose some permutation of the given infinite sequence to obtain a sequence $B_1,B_2,\ldots$. Then form the products $C_{p,r}$ of the matrices $B_{p+1}, \ldots, B_{p+r}$ in some order. We shall call $C_{p,r}$ a {\em general product} from the sequence $A_1,A_2,\ldots$ and we shall consider the existence of $\lim_{r\rightarrow\infty} C_{p,r}$. If this limit is $0$, for all permutations of $A_1, A_2, \ldots $ and all $p, \ p \geq 0$, then we shall say that all general products from the the sequence $A_1,A_2,\ldots$ converge to $0$.\\ As an example of a sequence of general product suppose the chosen order is $A_{43}, A_9, A_7, A_5$, $A_{14}, A_2, \ldots$. Then the sequence of $(C_{2,1}, C_{2,2}, \ldots)$ may begin thus: $ C_{2,1} = A_7, \ C_{2,2} = A_7 A_5, \ C_{2,3} = A_5 A_2 A_7 ,\ C_{2,4} = A_2 A_7 A_{14} A_5$. %\bd % \begin{array}{l} % C_{2,1} \e A_7, \ \\ % \ \\ % C_{2,2} \e A_7 A_5, \ \\ % \ \\ % C_{2,3} \e A_5 A_2 A_7 ,\ \\ % \ \\ % C_{2,4} \e A_2 A_7 A_{14} A_5. % \end{array} %\ed Note that, for a given sequence $C_{p,1}, C_{p,2}, \ldots$ of general products each factor of $C_{p,r}$ occurs in $C_{p,r+1}$, but the order in which the factors occur in $C_{p,r}$ is arbitrary.\\ Let $\mu$ be a matrix norm (viz. a submultiplicative norm on $\F^{nn}$) and denote \bd \mu^+(P) \e \max (\mu(P), 1) \;\;\;\;\;\; \mbox{and}\;\;\;\;\;\; \mu^-(P) \e \min (\mu(P), 1). \ed Now let $A_1,A_2,\ldots$ be a sequence of matrices in $\F^{nn}$ and let $\mu$ be a matrix norm. We now define two conditions:\\ \begin{description} \item[{\fbox{Condition (C)}}]: We say that the sequence $A_1,A_2,\ldots,$ satisfies Condition\\ {\bf (C)} for the norm $\mu$ if \be \label{condC} \sum_{i=1}^{\infty} (\mu^+(A_i)-1) \ {\rm converges}. \ee \item[{\fbox{Condition (D)}}]: We say that the sequence $A_1,A_2,\ldots$ satisfies Condition\\ {\bf (D)} for the norm $\mu$ if \be \label{condD} \sum_{j=1}^{\infty} (1-\mu^-(A_i)) \ {\rm diverges. } \ee \end{description} We are now ready to prove the following result:\\ \begin{prop} \label{prop.bdd} Let $A_1,A_2,\ldots$ be a sequence of matrices in $\F^{nn}$. Let $\mu$ be a matrix norm on $\F^{nn}$. Suppose that the sequence $A_1,A_2,\ldots$ satisfies Condition \CC \ for the norm $\mu$. Then all general products from $A_1,A_2,\ldots$ are bounded. \end{prop} \bp Let $B_1,B_2, \ldots$ be a permutation of $A_{1}, A_2, \ldots $ and let $C_{p,r}$ be a product of $B_{p+1}, \ldots, B_{p+r}$ in some order. By Condition \ \CC and \cite[Theorem 14]{Hysl45}, $\sum_{i=1}^{\infty}(\mu^+(B_i)-1)$ converges and hence $\sum_{i=1}^{\infty}(\mu^+(B_{p+i})-1)$ also converges. Thus, by \cite[Theorem 51]{Hysl45}, the product $\prod_{i=1}^{\infty} \mu^+(B_{p+i})$ converges and so there exists a positive constant $M$ such that $\prod_{i=1}^r \mu^+(B_{p+i})\leq M$, for each $r \in \{1,2,\ldots\}$. It follows that \begin{equation} \label{eqn1} \begin{array}{lll} \mu\left(C_{p,r}\right ) & \leq & \mu\left( B_{p+1} \right) \cdots \mu\left(B_{p+r}\right) \\ & \ & \ \\ & = & \left[\prod_{i=1}^{r} \mu^-\left(B_{p+i}\right)\right] \left[\prod_{i=1}^{r} \mu^+\left(B_{p+i}\right)\right] \\ \ & \ & \ \\ & \leq & M \left[\prod_{i=1}^{r} \mu^-\left(B_{p+i}\right)\right] \\ \ & \ & \ \\ & \ \leq & M. \end{array} \end{equation} \ep The above proposition allows us to prove a stronger result under an additional conditions. Note that in the theory of infinite products of nonnegative numbers it is customary to speak of {\it divergence} to $0$, see e.g. \cite[p. 93]{Hysl45}. \\ \begin{theorem} \label{theorem.conv} Let $A_1,A_2,\ldots$ be a sequence of matrices in $\F^{nn}$. Let $\mu$ be a matrix norm on $\F^{nn}$. Suppose that the sequence $A_1,A_2,\ldots$ satisfies Conditions \CC \ and \DD \ for the norm $\mu$. Then all general products from $A_1,A_2,\ldots$ converge to $0$. \end{theorem} \bp Let $B_1,B_2, \ldots$ be a permutation of $A_{1}, A_2, \ldots $ and let $C_{p,r}$ be a product of $B_{p+1}, \ldots, B_{p+r}$ in some order. As in the proof of Proposition(\ref{prop.bdd}), we have that \begin{equation} \label{eqn2} \mu\left(C_{p,r}\right ) \ \leq \ M \left[\prod_{i=1}^{r} \mu^-\left(B_{p+i}\right)\right]. \end{equation} By Condition \DD, the sum $\sum_{i=1}^{\infty} (1-\mu^-(A_i))$ diverges and so, by \cite[Theorem 14]{Hysl45}, $\sum_{i=1}^{\infty} (1-\mu^-(B_i))$ diverges. Thus $\sum_{i=1}^{\infty} (1-\mu^-(B_{p+i}))$ also diverges. %Hence by %\cite[Theorem 14]{Hysl45}, $\sum_{i=1}^{\infty} (1-\mu^-(B_{i})$ %diverges. We again apply \cite[Theorem 51]{Hysl45}, and we obtain that $\prod_{i=1}^{\infty} \mu^-(B_{p+i})$ diverges. But since $\mu^-(B_i) \leq 1$, the last product must diverge to $0$ and the proof is done. \ep \section{Applications to Stochastic Matrices} \label{sec4} %\setcounter{equation}{0} In this section we apply the foregoing results to stochastic matrices. In order to be consistent with our previous section we consider {\em column} stochastic matrices.Thus ``stochastic matrix'' will mean ``column stochastic matrix''.\\ Let $e = (1,\ldots,1)^T \in \R^n$ and let \be \label{partic.H} H \e \{x \in \R^n \ : \ e^Tx= 0 \}. \ee If $A$ is a stochastic matrix in $\R^{n,n}$, then $H$ is invariant under $A$. If $\nu$ is a norm on $\R^n$ and $A$ is a stochastic matrix, then corresponding {\em coefficient of ergodicity} is defined by \be \label{Hcond} \nu_e(A) \ = \ \sup_{0 \neq x\in H}\frac{\nu(Ax)}{\nu(x)}. \ee as is usual in the literature on Markov chains, see for example \cite{Rhod97}. We may extend the definition of $\nu_e$ to all matrices $A$ in $\R^{nn}$ which leave $H$ invariant. Evidently $\nu_e$ is the (submutliplicative) operator norm induced by $\nu$ on the algebra of matrices which leave $H$ invariant.\\ The $\ell_1$ norm on $\R^n$ plays a special role in this theory and we shall denote it henceforth by $\w$. The corresponding coefficient of ergodicity was apparently first computed in Bauer, Deutsch, and Stoer \cite{BaDeSt69}, see also Zenger \cite{Zeng72}, and equals \bd \w_e(A) \e (1/2) \max_{i,k \in \{1,\dots,n\}} \sum_{j=1}^n |a_{i,j}-a_{k,j}|. \ed However, this quantity appeared previously in the equivalent form \bd 1 - \min_{i,k} \sum_{j=1}^n \min(a_{i,j},a_{k,j}). \ed in \cite{Hajn58}, see \cite[Theorem 2.10]{Sene81} for a proof of the equality of the two expressions. It is known that $\w_e(A) \leq 1$ for all stochastic matrices $A$ and $\w_e$ is the only coefficient of ergodicity that satisfies this inequality, \cite{KuRh90} and \cite{Lesa90}, but see also \cite{Rhod97}.\\ \begin{defin} \label{weak} {\rm Let $P_1,P_2,\ldots$ be a sequence of $n \times n$ stochastic matrices. We shall say that all general products formed from this sequence are {\em weakly ergodic} if for all general products $B_{p,1}, B_{p,2}, \ldots$, we have that \be \label{weak.con} lim_{r \rightarrow \infty}B_{p,r}x \e 0, \ \ {\rm for \ all} \ \ x \in H. \ee } \end{defin} Since every $x \in H$ can be written $x = c(u - v)$, where $u,v \in \R^n$ are nonnegative and $e^Tu = e^Tv = 1$ and $c \in \R$, it is easily seen that, for each product considered, our definition is equivalent to that in \cite{Hajn58}, \cite{MoSc57}, or \cite[Defn. 3.3]{Sene81}.\\ By Theorem \ref{theorem.conv} we now immediately obtain:\\ \begin{theorem} \label{wkerg} Let $\nu$ be a norm on $\R^n$ and let $\ms$ be the corresponding coefficient of ergodicity. Let $P_1,P_2,\ldots$ be a sequence of $n \times n$ stochastic matrices. Then all general products formed from this sequence are weakly ergodic if \be \label{condCW} \sum_{i=1}^{\infty} ({\ms}^+(P_i)-1) \ {\rm converges} \ee and \be \label{condDW} \sum_{i=1}^{\infty} (1-{\ms}^-(P_{i})) \ {\rm diverges} \ee \end{theorem} Note that (\ref{condCW}) is automatically satisfied if $\nu = \w$, the $\ell_1$--norm. This special case of Theorem \ref{wkerg} is contained in \cite[Theorem 3]{Hajn58}, see also \cite[Exercise 4.36]{Sene81}. By means of an inequality found in \cite[(4.6)]{Sene81}, this result in turn implies \cite[Theorem 3]{Mott57}, see also \cite[Theorem 4.9]{Sene81}. Further results related to the special case $\nu = \w$, of Theorem \ref{wkerg} (and which therefore involve only (\ref{condDW}) explicitly) are to be found in \cite[Theorem 1]{Sene73} and in \cite{MoSc57}. The theorem in the latter paper is there illustrated by an example of a sequence of stochastic matrices that satisfies (\ref{condDW}) for the norm $\w$, see \cite[p. 333]{MoSc57}.\\ The following corollary to Theorem \ref{wkerg} is due to Rhodius \cite[Thm. 3, Part I]{Rhod97} in the case of $\nu = \w$, see Leizarowitz \cite[Thm A (i)]{Leiz92} for a related result. \begin{cor} \label{accum} Let $P_1, P_2, \ldots$ be a sequence of stochastic matrices. If $\ \nu_e(P_i)$ \ $\leq 1$ for all $i, \ i = 1,2, \ldots$, and there exists a point of accumulation $c$ of the sequence $\nu_e(P_1),\nu_e(P_2), \ldots$ such that $c < 1$, then all general products of the sequence are weakly ergodic. \end{cor} \bp Clearly condition \reff{condCW} holds and there is an infinite subsequence $j_1, j_2, \ldots$ such that $\nu_e(P_{i_j}) < (1+c)/2 < 1$, $j = 1,2, \ldots$. Then condition \reff{condDW} holds for this subsequence. The result follows from Theorem (\ref{wkerg}). \ep Another corollary of Theorem \ref{wkerg} is \cite[Thm A (ii)]{Leiz92}: \begin{cor} \label{accum2} Let $P_1, P_2, \ldots$ be a sequence of stochastic matrices and let $\nu$ be a norm on $\R^n$. If all points of accumulation $c$ of the sequence $\nu_e(P_1)$, \ $\nu_e(P_2), \ldots$ satisfy $c < 1$, then all general products of the sequence are weakly ergodic. \end{cor} \bp Since the set of accumulation points of a bounded sequence is compact, there exists $d < 1$ such that only a finite number of terms of the sequence $\nu_e(P_1),\nu_e(P_2), \ldots$ exceed $d$. Hence \reff{condCW} and \reff{condDW} hold for the sequence of ergodicity coefficients and the corollary follows from Theorem \ref{wkerg}. \ep \section{Comparisons of ergodic coefficients} \label{sec5} %\setcounter{equation}{0} We observe that detailed comparison of of our results above to some results in \cite[Chapter 4]{Sene81} is difficult since in the latter coefficient of ergodicity is defined in \cite[Definition 4.6]{Sene81} not in terms of norms but as a continuous function $\phi$ on the set of matrices satisfying $0 \leq \phi \leq 1$, and theorems require the hypothesis that this function is submutliplicative, see also \cite{Sene73} for a similar approach. It may be noted that in our proofs we have not used the subadditive property of norms, only its submultiplicative property.\\ The $\ell_1$ coefficient of ergodicy $\w_e$ is advantageous for obtaining theoretical results since $\w_e(A) \le 1$ for all stochastic matrices $A$. However, as we pointed out in the introduction, there are natural and useful coefficients of ergodicity $\nu_e$ associated with a norm $\nu$ such that $\nu_e(A) > 1$ for some stochastic matrix $A$. In order to provide a class of such examples, we state and prove a proposition. \begin{prop} \label{last} Let $n > 1$ and let $1 \le k \le n$. For any $A \in \R^{nn}$ which leaves $H$ invariant, let $\tA_k \in \R^{n-1,n-1}$ be defined by \begin{equation} \label{A.tilde} \tilde{a}_{ij} \e a_{ij} - a_{ik},\ i,j = 1, \ldots, n, \ i,j \ne k . \end{equation} Let $\tnu$ be any norm on $\R^{n-1}$. Then there exists a norm $\nu$ on $\R^n$ such that the corresponding coefficient of ergodicity satifies $\nu_e(A) = \tnu^0(\tA_k)$ for all stochastic matrices $A \in \R^{nn}$, where $\tnu^0$ is the operator norm on $\R^{n-1,n-1}$ induced by $\tnu$. \end{prop} \bp Without loss of generality, we may assume that $k = 1$ and we put $\tA_1 = \tA$. For $x \in \R^n$ define $\tx = (x_2,\ldots,x_n)^T \in \R^{n-1}$. Note that $\te = (1,\ldots,1)^T \in \R^{n-1}$ and define the norm $\nu$ on $\R^n$ by \be \label{normdef} \nu(x) \e |x_1 + \te^T\tx| + \tnu(\tx), \ x \in \R^n. \ee Let $x \in H$. Then $x_1 = -\te^T \tx$ and hence $\nu(x) = \tnu(\tx)$.. If $A$ leaves $H$ invariant (and, in particular if A is stochastic) we therefore have $\nu(Ax)/\nu(x) = \tnu(\wt{Ax})/\tnu(\tx)$ when $x \ne 0$. But it easily checked that $(\wt{Ax}) = \tA\tx$ for $x \in H$ since $x^T = (-\te^T\tx, \tx)$. The result follows. \ep\\ The special case of Proposition \ref{last} where $\tnu$ is the $\ell_1$ norm on $\R^{n-1}$ may be found in \cite[Example 1]{Rhod93} with a different proof. Observe that the coefficient of ergodicity so obtained is in general {\em not} equal to $\w_e$.\\ If we wish to find examples of ergodicity coefficients, it follows from the above proposition that we do not need to start with a norm on $\R^n$ and use the definition (\ref{Hcond}) to compute the coefficient. Instead, we may pick $k,\ 1 \le k \le n$, and a norm $\tilde{\nu}_k$ on $\R^{n-1}$ and compute $\tnu^0(\tilde{A}_k)$. Also, for many purposes, it is possible to consider $\beta = \min_{k = 1,\ldots,n}\tnu^0(\tA_k)$, for example for when finding upper bounds on the moduli of eigenvalues of $A$ which do not equal $1$, and our MATLAB experiments using the {\bf rand} function show that in most cases $\beta < \w_e(A)$ when $\tnu$ is the $\ell_2$ norm.\\ We end with the easily proved remark that the mapping $x \rightarrow \tx$ of $\R^n$ onto $\R^{n-1}$ in the proof of Proposition \ref{last} is a vector space homomorphism whose restriction to $H$ is an isomorphism. The mapping $A \rightarrow \tA_k$ onto $\R^{n-1,n-1}$ from the algebra of matrices in $\R^{nn}$ that map $H$ into itself is a homomorphism whose kernel consists of all matrices in the algebra of rank $r, \ r \le 1$.\\ %We have run several hundred examples on MATLAB using the {\bf %rand} function with the columns of the matrices normalized to %sum to %$1$ and with the size of matrices ranging up to 100. For our %norm $\tnu$ we chose %the $\ell_2$ norm on $\R^{n-1}$ which we here denote by %$\tsi$. We compared the %$resulting values with those obtained for the ergodicity %coefficient $\w_e$ of the $\ell_1$ norm and found %that both $\tsi^0(\tA) < \w_e(A)$ and %$\tsi^0(\tA)> \w_e(A)$ occurred frequently. %We also observed that the for most large stochastic %matrices the moduli of the eigenvalues that differ from $1$ were %much smaller in modulus than either of the coefficients of %ergodicity. \\ \bigskip \centerline{{\bf Acknowledgment}} \vspace{.15in} We would like to thank Wenchao Huang for some helpful remarks. We thank Olga Holtz for her careful reading of the manuscript.\\ \bibliographystyle{plainxe} \begin{thebibliography}{0} \bibitem{BaDeSt69} F. L. Bauer, Eck. Deutsch, and J. Stoer. \newblock Absch\"{a}tzungen f\"{u}r die Eigenwerte positiver linearer Operatoren. \newblock {\it Lin. Alg. Appl.}, 2:275--301, 1969. \bibitem{BeEl97} W. J. Beyn and L. Elsner. \newblock Infinite products and paracontracting matrices. \newblock {\it Elec. J. Lin. Alg.}, 2:1--8, 1997. \bibitem{Hajn56} J. Hajnal. \newblock The ergodic properties of non--homogeneous finite Markov chains. \newblock {\it Proc. Cambridge Phil. Soc.}, 52:67--77, 1956. \bibitem{Hajn58} J. Hajnal. \newblock Weak ergodicity in non--homogeneous Markov chains. \newblock {\it Proc. Cambridge Phil. Soc.}, 54:52--67, 1958. \bibitem{HaRo97} D.J. Hartfiel and U.G. Rothblum. \newblock Convergence of inhomogeneous products of matrices and coefficients of ergodicity. \newblock {\it Lin. Alg. Appl.}, 277:1--9, 1998. \bibitem{Hysl45} J. M. Hyslop. \newblock Infinite Series. \newblock {\it Oliver and Boyd}, Edinburgh, 1945. \bibitem{KuRh90} R. K\"uhne and A. Rhodius. \newblock A characterization of Dobrushin's coefficient of ergodicity. \newblock {\it Z. Anal. Anw.} 9(2):187--188, 1990. \bibitem{Leiz92} A.Leizarowitz. \newblock On infinite products of stochastic matrices. \newblock {\it Lin. Alg. Appl.} 168:189--219, 1992. \bibitem{Lesa90} A. Le\v{s}anovsk\'{y}. \newblock Coefficients of ergodicity generated by non--symmetrical vector norms. \newblock {\it Czechoslovak Math. J.} 40 (115):284--294, 1990. \bibitem{Mott57} J. L. Mott. \newblock Conditions for the ergodicity of non--homogeneous finite Markov chains. \newblock {\it Proc. Roy. Soc, Edinburgh}, Section A, 64:369--380, 1957. \bibitem{MoSc57} J. L. Mott and H. Schneider. \newblock Matrix norms applied to weakly ergodic Markov chains. \newblock {\it Arch. Math.}, 8:331--333, 1957. \bibitem{Rhod93} A. Rhodius. \newblock On explicit forms of ergodicity coefficients. \newblock {\it Lin. Alg. Appl.}, 194:71--83, 1993. \bibitem{Rhod97} A. Rhodius. \newblock On the maximum ergodicity coefficient, the Dobrushin coefficient and products of stochastic matrices. {\it Lin. Alg. Appl.}, 253:141--157, 1997. \bibitem{Sene73} E. Seneta. \newblock On the historical development of the theory of finite inhomogeneous Markov chains. \newblock{\it Proc. Cambridge Phil. Soc}, 74:507--513, 1973. \bibitem{Sene81} E. Seneta. \newblock Non--negative Matrices and Markov Chains, Second Edition. \newblock {\it Springer Verlag}, New--York, 1981. \bibitem{Zeng72} C. Zenger. \newblock A comparison for some bounds for the nontrivial eigenvalues of stochastic matrices. \newblock {\it Numer. Math.}, 19:209--211, 1972. \end{thebibliography} \end{document} ----------------------------------------------------------------- ----------- Phones: (New) Area Code 860 Michael Neumann Office 486 3918 Department of Mathematics Main Office 486 3923 University of Connecticut Fax 486 4238 Storrs, Connecticut O6269-3OO9 Home 236 2068 www home page: http://tatung.math.uconn.edu/~neumann