Off-diagonal range for guaranteed positive definiteness? Consider the problem of randomly generating a $p \times p$ covariance matrix $\Sigma$ with the diagonal entries constrained to be 1, and the off-diagonal entries $\Sigma_{ij}=\Sigma_{ji} \sim Unif[-a,a]$.  What is the maximum value of $a$, as a function of $p$, such that $\Sigma$ is positive definite with probability 1?
 A: The maximum is $1/(p-1)$.
To see this, note first that the eigenvalues of the matrix with all off-diagonal entries equal to a constant $x$ are $1-x$ (with multiplicity $p-1$) and $1+(p-1)x$.  When $x \lt -1/(p-1)$, the smallest eigenvalue will therefore be negative implying the matrix is not positive definite.  Because the smallest eigenvalue is a continuous function of the entries, we can find a positive $\epsilon$ such that when all off-diagonal entries are in the interval $[x, x+\epsilon]$ (but no longer all equal to each other), the smallest eigenvalue remains negative.
Now suppose $a \gt 1/(p-1)$.  Setting $x=-a$, choose an $\epsilon$ as just described and if necessary make it even smaller, but still positive, to assure that $a - \epsilon \gt 1/(p-1)$.  Assuming the off-diagonal entries are independently generated, the probability that all entries lie in the interval $[-a, -a+\epsilon]$ equals $(\epsilon / (2a))^{p(p-1)/2} \gt 0$, showing that the matrix has a positive probability of not being positive definite.
This has established $1/(p-1)$ as an upper bound for $a$.  We need to show that it suffices.  Consider an arbitrary symmetric $p$ by $p$ matrix $(a_{ij})$ with unit diagonal and all entries in size less than $1/p$.  By a suitable induction on $p$, and by virtue of Sylvester's Criterion, it suffices to show this matrix has positive determinant.  Row-reduction using the first row reduces this question to considering the sign of a $p-1$ by $p-1$ determinant with entries $(a_{ij} / (1 + a_{1i})$.  Because $-1/p \lt a_{1i} \lt 1/p$, these clearly are less than $1/(p-1)$ in absolute value, so we are done by induction.  (The base case $p=2$ is trivial.)
