2025-11-24T15:25:16.688425

A stronger Sylvester's criterion for positive semidefinite matrices

Zhang, Ding

Sylvester's criterion characterizes positive definite (PD) and positive semidefinite (PSD) matrices without the need of eigendecomposition. It states that a symmetric matrix is PD if and only if all of its leading principal minors are positive, and a symmetric matrix is PSD if and only if all of its principal minors are nonnegative. For an $m\times m$ symmetric matrix, Sylvester's criterion requires computing $m$ and $2^m-1$ determinants to verify it is PD and PSD, respectively. Therefore, it is less useful for PSD matrices due to the exponential growth in the number of principal submatrices as the matrix dimension increases. We provide a stronger Sylvester's criterion for PSD matrices which only requires to verify the nonnegativity of $m(m+1)/2$ determinants. Based on the new criterion, we provide a method to derive elementwise criteria for PD and PSD matrices. We illustrate the applications of our results in PD or PSD matrix completion and highlight their statistics applications via nonlinear semidefinite program.

academic

양반정치 행렬에 대한 더 강한 Sylvester 판정법

기본 정보

논문 ID: 2501.00894
제목: A stronger Sylvester's criterion for positive semidefinite matrices
저자: Mingrui Zhang (UC Berkeley), Peng Ding (UC Berkeley)
분류: math.RA (환과 대수), math.ST (통계 이론), stat.TH (통계 이론)
발표 시간: 2025년 1월 1일 (arXiv 사전인쇄본)
논문 링크: https://arxiv.org/abs/2501.00894

초록

Sylvester 판정법은 고유값 분해 없이 정부호(PD)와 반정부호(PSD) 행렬을 판정하는 고전적 방법입니다. 고전 판정법은 다음을 요구합니다: 대칭 행렬이 정부호인 것은 모든 주도 주소행렬식이 양수인 것과 동치이며, 대칭 행렬이 반정부호인 것은 모든 주소행렬식이 음이 아닌 것과 동치입니다. $m\times m$ 대칭 행렬에 대해 Sylvester 판정법은 정부호성과 반정부호성을 검증하기 위해 $m$ 개와 $2^m-1$ 개의 행렬식을 계산해야 합니다. 주소행렬의 개수가 지수적으로 증가하기 때문에, 이 판정법은 반정부호 행렬에 대한 실용성이 제한적입니다. 본 논문은 $m(m+1)/2$ 개의 행렬식의 음이 아닌 성질만 검증하면 되는 더 강한 반정부호 행렬 Sylvester 판정법을 제안합니다. 새로운 판정법을 기반으로, 저자들은 정부호 및 반정부호 행렬의 원소별 판정법을 도출하는 방법을 제공하고 행렬 보완 및 비선형 반정규계획에서의 응용을 보여줍니다.

연구 배경 및 동기

문제 정의

본 연구는 반정부호 행렬 판정 시 고전 Sylvester 판정법의 계산 복잡도가 과도하게 높은 문제를 해결하는 것을 목표로 합니다. 구체적으로:

계산 복잡도 문제: $m\times m$ 행렬에 대해 반정부호성 검증은 $2^m-1$ 개의 주소행렬식을 확인해야 하며, 행렬 차원이 증가함에 따라 지수적으로 증가합니다
실용성 제한: 지수급의 계산량으로 인해 고전 판정법은 고차원 행렬의 반정부호성 판정에서 실용적 가치가 부족합니다
이론 완성 필요: 기존 문헌에서 Sylvester 판정법의 오용 및 부적절한 확장이 존재합니다

연구의 중요성

반정부호 행렬은 수학, 통계학, 최적화 등 다양한 분야에서 중요한 역할을 합니다:

공분산 행렬은 반정부호여야 함
반정규계획 문제의 핵심 제약 조건
행렬 보완 문제의 핵심 성질
통계 추론의 기초 도구

기존 방법의 한계

고전 Sylvester 판정법: 반정부호 행렬에 대해 $O(2^m)$ 번의 행렬식 계산 필요
고유값 분해 방법: 계산 복잡도가 높고 특정 응용에서 직관성 부족
그래프 이론 방법: 특정 구조(예: 현 그래프)에만 적용 가능하며 일반성 제한

핵심 기여

더 강한 반정부호 Sylvester 판정법 제안: 필요한 행렬식 계산을 $2^m-1$ 개에서 $m(m+1)/2$ 개로 감소
내부 포화 부분행렬 개념 도입: 새로운 판정법의 이론적 기초 제공
원소별 판정 방법 수립: 체계적인 행렬 원소 범위 결정 방법 제공
실제 응용 시연: 행렬 보완 및 비선형 반정규계획에서 방법의 유효성 검증
완전한 이론 증명 제공: 엄격한 수학 증명 및 보조정리 지원

방법 상세 설명

핵심 개념 정의

연속 주소행렬

정의 2: $m\times m$ 행렬 $X$ 와 정수 $a \leq b$ 에 대해, $X_{a:b,a:b}$ 를 $X$ 의 연속 주소행렬이라고 합니다.

내부 포화 부분행렬

정의 3: 대칭 $m\times m$ 행렬 $X$ 에 대해, $X_{I,I}$ 를 내부 포화 부분행렬로 정의합니다. 여기서 $I = \{1,m\} \cup J$ 이고, 색인 집합 $J$ 는 다음을 만족합니다:

$m \leq 2$ 일 때, $J = \emptyset$
$m \geq 3$ 일 때, $\{X_{2:(m-1),j} : j \in J\}$ 는 $X_{2:(m-1),2:(m-1)}$ 의 열 벡터의 극대 선형독립 집합

주요 정리

정리 2 (새로운 Sylvester 판정법): 대칭 $m\times m$ 행렬 $X$ 에 대해, 다음 조건들은 동치입니다:

$X$ 는 반정부호 행렬
$X$ 의 임의의 연속 주소행렬에 대해, 어떤 내부 포화 부분행렬이 음이 아닌 행렬식을 가짐
$X$ 의 임의의 연속 주소행렬에 대해, 모든 내부 포화 부분행렬이 음이 아닌 행렬식을 가짐

기술적 혁신점

복잡도 최적화: $O(2^m)$ 에서 $O(m^2)$ 로 감소
동치성 증명: 조건 (ii)와 (iii)의 동치성이 핵심 혁신
구성적 방법: 구체적인 행렬 원소 범위 결정 알고리즘 제공

원소별 판정 방법

부분 순서 관계

상삼각 원소의 부분 순서 관계 $\preceq$ 정의: $X_{i',j'} \preceq X_{i,j}$ ⟺ $i \leq i' \leq j' \leq j$

판정 절차

대각 원소: 음이 아니어야 함
k-대각 원소: 부분 순서 관계에 따라 범위 순차 결정
재귀적 결정: 연속 주소행렬의 내부 포화 부분행렬 행렬식 제약 활용

실험 설정

이론 검증

논문은 주로 수학 증명을 통해 이론의 정확성을 검증하며, 다음을 포함합니다:

세 개의 핵심 보조정리 증명
주 정리의 귀납적 증명
명제 1과 2의 구성적 증명

응용 예시

행렬 보완 문제

예 3: 부분 관측된 $5\times 5$ 대칭 행렬을 고려하며, 여기에는 3개의 누락된 원소 $x_1, x_2, x_3$ 가 포함됩니다. 새로운 판정법을 통해 누락된 원소의 가능 영역을 결정하고, 행렬이 정부호 보완을 가지는지 검증합니다.

비선형 반정규계획

예 4: 최적화 문제 $\max X_{11}^2 + X_{22}^2 + X_{33}^2 + X_{44}^2 - X_{12}X_{23}X_{34} - X_{13}X_{24} + X_{14}$ 제약 조건: $X$ 는 반정부호, $0 \leq X_{ii} \leq 1$