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

1. 연구 배경 및 문제 정의 (Problem)

• 주제: 수치 선형대수학의 고전적인 문제인 **완전 피벗팅 (Complete Pivoting) 을 적용한 가우스 소거법 (Gaussian Elimination) 에서의 최대 성장 인자 (Growth Factor)**를 규명하는 것입니다.
• 성장 인자 ($g(A)$): 가우스 소거법 과정에서 행렬의 요소 크기가 초기 행렬의 최대 요소 크기에 비해 얼마나 커지는지를 나타내는 지표입니다. $g(A) = \frac{\max \|L\|_{\max}, \|U\|_{\max}}{\|A\|_{\max}}$로 정의되며, 이 값이 작을수록 수치적 안정성이 높습니다.
• 현재 상황:
  • $n=1, 2, 3, 4$에 대한 최대 성장 인자는 각각 $1, 2, 2.25, 4$로 알려져 있습니다.
  • $n=5$인 경우, 1988 년 (Day & Peterson), 1991 년 (Gould), 2024 년 (JuMP) 등 여러 번의 수치 최적화 실험을 통해 약 **4.1325...**라는 값이 발견되었으나, 이것이 진정한 최대값인지, 그리고 이 값이 어떤 수학적 형태를 가지는지는 명확하지 않았습니다.
  • 기존 상한선 (Upper Bound) 은 1969 년 Tornheim 에 의해 $4 \frac{17}{18} \approx 4.94$로 설정되어 있었으나, 이는 하한선 (Lower Bound) 과 큰 간격을 가지고 있었습니다.

2. 연구 방법론 (Methodology)

저자들은 수치 최적화와 기하학적/대수적 기법을 결합한 새로운 하이브리드 접근법을 제시합니다.

A. JuMP + 그로브너 기저 (Groebner Basis) + 판별식 (Discriminant) 접근법

이 방법은 수치 최적화로 후보를 찾은 후, 이를 엄밀한 대수적 증명으로 전환하는 과정입니다.

1. 수치 최적화 (JuMP): Julia 언어 기반의 최적화 패키지인 JuMP 를 사용하여 $n=5$ 행렬에 대한 성장 인자를 최대화하는 행렬을 탐색합니다. 이를 통해 특정 등식 제약 조건 (equality constraints) 과 행렬 구조를 파악합니다.
2. 등식 제약 조건 고정: 수치 최적화 결과 도출된 "tight constraints" (등식으로 묶인 제약) 를 고정하고, 나머지 자유 변수를 대수적 변수로 둡니다.
3. 그로브너 기저 (Groebner Basis) 활용: 비선형 다항식 시스템에서 변수를 제거하여 방정식을 단순화합니다. 이를 통해 $x, y, z$와 같은 변수들을 소거하고 성장 인자 $g$에 대한 다항식 관계를 유도합니다.
4. 판별식 (Discriminant) 활용: 유도된 다항식 $P(g, z)=0$에 대해 $z$에 대한 판별식을 계산합니다. 이는 $g$가 극값 (최대값) 을 가질 때 $P$와 그 편미분 $P_z$가 동시에 0 이 되어야 한다는 조건을 만족하는 $g$의 값을 찾는 과정입니다.
5. 정확한 최적화: 판별식을 통해 얻은 $g$에 대한 단일 변수 다항식의 근을 구함으로써 정확한 수학적 값을 도출합니다.

B. 구간 산술 (Interval Arithmetic) 및 가지치기 (Branch-and-Bound)

• 상한선 개선: $n=5$ 행렬의 성장 인자 상한선을 낮추기 위해 구간 산술을 사용합니다.
• 3x3 서브행렬 분석: $5 \times 5$ 행렬의 3 번째 피벗 이후의 $3 \times 3$ 서브행렬이 가질 수 있는 성장 인자의 범위를 분석합니다.
• 불일치 테스트: 큰 성장 인자를 가진 $3 \times 3$ 행렬들이 $5 \times 5$ 행렬 내에서 동시에 존재할 수 있는지 (즉, 특정 부등식이 성립하는지) 를 구간 산술과 가지치기 알고리즘을 통해 검증하여 불가능한 경우를 배제합니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

A. $n=5$에 대한 정확한 하한선 및 다항식 유도

• 61 차 다항식의 발견: 수치적으로 관찰된 $4.1325...$라는 값이 정수 계수를 가진 **61 차 다항식$P_5(g)$의 유일한 실근**임을 증명했습니다.
  • 이 다항식은 논문 (식 2.15) 에 명시되어 있으며, 그 근은 $g \approx 4.1325170786...$입니다.
• 최대값 추측 (Conjecture 2.1): 이 값이 $n=5$ 완전 피벗팅 행렬에 대한 진정한 최대 성장 인자임을 강력히 추측합니다. 수치 최적화와 대수적 계산의 일치로 인해 이 추측의 타당성이 매우 높습니다.
• 정확한 행렬 구성: 이 성장 인자를 달성하는 $5 \times 5$ 행렬의 요소들이 모두 61 차 다항식의 근임을 보였습니다.

B. $n=6, 7, 8$에 대한 확장

• 동일한 기법을 $n=6, 7, 8$에 적용하여 새로운 하한선을 제시했습니다.
  • $n=6$: 성장 인자 5 (기존 결과와 일치).
  • $n=7$: 6 차 다항식의 근인 약 6.0569... (기존 6 보다 큼).
  • $n=8$: 성장 인자 8 (실버스터 행렬 및 비실버스터 행렬 모두 가능).

C. $n=5$ 상한선 개선

• 기존 1969 년 Tornheim 의 상한선 $4.94$를 4.84로 낮췄습니다 (Theorem 3.5).
• 이는 구간 산술과 $3 \times 3$ 행렬의 성장 인자 상호작용에 대한 정밀한 분석을 통해 달성되었습니다.

4. 의의 및 중요성 (Significance)

1. 수치와 기하학의 융합: 이 논문은 수치 최적화 (Numerical Optimization) 가 단순히 근사값을 찾는 도구를 넘어, 정확한 대수적 구조 (다항식 근) 를 발견하는 데 핵심적인 역할을 할 수 있음을 보여줍니다. "수치적 발견 $\rightarrow$ 대수적 증명"이라는 새로운 패러다임을 제시했습니다.
2. 복잡한 다항식 구조의 규명: $n=5$ 문제의 해가 단순한 유리수나 간단한 근이 아닌, 61 차 다항식의 근이라는 사실은 수치 선형대수학의 예측 불가능한 복잡성을 보여줍니다. 이는 Tarski-Seidenberg 정리에 의해 대수적 수임이 보장되지만, 그 차수가 매우 높을 수 있음을 시사합니다.
3. 알고리즘 안정성 이론의 발전: 가우스 소거법의 최악의 경우 안정성 (Worst-case stability) 에 대한 이해를 심화시켰으며, 완전 피벗팅의 한계를 더 정밀하게 규명했습니다.
4. Nick Higham 에 대한 헌정: 이 연구는 가우스 소거법과 성장 인자 문제에 깊은 관심을 가졌던 고 Nick Higham 의 업적을 기리며, 그가生前에未能한 (미완성) 문제 해결을 위한 기술적 진전을 보여줍니다.

5. 결론

이 논문은 $n=5$ 완전 피벗팅 가우스 소거법의 최대 성장 인자가 61 차 다항식의 근임을 발견하고, 그 값을 **4.1325...**로 정확히 규명했습니다. 또한, 이를 통해 $n=7$에 대한 새로운 하한선을 제시하고 $n=5$의 상한선을 4.84 로 개선했습니다. 이 연구는 수치 계산과 정밀한 대수적 기법 (그로브너 기저, 판별식, 구간 산술) 을 결합한 강력한 방법론을 제시하여, 향후 더 높은 차수 ($n>8$) 의 성장 인자 문제 해결에 중요한 토대를 마련했습니다.