Let $\lfloor x\rfloor$ be the floor function.
QUESTION: Does the determinant
$$D_p=\det\left[\left\lfloor\frac{i^2+j^2}p\right\rfloor\right]_{1\le i,j\le(p-1)/2}$$ vanish for each prime $p>7$ with $p\equiv3\pmod4$?
My comptation suggests that the answer should be positive. Any ideas?
Let $p$ be large enough. Then there are two pairs of consecutive squares $a$, $a+1$ and $b$, $b+1$ modulo $p$ (otherwise the parities of sqiares modulo $p$ cannot alternate more than constant times, but among them there are $1,4,9,16,\dots$). Since $-(a+1)$ is not a square, the difference between the rows corresponding to $a$ and $a+1$ has all its entries equal (namely, if $i^2\equiv a$ and $j^2\equiv b$, this common value is $\frac{i^2-j^2+1}p$). The same holds for the rows corresponding to $b$ and $b+1$. Therefore, these four (or three, if $a+1=b$ or vice versa) rows are linearly dependent.
Small values of $p$ can be checked manually. The above arguments, however, may also be relevant, if such two pairs exist.
[ADDENDUM] THis addresses the generalization suggested by @KConrad, on the values of $D_n$ for odd $N\geq 3$. Sorry for being sketchy.
If $n$ is divisible by at least two distinct primes, then any square $\mod n$ coprime with $n$ appears at least twice among the $i^2$; the difference of such two rows is a constant row again. Hence, in this case $D_n=0$. (But what if we compose such matrix of representatives of all distinct squares modulo $n$???)
If $n=p^k$ with $p\geq 7$ and $k\geq 2$, then the rows for $i=p^{k-1}$, $i=2p^{k-1}$, and $i=3p^{k-1}$ are dependent for the same reason; act similarly for $3^k$ and $5^k$ with $k\geq 4$.
Essentially, the remaining cases are $p\equiv1\pmod 4$, and they seem to be a bit more interesting. Here is what I can say on them so far.
Arrange the rows in the increasing order according to $i^2\mod p$, and the columns --- in decreasing order according to $j^2\mod p$. Let $a$ and $b$ be the squares corresponding to the $i$th and the $(i+1)$st rows of the new matrix. Then the difference of these two rows is constant, apart from the column corresponding to $-b$ (whose entry is by $1$ larger). This shows that the rank of the matrix is at least $\frac{p-1}2-1$, and the degeneracy may happen if the first row can be expressed via the differences mentioned above.
I have some aditional thoughts on this case, but it still seems that this case is rare but should not appear only for $p=13$...
