Is there any intuition why the following matrix is positive semidefinite?

I have the following 8 by 8 square matrix, which is positive semidefinite: \begin{bmatrix}3&1&1&-1&1&-1&-1&-3\\1&3&-1&1&-1&1&-3&-1& \\ 1&-1&3&1&-1&-3&1&-1 \\ -1&1&1&3&-3&-1&-1&1 \\ 1&-1&-1&-3&3&1&1&-1 \\ -1&1&-3&-1&1&3&-1&1 \\ -1&-3&1&-1&1&-1&3&1 \\ -3&-1&-1&1&-1&1&1&3 \end{bmatrix}

I wonder if there is an intuitive argument why this matrix is positive semidefinite.

This matrix has some interesting properties:

1. It is symmetric, diagonal elements have the largest values, and antidiagonal have the smallest values.

2. The sum of each row and column is $0$.

3. I also notice it is symmetric in the sense that first column is the inverse of the last column, the second column is the inverse of the 7th column.

If it helps, I computed the eigenvalues, which are $0,0,0,0,0,8,8$ and $8$.

Solution 1:

If $A$ is the $4\times 4$ submatrix in the upper left corner and $J$ is the negative permutation matrix $$ J=\begin{bmatrix} &&&-1\\ &&-1&\\ &-1&&\\ -1&&& \end{bmatrix} $$ then the original matrix is $$ \begin{bmatrix} A & AJ\\ JA & JAJ \end{bmatrix}= \begin{bmatrix} I\\J\end{bmatrix}A \begin{bmatrix} I &J\end{bmatrix} $$ which is positive semidefinite if $A$ is. The positive semidefiniteness of $A$ follows e.g. from $$ A=2(I+J)+ee^T $$ where $e$ is the vector of all ones.

Solution 2:

Using the A.Γ.'s method, we can obtain the spectrum of $M=\begin{pmatrix}A&B\\B&A\end{pmatrix}$.

Note that $B=JA=AJ$, $J^2=I_4$, $AB=BA,Jee^T=ee^TJ$ and then $B^2=A^2$.

Thus $\det(M-\lambda I_8)=\det((A-\lambda I_4)^2-B^2)=\det(\lambda^2I_4-2\lambda A)=$

$\lambda^4\det(\lambda I_4-2A)$. Let $spectrum(A)=\{a,b,c,d\}$; then $spectrum(M)=\{0,0,0,0,2a,2b,2c,2d\}$.

Since $J^2=I_4,tr(J)=0$, we deduce $spectrum(2(I_4+J))=\{4,4,0,0\}$.

Since $rank(ee^T)=1,tr(ee^T)=4$, we deduce $spectrum(ee^T)=\{0,0,0,4\}$.

Since $2(I_4+J)$ and $ee^T$ commute, $spectrum(A)=\{4,4,4,0\}$ or $\{8,4,0,0\}$. This is the first option that is correct because the $3\times 3$ submatrix of $A$ in the upper left corner has a strictly dominant diagonal and, consequently, $rank(A)\geq 3$.