Is it possible to determine the given matrix is positive semidefinite under these conditions?

Question

Suppose I have a $2^n$ by $2^n$ symmetric matrix M. I know the following facts are true about $M$.

1. The diagonal of M is $n+1$, which is strictly larger than any other non-diagonal entry.

2. The sum of each row of the matrix M is exactly $2^n$

3. The value of non-diagonal entry cannot be smaller than $-n+1$

4. Each row contains the same elements (but the order is different so that $M$ is symmetric)

I really hope to conclude $M$ is positive semidefinite, but I have to admit this may not be true. I know the fact that if each diagonal entry is greater than the sum of the absolute values of all other entries in the corresponding row, $M$ would be positive definite. However, we cannot use here because of fact 2. On the other hand, fact 2 implies $M$ has eigenvector 1 with eigenvalue $2^n$ and there cannot be too many negative entries in $M$. I wonder if these conditions can be sufficient for me to draw such a conclusion.

Courant fischer theorem seems helpful here since we can express the smallest eigenvalue as $\min_{v \perp 1} \frac{v^{T}Mv}{v^{T}v}$

Answer 1

The hypoteses given on $M$ don't allow to conclude that $M$ is positive semidefinite. The following is a counterexample for $n=3$. Define:

$$A:=\begin{bmatrix} 4& -2& -2& -2\\ -2& 4& -2& -2\\ -2& -2& 4& -2\\ -2& -2& -2& 4\\ \end{bmatrix} \qquad B:=\begin{bmatrix} 3 & 3 & 2 & 2\\ 3 & 3 & 2 & 2\\ 2 & 2 & 3 & 3\\ 2 & 2 & 3 & 3\\ \end{bmatrix} \qquad M:=\begin{bmatrix}A & B\\B& A\end{bmatrix} $$ For $x=(1,1,1,1,-1,-1,-1,-1)_T$,we have $Mx=-12x$, showing $M$ has at least one negative eigenvalue and therefore is not positive semidefinite. Similar counterexamples can be built for $n> 3$.