# Needing proof of convergence for a sequence

Let $\left\{u_i\right\}_{i=1}^\infty$ be a sequence of real vectors (i.e. $u_i\in R^n, i=1,2,...$) and $m$ an integer large enough such that $\sum_{i=1}^m u_i u_i^T$ is a positive definite matrix. Define:

$$K_m:=\left(\sum_{i=1}^m u_i u_i^T\right)^{-1}u_m$$

Show that $\left\| K_m\right\|$ tends to zero as $m\longrightarrow \infty$.

If $u_i$s are scalar, i.e. $n=1$, the proof seems trivial (not that trivial, but easy to get). I have not been able to find a counter-example for the cases where $u_i$s are vectors (and believe me, I have tried hard). So I think this is very likely to be true in general.

• Say $m > n$. Let $u_1,\ldots,u_{n-1}$ be canonical basis vectors $(e_i)_{i=1}^{n-1}$. Let $u_{n},\ldots,u_{m-1}=0$ and let $u_m=e_n$. Then $\sum_{i=1}^m u_iu_i^T$=$I_n$ and $\|K_m\|=1$. – Suvrit Jun 7 '16 at 14:57
• @Suvrit Ok, but how do you continue with the $u_m$? Setting $u_m=0$ from that point on will give $K_m=0$, and continuing with $u_m = e_n$ will drive the inverse down to zero… Seems like and interesting question to me. – Dirk Jun 7 '16 at 15:31
• @Dirk yes, indeed. This example was written only for a single fixed $m$... – Suvrit Jun 8 '16 at 8:10

Let me first discuss the special case where $|u_n|$ is bounded. Let's denote our matrices by $A_n=\sum_{j=1}^n u_ju_j^*$. What we're trying to show can only fail if there are infinitely many $u_n=c_nv_n + w_n$ that have a coefficient $|c_n|\ge\delta >0$ when expanded in terms of the eigenvectors of $A_n$, such that the corresponding eigenvalue $\lambda_{n}$ stays bounded.

By compactness, these eigenvectors $v_n$ converge to a vector $v$ on a subsequence. Then, however, $\langle v_n, A_n v_n\rangle$ will become large because each of the many summands $u_ju_j^*$ of $A_n$ with a $u_j$ that is as above (with a component $\ge\delta$ in almost the direction of $v_n$) makes a contribution $\gtrsim \delta^4$ to this quadratic form. So $\lambda_n$ can not stay bounded.

In general, if $|u|$ is large, then consider (writing $Q=uu^*$) $$|A^{-1/2}u|^2 = |(Q+B)^{-1/2}u|^2 =\langle u, (Q+B)^{-1} u\rangle ;$$ this is bounded because $-1/z$ is operator monotone, so $B$ in the quadratic form can be essentially dropped (more precisely, replace it by $\epsilon B$).

In other words, $x_n=A_n^{-1/2}u_n$ is always bounded, and we still find ourselves in the same scenario as above: to prevent $A_n^{-1/2}x_n$ from going to zero, $x_n$ and thus also $u_n$ must have a component bounded away from zero belonging to a bounded eigenvalue of $A_n$.

• In 2nd paragraph, you stated: By compactness, these eigenvectors $v_n$ converge to a vector $v$ on a subsequence. I didn't get it. Actually I didn't get the whole paragraph. Could you explain more? – polfosol Jun 8 '16 at 8:52
• First, writing $A_n$ as above. Let $\lambda_{n,k}$ be the eigenvalues of $A_n$. By what Ilya wrote you have that for a fixed $k$, $\lambda_{n,k}$ is increasing in $n$. So $\lambda_n$ is bounded from below. Let $x_n$ be a sequence of bounded vectors such that $\|A_n^{-1} x_n\| \not\to 0$, this requires that along a subsequence at least one of the eigenvalues $\lambda_{n_j,k_j}$ remain bounded, and that the projection of $x_{n_j}$ onto the eigenvector $v_{n_j,k_j}$ be bounded below. – Willie Wong Jun 8 '16 at 14:01
• Now let $x_n$ be $u_n$ as in the first paragraph. The previous comment allows to extract a subsequence $v_{n_j, k_j}$ of vectors, each of which is a (normalized) eigenvector of $A_{n_j}$. As the unit sphere is compact in finite dimensional space, this subsequence as a limit point $v$ on the unit sphere. The key is now that for large $N$, there are many $n_j < N$. For each $n_j$, the $u_{n_j}$ contributes to $A_N$ roughly in the direction of $v$ a non-negligible amount. And since $v$ is almost parallel to $v_{n_j,k_j}$ for large $j$, this tells us that the eigenvalue $\lambda_{n_j,k_j}$ cannot – Willie Wong Jun 8 '16 at 14:06
• ... be bounded after all. @polfosol Implicit in the argument before is that by your construction (and again by the argument in Ilya's post), adding $u_k u_k^*$ to $A_{k-1}$ cannot decrease its size along any direction. Only increase it. – Willie Wong Jun 8 '16 at 14:09
• @polfosol: Willie has already commented in detail on your question; I assume that the $v_n$ are normalized, so the compactness referred to is the fact that the unit sphere is compact. – Christian Remling Jun 8 '16 at 17:13

Thanks to Fedor Petrov for repeatedly pointing out my silly mistakes, and for suggestions how to improve the text (now I've rewritten the whole text).

$\let\eps\varepsilon\def\tr{\mathop{\rm tr}}\def\pr{\mathop{\rm pr}\nolimits}$ Denote $U_m=\sum_{i=1}^m u_iu_i^T$ ($U_m$ is regarded as a nonnegative self-agjoint operator in the Euclidean space). Set $f_m(x)=\langle U_mx,x\rangle=\sum_{i=1}^m\langle u_mx,u_mx\rangle^2$. By $\tr f$ we always mean the trace of the self-adjoint operator corresponding to a quadratic form $f$. Notice that $\tr f_m=\sum_{i=1}^m\|u_i\|^2$ and, more generally, $\tr f\big|_V=\sum_{i=1}^m\|\pr_Vu_i\|^2$ for every subspace $V$.

Let $\lambda_{1,m}\leq\dots\leq\lambda_{n,m}$ be the eigenvalues of $U_m$. Notice that $$\lambda_{i,m}=\max_{V_{n-i+1}}\min_{0\neq x\in V_{n-i+1}}f_m(x)/\|x\|^2 =\min_{V_{i}}\max_{0\neq x\in V_{i}}f_m(x)/\|x\|^2, \qquad(*)$$ where $V_j$ is assumed to run over all $j$-dimensional subspaces. Since $f_m(x)$ does not decrease as $m$ grows, we have $\lambda_{i,m+1}\geq \lambda_{i,m}$ for all $m$. Moreover, $\lambda_{1,m}\geq c>0$ for sufficiently large $m$ (and some constant $c$), and we consider only much larger values of $m$. Finally, notice that for every $V_j$ we have $$\lambda_{1,m}+\dots+\lambda_{j,m}\leq \tr f_m\big|_{V_j} \leq \lambda_{n-j+1,m}+\dots+\lambda_{n,m}.$$

Assume that the claim does not hold. We first show that $\lambda_{1,m}$ is bounded, and then show why it is impossible.

1. Assume that $\|U_m^{-1}u_m\|\geq \eps$ for some $m$. Set $v=U_m^{-1}u_m$, $w=U_{m-1}v$, $\alpha=\langle v,w\rangle=f_{m-1}(v)\geq \lambda_{1,m-1}\|v\|$ (so $\alpha$ is bounded away from $0$). Then $u_m=U_mv=w+\langle v,u_m\rangle u_m$ is collinear with $w$, $u_m=\beta w$. Now we have $\beta w=w+\beta^2\alpha w$, so $\alpha\beta^2-\beta+1=0$, $\beta=(1\pm\sqrt{1-4\alpha})/2\alpha$. This means that $\lambda_{1,m}\leq \alpha\leq 1/4$. So $\lambda_{1,m}\leq 1/4$ always. Moreover, $\beta$ is bounded away from $0$, as well as bounded from above (since $\alpha$ is not very small). Thus $f_m(v)=\langle v,w\rangle+\langle v,u_m\rangle^2=\alpha+(\beta\alpha)^2$ is also bounded by some constant $C_1$.

2. Let $e_1,\dots,e_n$ be the orthonormal base in which $U_m$ diagonalizes as $\mathop{\rm diag}(\lambda_{1,m},\dots,\lambda_{n,m})$. Consider the expansion of $v$ in this base. Since $\|v\|\geq \eps$ and $f_{m}(v)\leq C_1$, some eigenvector $e_i$ with eigenvalue $\lambda_{i,m}\leq 2C_1/\eps=:C$ appears in this expansion with a coefficient $\mu$ which is bounded away from $0$. Then $\langle e_i,u_m\rangle=\mu\lambda_{i,m}$ is also bounded away from $0$ by some $\delta>0$.

Set $V_i$ to be the span of $e_1,\dots,e_i$. Then $$\lambda_{1,m}+\dots+\lambda_{i,m} =\tr f_m\big|_{V_i}=\tr f_{m-1}\big|_{V_i}+\|\pr_{V_i}u_m\|^2 \geq \lambda_{1,m-1}+\dots+\lambda_{i,m-1}+\delta^2.$$ This means that there exists some $k$ such that $C\geq \lambda_{k,m}\geq \lambda_{k,m-1}+\delta^2/n$. But such event (a small eigenvalue increases by at least $\delta^2/n$) may happen only finitely many times --- a contradiction.

• Oh dear! It doe not look easy to formalize intuitive thoughts. Hope now it is OK;)... – Ilya Bogdanov Jun 8 '16 at 6:55
• This seems unexpectedly way too complex. I hope there was a simpler solution or some references to dig deeper into your proposed solution. – polfosol Jun 8 '16 at 8:55
• Sorry, found a mistake; everything is rewritten (and explained a bit more thoroughly). It is eaier now... – Ilya Bogdanov Jun 8 '16 at 9:37
• I was stuck between two good answers and didn't know which to accept. So I simply flipped a coin! Thanks by the way – polfosol Jun 11 '16 at 6:23