Eigenvalue decomposition of $A = I - xx^T$ [duplicate]

$\begingroup$

Let $A = I - xx^T$, where $x \in \mathbb{R}^n$ and $I$ is the identity matrix of $\mathbb{R}^n$

We know that $A$ is a real symmetric matrix, therefore there exists an eigenvalue decomposition of $A$ such that

$$A = Q^T\Lambda Q$$

Is it possible to find $Q$, $\Lambda$?

$I - xx^T = Q^TQ - xQ^TQx^T = Q^TQ - (Q^Tx)^T(x^TQ)^T...$

$\endgroup$ 0

2 Answers

$\begingroup$

Consider $$ Ax=(I-xx')x=(1-x'x)x $$ so $x$ itself is an eigenvector with eigenvalue $1-x'x$. In fact, if $v$ is an eigenvector with some eigenvalue $\alpha$, we have $$ \alpha v=Av=(I-xx')v=v-(x'v)x\implies(1-\alpha)v=(x'v)x. $$ This means if $\alpha\neq 1$, then $v$ is proportional to $x$ so in fact $v$ is an eigenvector with eigenvalue $1-x'x$. If $\alpha=1$, then $x'v=0$. Conversely, if $v'x=0$, then $v$ is an eigenvector with eigenvalue $1$: $$ Av=(I-xx')v=v-(x'v)v=v. $$Conclusion: $I-xx'$ has eigenvalues $1-x'x$ and $1$ where $1$ has multiplicity $n-1$. The eigenvectors for $1-x'x$ are parallel to $x$ and the eigenvectors of $1$ are any vector in the space orthogonal to the space spanned by $x$. So you can take $Q'=\Big(\frac{x}{|x|}\;r_1\;\cdots\;r_{n-1}\Big)$ where each $r_i$ is $n\times 1$ and $\{r_1,\ldots,r_{n-1}\}$ is some orthonormal basis of $[\text{span}(x)]^\perp$.

$\endgroup$ $\begingroup$

I'll assume $x\neq0$.

Note that $x/||x||$ is an eigenvector and it's easy to see that $A(x/||x||)=0$. For all vectors $v$ orthogonal to x, it's clear that $Av=v$.

Then, you can just take $\Lambda=diag(0,1,1,...,1)$ and $Q'=[x\ v_1\ ...\ v_{n-1}]$ with $\{v_1,...,v_{n-1}\}$ an independently linear set on which every vector is orthogonal to $x$. That way you would have that $$A=Q'\Lambda(Q')^{-1}$$ and by applying the Gramm-Schmidt process to the columns of $Q'$ and storing them in the columns of a new matrix $Q$ you will have the requested decomposition of $A$ as $$A=Q\Lambda Q^T$$

$\endgroup$