Linear Algebra – Maximal Eigenvalue of a Correlation Matrix with Fixed Zeros

eigenvalueslinear algebramatricesoc.optimization-and-controlspectral-radius

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?

Best Answer

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$.

Related Question