Definition of band matrix

Definition: A band matrix is a sparse matrix whose nonzero entries are confined to a diagonal band around the main diagonal. A matrix with lower bandwidth $p$ and upper bandwidth $q$ satisfies:

$$a_{ij} = 0 \quad \text{whenever} \quad i - j > p \; \text{or} \; j - i > q$$

The total bandwidth is $p + q + 1$.

Special cases:

• Tridiagonal ($p = q = 1$): nonzero only on main diagonal and adjacent diagonals
• Diagonal ($p = q = 0$): nonzero only on main diagonal
• Upper bidiagonal ($p = 0, q = 1$)
• Lower bidiagonal ($p = 1, q = 0$)

Example (tridiagonal):
$$A = \begin{pmatrix} 2 & 1 & 0 & 0 \\ 1 & 2 & 1 & 0 \\ 0 & 1 & 2 & 1 \\ 0 & 0 & 1 & 2 \end{pmatrix}$$

Band matrices arise frequently in numerical solutions of differential equations. Specialized algorithms can solve band systems in $O(n)$ time vs $O(n^3)$ for general matrices.