Upper bound on maximum eigenvalue

Question

Let $A,B\in\mathbb{R}^{n\times n}$. What is an upper bound $M$ such that \begin{equation} \lambda_{\rm max}\left((A+B)^{\rm T}(A+B)\right)\leq M? \end{equation}

Answer 1

You can take $M =(\sigma_A+\sigma_B)^2$, where $\sigma_A$ and $\sigma_B$ are the largest singular values of $A$ and $B$, respectively. This bound is tight when $A$ and $B$ can be mutually diagonalized.

This bound can be proven using the fact that, for any vector $x$, $$\|Ax\| \leq \sigma_A \|x\|,$$ and likewise for $B$. Then if $v$ is the eigenvector of $(A+B)^T(A+B)$ with largest eigenvalue $\lambda$, $$\lambda = \|\lambda v\| = \|(A+B)^T(A+B)v\| \leq \|A^TAv\| + \|A^TBv\| + \|B^TAv\| + \|B^TBv\|\leq \sigma_A^2 + 2\sigma_A\sigma_B + \sigma_B^2$$