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!
