2

$P \in {\mathbb R^{N \times N}}$ is a nonnegative matrix with the properties:

  1. Each row sums to 1,
  2. for some $\alpha>0$ and for some column, all entries of the columns are larger or equal than $\alpha$.

Given any vector $x \in {\mathbb R^n}$, we decompose it as $x = y + ce$, where $c$ is a scalar, $e$ is the vector with all entries equal to $1$ and $y$ has one zero entry and all other entries are nonnegative. ($c$ equals the minimum of the components of $x$.)

Let $x(k + 1) = Px(k),x(k) = y(k) + c(k)e$. Does the following inequality hold? $${\left\| {y(k + 1)} \right\|_\infty } \le (1 - \alpha ){\left\| {y(k)} \right\|_\infty }$$

Martin Argerami
  • 205,756
wenbo
  • 59

1 Answers1

1

I have got the answer. Given any vector $x \in {\mathbb R^n}$, we decompose it as $x = y + c1$, where $c$ is a scalar and $y$ has one zero entry and all other entries are nonnegative. ($c$ equals the minimum of the entries of $x$.) Let $x(k + 1) = Px(k),x(k) = y(k) + c(k)1$, we have \begin{align}\label{p_lem1.0} \begin{split} x(k + 1)&= P(y(k) + c(k)1)\\ &= Py(k)-h(k)1 + (c(k) + h(k))1, \end{split} \end{align} where $h(k) = \min (Py(k))$ is a scalar. Then, we can easily obtain that $y(k + 1) = Py(k) - h(k)1$ and $c(k + 1)=c(k) + h(k)$. Note that $\mathop {\max }\limits_{j = 1}^N \mathop {\min }\limits_{i = 1}^N {P_{ij}} > 0$ if and only if there is at least one column of $P$ whose entries are all positive. We suppose that the all the entries of the $m$th column of $P$ are positive. Then, for $\forall i = 1,2, \cdots ,N$, we get \begin{equation} {y_i}(k + 1) = \sum\limits_{j = 1}^N {{p_{ij}}{y_j}(k)} - h(k) \le \lambda {y_m}(k) + (1 - \lambda ){\left\| {y(k)} \right\|_\infty } - h(k). \end{equation} Since, $y(k+1)$ and $y(k)$ has at least one zero entry, we get \begin{equation} - h(k) = - \mathop {\min }\limits_{i = 1,2, \cdots ,N} \left( {\sum\limits_{j = 1}^N {{p_{ij}}{y_j}(k)} } \right) \le - \lambda {y_m}(k) \end{equation} By the above two inequalities , for $\forall i = 1,2, \cdots ,N$, we get ${y_i}(k + 1) \le (1 - \lambda ){\left\| {y(k)} \right\|_\infty }$.

wenbo
  • 59