eigenvalues of $Q+\mu cc^T$ as $\mu\rightarrow +\infty$

Question

Assume $Q$ is a $n\times n$ SPD, $c$ is a $n\times 1$ matrix. Let $\mu>0$, then one of the eigenvalues of $Q+\mu cc^T$ will go to infinity as $\mu\rightarrow +\infty$ and the other eigenvalues will remain bounded.

Any hint on how to prove the claim?

Answer 1

Let $\lambda_{1}(\mu)\geq\lambda_{2}(\mu)\geq\ldots\geq\lambda_{n}(\mu)$ be the eigenvalues of $Q+\mu cc^{*}$ where $^{*}$ denotes transposition. Use the Courant minimax principle, the largest eigenvalue is given by

$$\lambda_{1}(\mu)=\max\limits_{|x|=1}x^{*}(Q+\mu cc^{*})x$$ Then $\lambda_{1}(\mu)\geq\mu$. The remaining eigenvalues are given by $$\lambda_{j}(\mu)=\min\limits_{K\in\mathbb{C}^{(j-1)\times n}}\max\limits_{|x|=1,Kx=0}x^{*}(Q+\mu cc^{*})x$$ In particular, for the second one one you may choose $K=c^{*}$, so $$\lambda_{2}(\mu) =\min\limits_{K\in\mathbb{C}^{1\times n}}\max\limits_{|x|=1,Kx=0}x^{*}(Q+\mu cc^{*})x \leq\max\limits_{|x|=1,c^{*}x=0}x^{*}(Q+\mu cc^{*})x =\max\limits_{|x|=1,c^{*}x=0}x^{*}Qx $$ Hence, $\lambda_{2}(\mu)$ (and thus the rest of them) remains bounded regardless of $\mu$

A similar reasoning applies for perturbations of prescribed rank $Q+\mu K$, $\mbox{rank}(K)=k$, showing that only the first $k$ eigenvalues diverge along with $\mu$

Answer 2

The characteristic equation of $Q+\mu cc^T$ is:

$$det((Q + \mu cc^T)-\lambda I)=det((Q-\lambda I) + \mu cc^T)=0.$$

It can be transformed, using matrix-determinant lemma (https://en.wikipedia.org/wiki/Matrix_determinant_lemma), into:

$$\left(1+\mu c^T(Q-\lambda I)^{-1}c\right)det(Q)=0$$

Because $det(Q)\neq0$, this is equivalent to the following equation:

$$\tag{1}c^T(Q-\lambda I)^{-1}c=-\frac{1}{\mu}.$$

Let us now diagonalize $(Q-\lambda I)^{-1}$.

We assume that $A$ is diagonalizable under the form $Q=R^{-1} D R=R^T D R$ with

• $R$ invertible, because $A$ is SDP, with the essential property that $R$ is orthogonal, i.e. $R^{-1}=R^T$, and

• $D:=diag(\lambda_1,...\lambda_n)$.

We then have $Q-\lambda I=R^{-1} D R-\lambda R^{-1}R$, i.e., $Q-\lambda I=R^{-1}(D-\lambda I)R.$

Thus,

$$\tag{2}(Q-\lambda I)^{-1}=R^{-1}(D-\lambda I)^{-1}R=R^{T}(D-\lambda I)^{-1}R.$$

Inserting (2) into (1), and setting $v:=Rc$, we get:

$$\tag{3}v^T(D-\lambda I)^{-1}v=-\frac{1}{\mu}$$

Let $v_k$ be the coefficients of $v$. (3) is equivalent to:

$$\tag{4}\underbrace{\sum_{k=1}^n \dfrac{v_k^2}{\lambda_k - \lambda}}_{f(\lambda)}=-\frac{1}{\mu}$$

Now, a graphical end on a particular case, explaining how the roots behave, for the sake of understanding:

We have taken a particular case with $n=3$,

$$f(\lambda):=\dfrac{4}{1-\lambda}+\dfrac{2}{3-\lambda}+\dfrac{1}{6-\lambda}$$

with $f'(\lambda)>0$ thus $f$ increasing.

This curve has the $\lambda$-axis for its horizontal asymptote and possesses $3$ vertical asymptotes (one for each pole of $f$). Of course, what we are going to say is immediately generalizable (For example, the fact that $f'(x)>0$). The roots of equation (4) are the abscissas of intersection points between the curve and the horizontal (red) line with equation $y=-\frac{1}{\mu}$. As $\mu \to +\infty$, $-\frac{1}{\mu} \to 0_{-}$: the red line intersects the curve

• at "ordinary" points (all but the last) that gently swift to the right, staying in their "confinement intervals", here $(1,3)$ or $(3,6)$,

• at an "extraordinary point", the rightmost one, whose abscissa tends to $+\infty$.

Remark: This technique of resolution is called "secular equation method"; see for example, pages 10 and 11 of (http://www.netlib.org/lapack/lawnspdf/lawn69.pdf) or (http://www2.cs.cas.cz/harrachov/slides/Golub.pdf))