Recurrence Equation and Matrix Convergence

Question

To begin with, let us give the conceptual background needed to expose the problem. First of all, we shall consider the set $\mathbb{L}^{n} = \mathbb{R}^{n}_{\geq0} = \{\overrightarrow{x}\in\mathbb{R}^{n}_{\geq0}\mid\sum x_{i} = 1\}$. More precisely, $\overrightarrow{x} = (x_{1},x_{2},\ldots,x_{n})$ belongs to $\mathbb{L}^{n}$ iff its coordinates are non-negative and its sum totals one. From this convention, it is associated to each vector $\overrightarrow{x}\in\mathbb{L}^{n}\backslash\{(1/n,1/n,\ldots,1/n)\}$ the following function $$P(x_{i},x_{j}) = P(x_{j},x_{i}) := \frac{1}{2}\frac{|x_{i}-x_{j}|}{\displaystyle\sum_{\delta=1}^{n-1}|x_{k}-x_{l}|}\quad\text{where}\quad\delta = k - l$$ Moreover, we are going to associate to this function the following matrix $A_{0} = [a^{0}_{ij}] := [P(x_{i},x_{j})]$ with the additional restriction that $x_{1}\leq x_{2}\leq\ldots\leq x_{n}$. Given that this matrix is self-adjoint, we may associate to it the matrix $\Lambda_{0}:= [\lambda^{0}_{ij}]$ which is obtained from $A_{0}$ by diagonalizing it and taking the norm of its coordinates. We are going to impose now a restriction over $\Lambda_{0}$: $\lambda^{0}_{11}\leq\lambda^{0}_{22}\leq\ldots\leq\lambda^{0}_{nn}$. Then it is possible to propose the problem itself. Given the recurrence equation \begin{align*} A_{k+1} & = \frac{A_{k} + \Lambda_{k}}{1+\displaystyle\sum_{i=1}^{n}\lambda^{k}_{ii}} \end{align*} Where $\Lambda_{k}:= [\lambda^{k}_{ij}]$ is the diagonalization of $A_{k}$ whose coordinates have been normed and which satisfy $\lambda^{k}_{11}\leq\lambda^{k}_{22}\leq\ldots\leq\lambda^{k}_{nn}$, the question is: does this sequence converge? If so, could anyone provide me its limit? It seems to me that the non-diagonal elements converge to zero. Nonetheless I am not able to conjecture what happens to the diagonal. In order to avoid misunderstandings, here it comes an example. Let's take the vector $\overrightarrow{x} = (0.1,0.3,0.6)$ whose associated matrix is: $$A_{0} = \left[ \begin{array}{ccc} 0 & 0.1 & 0.25 \\ 0.1 & 0 & 0.15 \\ 0.25 & 0.15 & 0 \end{array} \right]$$ And its corresponding eigenvalues are $\lambda_{1} \cong -0.26,\,\lambda_{2} \cong -0.09,\,\lambda_{3} \cong 0.34$. Therefore: $$\Lambda_{0} = \left[ \begin{array}{ccc} 0.09 & 0 & 0 \\ 0 & 0.26 & 0 \\ 0 & 0 & 0.34 \end{array} \right] $$ We may now give the expression of $A_{1}$. Indeed, here it is \begin{align*} \sum_{i=1}^{3}\lambda^{0}_{ii} & = 0.09 + 0.26 + 0.34 = 0.69\Rightarrow A_{1} = \frac{1}{1.69}\left[ \begin{array}{ccc} 0.09 & 0.1 & 0.25 \\ 0.1 & 0.26 & 0.15 \\ 0.25 & 0.15 & 0.34 \end{array} \right] \end{align*} I think this is it. Thank you in advance for any contribution.

PS: the same question has been asked at MSE

https://math.stackexchange.com/questions/1897558/recurrence-equation-and-matrix-convergence

$\textbf{Remark}$. After one hundred computer-aided iterations, the above sequence seems to converge: \begin{align*} A_{100} = \left[ \begin{array}{ccc} 0.064202 & 2.1000\cdot10^{-31} & 5.2499\cdot10^{-31} \\ 2.1000\cdot10^{-31} & 0.26237 & 3.1499\cdot10^{-31} \\ 5.2499\cdot10^{-31} & 3.1499\cdot10^{-31} & 0.67343 \end{array} \right] \end{align*} From then on, the results are extremely alike.

Answer 1

Your example does not quite fit the problem description, as the matrix $\Lambda_0$ you are adding has the absolute values of the eigenvalues of $A_0$ on its diagonal. If this variation is the problem you are interested in, then the convergence is fairly trivial.

Your initial condition is a matrix $A_0$ with nonnegative entries with the property that the sum of all entries is $1$. This property is clearly invariant under the iteration.

The iteration \begin{align*} A_{k+1} & = \frac{A_{k} + \Lambda_{k}}{1+\displaystyle\sum_{i=1}^{n}\lambda^{k}_{ii}} \end{align*} only adds to the diagonal and divides all entries by a constant greater than one. Thus the sequence of off-diagonal entries is strictly decreasing. The off-diagonal entries converge to zero as eventually $A_k$ is strictly diagonally dominant and from this point on the eigenvalues are indeed all positive. And then $\sum_{i=1}^{n}\lambda^{k}_{ii}$ is bounded away from zero. So there is even an exponential convergence of the off-diagonal entries to zero.

The diagonal matrices with nonnegative diagonal elements summing to one are fixed points under the iteration and each trajectory will converge to one of these fixed points. An application of Gershgorin's theorem shows that there can be no nontrivial limit sets.