Upper bound on the largest eigenvalue

Question

Let

$$A := W \left( P \Sigma P^{\top} + W^{\top} W \right)^{-1} W^{\top}$$

where $W \in \mathbb{R}^{n \times k}$ may either be fat or skinny, and it's possible $\text{Rank}(W) < \min(n,k)$. $P \in \mathbb{R}^{k \times k}$ is an orthonormal matrix, and $\Sigma \in \mathbb{R}^{k \times k}$ is a diagonal matrix with positive diagonal entries (so $P \Sigma P^{\top}$ is positive definite).

Show that the largest eigenvalue of $A$ is less than $1$.

---

I tried the Woodbury identity but failed. I also looked at this post, but its Cholesky decomposition does not seem to help much about upper bound on eigenvalue. And I did some numerical experiment and it seems to me that the eigenvalue must be bounded by $1$.

Any help would be greatly appreciated!

Answer 1

We can write simply $A=W(S+W^TW)^{-1}W^T$, where $S$ is positive definite. Note that the matrix $A$ itself is positive semidefinite and hence its eigenvalues are real nonnegative.

Since this is true, the nonzero eigenvalues of $A$ are the same as nonzero eigenvalues of $B$, where $$ B=(S+W^TW)^{-1}W^TW. $$ Note that the eigenvectors can be chosen real as well.

Assume that $\lambda $ and $x$ is an eigenpair of $B$ so $$\tag{1} Bx=\lambda x \iff (S+W^TW)^{-1}W^TWx=\lambda x. $$ This gives $W^TWx=\lambda(S+W^TW)x$ and by pre-multiplying with $x^T$ we get $$\tag{2} (1-\lambda)x^TW^TWx=\lambda x^TSx. $$

The only interesting case is when $\lambda>0$ (otherwise, there's nothing to prove). This implies that $Wx\neq 0$. Therefore, we have $x^TW^TWx>0$. Since we also have $x^TSx>0$, putting these facts together in (2), we get that $(1-\lambda)>0$ and hence $\lambda<1$.

Answer 2

Assume $W$ is full rank, then $W$ has a $QR$ factorization, i.e. $W = QR$ where $Q$ has orthonormal column and $R$ is an invertible upper triangular matrix. Hence it follows \begin{align} A = QR(P\Sigma P^T+R^TR)^{-1}R^T Q^T = Q(R^{-T}P\Sigma P^T R^{-1}+I)^{-1}Q^T \end{align} which means \begin{align} \|A \mathbf{x}\|^2 = \mathbf{x}^TA^TA\mathbf{x} = \mathbf{x}^TQ(R^{-T}P\Sigma P^T R^{-1}+I)^{-2}Q^T\mathbf{x} \leq \mathbf{x}^TQQ^T\mathbf{x} = \|Q^T\mathbf{x}\|^2 \leq \|\mathbf{x}\|^2. \end{align} The rest is straightforward.