Suppose that positive semi-definite matrix $M$ satisfies the following on the $n$-hypercube:
\begin{align}
v ^\top M v \ge \|v\|^2 && \forall v\in\{-1,0,1\}^n
\end{align}
Is it possible that the matrix is singular $\lambda_{min}(M)=0$? Otherwise, can we prove for some $\epsilon>0$, that any such matrix would have $\lambda_{min}(M)\ge \epsilon$?
update: thanks to response by @JoshB I slightly modified the constraint to $\{-1,0,1\}^n$ rather than hypercube only$\{-1,1\}^n$.
I have the following sketch of proof for why $\epsilon = 1/n$ works. Is the argument correct?
For arbitrary unit vector $u\in R^n, \|u\|=1$, define \begin{align} v := \frac{1}{\sqrt{n}}(sgn(u_i))_{i\le n} && w_i=sgn(v_i) e_i \text{ for } i=1,\dots,n \end{align} where $e_i$ is the $i$th basis and $sgn$ is the sign. Put \begin{align} S:=\{v\}\cup \{w_i: v_i\neq 0\} \end{align} and consider that $u$ is in the convex hull $u\in Conv(S)$. So we can argue that $v$ and $u$ are closer in angle than $u$ to any $w_i\in S$: $\langle u,v\rangle \ge \langle u, w_1\rangle = 1/\sqrt{n}$. By invoking $v^\top M v \ge \|v\|^2=1$, we can argue that $u^\top M u \ge v^\top M v \langle u,w_1\rangle^2 \ge (1/\sqrt{n})^2=1/n$. Since $u$ was chosen arbitrarily, this implies that $\lambda_{min}(M)\ge 1/n$.
It is absolutely possible for $M$ to be singular.
Take $n=2$ and the matrix
$$ M=\begin{pmatrix} 1 & 0 \\ 0 & 0\end{pmatrix} $$
The act of multiplying any $v$ by $M$ only extracts the first entry of $v$ and sets the second entry to 0, so
$$ M\begin{pmatrix} a \\ b\end{pmatrix}=\begin{pmatrix} a \\ 0\end{pmatrix} $$
As such, if we have if $v=(a\;\;b)^T$, then
$$v^TMv=a^2$$
For the restriction of $v$ as you have described, this tells us that $v^TMv=1$ for any choice of $v$, and $M$ is singular.