Let $M$ be a symmetric matrix and $a \in \mathbb{R}$, $a \geq 0$. How do I go about showing that the set $$C = \left\{ \lambda_{\min}(M) \geq a : M \, \text{symmetric} \right\}$$ is a convex set?
If we restrict ourselves to positive definite matrices, I had the following idea:
$$\lambda_{\min}(M) \geq a \iff \lambda_{\min}(M)^{-1} \leq a^{-1} \iff \lambda_{\max}(M^{-1}) \leq a^{-1}$$
Now, since $\lambda_{\max}$ is a norm of symmetric matrices, the above set is a ball, hence convex. But I can't prove it for general symmetric matrices, which aren't necessarily invertible. Any help is greatly appreciated.
Best Answer
This comes down to the fact that two choices are better than one. First recall: $\min_{\mathbf x_: \Vert \mathbf x\Vert_2=1}:\text{trace}\big(\mathbf x\mathbf x^T M\big)=\min_{\mathbf x_: \Vert \mathbf x\Vert_2=1}:\mathbf x^T M\mathbf x = \lambda_\min(M)$
Thus for arbitrary $M, M' \in C$ and $p \in [0,1]$ and $q:=1-p$
$\lambda_\min\big(pM +qM'\big)$
$= \min_{\mathbf x_: \Vert \mathbf x\Vert_2=1}:\text{trace}\Big(\mathbf x\mathbf x^T \big(pM +qM'\big)\Big)$
$=\min_{\mathbf x_: \Vert \mathbf x\Vert_2=1}:\Big\{\text{trace}\Big(\mathbf x\mathbf x^T \big(pM\big)\Big)+\text{trace}\Big(\mathbf x\mathbf x^T \big(qM'\big)\Big)\Big\}$
$=\min_{\mathbf x, \mathbf y: \Vert \mathbf x\Vert_2=1 \& \Vert \mathbf y\Vert_2=1 \&\mathbf x:=\mathbf y}: \Big\{\text{trace}\Big(\mathbf x\mathbf x^T \big(pM\big)\Big)+\text{trace}\Big(\mathbf y\mathbf y^T \big(qM'\big)\Big)\Big\}$
$\geq \min_{\mathbf x, \mathbf y: \Vert \mathbf x\Vert_2=1 \& \Vert \mathbf y\Vert_2=1 }: \Big\{\text{trace}\Big(\mathbf x\mathbf x^T \big(pM\big)\Big)+\text{trace}\Big(\mathbf y\mathbf y^T \big(qM'\big)\Big)\Big\}$
$= p\cdot \min_{\mathbf x:\Vert \mathbf x\Vert_2=1 }: \text{trace}\Big(\mathbf x\mathbf x^T M\Big)+q\cdot \min_{\mathbf y:\Vert \mathbf y\Vert_2=1 }:\text{trace}\Big(\mathbf y\mathbf y^T \big(M'\big)\Big)$
$\geq p\cdot a +q\cdot a$
$=a$
$\implies \big(pM +qM'\big) \in C$