origmat
1 1 0 1 0
1 1 0 1 0
0 0 1 0 1
1 1 0 1 0
0 0 1 0 1
Given a covariance matrix with some covariances fixed to 0, is it possible to permute the rows and columns so that the matrix is block diagonal? In this post, we consider an automated method for answering this question.
March 20, 2025
Given a covariance matrix with some covariances fixed to 0, is it possible to permute the rows and columns so that the matrix is block diagonal? This question is important in Bayesian latent variable modeling and elsewhere, because it influences the prior distributions that we can use. To be specific, if our covariance matrix consists of unrestricted blocks, then the 0 entries don’t really matter. We can specify an inverse Wishart or LKJ or other prior on each block of the covariance matrix. On the other hand, if our covariance matrix does not consist of unrestricted blocks, then the prior distribution becomes complicated (e.g., Merkle et al. 2023). This is because the possible values of unrestricted covariances are influenced by the zero entries, along with the constraint that the entire covariance matrix is positive definite.
To make this more concrete, let’s consider the correlation matrix below.
The entries of 0 are fixed to 0, and the entries of 1 are free parameters. For most of us, it is not clear whether or not this is a block diagonal matrix. But if we reorder the rows and columns so that the first, second, and fourth come first, followed by the third and fifth, we obtain:
which is a block diagonal matrix. We now know we can use one prior distribution on the block in rows/columns one to three, and a separate prior distribution on the block in rows/columns four to five. In general, we want to automatically permute the rows and columns to block diagonal form where possible. This is because we can’t be sure that the matrix will be pre-specified in block diagonal form.
For a time, I wasn’t sure how to automate this. I could have coded something myself, but I was pretty sure that I would be re-inventing the wheel.
I found an answer in the graph theory concept of connectivity. In short, we treat each unrestricted entry of the covariance matrix as an undirected edge in a graph. We then search for the connected components of the graph. Each component is a block of the covariance matrix. We can then determine whether or not each block is unrestricted.
Functionality for doing this comes from the igraph package (Csárdi and Nepusz 2006; Csárdi et al. 2025). Below, we create a graph of our covariance matrix, where each free parameter is an undirected edge. The components()
function then finds blocks of the covariance matrix; in network language, these are the maximal connected components of the graph.
The membership
entry of the results shows that rows 1, 2, and 4 belong to one block, and rows 3 and 5 belong to the other block. After that, we see that the first block contains 3 variables and the second block contains 2 variables. We can reorder the covariance matrix using this membership information, via
Let’s consider a larger example with an
[[1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 1. 0. 0. 0. 1. 0. 0. 0.]
[0. 0. 0. 0. 1. 0. 1. 0. 1. 0. 0.]
[0. 0. 0. 0. 0. 1. 0. 0. 0. 1. 0.]
[0. 0. 0. 0. 1. 0. 1. 0. 0. 0. 1.]
[0. 0. 0. 1. 0. 0. 0. 1. 0. 0. 0.]
[0. 0. 0. 0. 1. 0. 0. 0. 1. 0. 1.]
[0. 0. 0. 0. 0. 1. 0. 0. 0. 1. 0.]
[0. 0. 0. 0. 0. 0. 1. 0. 1. 0. 1.]]
Here is the same matrix with just the 1s, so that it is easier to see the free entries:
1
1
1
1 1
1 1 1
1 1
1 1 1
1 1
1 1 1
1 1
1 1 1
The free entries look structured, but it is not clear whether this could be a block diagonal matrix. So we examine connectivity:
These results indicate 6 blocks in the covariance matrix, some of which are of size 1. The blocks of size 1 indicate standalone variables, which could receive inverse gamma (or other) priors on variances.
To examine whether or not the blocks are fully unrestricted, we permute the rows and columns of our matrix:
1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 1 1 0 1 0 0
0 0 0 0 0 1 0 1 1 0 0
0 0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 1 1
[[1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 1. 1. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 1. 1. 0. 0. 0. 0. 0. 0.]
[0. 0. 0. 0. 0. 1. 1. 1. 0. 0. 0.]
[0. 0. 0. 0. 0. 1. 1. 0. 1. 0. 0.]
[0. 0. 0. 0. 0. 1. 0. 1. 1. 0. 0.]
[0. 0. 0. 0. 0. 0. 1. 1. 1. 0. 0.]
[0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1.]
[0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1.]]
The output shows two
We need to specially consider the prior distribution for this
Even though we were not able to permute this matrix to have fully unrestricted blocks, we have reduced the dimension of the problematic block from 11 to 4. We are likely to see improvements in the computational efficiency of MCMC methods due to this reduced dimension.
Connectivity is a well known concept in graph theory, and it is not really surprising that it can be applied to covariance matrices. This post shows exactly how the covariance matrix can be translated to a graph, which then opens the door to connectivity. Under this representation, we can easily see whether our matrix is block diagonal. This information can then be used to automatically determine appropriate prior distributions for the covariance matrix.
The code on this page is copyrighted by Edgar Merkle and licensed under the GPLv3 license:
https://www.gnu.org/licenses/gpl-3.0.en.html
The text and figures on this page are copyrighted by Edgar Merkle and licensed under the CC BY-NC 4.0 license:
R version 4.4.3 (2025-02-28)
Platform: x86_64-pc-linux-gnu
Running under: Ubuntu 22.04.5 LTS
Matrix products: default
BLAS: /usr/lib/x86_64-linux-gnu/atlas/libblas.so.3.10.3
LAPACK: /usr/lib/x86_64-linux-gnu/atlas/liblapack.so.3.10.3; LAPACK version 3.10.0
locale:
[1] LC_CTYPE=en_US.UTF-8 LC_NUMERIC=C
[3] LC_TIME=en_US.UTF-8 LC_COLLATE=en_US.UTF-8
[5] LC_MONETARY=en_US.UTF-8 LC_MESSAGES=en_US.UTF-8
[7] LC_PAPER=en_US.UTF-8 LC_NAME=C
[9] LC_ADDRESS=C LC_TELEPHONE=C
[11] LC_MEASUREMENT=en_US.UTF-8 LC_IDENTIFICATION=C
time zone: America/Chicago
tzcode source: system (glibc)
attached base packages:
[1] stats graphics grDevices datasets utils methods base
other attached packages:
[1] igraph_2.1.4
loaded via a namespace (and not attached):
[1] digest_0.6.37 fastmap_1.2.0 xfun_0.51
[4] Matrix_1.7-2 lattice_0.22-6 magrittr_2.0.3
[7] reticulate_1.41.0.1 bspm_0.5.5 knitr_1.49
[10] pkgconfig_2.0.3 htmltools_0.5.8.1 png_0.1-8
[13] rmarkdown_2.29 lifecycle_1.0.4 cli_3.6.4
[16] grid_4.4.3 compiler_4.4.3 tools_4.4.3
[19] evaluate_1.0.3 Rcpp_1.0.14 yaml_2.3.10
[22] rlang_1.1.5 jsonlite_1.9.1 htmlwidgets_1.6.4
@online{merkle2025,
author = {Merkle, Edgar C.},
title = {Finding Blocks in Covariance Matrices},
date = {2025-03-20},
url = {https://ecmerkle.github.io/cs/blockmat.html},
langid = {en}
}