Computing Left Eigenvalues of Quaternion Matrices

1. 문제 정의 (Problem Statement)

• 좌측 고유값의 정의: 쿼터니언 행렬 $A \in \mathbb{H}^{n \times n}$에 대해, $Av = \lambda v$를 만족하는 0 이 아닌 벡터 $v \in \mathbb{H}^n$과 쿼터니언 $\lambda \in \mathbb{H}$를 좌측 고유값이라고 합니다.
• 주요 난제:
  1. 비가환성: 쿼터니언의 곱셈 순서가 바뀌면 결과가 달라지므로, 복소수 행렬에서와 같은 대칭성이나 고유값의 불변성이 성립하지 않습니다.
  2. 게이지 자유도 (Gauge Freedom): 고유벡터 $v$는 오른쪽에서 임의의 0 이 아닌 쿼터니언 $q$를 곱해도 ($v \to vq$) 고유값 $\lambda$가 변하지 않습니다. 이로 인해 수치 계산 시 해가 고립되지 않고 연속적인 궤적을 이룰 수 있어, 표준적인 뉴턴 방법 적용이 어렵습니다.
  3. 스펙트럼의 복잡성: 좌측 스펙트럼은 고립된 점 (isolated points) 만 있는 것이 아니라, 구면 (spherical) 형태의 연속체 (continua) 를 포함할 수 있으며, $n \times n$ 행렬의 경우 $n$개보다 많거나 적은 개수의 고립된 고유값을 가질 수도 있습니다.
  4. 계산적 비용: 행렬식 기반의 소거법 (determinantal elimination) 은 고차 다항식 문제로 이어져 $n$이 커질수록 계산 비용과 수치적 민감도가 급격히 증가합니다.

2. 방법론 (Methodology)

논문은 직접적인 고유쌍 (Eigenpair) 공식화와 **실수 임베딩 (Real Embedding)**을 결합한 뉴턴 방법을 제시합니다.

• 게이지 제약 (Gauge Constraint) 도입:

  • 고유벡터의 오른쪽 스케일링 자유도를 제거하기 위해 게이지를 고정합니다.
  • 구체적으로, 고유벡터의 노름을 1 로 고정 ($\|x\|_2 = 1$) 하고, 특정 피벗 성분 $x_j$가 실수이며 양수 ($x_j \in \mathbb{R}_{>0}$) 가 되도록 4 개의 실수 제약 조건을 부과합니다.
  • 이를 통해 비선형 방정식 $Ax - \lambda x = 0$을 정방 (square) 시스템으로 변환합니다.

• 실수 임베딩 (Real Embedding):

  • 쿼터니언 연산을 직접 처리하는 대신, 쿼터니언을 $4 \times 4$ 실수 행렬로 매핑하는 임베딩 $\rho(\cdot)$을 사용합니다.
  • $n \times n$ 크기의 쿼터니언 행렬은 $4n \times 4n$ 크기의 실수 행렬로 변환되어, 표준적인 실수 선형대수 솔버 (LU 분해, SVD 등) 를 사용할 수 있게 합니다.
  • 뉴턴 보정 단계는 구조화된 실수 선형 시스템으로 귀결됩니다.

• 뉴턴 반복 및 다중 시작 전략 (Multi-start Strategy):

  • 게이지가 고정된 시스템에 대해 뉴턴 방법을 적용하여 국소 2 차 수렴 (local quadratic convergence) 을 달성합니다.
  • 전역 해를 찾기 위해 무작위 초기값을 여러 번 시도 (multi-start) 하고, 수렴된 해를 중복 제거 (de-duplication) 하여 고유값 집합을 구성합니다.
  • 구면 성분 감지: 수렴된 점들이 구면 상에 분포하는지 확인하기 위해 클러스터링과 구면 피팅 (sphere fitting) 알고리즘을 적용하여 연속적인 스펙트럼 성분을 탐지합니다.

• 잔차 기반 인증 (Residual Certificates):

  • 계산된 고유값의 정확도를 검증하기 위해 $\text{res}(A, \lambda, v) = \|Av - \lambda v\|_2$ 및 최소 잔차 $\text{res}_{\min}(A, \lambda) = \sigma_{\min}(\rho(A - \lambda I))$를 계산하여 수치적 신뢰도를 보장합니다.

3. 주요 기여 (Key Contributions)

1. 효율적인 뉴턴 반복식 유도: 고유벡터의 게이지를 명시적으로 고정하여 실수 해석적 시스템을 구성하고, 이를 통해 국소 2 차 수렴을 보장하는 뉴턴 반복식을 유도했습니다.
2. 강건한 솔버 개발: 다중 시작 전략, 재시작 (restart), 중복 제거 로직을 포함한 전역 솔버를 구축하여, 비정형적인 스펙트럼 상황 (고립되지 않은 해, 스펙트럼 결핍 등) 에서도 재현 가능한 결과를 제공합니다.
3. 광범위한 검증:
   • 문헌에 알려진 2x2 및 3x3 행렬 예시 (구면 스펙트럼 포함) 에 대한 검증.
   • 밀집 (dense), 에르미트 (Hermitian), 삼각 (triangular), 희소 (sparse) 행렬 등 다양한 벤치마크 집합에 대한 몬테카를로 실험 (최대 $64 \times 64$ 크기까지).
4. 오픈 소스 구현체 제공: 재현성과 독립적 검증을 위해 MATLAB 기반의 경량 참조 구현체 (stand-alone reference implementation) 를 공개했습니다.

4. 실험 결과 (Results)

• 정확도: 제안된 방법은 $64 \times 64$ 크기까지의 행렬에서 기계 정밀도 (machine precision) 수준의 잔차를 갖는 고유쌍을 성공적으로 계산했습니다.
• 비정형 현상 탐지:
  • $n$개 초과 고유값: $3 \times 3$ 행렬에서 5 개의 고립된 좌측 고유값이 존재하는 경우를 발견하고 정확하게 계산했습니다.
  • 스펙트럼 결핍 (Left-spectrum deficiency): $4 \times 4$ 행렬에서 4 개가 아닌 2 개의 고립된 고유값만 존재하는 경우를 탐지했습니다.
  • 구면 성분: 연속적인 구면 스펙트럼을 가진 경우, 뉴턴 방법이 무작위 초기값에 따라 구면 상의 서로 다른 점들로 수렴하는 것을 관찰하고, 이를 통해 구면 성분을 성공적으로 식별 및 파라미터화했습니다.
• 성능: 표준 실수 선형대수 커널만 사용하여 구현이 간단하며, 대규모 행렬에서도 효율적으로 작동함을 확인했습니다.

5. 의의 및 중요성 (Significance)

• 실용적 접근: 이론적인 분류보다는 실제 계산 가능한 방법을 중시하여, 공학 및 제어 이론에서 쿼터니언 행렬을 다루는 연구자들에게 신뢰할 수 있는 도구를 제공합니다.
• 수치적 안정성: 비가환성으로 인한 수치적 불안정성을 게이지 고정과 실수 임베딩을 통해 효과적으로 해결했습니다.
• 새로운 통찰: 기존에는 잘 알려지지 않았던 고차 쿼터니언 행렬의 스펙트럼 특성 (예: $n$개보다 많은 고유값, 스펙트럼 결핍, 혼합된 구면/고립 구조) 을 수치적으로 탐지하고 문서화함으로써, 해당 분야의 이론적 이해를 확장하는 데 기여합니다.
• 재현성: 공개된 코드와 상세한 실험 프로토콜을 통해 다른 연구자들이 결과를 검증하고 확장할 수 있는 기반을 마련했습니다.

결론적으로, 이 논문은 쿼터니언 행렬의 좌측 고유값 계산이라는 난제를 뉴턴 방법과 실수 임베딩을 통해 체계적으로 해결하며, 다양한 비정형 스펙트럼 현상을 탐지할 수 있는 강력한 계산 프레임워크를 제시했습니다.