Maximal eigenvalue of a correlation matrix with some entries fixed as zeros

Question

Let $A$ be real a positive semidefinite matrix of dimension $n$ and with $1$s on the diagonal. Those matrices are sometimes referred to as correlation matrices. From the positivity of the minors, we know that each matrix element $a_{ij}$ satisfies $-1 \leq a_{ij} \leq 1$. The problem is the following: considering that some fixed off-diagonal elements are zero, what is the maximal possible largest eigenvalue $\lambda_1$ of $A$?

Remark: since $\lambda_1(A) \leq \lambda_1(|A|)$, where $|A|$ is the entry-wise absolute value of $A$, we can restrict ourselves to $0\leq a_{ij} \leq 1$.

As an example, let’s take

$$ A= \begin{pmatrix} 1 & a_{12} & 0 & 0 \\ a_{12} & 1 & a_{23} & 0 \\ 0 & a_{23} & 1 & a_{34} \\ 0 & 0 & a_{34} & 1 \end{pmatrix}. $$

From numerical optimisation, I know that the maximal largest eigenvalue reachable with the constraint that $A$ is positive semidefinite is $2$. This is obtained e.g. by taking $a_{12}=a_{34}=1$ and $a_{23}=0$. Furthermore, if we did not have the PSD constraint, the maximum would always be reached at an extreme point (i.e., at some attribution of $0$ or $1$ to each entry and in this case, $1$ everywhere). My intuition is that this is still true for PSD matrices, i.e., it would be attained by a PSD $\{0,1\}$-matrix. Note that the only PSD $\{0,1\}$-matrices are block-diagonal matrices with blocks consisting of only ones (up to some permutation).

Is there a way to prove this, without using the explicit from of the eigenvalues, which can become very cumbersome for general matrices?

Answer 1

The answer to your question is positive, in every dimension:

Let $A=I_n+T$ be symmetric positive semi-definite, with ${\rm diag}T=(0,\ldots,0)$ and $T$ tridiagonal. Then the largest eigenvalue $\rho(A)$ is $\le2$.

The proof is actually quite simple. On the one hand, the spectrum of $A$ is that of $T$, shifted by $+1$. In particular $\rho(A)=1+\mu$ where $\mu$ is an eigenvalue of $T$. On the other hand, $T$ is conjugated to $-T$, namely $\sigma^{-1}T\sigma=-T$ where $\sigma={\rm diag}(1,-1,1,-1,\ldots,(-1)^{n+1})$ is an orthogonal symmetry. Thus the spectrum of $T$ is even. In particular $-\mu$ is an eigenvalue of $T$ and $1-\mu$ is an eigenvalue of $A$. Since $A$ is positive semi-definite, $1-\mu\ge0$, that is $\mu\le1$, which implies $\rho(A)\le2$.

Remark the Bang-bang phenomenon: an eigenvalue $\lambda$ achieves the maximal value $2$ if, and only if, another eigenvalue achieves the minimal value $0$.

Answer 2

The question can be solved by considering the Lovász number of a graph whose adjacency matrix has entries $0$ if $a_{ij} \neq 0$ and $1$ everywhere else. This is proven (up to a typo) in Section 33 here.