# Recurrence Equation and Matrix Convergence

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.

• I'm not quite sure I understand the notation $\sum_{\delta=1}^{n-1} |x_k-x_l|$ "where $\delta=k-l$", but what is $P$ if $x=(1/n,1/n,\dots,1/n)$? – Pietro Majer Aug 21 '16 at 7:33
• Let us fix $\delta = 1$. Hence the associated sum is $|x_{2} - x_{1}| + |x_{3} - x_{2}| + \ldots + |x_{n} - x_{n-1}|$. Once again, let us fix $\delta = 2$. Thus the associated sum corresponds to $|x_{3} - x_{1}| + |x_{4} - x_{2}| + \ldots + |x_{n} - x_{n-2}|$. The same reasoning applies to the other values of $\delta$. As to the case when $\overrightarrow{x} = (1/n,1/n,\ldots,1/n)$, it does not make sense to associate to it the function $P$. The justification is based on the theoretical context where it came from. Hopefully it helps. – user1337 Aug 21 '16 at 21:29
• OK --So to be precise the domain of $P$ is not the whole set $\mathbb{L}^n$ – Pietro Majer Aug 21 '16 at 22:24

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.