Solved – Off-diagonal range for guaranteed positive definiteness

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.)