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?



Maximal eigenvalue of a correlation matrix with some entries fixed as zeros
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](https://arxiv.org/pdf/math/9312214.pdf).


