I am reading a paper on bandits where it defines a matrix:
$$V_t = \lambda I + \sum_{s=1}^{t} A_{s} A_{s}^{T} $$
where $\lambda$ is a scalar constant, $I \in R^{d \times d}$, $A_s \in R^{d}$
Basically we have a sequence of vectors $(A_s)_{s=1}^{\infty}$ and as time goes we keep adding the outerproducts of those vectors with the matrix $V_t$.
The paper says that as $t$ increases the eigenvalues of the matrix $V_t$ increases.
I am not sure why this is the case. Could anyone help me with the intuition behind this claim? Also where should I begin to try to prove this?
Your matrices are positive semi-definite and selfadjoint (hermitian). Given a selfadjoint matrix $A$, denote by $\lambda_1(A),\ldots,\lambda_n(A)$ the eigenvalues, in non-increasing order, counting multiplicities.
For two positive semi-definite matrices $A,B$ with $B\leq A$ (in the sense that $A-B$ is positive semi-definite. so $\langle (A-B)x,x\rangle\geq0$ for all $x$), you have by the Min-Max Theorem \begin{align} \lambda_k(B)&=\min_{\dim M=k}\,\max\{\langle Bx,x\rangle:\ x\in M,\ \|x\|=1\}\\ &\leq \min_{\dim M=k}\,\max\{\langle Ax,x\rangle:\ x\in M,\ \|x\|=1\}\\ &=\lambda_k(A). \end{align} In your case, you have $$ V_{t+1}-V_t=A_{t+1}A_{t+1}^T, $$ which is positive semi-definite.