Sharp growth for unequal lower and upper bandwidths
For integers $p, q \ge 0$ and $n \ge 1 + \max(p, q)$ let $\mathcal{B}_n(p, q)$ be the set of nonsingular $A \in \mathbb{C}^{n \times n}$ with $a_{ij} = 0$ whenever $i - j > p$ or $j - i > q$, that is, with lower bandwidth at most $p$ and upper bandwidth at most $q$. Gaussian elimination with partial pivoting (GEPP) is applied to $A$ in its given ordering, in exact arithmetic: at each step a row whose entry in the active first column has the largest modulus is moved to the top, and the Schur complement is formed. Every choice among tied entries is allowed, and each sequence of choices is a pivoting path $\pi$. Let $\rho(A, \pi)$ be the largest entry modulus of the successive active matrices $S_1 = A, S_2, \dots, S_n$ along $\pi$, divided by that of $A$, and $$G(p, q) = \sup_{n \ge 1 + \max(p, q)} \ \sup_{A \in \mathcal{B}_n(p, q)} \ \sup_{\pi} \rho(A, \pi).$$ For $p = q \ge 1$, $G(p, p) = 2^{2p-1} - (p-1) 2^{p-2}$: Bohte proved this upper bound, and it is almost attained by matrices of order $2p + 1$ (Higham).
Problem. Determine $G(p, q)$ for every pair of integers $p, q \ge 0$ with $p \ne q$.
Source: Higham (2002), Problem 9.15(a), a research problem generalizing Bohte's theorem for equal bandwidths (Higham's Theorem 9.11); in this form (complex matrices, every pivoting path, the supremum over all orders n ≥ 1 + max(p, q), p ≠ q), OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Keywords
- banded matrices, Gaussian elimination, growth factors, OpenProblemsInNLA
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@book{higham2002,
author = {Higham, Nicholas J.},
title = {Accuracy and Stability of Numerical Algorithms},
edition = {2nd},
publisher = {SIAM},
address = {Philadelphia},
year = {2002},
doi = {10.1137/1.9780898718027},
note = {Theorem 9.11 and Problem 9.15(a)},
}
@article{bohte1975,
author = {Bohte, Z.},
title = {Bounds for rounding errors in the {G}aussian elimination for band systems},
journal = {IMA J. Appl. Math.},
volume = {16},
number = {2},
year = {1975},
pages = {133--142},
doi = {10.1093/imamat/16.2.133},
}
@misc{openproblemsinnla-ie13,
author = {Townsend, Alex},
title = {{IE-13}: Sharp growth for unequal lower and upper bandwidths},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/linear-systems-and-elimination/IE-13/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
For lower bandwidth $p \ge 1$ and upper bandwidth $q \ge 0$, the manuscript proves that the optimal dimension-independent growth factor of Gaussian elimination with partial pivoting is $h_{p+q}$, where $h_t = 0$ for $t \le 0$ and $h_t = 1 + \sum_{r=1}^{p} h_{t-r}$ for $t \ge 1$; for $p = 0$ it is $1$. A sorted-front argument gives an …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00222, "Sharp growth for unequal lower and upper bandwidths", clopen.solutions.