4

I was reading a paper about variance reduction techniques, where they want to create a valid correlation matrix of size $n \times n$, but with the same pairwise-correlation coefficient, therefore, every off-diagonal entries are set to the same number $\alpha$:

$$ R_n = (r_{ij}) =\begin{pmatrix} 1 & \alpha & \cdots & \alpha \\ \alpha & 1 & \cdots & \alpha \\ \vdots & \vdots & \ddots & \vdots \\ \alpha & \alpha & \cdots & 1 \end{pmatrix}$$

Then, they say that this matrix must be positive-definite to be a valid correlation matrix which I understand perfeclty, but they say that this matrix is therefore constrained by the following relation:

$$0 \leq \sum_{i=1}^{n} \sum_{j=1}^{n} r_{ij} \leq n^2 $$

This relation, however, is totally new for me and I couldn't find where it came from. So my question is: Is this relation correct? Is there some kind of proof for it? Any help would be greatly appreaciated.

PS: English is not my first language, so apologies for my grammar.

Gonzalo Nelis
  • 43
  • 3
  • Hint: The expression simplifies to $$\sum_{i=1}^n\sum_{j=1}^n r_{ij} = n(1-\alpha) + n^2\alpha = n^2(\alpha + (1-\alpha)/n).$$This reduces the relation to $$0 \le \alpha + (1-\alpha)/n \le 1.$$ – whuber Feb 16 '18 at 19:21

1 Answers1

3

The matrix will be positive semi-definite if and only if $-1/(n-1) \le \alpha \le 1$, as shown in answers at Bound for the correlation of three random variables .

The upper bound of $n^2$ in $0 \leq \sum_{i=1}^{n} \sum_{j=1}^{n} r_{ij} \leq n^2 $ is achieved using $\alpha = 1.$

The lower bound of $0$ is achieved using $\alpha = -1/(n-1)$, because there are $n(n-1)$ occurrences of $\alpha$ in the double sum, together with n occurrences of $1$ (the diagonal elements). Therefore the double sum = $n(n-1)*(-1)/(n-1) + n*1 = 0$.

So what you state from the paper is consistent with the link I provided.

Mark L. Stone
  • 12,546
  • 1
  • 31
  • 51
  • Thank you!. I realized the relation holds true, but I have one more question: Is there some proof that the positive semi-definite property implies that relation?. In the link they get the lower-bound but only using the fact that the variance of the sum of random vectors must be positive. In another answer they get the same bound but they only use the expression for the eigenvalues (which is clearer for me since that property is expected for a positive definite matrix). So my guess is that relation comes from the positive variance property only, am I correct? – Gonzalo Nelis Feb 16 '18 at 20:12
  • As seen in the answers, there are multiple ways to determine the "relations". Non-negative variance, non-negative eigenvalues, it's all related. There is a consistency to math. – Mark L. Stone Feb 16 '18 at 20:22
  • That's what I thought, but since the paper did not provide any other clarification, I thought that there was a more explicit way to get that relation. Thanks! – Gonzalo Nelis Feb 16 '18 at 20:25