Spectral Exponent Equivalence of K-matrix and Normalized Laplacian

Overview

Fan & Huang (2025)의 spectral dimension 는 degree-normalized random walk의 heat kernel로 정의된 양이다. 반면 우리가 대각화하는 K-matrix는 combinatorial Laplacian 그 자체다. 두 operator는 서로 다른 행렬이고 eigenvalue도 다르다. 이 노트는 그럼에도 두 행렬의 eigenvalue power-law exponent ()가 같다는 것을 random walk 이론 없이 선형대수만으로 보이는 논증을 정리한다. 핵심 도구는 Courant–Fischer min–max theorem과 그 따름정리인 Ostrowski’s theorem이다.

Symbol	Meaning
	adjacency matrix (, symmetric, 0/1)
	degree matrix, ,
	combinatorial (unnormalized) Laplacian,
	K-matrix of the generalized Rouse model,
	generator of the degree-normalized walk,
	symmetric normalized Laplacian,
	-th smallest eigenvalue of symmetric (오름차순)
	그래프의 최소/최대 degree
	eigenvalue exponent,
	integrated density of states,
	congruence factor,

Key Points

• 은 similarity transform으로 와 spectrum이 정확히 같다.
• 는 의 congruence transform이다. Ostrowski’s theorem에 의해 같은 index 의 eigenvalue끼리 로 sandwich된다.
• 이 bound는 에 무관한 상수 폭 의 띠이므로, log–log plot의 asymptotic slope()는 두 spectrum에서 같다.
• (backbone), (allow_multi) 또는 (nomulti)이므로 띠의 폭은 에 대해 기껏해야 으로 자란다.
• 따라서 K-matrix의 와 Fan–Huang의 는 로 연결된다.

Notes from Claude

1. 세 개의 operator와 그 관계

Loop가 있는 polymer를 그래프 로 본다. Vertex는 monomer, edge는 backbone bond와 loop bond. 모든 edge의 spring constant는 1이다.

(a) Combinatorial Laplacian.

K-matrix는 이다 (대각 성분이 ).
Generalized Rouse model 의 relaxation rate는 의 eigenvalue다.

(b) Degree-normalized generator. Fan & Huang의 simple random walk는 각 step에서 이웃을 균등하게 고른다. 전이확률 , 즉 이고 generator는

(c) Symmetric normalized Laplacian. 는 대칭행렬이 아니지만, 로 similarity transform하면

Similarity transform은 eigenvalue를 보존하므로 . 따라서 문제는 대칭행렬 두 개 과 의 spectrum 비교로 환원된다.

Similarity vs congruence

(similarity)는 eigenvalue를 보존한다. (congruence)는 일반적으로 eigenvalue를 보존하지 않고 inertia(양/음/0 eigenvalue의 개수)만 보존한다 (Sylvester’s law of inertia). 식 (3)의 첫 등호는 similarity, with 는 congruence다. 가 대각행렬이라 이고, 이므로 이 congruence는 similarity가 아니다. 그래서 과 의 eigenvalue는 다르다.

2. 왜 두 walk의 자연스러운 measure가 다른가 (counting vs degree measure)

Reversible Markov chain은 detailed balance 를 만족하는 measure 을 가진다. 이 이 heat kernel 정의 와 volume 정의 에 들어간다.

• Degree-normalized walk (): 이므로 . 이것이 degree measure이고 Fan & Huang의 가 여기서 나온다.
• Variable-speed walk (generator ): 각 edge를 따라 rate 1로 점프하므로 rate , detailed balance는 로 . 이것이 counting measure — 모든 vertex에 질량 1을 주는 measure. K-matrix가 대칭행렬인 것 자체가 counting measure에 대한 reversibility의 표현이다.

두 measure는 vertex마다 배 차이가 나고, 이므로 그 비율은 유계다. 이 유계성이 아래 spectral 논증에서 그대로 로 나타난다.

3. Rayleigh quotient와 Courant–Fischer min–max theorem

대칭행렬 의 Rayleigh quotient는

의 eigenvector 에서 이고, 일반적으로 이다 (spectral theorem으로 를 eigenbasis로 전개하면 은 들의 convex combination).

Courant–Fischer theorem. 을 의 eigenvalue라 하면, 모든 에 대해

여기서 는 의 부분공간이다.

직관: 차원 부분공간 를 “잘” 고르면 (처음 개 eigenvector가 span하는 공간) 그 안에서 Rayleigh quotient의 최댓값은 정확히 다. 다른 차원 부분공간은 반드시 이상의 Rayleigh quotient를 가지는 방향을 포함한다 (차원 세기: 이므로 두 공간은 0이 아닌 공통 벡터를 가진다). 그래서 .

이 정리가 강력한 이유는 eigenvector를 몰라도 eigenvalue를 부분공간 위의 최적화로 특징짓기 때문이다. Perturbation bound는 대부분 여기서 나온다.

4. Weyl’s inequality (참고: 이 문제에는 직접 안 맞음)

Courant–Fischer의 첫 번째 따름정리는 additive perturbation에 대한 Weyl’s inequality다. 대칭이면

즉 . 이것은 절대 오차 bound다. 우리 문제에서 을 로 두면 는 로 상수 크기이지만, 우리가 관심 있는 저 mode index의 eigenvalue는 이라 절대 오차 은 아무 정보도 주지 못한다. 필요한 것은 상대 오차 bound이고, 그것이 다음의 Ostrowski’s theorem이다.

5. Ostrowski’s theorem (congruence에 대한 상대 오차 bound)

정리. 대칭, invertible이면 각 에 대해 어떤 가 존재하여

증명 (Courant–Fischer에서 두 줄). 에 대해 로 치환하면

마지막 인수는 의 Rayleigh quotient이므로 안에 있다. 또한 가 invertible이므로 는 부분공간의 차원을 보존한다: . 따라서 식 (5)의 min–max를 에 적용하고 대신 위에서 최적화하면, 각 단계에서 이 안의 인수만큼 곱해진다. 결과가 식 (8)이다. ( 인 positive semidefinite 경우 부호 문제도 없다.)

우리 경우. 이므로 , 그 eigenvalue는 . 따라서 식 (9)를 정리하면,

이 부등식이 비교하는 것은 순위(rank) 다. 의 eigenvalue를 오름차순으로 줄 세우고 의 eigenvalue도 오름차순으로 줄 세운 뒤, 두 목록의 번째끼리 비교한다. 질량을 바꾸면 mode들이 섞이므로 의 번째 mode가 의 번째 mode”에서 왔다”고 말할 수는 없다 — 그것은 의 여러 mode의 혼합이다. 그럼에도 줄 세운 목록끼리는 위 비율 안에서 맞물린다는 것이 정리의 내용이고, 우리가 필요한 것은 순위 대 값 의 관계이므로 이것으로 충분하다.

6. Exponent가 같다는 결론

식 (10)의 양변을 으로 나누고 로그를 취하면 (로그는 단조증가라 부등호 방향 유지)

즉 차이 는 에 무관한 고정 구간 안에 있다. 이 구간의 길이를 로 두면, vs plot에서 두 곡선은 수직 폭 인 띄 안에 함께 들어간다.

Local slope에 대한 함의. 창 에서의 평균 기울기를 로 정의하면, 이므로

창의 폭 이면 우변은 0으로 간다. 따라서 asymptotic exponent는 같다: .

IDS에 대한 함의. 같은 사실을 integrated density of states로 쓰면

의 exponent는 argument를 상수배 해도 변하지 않는다.

7. 과 의 크기

이제 남는 것은 뿐이다.

• . Ring polymer의 backbone이 모든 vertex에 두 개의 edge를 보장한다 (linear chain이면 양 끝만 1).
• , allow_multi 경우. Vertex 의 degree는

각 indicator는 확률 ()의 Bernoulli이고, LRP 정의상 서로 다른 edge는 독립이므로 이것은 독립 Bernoulli의 합 (Poisson-binomial)이다. 평균은

는 와 로 모든 에서 수렴하지만 elementary closed form은 없다. 두 regime의 asymptotic:

(15b)는 이 폭 인 매끄러운 bump이므로 합을 적분으로 바꾼 것 (Euler–Maclaurin, , 는 에서 flat). 핵심 적분은 (부분적분 후 ). 수치 비교: 에서 exact , (15a) , (15b) ; 에서 exact , (15b) ; 에서 exact , (15b) . 따라서 , , .

형태의 물리적 의미: 인 이웃과는 확률 1에 가깝게 연결되므로, 큰 에서는 각 monomer가 반경 안의 모든 monomer와 붙은 “두꺼운 backbone”이 된다. 실효 lattice spacing이 로 커져 유한 에서 쓸 수 있는 scale 범위가 로 줄어든다.

독립 Bernoulli 합에 대한 Chernoff bound 와 개 vertex에 대한 union bound를 합치면, 높은 확률로

, 이면 대략 정도. 그러면 decade. 이것은 worst-case bound이고, 실제 비율 은 대부분의 에서 근처에 몰려 있을 것으로 예상된다.

• , nomulti 경우. 한 vertex당 loop 하나라는 exclusion으로 degree가 3 이하다. decade로 두 spectrum이 거의 구분되지 않는다. 다만 이 exclusion은 indicator 사이에 의존성을 만들어 그래프의 확률법칙이 LRP와 달라지므로, Fan–Huang의 정리 자체는 이 variant에 직접 적용되지 않는다. 이것은 “operator가 다르다”는 문제와 별개의, 더 근본적인 차이다.

8. 논리 사슬 정리

1. Fan & Huang: degree-normalized walk의 heat kernel exponent .
2. 그들의 annealed heat kernel bound(모든 에 대해 양쪽, 로그 보정 없음)와 translation invariance로부터 의 IDS exponent도 . (표준 Tauberian 연결.)
3. 이 노트: 이고, Ostrowski로 과 의 IDS exponent가 같다.
4. 따라서 K-matrix의 .

이 논증이 random walk 경유 argument (time change, Kumagai–Misumi framework)보다 좋은 점: realization마다 deterministic하게 성립하고 (quenched), heat kernel을 거치지 않고 eigenvalue counting 자체를 다룬다.

9. 한계

• 식 (10)은 eigenvalue만 제어한다. Eigenvector에 대해서는 아무 말도 하지 않는다. 체인이 eigenvalue counting만 쓰는 한 문제없지만, monomer별 MSD, participation ratio, localization을 논할 때는 별도 논증이 필요하다.
• 유한 에서 두 spectrum의 local slope는 서로 다른 구간에서 다르게 휠 수 있다. 식 (12)는 충분히 넓은 창에서만 의미가 있다.

Questions & Insights

• 같은 realization에서 과 (generalized eigenproblem )을 둘 다 구해 비율 을 에 대해 그리면, 이론상 이고 실제로는 근처에서 평평할 것으로 예상. nomulti와 allow_multi 둘 다 확인하면 식 (16)의 띠 폭 예측도 검증된다.
• Ostrowski의 가 실제로 어떤 분포를 가지는지 (즉 가 에 얼마나 집중되는지)는 degree의 공간적 상관과 eigenvector의 delocalization에 달려 있을 것. 이것이 eigenvector 정보 없이 얻을 수 있는 한계 지점이다.
• Fan–Huang 세팅은 infinite , 우리는 finite ring. Finite-size 효과와 boundary는 별도 고려.

Related Concepts

• K-matrix Diagonalization (Generalized Rouse Model)
• 📑 Journal reading - Spectral dimensions for one-dimensional critical long-range percolation

References

• Z. Fan, L.-J. Huang, “Spectral dimensions for one-dimensional critical long-range percolation”, arXiv:2505.15037 (2025). Theorem 1.1, Section 2 (Kumagai–Misumi framework).
• J. Ding, Z. Fan, L.-J. Huang, “The polynomial growth of effective resistances in one-dimensional critical long-range percolation”, arXiv:2504.21378 (2025). Theorem 1.1 (의 정의).
• Courant–Fischer, Weyl, Ostrowski 정리의 표준 출처: R. Horn, C. Johnson, Matrix Analysis (2nd ed.), Thm 4.2.6 (Courant–Fischer), 4.3.1 (Weyl), 4.5.9 (Ostrowski).