14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Suvrit Jun 7 '16 at 14:57
  • 2
    $\begingroup$ @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. $\endgroup$ – Dirk Jun 7 '16 at 15:31
  • $\begingroup$ @Dirk yes, indeed. This example was written only for a single fixed $m$... $\endgroup$ – Suvrit Jun 8 '16 at 8:10
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – polfosol Jun 8 '16 at 8:52
  • 1
    $\begingroup$ 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. $\endgroup$ – Willie Wong Jun 8 '16 at 14:01
  • 1
    $\begingroup$ 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 $\endgroup$ – Willie Wong Jun 8 '16 at 14:06
  • 1
    $\begingroup$ ... 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. $\endgroup$ – Willie Wong Jun 8 '16 at 14:09
  • $\begingroup$ @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. $\endgroup$ – Christian Remling Jun 8 '16 at 17:13
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.