Proving that symmetric matrix can be shifted to be positive definite

Question

In my studies of matrix analysis, particularly in positive semidefinite matrices, I have come across the following question:

Let $ I $ be the $ n \times n $ identity matrix, and let $ v $ be a length n real column vector, we are asked to prove there exists a positive $ \delta > 0 $ such that the matrix $ I - \delta vv^T $ is positive semi definite.

Now, I know for any positive $ \delta $ we know that $ I - \delta vv^T $ is a real symmetric matrix and thus its positive semi definiteness is equivalent to non-negativity of its eigenvalues, but how do I prove there exists a positive $ \delta > 0 $ such that the eigenvalues of $ I - \delta vv^T $ are non negative and I have no real idea on how to do this, or even if this is the right approach, I would certainly appreciate any help on this, I thank all helpers.

Answer 1

Let $A:=I-\delta vv^T$. Complete $v_1:=v$ to an orthonormal basis $v_1,\ldots,v_n$. Note that for $k>1$, $$ A v_k = v_k - \delta v_0v_0^Tv_k = v_k $$ because $v_0^Tv_k=0$. So $A$ has $(n-1)$ eigenvectors with eigenvalue $1$. You know that $\chi_A(t) = (t-1)^{n-1}(t-\lambda)$ is the characteristic polynomial of $A$, where $\lambda$ is some real number. You know that $\operatorname{trace}(vv^T)=\sum_i v_i^2 = v^Tv$ and because the trace of a matrix is the sum of its eigenvalues, $$ \lambda+n-1=\operatorname{trace}(A)=\operatorname{trace}(I-\delta vv^T)=\operatorname{trace}(I)+\operatorname{trace}(\delta vv^T)=n-\delta v^Tv. $$ This implies $\lambda = 1- \delta v^T v = 1 - \delta \cdot \|v\|^2$. If you chose $$\delta<\frac1{\|v\|^2},$$ then $\lambda > 0$.

Answer 2

@Jesko Hüttenhain There is a slightly more direct explanation with a precise bound for $\delta$.

Rank-one matrix $M:=vv^t$ has the following eigenvalues (see explanation below):

• $\lambda_1=\|v\|^2$ (multiplicity 1)

• $\lambda_k=0$ ($k=2,3,\cdots n$, i.e., multiplicity $(n-1)$).

Then the eigenvalues of $f(M)=I-\delta M=I-\delta vv^T$ are the $f(\lambda_k)$, i.e.,

• $1-\delta \|v\|^2$ (multiplicity 1).

• $1 -\delta 0 = 1$ (multiplicity $(n-1)$).

It suffices thus to ensure that $1-\delta \|v\|^2>0$, i.e.,

$$\delta<\dfrac{1}{\|v\|^2}$$

Explanation about eigenvalues :

$Mv=(vv^t)v=v(v^tv)=v\|v\|^2=\|v\|^2v$ proving that $\|v\|^2$ is an eigenvalue associated with eigenvector $v$. As $M$ is rank 1, all the other eigenvalues are $0$.