OP-00224 Solution claimed

Exact small-order growth factors for rook pivoting

Gaussian elimination with rook pivoting is applied in exact arithmetic to a nonsingular $A \in \mathbb{R}^{n \times n}$: at each step a nonzero entry of the active matrix that is largest in absolute value both in its row and in its column is moved to the leading position by a row and a column interchange, and the Schur complement is formed. Any such entry may be chosen, including among ties, and each sequence of choices is a pivoting path $\pi$. Let $\rho(A, \pi)$ be the largest absolute value of an entry of the successive active matrices $S_1 = A, S_2, \dots, S_n$ along $\pi$, divided by that of $A$, and let $$g_{\mathrm{RP}}(n) = \sup_{A} \ \sup_{\pi} \rho(A, \pi),$$ over all nonsingular $A \in \mathbb{R}^{n \times n}$ and all their pivoting paths. One has $g_{\mathrm{RP}}(1) = 1$ and $g_{\mathrm{RP}}(2) = 2$. Higham reports the lower bounds $2.9$ for $n = 3$ and $4.16$ for $n = 4$, found by direct search.

Problem. Determine $g_{\mathrm{RP}}(3)$ and $g_{\mathrm{RP}}(4)$.

Source: Higham (2002), Problem 9.18, a research problem asking for the exact value, for n ≤ 4, of the rook-pivoting analogue of Cryer's largest growth factor g(n); for n = 3 and 4, nonsingular matrices and every admissible rook-pivoting path, as stated by OpenProblemsInNLA.

Imported from github.com/ajt60gaibb/OpenProblemsInNLA.

Classification

Primary: NA — Numerical Analysis
Keywords: Gaussian elimination, growth factors, OpenProblemsInNLA, rook pivoting
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      = {Problem 9.18 and equation (9.15)},
}
@misc{openproblemsinnla-ie15,
  author       = {Townsend, Alex},
  title        = {{IE-15}: Exact small-order growth factors for rook pivoting},
  howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
  year         = {2026},
  url          = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/linear-systems-and-elimination/IE-15/README.md},
  note         = {Read at commit eb7c9d6, 2026-10-07},
}

Resolution claims

Exact rook-pivoting growth factors in orders three and four v1 GitHub ↗

George Stepaniants

For Gaussian elimination with rook pivoting on real nonsingular matrices in exact arithmetic, allowing every admissible choice of pivot, ties included, and measuring growth over every entry of every active matrix, the manuscript proves that the largest growth factor is $3$ in order three and $14/3$ in order four. After normalisation the matrix is $A = LDR$ with positive pivots …

Full resolution · not verified · fidelity not established · posted on GitHub 11 Sep 2026

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-00224, "Exact small-order growth factors for rook pivoting", clopen.solutions.