0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.