M-행렬

1. 개요

M-행렬 M-matrix
정의	A = sI − B, B ≥ 0, s ≥ ρ(B)
부호 패턴	비대각 ≤ 0 (Z-행렬), 대각 > 0
핵심 성질	역행렬의 모든 원소 ≥ 0 (정칙일 때)
대칭판	스틸티어스 행렬
이름	오스트롭스키(1937), 민코프스키를 기려
등장처	확산 이산화, 풍상 대류, 마르코프 연쇄, 레온티예프 모형

양수 원천을 넣으면 양수 해가 나온다. 당연해 보이는 이 성질을 이산화가 지켜 주는지 판정하는 행렬 클래스다.

M-행렬(M-matrix)은 비대각 원소가 모두 0 이하인 정사각행렬(Z-행렬) 중에서 $A = sI - B$, $B \ge 0$(원소별), $s \ge \rho(B)$ 로 쓸 수 있는 것이다. $s > \rho(B)$ 이면 정칙 M-행렬이라 하고, 이때 $A^{-1}$ 의 모든 원소가 0 이상이다. 1937년 오스트롭스키가 대각 우세 행렬식을 연구하면서 정의했고, 이름의 M 은 민코프스키에서 따왔다¹.

시뮬레이션에서 이 클래스가 중요한 이유는 하나로 모인다 — 이산 시스템이 M-행렬이면 이산 최대 원리가 성립한다. 확산 방정식을 풀었는데 온도가 경계값보다 낮게 찍히거나 농도가 음수로 나온다면, 거의 언제나 범인은 M-행렬 성질이 깨진 이산화다. 같은 성질이 야코비·가우스-자이델 수렴, 불완전 촐레스키 분해의 존재, 고전 대수적 다중격자의 이론까지 받친다.

2. 정의와 동치 조건

$A$ 가 Z-행렬일 때 다음은 모두 ”$A$ 는 정칙 M-행렬”과 동치다(일부).

• $A^{-1}$ 이 존재하고 $A^{-1} \ge 0$ (역양성, inverse-positive).
• 모든 고유값의 실수부가 양수.
• 모든 주소행렬식(principal minor)이 양수.
• 어떤 벡터 $\mathbf x > 0$ 에 대해 $A\mathbf x > 0$ (준양성, semipositive).
• 대각이 양수인 $LU$ 분해가 피벗 없이 존재.
• $A$ 의 모든 정규 분할 $A = M - N$ ($M^{-1} \ge 0$, $N \ge 0$)에 대해 $\rho(M^{-1}N) < 1$.

버먼-플레먼스는 이런 동치 조건을 50개 모아 정리했다. 실무에서 가장 자주 쓰는 충분조건은 이거다.

대각이 양수인 Z-행렬이 엄격 대각 우세이거나, 기약이면서 대각 우세이고 한 행 이상에서 엄격하면 정칙 M-행렬이다.

디리클레 경계가 있는 포아송 방정식의 5점 차분 행렬이 정확히 두 번째 경우다(내부 행은 대각 4, 이웃 −1 넷으로 등호, 경계 옆 행은 엄격). 실제로 $10\times10$ 격자에서 $A^{-1}$ 의 최소 원소는 $2.5\times10^{-4} > 0$ — 모든 원소가 엄격히 양수다. 한 점의 열원이 영역 전체를 데운다는 확산의 물리가 행렬에 그대로 찍혀 있다.

대칭이고 정칙인 M-행렬은 스틸티어스 행렬이라 따로 부르며, 이건 대칭 양정치 Z-행렬과 같은 말이다.

3. 이산 최대 원리 — 왜 시뮬레이션에서 중요한가

$A\mathbf u = \mathbf f$ 에서 $A^{-1} \ge 0$ 이면 $\mathbf f \ge 0 \Rightarrow \mathbf u \ge 0$ 이다. 경계값을 우변으로 넘긴 형태에 적용하면 “내부 해는 원천이 없을 때 경계값의 최소·최대 사이에 있다”는 이산 최대 원리가 된다. 연속 문제의 최대 원리를 이산 문제가 물려받는지가 곧 M-행렬 여부다.

3.1. 검산 — 1차원 대류-확산

$-\varepsilon u'' + c u' = 0$, $u(0) = 0$, $u(1) = 1$ 의 정해는 0과 1 사이의 단조 함수다. 내부 19점, 격자 페클레 수 $\mathrm{Pe}_h = ch/\varepsilon$ 로 두 가지 이산화를 비교했다($\varepsilon/h^2$ 를 곱한 3대각 계수).

• 중앙차분: $\bigl(-(1 + \tfrac{\mathrm{Pe}_h}{2}),\ 2,\ -(1 - \tfrac{\mathrm{Pe}_h}{2})\bigr)$
• 1차 풍상: $\bigl(-(1 + \mathrm{Pe}_h),\ 2 + \mathrm{Pe}_h,\ -1\bigr)$

$\mathrm{Pe}_h$	방식	M-행렬?	$\min u$	$\min (A^{-1})_{ij}$	야코비 $\rho$
1	중앙	예	0.000	$1.2\times10^{-9}$	0.855
4	중앙	아니오	−0.333	−0.111	1.711
4	풍상	예	0.000	$4.2\times10^{-14}$	0.736
10	중앙	아니오	−0.667	−0.111	4.839
10	풍상	예	0.000	$1.5\times10^{-20}$	0.546

$\mathrm{Pe}_h > 2$ 가 되는 순간 중앙차분의 위쪽 비대각이 양수로 바뀌어 Z-행렬이 아니게 되고, 세 가지가 동시에 터진다. 해가 0 아래로 내려가 진동하고($u \ge 0$ 이어야 할 곳에서 −0.67), 역행렬에 음수 원소가 생기고, 야코비 반복이 발산한다. 풍상차분은 정확도가 1차로 떨어지는 대신 모든 $\mathrm{Pe}_h$ 에서 M-행렬을 지킨다 — 이게 풍상차분이 수치확산이라는 욕을 먹으면서도 살아남은 이유이고, 고차 도식들이 전변분 감소 제한자로 이 성질을 국소적으로 되찾으려는 이유다. ($\mathrm{Pe}_h = 2$ 정확히에서는 중앙차분 위쪽 계수가 0이 되어 경계값 정보가 상류로 전혀 안 올라간다.)

3.2. 유한요소에서 — 둔각 금지

P1 선형 유한요소법의 라플라스 강성행렬은 내부 변 $ij$ 에 대해

$$K_{ij} = -\tfrac12\bigl(\cot\alpha_{ij} + \cot\beta_{ij}\bigr)$$

이다. $\alpha, \beta$ 는 그 변을 마주 보는 두 각이다. $K_{ij} \le 0$ 이려면 $\alpha + \beta \le \pi$ 여야 하고, 이건 2차원에서 정확히 들로네 삼각분할의 조건이다. 둔각 삼각형이 하나도 없으면(모든 각 ≤ 90°) 충분하다(치아를레-라비아르 1973). 꼭짓점 $(0,0), (1,0), (0.5, 0.2)$ 인 납작한 삼각형 하나만 만들어도 꼭짓점 각이 약 136° 라 그 각을 마주 보는 원소가 $K_{01} = +0.525$ 로 양수가 된다. 3차원 사면체에서는 들로네여도 이 보장이 안 되어 메시 품질 조건이 더 까다롭다².

4. 반복법과 전처리 — 존재 보장

• 분할 반복. M-행렬이면 야코비·가우스-자이델은 수렴한다(둘 다 정규 분할이다). 스타인-로젠베르크 정리에 따르면 야코비 반복행렬이 음 아닌 행렬일 때 둘은 함께 수렴하거나 함께 발산하고, 수렴하면(둘 다 0 인 자명한 경우를 빼고) $\rho_{\mathrm{GS}} < \rho_{\mathrm{J}} < 1$ 이다. 정규 분할끼리는 $M$ 이 “더 큰” 쪽이 더 빨리 수렴한다는 비교 정리도 있다.
• 불완전 분해. 메이에링크-판데르포르스트(1977)는 M-행렬이면 어떤 희소 패턴을 고르든 불완전 LU·불완전 촐레스키 분해가 존재하고 그 결과가 정규 분할임을 보였다. ICCG 가 탄생한 바로 그 논문이다. M-행렬을 벗어나면 피벗이 음수가 되어 분해가 죽을 수 있고, 그래서 전처리기 실무에 시프트 처방이 붙는다.
• 대수적 다중격자. 루게-스튀벤 계열 고전 다중격자법 AMG 의 강결합 판정과 보간 공식은 M-행렬(또는 그 근방)을 가정하고 유도됐다. 비대각에 양수가 섞이면 성능이 떨어지는 이유다.

5. 다른 분야의 M-행렬

• 경제학. 레온티예프 투입-산출 모형 $(I - A)\mathbf x = \mathbf d$ 에서 $A \ge 0$ 이 투입계수다. 모든 최종 수요 $\mathbf d \ge 0$ 에 대해 생산량 $\mathbf x \ge 0$ 이 존재할 조건(호킨스-사이먼 조건)이 바로 ”$I - A$ 가 정칙 M-행렬”이다.
• 마르코프 연쇄. 연속시간 생성자의 부호를 뒤집은 $-Q$, 그리고 $I - P$ ($P$ 는 확률행렬)는 특이 M-행렬이다. 흡수 확률·평균 흡수 시간을 구하는 기본 행렬 $(I - P_{\text{과도}})^{-1} \ge 0$ 이 M-행렬 역양성의 직접 응용이다.
• 그래프 라플라시안. $L = D - W$ 는 특이 M-행렬이고 영공간이 상수 벡터다. 디리클레 경계를 한 점이라도 걸면 정칙이 된다.
• 스펙트럼 반지름과 페론-프로베니우스 정리. 정의의 $s \ge \rho(B)$ 가 페론 고유값 이야기라, 이론 전개는 거의 전부 음 아닌 행렬 이론 위에 서 있다³.

6. 관련 문서

• 반복법 · 불완전 촐레스키 · 전처리기 · 다중격자법 · 쌍켤레 기울기법
• 포아송 방정식 · 대류-확산 방정식 · 페클레 수 · 풍상차분 · 이산 최대 원리
• 유한요소법 · 들로네 삼각분할 · 스펙트럼 반지름 · 페론-프로베니우스 정리 · 대각 우세 행렬

7. Footnotes

1. 그래서 M 이 Matrix 의 M 이 아니다. 행렬 이름에 사람 이니셜 하나만 박아 두는 건 지금 기준으로 보면 꽤 힙한 작명이다. ↩

2. 3차원에서 “모든 이면각이 예각인 사면체 메시”를 일반 형상에 만드는 건 사실상 불가능에 가깝다. 그래서 3차원 비음수 보장은 메시가 아니라 도식(제한자, 대수적 보정) 쪽에서 해결하는 경우가 많다. 메시 생성기 탓만 하는 건 반칙이다. ↩

3. M-행렬 이론은 페론-프로베니우스 정리를 거꾸로 세운 것에 가깝다. 음 아닌 행렬 $B$ 를 대각에서 빼면 M-행렬, 그 역행렬은 다시 음 아닌 행렬. 부호 두 번 뒤집으면 원위치라는 국룰이다. ↩