Sum of the matrix series

Question

Let $A\in\mathbb R^{n\times n}$ be a symmetric matrix which $0\preceq A\preceq I$ ($I$ is identity matrix), and $w_k\in\mathbb R^n$ are arbitrary certain vectors which $\|w_k\|\leq1,\,\,k=0,1,\ldots$ (all norms are euclidean).

The goal is to obtain an upper bound for vector $$ \left\|\sum\limits_{k=0}^\infty(I-A)^kAw_k\right\|. $$

Evidently, this quantity is less than $\sqrt{n}$, but it seems that it should not depend on $n$.

Answer 1

$A$ has an orthonormal basis of eigenvectors, with real eigenvalues between $0$ and $1$. However, $(I-A)A$ kills off eigenvectors with eigenvalue $1$ and $0$; so you need only consider the eigenvectors with eigenvalues strictly between $0$ and $1$. If there are no eigenvalues between $0$ and $1$, then $(I-A)^{k}A=0$ for $k \ge 1$, and a bound is obvious. Otherwise, let $\lambda_{min}$ and $\lambda_{max}$ be the minimum and maximum eigenvalues of $A$ strictly between $0$ and $1$. Then $\|(I-A)^{k}Aw_{k}\| \le (1-\lambda_{min})^{k}\lambda_{max}\|w_{k}\|\le (1-\lambda_{min})^{k}\lambda_{max}$ for $k \ge 0$, which gives $\lambda_{max}/(1-(1-\lambda_{min}))=\lambda_{max}/\lambda_{min}$ as a bound for the sum.

Answer 2

Just using matrix norms, triangle inequality and geometric series you obtain the bound

$$\frac{\|A\|}{1-\|I-A\|}.$$

---

Let's try to get matrix independent. The spectrum of $(I-A)^kA=(I-A)^k-(I-A)^{k+1}$ consists of the eigenvalues

$$f_k(λ)=(1-λ)^k-(1-λ)^{k+1}$$

for $λ$ ranging over the eigenvalues of $A$. The maximum of the full function on $[0,1]$ is at

$$0=f_k'(λ)=-k(1-λ)^{k-1}+(k+1)(1-λ)^k=(1-λ)^{k-1}(1-(k+1)λ)\implies λ = \frac1{k+1}$$

This would give an estimate that is practically a harmonic series, since

$$f_k(\tfrac1{k+1})=\tfrac1{k+1}(1-\tfrac1{k+1})^k=\tfrac1k(1-\tfrac1{k+1})^{k+1}<\tfrac1ke^{-1}\le e^{-1}(\ln(k)-ln(k-1))$$

However, since there is only a finite number of eigenvalues of $A$, there is a smallest positive one with $\tfrac1{N+1}<λ_{min}\le \tfrac1N$, so that the maximum of $f_k$ for $k>N$ is always taken at $λ_{min}$. So one gets a bound of

\begin{align} &\|A\|+\frac14+\sum_{k=2}^{N} e^{-1}(\ln(k)-\ln(k-1)+\sum_{k=N+1}^\infty λ_{min}(1-λ_{min})^k\\ \le&\frac54+e^{-1}(\ln(N)-\ln(1))+(1-λ_{min})^{N+1}\\ \le&\frac54+e^{-1}(\ln(Nλ_{min})-\ln(λ_{min}))+e^{-(N+1)λ_{min}}\\ \le&\frac54+e^{-1}\bigl(1+|\ln(λ_{min})|\bigr) \end{align}

So this complicated expression may be a stricter bound, but still depends on the eigenvalue structure of $A$.

---

Using the recursion formula, one may try the following argument

$$x_+=x+A(w-x)=\tfrac12(x+w)+(A-\tfrac12I)(w-x).$$

Now since $\|A-\tfrac12I\|\le \tfrac12$, we have that $x_+$ is inside a ball with center the midpoint between $x$ and $w$ and so, that $x$ and $w$ are the poles of the ball. However, this ball can have parts outside the unit ball if $x$ and $w$ are close enough to the unit sphere.

Answer 3

$A$ is symmetric, its unit length eigenvectors $\big\{v_i\big|i\in\{1,2,...,n\}\big\}$ with respective eigenvalues $\big\{\lambda_i\big|i\in\{1,2,...,n\}\big\}$ form an orthogonal basis. $w_k=\sum\limits_{i=1}^n a_{ki}v_i$, where $\left|a_{ki}\right|\le 1$ as $\|w_k\|\le 1$.

$$s:=\sum_{k=0}^\infty (1-A)^kAw_k = \sum_{i=1}^n \Big(\sum_{k=0}^\infty (1-A)^kAa_{ki}\Big) v_i,$$ by Fubini's theorem, since $\sum\limits_{k=0}^\infty\big\|(1-A)^kA\big\|$ absolutely converges.

$$\|s\|^2 = \sum\limits_{i=1}^n \|u_i\|^2,$$ where $u_i:=\Big(\sum\limits_{k=0}^\infty (1-A)^kAa_{ki}\Big) v_i = \Big(\sum\limits_{k=0}^\infty (1-\lambda_i)^k\lambda_ia_{ki}\Big)v_i$. $$\|u_i\|\le\sum\limits_{k=0}^\infty (1-\lambda_i)^k\lambda_i\left|a_{ki}\right| \le\sum\limits_{k=0}^\infty (1-\lambda_i)^k\lambda_i =1.$$ Together with the previous inequality, we conclude $\|s\|\le \sqrt n$.

But I think the sharp bound is $1$, although I can not prove it.

I tried the following example. Let $w_k = v_{j+1},\, j\equiv k \ (\mod n)$. We see $\|u_i\| = \frac{(1-\lambda_i)^j}{\sum_{i=0}^{n-1} (1-\lambda_i)^i}$. The norm bound appears -- I have not checked carefully --- below $1$.