\(\DeclarePairedDelimiterX{\Set}[2]{\{}{\}}{#1 \nonscript\;\delimsize\vert\nonscript\; #2}\) \( \DeclarePairedDelimiter{\set}{\{}{\}}\) \( \DeclarePairedDelimiter{\parens}{\left(}{\right)}\) \(\DeclarePairedDelimiterX{\innerproduct}[1]{\langle}{\rangle}{#1}\) \(\newcommand{\ip}[1]{\innerproduct{#1}}\) \(\newcommand{\bmat}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\barray}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\mat}[1]{\begin{matrix}#1\end{matrix}}\) \(\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}\) \(\newcommand{\mathword}[1]{\mathop{\textup{#1}}}\)
Symmetric Matrices
Chordal Graphs
Needed by:
Sheet PDF
Graph PDF

Sparsity Patterns


Certain sparse matrices are easier to work with, especially those with chordal sparsity patterns.1


A sparsity pattern $E$ of order $n$ is a set of (unordered) pairs of $V = \set{1, \dots , n}$. A sparsity pattern is chordal if the undirected graph $(V, E)$ is chordal.

A symmetric matrix is said to have a sparsity pattern if its $ij$th entry is zero whenever $\set{i, j}$ is not in the sparsity pattern. The diagonal entries and off-diagonal entries for pairs appearing in the sparsity pattern may or may not be zero.

The graph whose vertices are one through $n$ and whose edge set is the sparsity patter is called the sparsity graph

A sparsity pattern is not a property of a matrix because it is not unique (unless all off-diagonal entries are non-zero). If a matrix has a particular sparsity pattern it has every sparsity pattern which is a superset of it. In other words, every matrix has the sparsity pattern which is the set of all pairs of integers.


Let $E \subset \Set*{\set{i, j}}{i, j \in \set{1, 2, \dots , n}}$. A symmetric matrix $A \in \mathbfsf{S} ^n$ is said to have sparsity pattern $E$ if $A_{ij} = A_{ji} = 0$ wheneer $i \neq j$ and $\set{i, j} \not\in E$. The graph $G = (V, E)$ where $V = \set{1, 2, \dots , n}$ is the sparsity graph associated with $E$.

We will denote the symmetric matrices of order $n$ with sparsity pattern $E$ by $\mathbfsf{S} ^n_{E}$.


The figure above shows a sparsity graph for the matrix

\[ A := \bmat{ A_{11} & A_{21} & A_{31} & 0 & A_{51} \\ A_{21} & A_{22} & 0 & A_{42} & 0 \\ A_{31} & 0 & A_{33} & 0 & A_{54} \\ 0 & A_{42} & 0 & A_{44} & A_{45} \\ A_{51} & 0 & A_{53} & A_{54} & A_{55} \\ }. \]

  1. Future editions will expand. ↩︎
Copyright © 2023 The Bourbaki Authors — All rights reserved — Version 13a6779cc About Show the old page view