How to diagonalize the sum of outer products

857 Views Asked by At

Consider the following sequence of matrices $S_n\triangleq I +\sum_{i=1}^n \mathbf{v}_i \mathbf{v}_i^{\operatorname{T}}$, where $(\mathbf{v}_i) \subset\mathbb{R}^m$. Given that $S_n$ is a symetric positive definite matrix, there exists an orthogonal and diagonal matrix $P_n$ and $D_n$, respectively, such that $S_n = P^{\operatorname{T}}_n D_n P_n$.

My question is the following; does there exist simple expressions for $P_{n+1}$ and $D_{n+1}$ as functions of $(\mathbf{v}_{n+1},S_n,S^{-1}_n,P_n,D_n)$?

I was hoping to find something similar to the Sherman–Morrison formula which gives the expression of the inverse of $S_{n+1}$ as \begin{align}S^{-1}_{n+1} = S^{-1}_n - \frac{S_n^{-1}\mathbf{v}_{n+1}\mathbf{v}^{\operatorname{T}}_{n+1}S^{-1}_{n}}{1 + \mathbf{v}_{n+1}^{\operatorname{T}} S^{-1}_n \mathbf{v}_{n+1}}. \end{align}

1

There are 1 best solutions below

3
On BEST ANSWER

First you have the ambiguity of ordering the eigenvectors/eigenvaules. If you ignore this ambiguity, then it is just the Bunch-Nielsen-Sorensen formula, plus finding the eigenvalues of $D_n+\mathbf{uu}^T$.

So you want to solve the characteristic equation $\det (D+\mathbf{uu}^T-\lambda I)=0$, which is $$ \prod_{i=1}^m (D_{ii}-\lambda)+\sum_{i=1}^m u_i^2\prod_{j\neq i}(D_{jj}-\lambda)=0. $$ (this comes from $\det(A+\mathbf{u}\mathbf{v}^T)=(1+\mathbf{v}^TA^{-1}\mathbf{u})\det A$ applied to $\mathbf{v}=\mathbf{u}$ and $A=D-\lambda I$)

In particular, if the diagonal of $D$ is increasing $D_{11}\leq D_{22}\leq\dots$ then the roots $\lambda_i$ satisfies $D_{ii}\leq\lambda_i\leq D_{i+1,i+1}$ for $i<m$ and the largest eigenvalue $\lambda_m$ is bounded by $D_{mm}\leq\lambda_m\leq D_{mm}+\sum u_i^2$.