The following problem is motivated by one of my research problems.

Let

$\Sigma$ be an $n \times n$ correlation matrix whose least eigenvalue is denoted by $\lambda$.

$\Sigma_i'$ be an $(n-1) \times (n-1)$ submatrix of $\Sigma$ obtained by eliminating the $i$-th row and $i$-th column and whose least eigenvalue is denoted by $\lambda_i'$.

Find an upper bound on the gap $$\Delta := \min_{i \in \{1,\dots,n\}}(\lambda_i' - \lambda)$$

**Empirical Observations:**

Empirically, I am making some observations about $\Delta$:

$\Delta \leq $ the mean of the absolute values of all off-diagonal entries of $\Sigma$.

$\Delta \leq \frac{||C_{j}||}{n-1} \leq \frac{||C_{j}||_1}{n-1}$ for all $j \in \{1\dots,n\}$, where $C_j$ denotes a column vector of $\Sigma$ including all off-diagonal entries.

Note that the bound in point 2 is strictly tighter than the one in point 1.

Furthermore, if the weights in the eigenvector corresponding to the least eigenvalue of $\Sigma$ are of the same sign (+ve or -ve), then the above observations are true even for the signed entries of $\Sigma$, i.e.,

- $\Delta \leq -\alpha$, where $\alpha$ denotes the mean of the values of all off-diagonal entries of $\Sigma$.
- $\Delta \leq -\frac{\sum_{i=1,i \neq j}^{n}c_{ij}}{n-1}$ for all $j \in \{1,\dots,n\}$, where $c_{ij}$ denotes the entry in $i$-th row and $j$-th column in $\Sigma$.

**EDIT: More empirical observations**

3) For a given set $S$ of $k$ variables with correlation matrix $\Sigma$ of size $k \times k$, $\Delta \leq \frac{1}{k-1}$. In fact, $\Delta$ turns out to be $\frac{1}{k-1}$ in the following two cases:

i) When all the off-diagonal entries of $\Sigma$ are $\frac{-1}{k-1}$. In other words, the $k$ variables of set $S$ would appear to be a negative clique in a 'correlation graph' (a graph where each vertex represents a variable and the weight of an edge between $v_1$ and $v_2$ is given by $corr(v_1,v_2)$) with each edge weight being $\frac{-1}{k-1}$. OR

ii) When all the off-diagonal entries are of magnitude $\frac{1}{k-1}$, and set $S$ can be partitioned into two negative cliques $S_1$ and $S_2$ such that all the cross edges between $S_1$ and $S_2$ are positive.

**END OF EDIT**

The negative sign in both equations suggests that negative correlations promote stronger $\Delta$, which is strongly evident empirically. However, theoretically I have only managed to get looser upper bounds so far. Specifically, the following is what I have at the moment:

$\Delta \leq ||C_j||\leq ||C_j||_1$ for all $j \in \{1,\dots,n\}$, where $C_j$ is same as above.

There exists $j \in \{1,\dots,n\}$, such that $\Delta \leq \frac{||C_{j}||}{\sqrt{n-1}}$, where $C_j$ is same as above.

Any improvements to this, or, alternatively, counterexamples to empirical observations are most welcome and **will be acknowledged in my research**. In particular, if anyone can prove this last bullet 2 for all columns, that would be great. Thanks!