Minimal Covariance of random variables. Now I was wondering if you have some bernulli random variables $X_1, X_2, X_3,\dots X_n$.
That distribute on some $1/2$ probability (Ber($1/2$)), and all of their Cov are equal, meaning that $\text{Cov}(X_i,X_j) = \text{Cov}(X_k, X_l)$ for every $i \neq j$, and every $k \neq l$.
I'm asked to find how small can the $\text{Cov}(X_i,X_j)$  be for $i \neq j$, give an example for when the minimum is received.
So I started by saying that $\text{Cov}(X_i,X_j) = \mathbb E [X_iX_j] - \mathbb E[X_i]\cdot \mathbb E[X_j] = \mathbb E[X_iX_j] - 0.25$
Basically I need now to minimize $\mathbb E [X_iX_j] $ but I'm having a hard time understanding what is exactly multiplying bernulli random variables.
Thanks for any help!
 A: This question need other expert in linear algebra to solve it. Here I just provide some examples in case of small $n$. Let $c$ be the common covariance to be minimized.
When $n = 2$, the covariance matrix of $\begin{bmatrix} X_1 \\ X_2\end{bmatrix}$ is
$\begin{bmatrix} \displaystyle \frac {1} {4} & c \\ 
c & \displaystyle \frac {1} {4}\end{bmatrix}$. 
The requirement of a matrix to be a valid covariance matrix is that it is positive semi-definite. Here I am lazy/ignorant and just use the Sylvestor's Criterion to check for positive definiteness. That means we just check for the leading principal minor being positive.
Obviously the first leading prinicipal minor $\displaystyle \frac {1} {4}$ is positive.
For the above case $n = 2$, the determinant is 
$ \displaystyle \frac {1} {16}(1 - 4c)(1 + 4c)$, so it is positive when $\displaystyle c \in \left(-\frac {1} {4}, \frac {1} {4}\right)$
You may check that the infimum $\displaystyle -\frac {1} {4}$ is attainable when $X_2 = 1 - X_1$, i.e. they are perfectly negatively correlated.
When $n = 3$, the determinant is 
$ \displaystyle \frac {1} {64}(1 - 4c)^2(1 + 8c)$, so it is positive when $\displaystyle c > -\frac {1} {8}$. Combining with the previous constraint, we have $\displaystyle c \in \left(-\frac {1} {8}, \frac {1} {4}\right)$
When $n = 4$,  the determinant is 
$ \displaystyle \frac {1} {256}(1 - 4c)^3(1 + 12c)$, so it is positive when $\displaystyle c \in \left(-\frac {1} {12}, \frac {1} {4}\right)$. 
So with these results, it is tempting to guess the determinant for general $n$ is
$$\frac {1} {4^n}(1 - 4c)^{n-1}(1 + 4(n-1)c)$$
and the infimum of $c$ is $\displaystyle -\frac {1} {4(n-1)}$. You may try to prove it via, say elementary row/column reduction and factorize it, or by induction.
P.S. For $n = 3$ case the infimum seems not attainable. Need further checking.
A: Let's say that $Cov(X_i, X_j) = c$. As all of the diagonal elements are $1/4$, the covariance matrix $C$ can be written as the sum of two matrices:
$$C = (1/4 - c) I_n - c J_n$$
where $J_n$ is the all ones matrix. Notice that the all ones vector $\vec{1}$ is the eigenvector of $C$ with the smallest eigenvalue (why?), and since we know that
$$\min_{\|v\| = 1} \vec{v}^T C \vec{v} = \lambda_{min}(C)$$
and that a matrix is positive semidefinite if and only if all of its eigenvalues are non-negative, we must have that $\lambda_{min}(C) = 1/4 - c - cn \geq 0$. Rearranging, we see that $c \geq (4 (1-n))^{-1}$, which confirms BGM's observations.
