The largest 5th pivot may be the root of a 61st degree polynomial

1. Problem Statement

The paper addresses a fundamental question in numerical linear algebra: What is the maximum possible growth factor ($g$) when performing Gaussian elimination with complete pivoting on an $n \times n$ real matrix?

• Context: The growth factor $g(A)$ measures the ratio of the largest element in the $L$ and $U$ factors to the largest element in the original matrix $A$. A large growth factor implies potential numerical instability.
• Known Sequence: For dimensions $n=1, 2, 3, 4$, the maximum growth factors are known to be $1, 2, 2.25, 4$.
• The Open Problem: For $n=5$, the exact maximum has been elusive. Since 1988, numerical optimization (using tools like NPSOL, LANCELOT, and JuMP) has consistently suggested a maximum value of approximately 4.1325. However, no proof existed that this was the true maximum, nor was the exact algebraic form of this number known.
• Upper Bounds: Prior to this work, the best known theoretical upper bound for $n=5$ was $4\frac{17}{18} \approx 4.94$ (Tornheim, 1969).

2. Methodology

The authors introduce a novel hybrid approach combining numerical optimization with exact symbolic algebra and interval arithmetic. The methodology is divided into two main parts: finding the exact lower bound (conjectured maximum) and improving the theoretical upper bound.

A. The "JuMP + Groebner Basis + Discriminant" Approach (Lower Bound)

This technique is used to determine the exact algebraic nature of the maximum growth factor for $n=5$ (and $n=6, 7, 8$).

1. Numerical Optimization: The authors use the JuMP (Julia for Mathematical Programming) package to perform non-linear optimization. This identifies a candidate matrix structure and suggests which constraints are "tight" (active equalities) at the optimum.
2. Constraint Fixing: Based on the numerical output, the authors fix the equality constraints (e.g., specific entries in the matrix or intermediate Schur complements being equal to $\pm 1$).
3. Symbolic Elimination (Groebner Bases): The remaining variables are treated as unknowns. The authors use Groebner basis computations (via Mathematica) to eliminate variables and reduce the system of polynomial equations. This transforms the problem from a high-dimensional non-linear optimization into a system of polynomial equations.
4. Exact Optimization (Discriminant Polynomials): To find the maximum value of the growth factor $g$, they treat $g$ as a variable in the polynomial system. They compute the discriminant of the resulting polynomial with respect to the remaining variables. The roots of this discriminant polynomial represent the stationary points (potential maxima) of the system.
5. Verification: They verify that the specific root corresponds to a valid, completely pivoted matrix.

B. Interval Arithmetic and Branch-and-Bound (Upper Bound)

To improve the upper bound, the authors combine mathematical analysis with rigorous interval arithmetic.

1. Decomposition: They analyze the $5 \times 5$ growth factor $g(A)$ as the product of the 3rd pivot ($p_3$) and the growth factor of the resulting $3 \times 3$ submatrix ($g(C)$).
2. Covering Sets: Using interval arithmetic, they construct "dyadic boxes" (hyper-rectangles) that cover the space of all possible normalized $3 \times 3$ completely pivoted matrices with growth factors above certain thresholds (e.g., $g(C) \ge 2.15$ and $g(C) \ge 2.2$).
3. Infeasibility Test: They prove that for a $5 \times 5$ matrix to achieve a growth factor $> 4.84$, the intermediate $3 \times 3$ matrices would have to satisfy a specific inequality involving rank-2 approximations. By checking these inequalities against the covering sets, they demonstrate that no such matrices exist.

3. Key Contributions and Results

A. The Exact Value for $n=5$

The paper establishes that the value $4.1325\dots$ observed numerically is not a coincidence but an exact algebraic number.

• The Polynomial: The maximum growth factor for $n=5$ is the unique real root in the interval $[4, 5]$ of a 61st-degree polynomial with integer coefficients, denoted as $P_5(g)$.
• The Value:
  $$g \approx 4.13251707863247285422\dots$$
• Conjecture: The authors conjecture that this value is the true global maximum for $n=5$ (Conjecture 2.1). While the combinatorial explosion of possible constraint structures prevents a full proof of global optimality, they prove that this value is the maximum given the specific set of equality constraints suggested by the numerical optimization (Theorem 2.2).

B. Results for $n=6, 7, 8$

The authors apply their technique to higher dimensions:

• $n=6$: The maximum growth is exactly 5.
• $n=7$: The maximum growth is the root of a 6th-degree polynomial, approximately 6.0569.
• $n=8$: The maximum growth is 8 (achieved by Sylvester's Hadamard matrix, but also by non-Hadamard matrices).

C. Improved Upper Bound for $n=5$

The paper lowers the theoretical upper bound for the $n=5$ case:

• Previous Bound: $4\frac{17}{18} \approx 4.944$.
• New Bound: 4.84.
• Significance: This is the first improvement on the upper bound in over 50 years, narrowing the gap between the lower bound (4.1325) and the upper bound (4.84).

4. Significance

• Bridging Numerics and Symbolics: The paper demonstrates a powerful workflow where numerical optimization guides the search for the correct algebraic structure, which is then rigorously solved using exact arithmetic. This avoids the pitfalls of floating-point errors while managing the complexity of high-dimensional non-linear systems.
• Algebraic Complexity: It reveals that the solution to a classic numerical analysis problem is an algebraic number of surprisingly high degree (61), challenging the intuition that such problems might have simpler rational or low-degree algebraic solutions.
• Methodological Advancement: The combination of Groebner bases, discriminant polynomials, and interval arithmetic provides a new toolkit for solving difficult optimization problems in numerical linear algebra that were previously intractable.
• Tribute: The work is dedicated to Nick Higham, a pioneer in the study of Gaussian elimination stability, highlighting the enduring importance of the growth factor problem.

Summary Table of Growth Factors ($n=1$ to $8$)

$n$	Maximum Growth Factor	Form
1	1	Integer
2	2	Integer
3	2.25	Rational ($9/4$)
4	4	Integer
5	$\approx 4.1325$	Root of 61st-degree polynomial
6	5	Integer
7	$\approx 6.057$	Root of 6th-degree polynomial
8	8	Integer

The paper concludes that while the exact global maximum for $n=5$ remains a conjecture due to the sheer number of possible constraint configurations, the evidence provided by the exact algebraic solution and the tightened upper bound strongly suggests that the root of the 61st-degree polynomial is indeed the answer.