Chapter 96. Structured Matrices
Chapter 96. Structured Matrices
A structured matrix is a matrix whose entries satisfy a special pattern or rule. The structure may be algebraic, geometric, combinatorial, or computational.
Sparse matrices are one kind of structured matrix. Their structure is the location of zero and nonzero entries. But structure is broader than sparsity. A matrix may be dense and still structured. Toeplitz, Hankel, circulant, Vandermonde, diagonal, triangular, banded, symmetric, orthogonal, and low-rank matrices all have special forms that can be exploited.
Structured linear algebra studies how these forms affect storage, computation, conditioning, and algorithms. The purpose is to avoid treating every matrix as an arbitrary dense array when more information is available.
96.1 What Structure Means
A general (m\times n) matrix has
$$ mn $$
independent entries.
A structured matrix has fewer independent degrees of freedom.
For example, a diagonal (n\times n) matrix has only (n) independent entries. A symmetric (n\times n) matrix has
$$ \frac{n(n+1)}{2} $$
independent entries. A Toeplitz (n\times n) matrix has only
$$ 2n-1 $$
independent entries because each descending diagonal is constant. Toeplitz matrices are commonly defined by the rule (a_{ij}=c_{i-j}), so entries on each descending diagonal are equal.
Structure reduces freedom. Reduced freedom often gives faster algorithms.
96.2 Examples of Structured Matrices
Common structured matrices include:
| Structure | Defining property |
|---|---|
| Diagonal | (a_{ij}=0) for (i\ne j) |
| Triangular | entries vanish above or below diagonal |
| Banded | nonzeros confined near diagonal |
| Symmetric | (A^T=A) |
| Skew-symmetric | (A^T=-A) |
| Orthogonal | (Q^TQ=I) |
| Toeplitz | (a_{ij}=c_{i-j}) |
| Hankel | (a_{ij}=c_{i+j}) |
| Circulant | each row is a cyclic shift of previous row |
| Vandermonde | (a_{ij}=x_i^{j-1}) |
| Cauchy | (a_{ij}=1/(x_i-y_j)) |
| Low-rank | rank much smaller than dimensions |
| Kronecker product | built from tensor products of smaller matrices |
A matrix may have several structures at once. A symmetric tridiagonal matrix is symmetric, sparse, banded, and structured.
96.3 Why Structure Matters
Structure matters for four main reasons.
| Reason | Effect |
|---|---|
| Storage | fewer values must be stored |
| Speed | specialized algorithms reduce work |
| Stability | structure may improve or damage conditioning |
| Interpretation | structure reflects the model that produced the matrix |
For example, a dense (n\times n) matrix needs (n^2) stored values. A Toeplitz matrix needs only (2n-1). A circulant matrix needs only (n). A diagonal matrix needs only (n).
The computational difference can be large. Multiplying by a dense matrix usually costs (O(n^2)). Multiplying by a diagonal matrix costs (O(n)). Multiplying by a circulant matrix can be done through the fast Fourier transform in (O(n\log n)).
96.4 Diagonal Matrices
A diagonal matrix has the form
$$ D= \begin{bmatrix} d_1 & 0 & \cdots & 0\ 0 & d_2 & \cdots & 0\ \vdots & \vdots & \ddots & \vdots\ 0 & 0 & \cdots & d_n \end{bmatrix}. $$
Multiplication is componentwise:
$$ (Dx)_i=d_ix_i. $$
Solving
$$ Dx=b $$
is also componentwise:
$$ x_i=\frac{b_i}{d_i}, $$
provided (d_i\ne 0).
Diagonal matrices are the simplest structured matrices. They represent independent scaling in coordinate directions.
96.5 Triangular Matrices
A lower triangular matrix has entries
$$ a_{ij}=0 \qquad \text{for } j>i. $$
An upper triangular matrix has entries
$$ a_{ij}=0 \qquad \text{for } i>j. $$
Triangular systems are solved by substitution.
For lower triangular (Lx=b), forward substitution computes
$$ x_i= \frac{1}{\ell_{ii}} \left( b_i-\sum_{j<i}\ell_{ij}x_j \right). $$
Triangular matrices are central because many factorizations reduce a problem to triangular solves:
| Factorization | Triangular part |
|---|---|
| LU | (L) and (U) |
| Cholesky | (L) and (L^T) |
| QR | (R) |
96.6 Banded Matrices
A banded matrix has nonzero entries only near the main diagonal.
A matrix has lower bandwidth (p) and upper bandwidth (q) if
$$ a_{ij}=0 \qquad \text{whenever } i-j>p $$
or
$$ j-i>q. $$
A tridiagonal matrix has
$$ p=q=1. $$
Banded matrices arise from local interactions, especially finite difference discretizations of differential equations.
Specialized algorithms for banded systems store only the bands and avoid arithmetic outside them.
96.7 Tridiagonal Matrices
A tridiagonal matrix has the form
$$ T= \begin{bmatrix} d_1 & u_1 & 0 & \cdots & 0\ \ell_1 & d_2 & u_2 & \cdots & 0\ 0 & \ell_2 & d_3 & \cdots & 0\ \vdots & \vdots & \vdots & \ddots & u_{n-1}\ 0 & 0 & 0 & \ell_{n-1} & d_n \end{bmatrix}. $$
It has at most
$$ 3n-2 $$
nonzero entries.
Tridiagonal systems can be solved in (O(n)) time by the Thomas algorithm, a specialized form of Gaussian elimination.
Symmetric tridiagonal matrices also appear in eigenvalue algorithms after reducing a symmetric dense matrix by orthogonal transformations.
96.8 Symmetric Matrices
A symmetric matrix satisfies
$$ A^T=A. $$
Thus
$$ a_{ij}=a_{ji}. $$
Only the upper or lower triangle must be stored.
Symmetric matrices have important spectral properties. If (A) is real symmetric, then its eigenvalues are real and it has an orthonormal eigenbasis.
Symmetry is more than a storage property. It changes which algorithms are valid.
| Problem | Symmetric algorithm |
|---|---|
| positive definite system | Cholesky factorization |
| eigenvalue problem | symmetric QR, Lanczos |
| large SPD system | conjugate gradient |
| indefinite symmetric system | MINRES |
96.9 Orthogonal Matrices
An orthogonal matrix satisfies
$$ Q^TQ=I. $$
Its inverse is its transpose:
$$ Q^{-1}=Q^T. $$
Orthogonal matrices preserve Euclidean norms:
$$ |Qx|_2=|x|_2. $$
This makes them numerically stable. Householder reflectors, Givens rotations, and orthogonal factors in QR decompositions are essential tools in numerical linear algebra.
Orthogonal structure is often preserved deliberately because it controls rounding error.
96.10 Toeplitz Matrices
A Toeplitz matrix is constant along descending diagonals:
$$ a_{ij}=c_{i-j}. $$
A typical Toeplitz matrix is
$$ T= \begin{bmatrix} c_0 & c_{-1} & c_{-2} & \cdots & c_{-(n-1)}\ c_1 & c_0 & c_{-1} & \cdots & c_{-(n-2)}\ c_2 & c_1 & c_0 & \cdots & c_{-(n-3)}\ \vdots & \vdots & \vdots & \ddots & \vdots\ c_{n-1} & c_{n-2} & c_{n-3} & \cdots & c_0 \end{bmatrix}. $$
Toeplitz matrices are closely connected to convolution. Linear convolution can be written as multiplication by a Toeplitz matrix.
They appear in signal processing, time series, stationary covariance models, and discretized translation-invariant operators.
96.11 Hankel Matrices
A Hankel matrix is constant along anti-diagonals:
$$ a_{ij}=c_{i+j}. $$
For example,
$$ H= \begin{bmatrix} c_2 & c_3 & c_4 & c_5\ c_3 & c_4 & c_5 & c_6\ c_4 & c_5 & c_6 & c_7\ c_5 & c_6 & c_7 & c_8 \end{bmatrix}. $$
Hankel matrices appear in moment problems, system identification, control theory, signal processing, and Padé approximation.
A Hankel matrix is closely related to a Toeplitz matrix after reversing row or column order. Sources often describe Hankel matrices as reversed Toeplitz matrices.
96.12 Circulant Matrices
A circulant matrix is determined by one vector. Each row is a cyclic shift of the previous row.
For example,
$$ C= \begin{bmatrix} c_0 & c_1 & c_2 & c_3\ c_3 & c_0 & c_1 & c_2\ c_2 & c_3 & c_0 & c_1\ c_1 & c_2 & c_3 & c_0 \end{bmatrix}. $$
Circulant matrices are special Toeplitz matrices with wraparound structure.
Their main computational property is that they are diagonalized by the discrete Fourier transform. Thus multiplication by a circulant matrix can be computed using FFT methods.
This makes circulant matrices important in periodic convolution, signal processing, image processing, and preconditioning.
96.13 Vandermonde Matrices
A Vandermonde matrix has the form
$$ V= \begin{bmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^{n-1}\ 1 & x_2 & x_2^2 & \cdots & x_2^{n-1}\ \vdots & \vdots & \vdots & \ddots & \vdots\ 1 & x_n & x_n^2 & \cdots & x_n^{n-1} \end{bmatrix}. $$
Vandermonde matrices appear in polynomial interpolation, quadrature, moment fitting, and signal processing.
They are structured because the entire matrix is determined by the nodes
$$ x_1,x_2,\ldots,x_n. $$
However, Vandermonde matrices can be severely ill-conditioned. Their conditioning depends strongly on the distribution of the nodes; one study notes exponential conditioning behavior unless the knots are roughly equally spaced on or near the unit circle.
96.14 Cauchy Matrices
A Cauchy matrix has entries
$$ a_{ij}=\frac{1}{x_i-y_j}, $$
where
$$ x_i\ne y_j. $$
Cauchy matrices appear in rational interpolation, integral equations, approximation theory, and structured direct solvers.
Like Vandermonde matrices, Cauchy matrices are dense but highly structured. Their entries are determined by two short vectors:
$$ x_1,\ldots,x_m $$
and
$$ y_1,\ldots,y_n. $$
This structure can be exploited in fast algorithms and displacement-rank methods.
96.15 Low-Rank Matrices
A matrix (A\in\mathbb{R}^{m\times n}) has rank (r) if its columns span an (r)-dimensional space.
If
$$ r\ll \min(m,n), $$
then (A) is low-rank.
A low-rank matrix can often be written as
$$ A=UV^T, $$
where
$$ U\in\mathbb{R}^{m\times r}, \qquad V\in\mathbb{R}^{n\times r}. $$
This representation stores
$$ r(m+n) $$
numbers instead of
$$ mn. $$
Low-rank structure appears in data compression, principal component analysis, integral equations, recommender systems, and model reduction.
96.16 Rank-Structured Matrices
Some matrices are not globally low-rank but contain low-rank off-diagonal blocks.
Such matrices are called rank-structured.
Examples include:
| Type | Basic idea |
|---|---|
| H-matrix | hierarchical block low-rank structure |
| HSS matrix | hierarchically semiseparable |
| HODLR matrix | hierarchically off-diagonal low-rank |
| quasiseparable matrix | low-rank subblocks in off-diagonal regions |
These structures occur in integral equations, kernel methods, covariance matrices, and discretized operators with smooth long-range interactions.
They allow approximate storage and fast multiplication or factorization.
96.17 Kronecker Product Structure
The Kronecker product of matrices (A) and (B) is written
$$ A\otimes B. $$
If
$$ A=[a_{ij}], $$
then
$$ A\otimes B = \begin{bmatrix} a_{11}B & a_{12}B & \cdots\ a_{21}B & a_{22}B & \cdots\ \vdots & \vdots & \ddots \end{bmatrix}. $$
Kronecker products appear in tensor grids, separable differential operators, multidimensional transforms, quantum mechanics, statistics, and signal processing.
They allow large matrices to be represented by smaller factors.
For example, a two-dimensional separable operator may be written as
$$ A_x\otimes I + I\otimes A_y. $$
This form enables fast matrix-vector products without constructing the full matrix explicitly.
96.18 Block Matrices
Block structure divides a matrix into submatrices:
$$ A= \begin{bmatrix} A_{11} & A_{12}\ A_{21} & A_{22} \end{bmatrix}. $$
Block structure may reflect multiple variables, domains, time steps, or physical components.
Block methods can improve cache behavior and expose mathematical structure. For example, saddle-point systems often have the form
$$ \begin{bmatrix} A & B^T\ B & 0 \end{bmatrix}. $$
Recognizing the block form helps choose solvers and preconditioners.
96.19 Displacement Structure
Some structured matrices can be described by displacement operators.
A matrix (A) has low displacement rank if an expression such as
$$ A - ZAZ^T $$
has low rank for a simple shift matrix (Z).
Toeplitz, Hankel, Vandermonde-like, and Cauchy-like matrices can often be described in this framework. Structured linear algebra literature uses displacement operators to unify fast algorithms for these matrix classes.
The point is that a matrix may be dense, but its departure from a shifted version of itself is simple.
This hidden simplicity supports fast direct solvers.
96.20 Structured Storage
Structured storage records only the data needed to reconstruct the matrix.
| Matrix | Minimal data |
|---|---|
| diagonal | diagonal vector |
| tridiagonal | three diagonals |
| banded | stored bands |
| symmetric | one triangle |
| Toeplitz | first row and first column |
| circulant | first row or column |
| Vandermonde | nodes (x_i) |
| Cauchy | vectors (x_i), (y_j) |
| low-rank | factors (U,V) |
| Kronecker | component matrices |
The matrix may never be materialized as a full dense array.
Instead, algorithms operate directly on the representation.
96.21 Structured Matrix-Vector Multiplication
For a general dense matrix,
$$ y=Ax $$
costs
$$ O(n^2). $$
For structured matrices, the cost may be lower.
| Structure | Multiplication cost |
|---|---|
| diagonal | (O(n)) |
| tridiagonal | (O(n)) |
| banded with bandwidth (w) | (O(wn)) |
| sparse | (O(\operatorname{nnz}(A))) |
| circulant | (O(n\log n)) |
| Toeplitz using FFT embedding | (O(n\log n)) |
| low-rank (UV^T) | (O(r(m+n))) |
These savings are often the reason to preserve structure.
96.22 Structured Solvers
A structured solver uses the matrix form directly.
Examples include:
| Matrix type | Solver idea |
|---|---|
| diagonal | componentwise division |
| triangular | substitution |
| tridiagonal | Thomas algorithm |
| symmetric positive definite | Cholesky |
| Toeplitz | Levinson-type or FFT-based methods |
| circulant | FFT diagonalization |
| low-rank update | Sherman-Morrison-Woodbury |
| Kronecker sum | separable transforms |
A general dense solver ignores this structure and may use more time and memory than necessary.
96.23 Structure and Conditioning
Structure does not automatically imply good conditioning.
A diagonal matrix may be ill-conditioned if the ratio
$$ \frac{\max_i |d_i|}{\min_i |d_i|} $$
is large.
A Vandermonde matrix may be extremely ill-conditioned for poorly chosen nodes.
A Toeplitz matrix may be well-conditioned or ill-conditioned depending on its generating sequence.
Therefore one must distinguish:
| Concept | Meaning |
|---|---|
| structural simplicity | few parameters or special pattern |
| numerical conditioning | sensitivity to perturbations |
| algorithmic stability | behavior under floating point computation |
A matrix can be simple to describe and still difficult to solve accurately.
96.24 Preserving Structure
Some operations preserve structure; others destroy it.
| Operation | Possible effect |
|---|---|
| adding two Toeplitz matrices | Toeplitz |
| multiplying two diagonal matrices | diagonal |
| inverse of diagonal matrix | diagonal |
| inverse of triangular matrix | triangular |
| product of Toeplitz matrices | generally not Toeplitz |
| LU factorization of sparse matrix | may create fill-in |
| perturbing a symmetric matrix asymmetrically | destroys symmetry |
Algorithms should preserve structure when doing so improves accuracy or speed.
For example, using symmetric eigensolvers on symmetric matrices avoids unnecessary complex arithmetic and improves numerical behavior.
96.25 Structured Perturbations
In ordinary perturbation analysis, a perturbation (\Delta A) may be any matrix.
In structured perturbation analysis, (\Delta A) must preserve the structure.
For example, if (A) is Toeplitz, a structured perturbation must also be Toeplitz.
Structured condition numbers may differ from unstructured condition numbers. Some analyses explicitly compare structured and unstructured sensitivity for matrix classes such as Toeplitz, Hankel, circulant, and symmetric matrices.
This matters when the data comes from a structured model. Perturbations outside the model may be irrelevant.
96.26 Applications
Structured matrices appear across applied mathematics.
| Application | Structure |
|---|---|
| signal processing | Toeplitz, circulant, Hankel |
| time series | Toeplitz covariance |
| image processing | block Toeplitz, circulant approximations |
| PDEs | sparse, banded, Kronecker sums |
| graph algorithms | sparse Laplacian |
| polynomial interpolation | Vandermonde |
| rational interpolation | Cauchy |
| statistics | covariance and kernel structure |
| optimization | block, sparse, low-rank Hessians |
| quantum mechanics | Kronecker products |
Recognizing the source of the matrix usually suggests the correct algorithm.
96.27 Matrix-Free Structured Operators
Some structured matrices are better represented as operators than arrays.
For example, convolution may be implemented by FFTs rather than by forming a Toeplitz matrix.
A Kronecker sum may be applied by reshaping vectors into arrays and multiplying along dimensions.
A low-rank matrix may be applied as
$$ x\mapsto U(V^Tx). $$
These forms avoid explicit storage and reduce cost.
Matrix-free structured operators are common in large-scale scientific computing and machine learning.
96.28 Practical Checklist
When given a matrix, ask:
| Question | Reason |
|---|---|
| Is the matrix sparse? | choose sparse storage and solvers |
| Is it symmetric? | use symmetric algorithms |
| Is it positive definite? | use Cholesky or conjugate gradient |
| Is it banded? | use band storage and band solvers |
| Is it Toeplitz or circulant? | exploit convolution or FFT methods |
| Is it low-rank or approximately low-rank? | use factorized representations |
| Is it a Kronecker product or sum? | avoid forming the full matrix |
| Is the structure exact or approximate? | controls algorithm choice |
| Does the algorithm preserve structure? | affects speed and stability |
The main rule is simple: do not discard useful structure too early.
96.29 Summary
Structured matrices are matrices with special patterns or representations.
Important examples include diagonal, triangular, banded, symmetric, orthogonal, Toeplitz, Hankel, circulant, Vandermonde, Cauchy, low-rank, block, sparse, and Kronecker-structured matrices.
Structure affects:
| Aspect | Effect |
|---|---|
| Storage | fewer parameters |
| Multiplication | faster matrix-vector products |
| Solving | specialized algorithms |
| Eigenvalue computation | specialized reductions |
| Conditioning | structured sensitivity may differ |
| Modeling | structure reflects the problem source |
Structured matrices are central in numerical linear algebra because they allow algorithms to use the information already present in the problem. Treating a structured matrix as a general dense matrix is often wasteful and may hide the best method.