$\newcommand{\Re}{\mathbb{R}}$I m looking for sufficient conditions that may guarantee positive semidefiniteness (PSD) of a block matrix
$$A = \begin{bmatrix} A_{1,1} & \cdots & A_{1,n} \\ \vdots & \ddots & \vdots \\ A_{n,1} & \cdots & A_{n,n}\end{bmatrix}$$
with consistent block dimensions, $A_{i,j} \in \Re^{d_i \times d_j}$.
I'm aware of the sufficient condition that if $A$ is block diagonally dominant (BDD) this implies PSD [1], but the BDD condition turns to be too restrictive for my case of interest (my block matrices are not BDD, yet they are PSD).
I looked for some alternative but couldn't find anything in the literature. Also I'm not interested in Schur-based exact conditions, but simpler conditions that work well often (but not necessarily always).
In looking at the block diagonally dominant (BDD) condition [1] I came up with a proposal which I briefly describe here.
First, consider the traditional BDD condition [1] from the following perspective:
Build the $n\times n$ matrix $M \in \Re_+^{n\times n}$ given as $$M=[m_{ij}]_{i,j=1}^n, \quad m_{ij} = \begin{cases} \inf_{x} \frac{||A_{ij}x||_2}{||x||_2} \text{ if } i=j\\ \sup_{x} \frac{||A_{ij}x||_2}{||x||_2} \text{ if } i\neq j \end{cases}$$
Considering this condensed matrix $M$, the traditional BDD condition [1] on $A$ is equivalent to the condition that $M$ is Diagonally Dominant (DD). Thus, we can state $M$ is DD $\implies$ $A$ is PSD.
Conjecture
Now, my first hunch was that maybe the relationship $M$ is PSD $\implies$ $A$ is PSD would stand. However, after some extensive numerical testing, I've found cases where my conjecture is contradicted. That is, $M$ is PSD $\nRightarrow$ $A$ is PSD.
A contradiction example
For completeness, I'm including here a simple numerical example where the conjecture fails. Consider the 3x3 block-matrix with block-dimension 2x2 (also available for download here): $$ A = \left[\begin{array}{cc|cc|cc} 1.0 & 0.6 & -0.3 & 0.4 & 0.2 & -0.2\\ 0.6 & 1.6 & 0.5 & -0.6 & -0.4 & 0.4\\ \hline -0.3 & 0.5 & 78.6 & 79.8 & 0.1 & -0.1\\ 0.4 & -0.6 & 79.8 & 84.2 & -0.3 & 0.2\\ \hline 0.2 & -0.4 & 0.1 & -0.3 & 3.5 & 0.5\\ -0.2 & 0.4 & -0.1 & 0.2 & 0.5 & 3.3 \end{array}\right]$$ This has the following eigenvalues $eig(A)=\{-0.0372 , 1.6458 , 2.3249 ,3.1036 , 3.9136 , 161.2494\}$, so it's indefinite. The condensed matrix M as defined above is $$ M = \left[\begin{array}{ccc} 0.6292 & 0.9271 & 0.6325\\ 0.9271 & 1.5509 & 0.3864\\ 0.6325 & 0.3864 & 2.8901 \end{array}\right]$$ with eigenvalues $eig(M)=\{0.0129, 1.7594, 3.2978\}$, so it's positive definite, contradicting the conjecture above.
It's obvious that the simple proposed relation does not fulfill the PSD test I was looking for. Still, for this and other cases I found so far, even though $A$ was not PSD, it wasn't too far (the negative eigenvalue was small). So I still wonder if the proposed relationship $M$ is PSD $\implies$ $A$ is PSD might stand under additional constraints.
I would appreciate if anyone has anything to contribute on this. I am assuming some properties on $A$ to simplify the problem, so $A$ can be considered symmetric, and the blocks all square with $d_i=d_j=d$.
Analysis using block Cholesky decomposition
So far, I tried to look at this using the block variant of Cholesky decomposition as a PSD test, so that if each diagonal sub-block in the block Cholesky decomposition is PSD, then the block matrix is PSD.
Special case: 2x2 block-matrix
Using the sufficient conditions from Cholesky decomposition, the 2x2 block case fulfills the proposed relationship. Consider the 2x2 block Cholesky decomposition
$$A = LDL^\top = \begin{bmatrix} I & 0 \\ L_{21} & I \end{bmatrix} \begin{bmatrix} D_1 & 0 \\ 0 & D_2 \end{bmatrix} \begin{bmatrix} I & L_{21}^\top \\ 0 & I \end{bmatrix}$$
By the properties of the Cholesky decomposition, {$D_1$ is PSD, $D_2$ is PSD} $\implies$ $A$ is PSD. Since $D_1 = A_{11}$ and $D_2 = A_{22} - A_{21} A_{11}^\top A_{12}$, it follows that: $$ m_{11} \geq 0 \implies D_1 \text{ is PSD} $$ $$ m_{11} - m_{21} m_{22}^{-1} m_{12} \geq 0 \implies D_2 \text{ is PSD} $$ The left hand inequality in the second expression can be written as $m_{11}m_{22} \geq m_{12} m_{21} = det(M) \geq 0$.
The sufficient conditions above for $A$ is PSD are clearly fulfilled if $M$ is PSD (just consider Sylvester criterion).
#
General case: nxn block matrix
As soon as we go further than 2x2, the expressions from Cholesky decomposition become more complex, and just forcing $M$ is PSD does not seem enough to provide sufficient conditions for PSD of $A$.
PD: I posted this same question some time ago in math.stackexchange, but didn't get any answer so far. So I was wondering if this might be a more appropriate forum to pose the question.
[1] Feingold, D. G., & Varga, R. S. (1962). Block diagonally dominant matrices and generalizations of the Gerschgorin circle theorem. Pacific J. Math, 12(4), 1241-1250.
