Sparse Matrix Decompositions and Graph Characterizations

Details Sparse Matrix Decompositions and Graph Characterizations Sparse Matrix Decompositions and Graph Characterizations

2011-11-28

arxiv.org/abs/1111.6845v2

Mathematics

Combinatorics

Scientific paper

The question of when zeros (i.e., sparsity) in a positive definite matrix $A$ are preserved in its Cholesky decomposition, and vice versa, was addressed by Paulsen et al. in the Journal of Functional Analysis (85, pp151-178). In particular, they prove that for the pattern of zeros in $A$ to be retained in the Cholesky decomposition of $A$, the pattern of zeros in $A$ has to necessarily correspond to a chordal (or decomposable) graph associated with a specific type of vertex ordering. This result therefore yields a characterization of chordal graphs in terms of sparse positive definite matrices. It has also proved to be extremely useful in probabilistic and statistical analysis of Markov random fields where zeros in positive definite correlation matrices are intimately related to the notion of stochastic independence. Now, consider a positive definite matrix $A$ and its Cholesky decomposition given by $A = LDL^T$, where $L$ is lower triangular with unit diagonal entries, and $D$ a diagonal matrix with positive entries. In this paper, we prove that a necessary and sufficient condition for zeros (i.e., sparsity) in a positive definite matrix $A$ to be preserved in its associated Cholesky matrix $L$, \, and in addition also preserved in the inverse of the Cholesky matrix $L^{-1}$, is that the pattern of zeros corresponds to a co-chordal or homogeneous graph associated with a specific type of vertex ordering. We proceed to provide a second characterization of this class of graphs in terms of determinants of submatrices that correspond to cliques in the graph. These results add to the growing body of literature in the field of sparse matrix decompositions, and also prove to be critical ingredients in the probabilistic analysis of an important class of Markov random fields.

Affiliated with

Also associated with

No associations

Rating

Sparse Matrix Decompositions and Graph Characterizations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sparse Matrix Decompositions and Graph Characterizations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sparse Matrix Decompositions and Graph Characterizations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-68511