SNT-Rank: Kronecker Products and Euclidean Distance Matrices

기술 요약: "SNT-RANK: 크로네커 곱과 유클리드 거리 행렬"

문제 정의
본 논문은 대칭 비음수 행렬(symmetric nonnegative matrices)의 **대칭 비음수 삼인수 분해(Symmetric Nonnegative Trifactorization, SN-Trifactorization)**를 조사한다. Bukovšek–Šmigoc에 의해 도입된 SN-Trifactorization은 $A \in S^+_n$에 대하여 $A = BCB^T$ (여기서 $B \in \mathbb{R}^{n \times k}_+$, $C \in S^+_k$) 형태를 갖는다. SNT-rank는 $st_+(A)$로 표기하며, 이러한 인수 분해가 존재하는 가장 작은 정수 $k$로 정의된다. SNT-rank는 행렬의 차원에 의해 제한되며 고전적 계수($rk$), 비음수 계수($rk_+$), 그리고 완전 양수 계수($cp$)와 관련이 있는 것으로 알려져 있으나, 그 정확한 값을 결정하는 것은 특히 유클리드 거리 행렬(EDM)에 대해 어려운 문제로 남아 있다. 본 논문은 세 가지 주요 과제를 다룬다:

1. 특정 EDM 가계, 특히 $A(1, \dots, n)$에 대한 SNT-rank의 더 정교한 상한(upper bounds) 도출.
2. 크로네커 곱(Kronecker product) 하에서의 SNT-rank의 거동 확립.
3. 크로네커 곱 하에서의 비음수 계수의 곱셈성(multiplicativity) 조사, 특히 $rk_+(A_1 \otimes A_2)$에 관한 추측 해결.

방법론
저자들은 대수적 행렬 이론, 조합론적 논증, 그리고 대칭 비음수 행렬의 구조적 분석을 결과적으로 결합하여 사용한다. 주요 방법론적 구성 요소는 다음과 같다:

• 구조적 분해: 본 논문은 주부분행렬(principal submatrices), 직합(direct sums), 그리고 합동 변환(congruence transformations, 치환 및 양의 대각 스케일링)의 성질을 활용하여 복잡한 행렬의 SNT-rank를 더 단순한 구성 요소들과 연관시킨다.
• 크로네커 곱 분석: 저자들은 $A_1$과 $A_2$의 인자들로부터 인수들을 구성함으로써 크로네커 곱 $A_1 \otimes A_2$의 SN-Trifactorization을 분석한다. 이들은 $(B_1 C_1 B_1^T) \otimes (B_2 C_2 B_2^T) = (B_1 \otimes B_2)(C_1 \otimes C_2)(B_1 \otimes B_2)^T$라는 항등식을 활용한다.
• EDM을 위한 재귀 관계: 유클리드 거리 행렬의 경우, 저자들은 특정한 블록 구조를 구축한다. 인덱스를 재배열하고 행렬을 작은 행렬들의 크로네커 곱(예: $\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$ 및 $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$)을 포함하는 블록 합으로 분해함으로써, SNT-rank에 대한 재귀 관계를 도출한다.
• 계수 부등식: 증명 과정에서 $rk$, $rk_+$, $st_+$를 연결하는 기성 부등식과 대각 성분이 0이고 비대각 성분이 양수인 행렬에 관한 특정 보조정리들을 빈번하게 사용한다.

주요 기여 및 결과

1. 유클리드 거리 행렬에 대한 개선된 상한:
   본 논문은 특정 EDM인 $A(1, \dots, n)$의 SNT-rank에 대해 기존에 알려진 상한을 개선한다. Shitov가 이전에 $st_+(A(1, \dots, n)) \le 4 \log_2 n + 4$임을 밝힌 반면, 저자들은 다음을 증명한다:
   $$st_+(A(1, \dots, n)) \le 2 \lceil \log_2 n \rceil$$
   이 결과는 정수 파라미터를 갖는 $A(x_1, \dots, x_n)$ 및 유리수 파라미터를 갖는 더 넓은 범위의 EDM 클래스로 확장되며, 파라미터의 범위에 의존하는 상한을 제공한다.

2. SNT-rank의 하위 곱성(Submultiplicativity):
   저자들은 SNT-rank가 크로네커 곱에 대해 하위 곱성을 가짐을 확립한다. 임의의 $A_1 \in S^+_{n_1}$ 및 $A_2 \in S^+_{n_2}$에 대하여:
   $$rk(A_1)rk(A_2) \le st_+(A_1 \otimes A_2) \le st_+(A_1)st_+(A_2)$$
   또한, $n_1, n_2 \le 3$인 경우 $st_+(A_1 \otimes A_2) = st_+(A_1)st_+(A_2)$가 성립함을 증명한다. 또한, 적어도 하나의 행렬이 계수 1을 가지면, 곱의 SNT-rank는 SNT-rank들의 곱과 같음을 보여준다.

3. 구조적 가정 하에서의 비음수 계수의 곱셈성:
   $rk_+(A_1 \otimes A_2) = rk_+(A_1)rk_+(A_2)$라는 추측(Vandaele 등에 의해 일반적인 경우에는 거짓임이 입증됨)을 다루며, 본 논문은 다음의 특정 조건 하에서 이 항등식이 성립함을 증명한다:

• $A_1$ 또는 $A_2$ 중 적어도 하나가 계수 1을 갖는 경우.
• 각 행렬 $A_i$에 대하여 행 또는 열의 수가 3 이하인 경우(즉, $m_i \le 3$ 또는 $n_i \le 3$). 이 경우, 결과는 차원이 $\le 3$인 행렬에 대해 비음수 계수가 고전적 계수와 일치한다는 사실에 기초한다.

4. 하한 및 구조적 성질:
   본 논문은 대각 성분이 0이고 비대각 성분이 양수인 대칭 비음수 행렬의 SNT-rank에 대한 하한을 제공하며, $st_+(A) \ge \min \{k : n \le \binom{k}{\lfloor k/2 \rfloor}\}$임을 보여준다. 이는 $n=4$일 때 $st_+(A) = 4$임을 의미한다. 또한, 저자들은 차수가 $n \le 3$인 행렬의 경우 SNT-rank가 고전적 계수와 정확히 일치함을 보여주는데, 이는 $n \ge 4$에서는 실패하는 성질이다.

의의
본 논문은 대칭 비음수 행렬의 저계수 구조(low-rank structures)에 대한 이론적 이해에 기여한다. 유클리드 거리 행렬의 SNT-rank에 대한 상한을 조임으로써, 이러한 특정 구조들에 대한 계산 복잡도 지형을 정교화한다. 크로네커 곱 하에서 SNT-rank의 하위 곱성을 확립한 것은 제어된 SNT-rank를 가진(예: SNT-rank가 최대 9인) 대칭 비음수 행렬을 구성하기 위한 새로운 도구를 제공한다. 마지막으로, 특정 차원 또는 계수 제약 조건 하에서 비음수 계수의 곱셈성을 해결함으로써, 본 연구는 Dagstuhl Seminar Report에서 제기된 추측의 경계를 명확히 하고, 비음수 계수가 곱셈적으로 동작하는 정확한 조건을 제시한다.