Concavity of smallest positive eigenvalue of a semidefinite matrix

Question

Let $A\in\mathbb{R}^{d\times d}$ be positive semidefinite with rank $n<d$. Hence $A$ is not positive definite. Is the function $$ A \mapsto \lambda^{+}_{\text{min}}(A)$$ concave? Here $\lambda^{+}_{\text{min}}(A)$ denotes the smallest positive eigenvalue of $A$.

Answer 1

Denote the set of all rank-$n$ positive semidefinite matrices by $\mathcal P_n$. The answer to your question is “yes” on each convex subset of $\mathcal P_n$.

We first remark that $\mathcal P_n$ is not convex. In particular, given two rank-$n$ PSD matrices $A$ and $B$, the matrices lying on the line segment $[A,B]=\{(1-t)A+tB:0\leq t\leq 1\}$ can have ranks greater than $n$.

However, if all matrices in $[A,B]$ have the same rank $n$, then $A,B$ and $(1-t)A+tB$ have the same nullity (namely, $d-n$). Since $$ \ker\left((1-t)A+tB\right) =\ker(A)\cap\ker(B)\tag{1} $$ when $0<t<1$, we must have $\ker(A)=\ker(B)=\ker\left((1-t)A+tB\right)$. Conversely, if $\ker(A)=\ker(B)$, $(1)$ shows that all matrices on $[A,B]$ share the same null space and the same range.

It follows that if we define an equivalence relation on $\mathcal P_n$ by $A\sim B$ if and only if $\ker(A)=\ker(B)$, the equivalence classes are precisely the maximal convex subsets of $\mathcal P_n$. Let $A\sim B$ and $V=\ker(A)^\perp$. For any $t\in[0,1]$, let $C=(1-t)A+tBx$. Then \begin{aligned} \lambda_\min^+(C) &=\min_{x\perp\ker(C),\,\|x\|=1}x^TCx\\ &=\min_{x\in V,\,\|x\|=1}x^TCx\\ &=\min_{x\in V,\,\|x\|=1}x^T\left[(1-t)A+tB\right]x\\ &\ge\min_{x\in V,\,\|x\|=1}(1-t)x^TAx +\min_{x\in V,\,\|x\|=1}tx^TBx\\ &=\min_{x\perp\ker(A),\,\|x\|=1}(1-t)x^TAx +\min_{x\perp\ker(B),\,\|x\|=1}tx^TBx\\ &=(1-t)\lambda_\min^+(A)+t\lambda_\min^+(B).\\ \end{aligned} Hence $\lambda_\min^+$ is concave on such an equivalence class.

Answer 2

The function is concave over the space of symmetric matrices. The formulation of @copper.hat shows that the function is concave because it is the minimum of concave (even linear) functions.