# Check if a large matrix containing positive definite block diagonal matrices is positive definite.

I have a large matrix in the following form: $$M=\begin{bmatrix} A_{11}& {A}_{12}&...&A_{1N}\\A_{21}& {A}_{22}&...&A_{2N}\\...&...&...&...\\A_{N1}& {A}_{N2}&...&A_{NN} \end{bmatrix}$$,

where $$A_{ij}=A_{ji}$$, and each $$A_{ij}$$ is a diagonal block matrix of the form: $$A_{ij}=\begin{bmatrix} a_{11}& 0&...&0\\0& {a}_{22}&...&0\\...&...&...&...\\0& 0&...&a_{NN} \end{bmatrix}$$.

All the diagonal entries of $$A_{ij}$$ are positive, and thus each $$A_{ij}$$ is a positive definite.

Now, I want to check if the matrix $$M$$ is positive definite. I think with its special form, there should be a practical way to check its definiteness. I have try the followings:

Diagonal dominant: The matrix $$M$$ also has an interesting characteristic. Let $$m_{ij}$$ be the entries of $$M$$. The sum of the off-diagonal entries on each row is exactly $$(N-1)$$ times the diagonal entries. So if $$N>3$$ the matrix is not diagonal dominant.

Cholesky decomposition: I have tried to check the square roots but the number of elements inside the square root increases as $$i,j$$ increase so it becomes impractical.

So, I want to ask if there is any efficient way to check if $$M$$ is positive definite. Thank you.

I assume that $$M$$ is an $$N \times N$$ block matrix and that each block is $$N \times N$$, as you have indicated (but not stated explicitly) in your post.
Any matrix with diagonal blocks (assuming the blocks have the same size) can be converted to a block-diagonal matrix. In particular, suppose that $$a_{ijk}$$ denotes the $$k$$th diagonal entry of the block $$A_{ij}$$, so that $$A_{ij} = \pmatrix{a_{ij1} \\ & \ddots \\ && a_{ijN}}.$$ There exists a permutation matrix $$P$$ such that $$PMP^T = \pmatrix{B_1\\ & \ddots \\ && B_N},$$ where $$B_k = \pmatrix{ a_{11k} & \cdots & a_{1Nk}\\ \vdots & \ddots & \vdots \\ a_{N1k} & \cdots & a_{NNk}}.$$ It follows that $$M$$ is positive definite if and only if every $$N \times N$$ matrix $$B_k$$ is positive definite.
Where an ordinary Cholesky decomposition on the $$N^2 \times N^2$$ matrix would have complexity $$O((N^2)^3) = O(N^6)$$, attempting a separate Cholesky decomposition of each $$B_k$$ has complexity $$N \cdot O(N^3) = O(N^4)$$.
If you're interested in what the matrix $$P$$ looks like, it can be written as $$P = \sum_{i,j = 1}^N (e_{i} \otimes e_j)(e_j \otimes e_i)^T$$ where $$e_i$$ denotes the $$i$$th canonical basis vector (the $$i$$th column of the identity matrix), and $$\otimes$$ denotes the Kronecker product.