Suppose $M$ is an $n \times n$ correlation matrix, with correlation $\rho_{i,j}$ between any pair of two random variables. What is the smallest possible average of the $\rho_{i,j}$ where $(i<j)$?
Or in another form what $M$ (class of $M$'s?) minimize
$$\frac{1}{m} \Sigma_{i<j} \, \rho_{i,j}$$
where $m = \frac{n(n-1)}{2}$.
Can this problem be reduced to this related question for constant correlation matricies?
The minimum possible average correlation is $-1/(n-1)$.
We may assume wlog the random variables all have variance $1$, so the correlations are covariances. The sum of all covariances (incuding the variances) of $n$ random variables is $$\sum_{i=1}^n \sum_{j=1}^n \text{Cov}(X_i, X_j) = \text{Cov}\left(\sum_i X_i, \sum_j X_j\right) = \text{Var}\left(\sum_i X_i\right) \ge 0$$ with equality iff $\sum_i X_i$ is almost surely constant. This can occur with an $n \times n$ covariance matrix having all diagonal elements $1$ and all off-diagonal elements $-1/(n-1)$. This is positive semidefinite because it has eigenvalues $0$ and $n/(n-1)$ (with multiplicity $n-1$).