I have a special matrix $X \in \mathbb R^{2n \times 2n}$ whose all elements are non-negative.
The matrix is in a block structure: $X = \begin{pmatrix} X^1 & X^2 \\ X^3 & X^4 \end{pmatrix}$ where $X^1 = \mathrm{diag}(x_1, x_2, \ldots,x_n)$ for some $x \in \mathbb{R}^n_+$ and $X^4 = \mathrm{diag}(y_1, y_2,\ldots,y_n)$ for some $y \in \mathbb{R}^{n}_+$, e.g., the diagonal blocks are diagonal matrices. Moroever, $X^2$ is a matrix whose $i$-th row sums to $x_i$, and $j$-th column sums to $y_j$. Similarly, $i$-th row of $X^3$ sums to $y_i$ and $j$-th column of $X^3$ sums to $x_j$.
An example matrix for $n= 2$ would be: $\begin{pmatrix} 0.3061 & 0 & 0 & 0.3061 \\
0 & 0.6939 & 0.0826 & 0.6112 \\
0 & 0.0826 & 0.0826 & 0 \\
0.3061 & 0.6112 & 0 & 0.9174 \end{pmatrix}.$
I would like to show that such an $X$ (in general, not this example above) is positive semi-definite. I don't know if it helps, but I have $\sum_i x_i = 1, \sum_j y_j = 1$.
Best Answer
One method is to use Gershgorin Circle theorem.
Thm: For a symmetric $m\times m$ matrix $A$ with diagonal elements $A_{ii}$, $i = 1,...,m$ the eigenvalues of $A$ lie in the union of sets $[D_{ii}-R_i, D_{ii}+R_i]$ where $R_i = \sum_{i\neq j}|A_{ij}|$.
So, if you can guarantee that for all rows $i$, the quantity $R_i \leq D_{ii}$, then you can ensure that $$\text{eigenvalues}(A) \geq \min_{i=1,...,m} D_{ii}-R_i \geq 0$$ hence, the matrix is PSD!