Convexity of λ_max and the spectral norm on symmetric matrices

Idea. A pointwise supremum of convex functions is convex, and linear functions are convex. The Rayleigh representation turns the largest eigenvalue into such a supremum.

Step 1: Rayleigh formula. Let $S=Q\Lambda Q^T$ with $\Lambda=\operatorname{diag}(\lambda_1\ge\dots\ge\lambda_n)$. For $|x|=1$ put $y=Q^Tx$ (also a unit vector). Then
$$x^TSx=\sum_i\lambda_iy_i^2\le\lambda_1\sum_iy_i^2=\lambda_1,$$
with equality for $x=Qe_1$. Hence $\lambda_{\max}(S)=\max_{|x|=1}x^TSx$.

Step 2: convexity. For each fixed unit vector $x$, the function $\ell_x:S\mapsto x^TSx$ is linear in $S$. For $S,T\in\mathrm{Sym}_n$ and $t\in[0,1]$,
$$x^T\bigl(tS+(1-t)T\bigr)x=t\,x^TSx+(1-t)\,x^TTx\le t\lambda_{\max}(S)+(1-t)\lambda_{\max}(T).$$
Taking the maximum over $x$ on the left gives $\lambda_{\max}(tS+(1-t)T)\le t\lambda_{\max}(S)+(1-t)\lambda_{\max}(T)$.

Step 3: the norm. Note $-\lambda_{\min}(S)=\lambda_{\max}(-S)$, so
$$\|S\|=\max_i|\lambda_i(S)|=\max\bigl(\lambda_{\max}(S),\lambda_{\max}(-S)\bigr)=\max_{|x|=1}|x^TSx|.$$
- *Definiteness:* $\|S\|=0$ forces all eigenvalues to vanish, hence $S=0$.
- *Homogeneity:* $\|cS\|=|c|\,\|S\|$ since the eigenvalues are multiplied by $c$.
- *Triangle inequality:* $|x^T(S+T)x|\le|x^TSx|+|x^TTx|\le\|S\|+\|T\|$ for every unit $x$; take the maximum over $x$.

Remark. $\lambda_{\max}$ itself is convex and positively homogeneous but *not* a norm: it is not symmetric ($\lambda_{\max}(-S)\ne\lambda_{\max}(S)$ in general) and it can be negative. The norm above equals the operator norm $\sup_{|x|=1}|Sx|$ for symmetric $S$.

Lesson. A supremum of linear functionals is convex; this is the standard way to prove convexity of spectral quantities.