# Positive definiteness of a correlation matrix

With $n$ natural numbers 1, 2, ..., $n$, there are $N=n(n-1)/2$ unique pairs that are the 2-D indices for random variables $z_{ij}$ ($1 \le i < j \le n$). I have the correlation matrix $A$ of $z_{ij}$ that is defined as follows:

$cor(z_{i_1 j_1}, z_{i_2 j_2})=1$, if $i_1=i_2, j_1=j_2$;

$cor(z_{i_1 j_1}, z_{i_2 j_2})=\rho$, if $\{i_1,j_1\}∩\{i_2,j_2\}$ has cardinality 1;

$cor(z_{i_1 j_1}, z_{i_2 j_2})=0$, if $i_1\neq i_2, j_1\neq j_2$.

For example, with $n=5$, the correlation matrix $A$ for the $N=n(n-1)/2=10$ $z$-variables is of the following structure,

${\begin{array}{c} z_{12} \\ z_{13} \\ z_{14} \\ z_{15} \\ z_{23} \\ z_{24} \\ z_{25} \\ z_{34} \\ z_{35} \\ z_{45} \\ \end{array}} \left[{\begin{array}{ccccccccccc} 1 & \rho & \rho & \rho & \rho & \rho & \rho & 0 & 0 & 0 \\ \rho & 1 & \rho & \rho & \rho & 0 & 0 & \rho & \rho & 0 \\ \rho & \rho & 1 & \rho & 0 & \rho & 0 & \rho & 0 & \rho \\ \rho & \rho & \rho & 1 & 0 & 0 & \rho & 0 & \rho & \rho \\ \rho & \rho & 0 & 0 & 1 & \rho & \rho & \rho & \rho & 0 \\ \rho & 0 & \rho & 0 & \rho & 1 & \rho & \rho & 0 & \rho \\ \rho & 0 & 0 & \rho & \rho & \rho & 1 & 0 & \rho & \rho \\ 0 & \rho & \rho & 0 & \rho & \rho & 0 & 1 & \rho & \rho \\ 0 & \rho & 0 & \rho & \rho & 0 & \rho & \rho & 1 & \rho \\ 0 & 0 & \rho & \rho & 0 & \rho & \rho & \rho & \rho & 1\\ \end{array}}\right].$

I have two questions:

1) Is there a special name for this type of matrix?

2) For the few $n$ values I've played with, it seems that $A$ is non-negative definitive if $0 \le \rho \le 0.5$. Is there a way to prove that $A$ is not positive definitive when $0.5 < \rho \le 1$?

• @A.S. Certainly not! Nonsingular does not imply positive definite. Dec 1, 2015 at 23:29
• @A.S. How do you know $A_n$ is positive semidefinite? Dec 1, 2015 at 23:41
• But the point is that it is not a covariance matrix if $\rho > 1/2$. Dec 1, 2015 at 23:45

Consider $z_{13}, z_{14}, z_{23}, z_{24}$. Their covariance matrix is $$A = \pmatrix{1 & \rho & \rho & 0\cr \rho & 1 & 0 & \rho\cr \rho & 0 & 1 & \rho\cr 0 & \rho & \rho & 1\cr}$$ Its characteristic polynomial factors as $$(\lambda - 1)^2 (\lambda + 2 \rho - 1)(\lambda - 1 - 2 \rho)$$ so for this to be positive semidefinite we need $-1/2 \le \rho \le 1/2$. For any $n \ge 4$, this is a principal submatrix of $A$, so $-1/2 \le \rho \le 1/2$ is a necessary condition for $A$ to be positive semidefinite.
On the other hand, for $n=3$ there are only three variables $z_{12},z_{13},z_{23}$, and $$A = \pmatrix{1 & \rho & \rho\cr \rho & 1 & \rho \cr \rho & \rho & 1\cr}\ \text{or}\ \pmatrix{1 & \rho & 0\cr \rho & 1 & \rho \cr 0 & \rho & 1\cr}$$ (depending on the interpretation, as noted in the comments). The first is positive semidefinite for $-1/2 \le \rho \le 1$, the second for $-1/\sqrt{2} \le \rho \le 1/\sqrt{2}$.
I can also show that $A$ is positive semidefinite for $0 \le \rho \le 1/2$ (in the interpretation where the covariance is $\rho$ if $\{i_1,j_1\} \cap \{i_2,j_2\}$ has cardinality $1$). To do this it's enough to find a probability model for $\rho = 1/2$ where the variables $z_{ij}$ have these covariances, and then use the fact that the positive semidefinite matrices form a convex set. Such a model can be obtained as follows: let $B_i$ be iid random variables taking values $\pm 1$, each with probability $1/2$, and let $Z_{ij} = (B_i + B_j)/\sqrt{2}$.
• Thanks again for the beautiful proof! It remains moot to me whether $A$ is positive semidefinite for $-1/2 \le \rho < 0$. I'm not so sure if it makes sense to have negative $\rho$ values, but, for completeness, it would be nice to sort out this last part. Dec 2, 2015 at 18:56
• With a few matrices I've tried, it seems that $-0.5 \le \rho < 0$ is not sufficient to guarantee the positive semi-definiteness of $A$. How to rigorously prove this part? So $0 \le \rho \le 0.5$ is a sufficient and necessary condition. Dec 3, 2015 at 16:01
• If $0 \ge \rho \ge -1/(2n-4)$, the matrix will be diagonally dominant and therefore positive semidefinite. Dec 3, 2015 at 18:08
• On the other hand, the vector $\bf 1$ of all $1$'s is an eigenvector of $A$ with eigenvalue $1 + (2n-4) \rho$, so $A$ is not positive semidefinite if $\rho < -1/(2n-4)$. Thus the full condition is $-1/(2n-4) \le \rho \le 1/2$. Dec 3, 2015 at 18:17