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.
Best Answer
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.