# 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$$.

• There is a result that a Hermitian matrix is positive semidefinite if and only if all its eigenvalues are nonnegative. Nov 16, 2019 at 1:30
• Hi I understand that. I guess another way to ask this question is whether there exist some results that can explain why the eigenvalues are all nonnegative? Nov 16, 2019 at 1:33
• If you reorder the rows and columns it becomes the Kronecker product of three $2\times2$ psd matrices. (I think: I have not checked every entry.) Nov 16, 2019 at 1:49
• Thank you for the Kronecker product idea! I just learnt this new concept but after rearranging some columns, I wasn't able to achieve the desired result. In addition, rearranging rows and columns would affect the positive definiteness of the matrix, if I remember correctly. Nov 16, 2019 at 2:22
• Aren't stochastic matrices nonnegative? Nov 16, 2019 at 11:33

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.

• Another way to see that $A$ is psd is to observe that its eigenvalues are real and in a circle centered at 3 with radius 3 (by Gershgorin) Nov 16, 2019 at 10:56
• @Lonidard This is a very nice observation.
– A.Γ.
Nov 16, 2019 at 17:00
• Sorry, I didn't realise that. I'll delete my comment. Nov 24, 2019 at 11:30

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$$.