Sharp growth for cyclic tridiagonal matrices
For $n \ge 4$ let $\mathcal{C}_n$ be the set of nonsingular $A \in \mathbb{C}^{n \times n}$ that are tridiagonal apart from two nonzero corner entries: $a_{ij} = 0$ unless $|i - j| \le 1$ or $(i, j) \in \{(1, n), (n, 1)\}$, and $a_{1n} \ne 0$, $a_{n1} \ne 0$. Higham calls these matrices quasi-tridiagonal; no symmetry or diagonal dominance is assumed. 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 $$c_n = \sup_{A \in \mathcal{C}_n} \ \sup_{\pi} \rho(A, \pi).$$ For tridiagonal matrices the growth factor of GEPP is at most $2$, a special case of Bohte's bound for banded matrices (Higham).
Problem. Determine $c_n$ for every $n \ge 4$.
Source: Higham (2002), Problem 9.15(b), a research problem asking for sharp bounds for quasi-tridiagonal matrices; in this form (n ≥ 4, complex entries, both corner entries nonzero, the exact supremum over every pivoting path for each n), OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Keywords
- Gaussian elimination, growth factors, OpenProblemsInNLA, tridiagonal matrices
- 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 = {Section 9.5 and Problem 9.15(b)},
}
@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-ie14,
author = {Townsend, Alex},
title = {{IE-14}: Sharp growth for cyclic tridiagonal matrices},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/linear-systems-and-elimination/IE-14/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
For Gaussian elimination with partial pivoting on nonsingular real or complex cyclic tridiagonal matrices of order $n \ge 4$, with nonzeros only on the three central diagonals and in the corners $(1, n)$ and $(n, 1)$, both corners nonzero, the manuscript proves that the largest growth factor over all such matrices and all maximal-modulus pivot ties, measured over every active …
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-00223, "Sharp growth for cyclic tridiagonal matrices", clopen.solutions.