H9 · 비음수 행렬: 고윳값의 위치와 반복의 수렴#
1. 두 지역 사이의 이동은 어느 비율에 가까워지는가#
총인구가 일정하고 출생·사망·외부 유입을 제외한 두 지역을 생각합시다. 한 기간 동안 첫 지역 주민의 30%가 둘째 지역으로, 둘째 지역 주민의 20%가 첫 지역으로 이동합니다. 비율은 시간에 따라 변하지 않는다는 모형 가정입니다. 행렬의 행을 출발 지역, 열을 도착 지역으로 정하면
인구 비율을 행벡터 \(p_k=(a_k,1-a_k)\)로 기록합니다. 각 성분은 무차원이고 \(0\le a_k\le1\)입니다. 다음 기간에는
고정된 비율은 \(a_*=a_*/2+1/5\)를 풀어 \(a_*=2/5\)입니다. 차이를 빼면 \(a_{k+1}-2/5=(a_k-2/5)/2\)이므로
이 모형에서는 초기 비율과 무관하게 \((2/5,3/5)\)로 수렴합니다. 두 확률분포의 총변동거리는 성분 차이의 절댓값 합의 절반이므로 여기서는 \(|a_k-2/5|\)입니다. 이것도 매 기간 정확히 절반으로 줄어듭니다.
그렇다고 양방향으로 이동할 수 있다는 조건만으로 수렴하지는 않습니다. \(F=\begin{pmatrix}0&1\\1&0\end{pmatrix}\)이면 \(p_0=(1,0)\)은 \((0,1),(1,0),\ldots\)를 반복합니다. 정상분포 \((1/2,1/2)\)는 유일하지만, 정상분포의 존재·유일성과 반복의 수렴은 다른 주장입니다. \(F\)의 고윳값 \(-1\)이 이 교대를 남깁니다.
그림 85 같은 초기분포 \((1,0)\)에서 출발한 두 모형. 점은 정수 기간의 값이며 선분은 순서를 보여 주기 위한 연결이다. 정상분포는 각각 점선으로 표시했다.#
2. 고윳값을 풀지 않고 범위를 좁히기#
\(Px=\lambda x\)에서 \(|x_i|\)가 최대인 성분을 고릅니다. \(x\ne0\)이므로 \(x_i\ne0\)입니다. 그 행의 방정식을 정리하면
따라서 고윳값 하나하나는 적어도 한 행의 Gershgorin 원판 안에 있습니다. 위 \(P\)에서는 중심 \(0.7\), 반지름 \(0.3\)인 원판과 중심 \(0.8\), 반지름 \(0.2\)인 원판입니다. 실수축과 만나는 구간은 \([0.4,1]\), \([0.6,1]\)이며, 실제 고윳값 \(1,0.5\)를 포함합니다. 일반 실수행렬의 고윳값은 복소수일 수 있어 구간 대신 복소평면의 원판이라고 말합니다.
반지름이 큰 행은 단위 선택 때문일 수도 있습니다. \(A=\begin{pmatrix}2&10\\0.1&2\end{pmatrix}\)의 원래 반지름은 \(10,0.1\)이지만 \(D=\operatorname{diag}(10,1)\)에 대해
이므로 두 반지름이 모두 1입니다. 고윳값은 닮음변환으로 바뀌지 않아 중심 2, 반지름 1 안으로 범위를 좁혔습니다. 실제 값은 1과 3입니다. 양의 \(d_i\)를 쓰면 바뀐 반지름은 \(r_i(d)=\sum_{j\ne i}|a_{ij}|d_j/d_i\)입니다.
그림 86 같은 행렬의 두 좌표 표현. 좌우 축 범위를 같게 두어 스케일링 전후의 포함 영역을 비교했다. 검은 십자는 실제 고윳값이다.#
두 행을 함께 쓰는 Brauer 영역도 있습니다. 행 반지름을 \(r_i\)라 하면 어떤 서로 다른 \(i,j\)에 대해
입니다. 두 초점까지 거리의 곱을 제한하는 Cassini 영역입니다. 이 영역들의 합집합은 Gershgorin 합집합 안에 들어갑니다. 두 거리 모두 자기 반지름보다 크면 곱 부등식이 불가능하기 때문입니다. 위 \(2\times2\) 예에서는 \(|\lambda-2|^2\le1\)로 스케일링과 같은 범위를 얻습니다.
3. 비음수라는 조건은 무엇을 더 주는가#
이 단원에서 \(A\ge0\)은 모든 성분이 비음수라는 뜻입니다. H7의 양의 준정부호 순서 \(A\succeq0\)와 구별합니다. \(P\)는 성분이 모두 양수지만 대칭행렬이 아니므로 이차형식의 순서를 논하는 대상이 아닙니다.
비음수 정사각행렬은 스펙트럼 반지름 \(\rho(A)\) 자체를 고윳값으로 갖고 비음수 고유벡터를 갖습니다. 양의 성분 사이에 연결이 충분하면 더 강한 결과를 얻습니다. 행 \(i\)에서 열 \(j\)로 \(a_{ij}>0\)인 화살표를 그렸을 때 모든 꼭짓점에서 모든 꼭짓점으로 경로가 있으면 기약이라고 합니다. 기약이고 \(A\ne0\)이면 Perron 고유벡터는 모든 성분이 양수이고 \(\rho(A)>0\)은 대수적 중복도 1입니다. 그러나 \(F\)처럼 같은 절댓값의 다른 고윳값은 남을 수 있습니다.
어떤 양의 정수 \(m\)에 대해 \(A^m\)의 성분이 모두 양수이면 원시적이라고 합니다. 이 경우 나머지 고윳값은 절댓값이 \(\rho(A)\)보다 작습니다. \(P\)는 이미 모든 성분이 양수이므로 \(m=1\)로 이 조건을 만족합니다.
행확률행렬에서는 \(P\mathbf1=\mathbf1\), \(\|P\|_\infty=1\)이므로 \(\rho(P)=1\)입니다. 기약이면 양의 정상분포를 열벡터 \(\pi\)로 유일하게 정규화할 수 있고
원시적이면 \(P^k\to\mathbf1\pi^T\)입니다. \(R=P-\mathbf1\pi^T\)라 하면 \(P^k-\mathbf1\pi^T=R^k\)이고 \(\rho(R)<1\)입니다. 일반적으로 \(\rho(R)>0\)이고 가장 느린 Jordan 블록의 크기가 \(s\)일 때 상한에는 \(k^{s-1}\rho(R)^k\)가 들어갈 수 있습니다. 모든 \(r\)에 대해 \(\rho(R)<r<1\)이면 \(O(r^k)\)라는 상한은 항상 가능합니다. 대각화 가능할 때에만 곧바로 \(O(\rho(R)^k)\)라고 쓸 수 있습니다. \(\rho(R)=0\)이면 유한 번 후 \(R^k=0\)입니다. 이 구별은 H8의 비정규 반복과 같습니다.
4. 음수가 없는 생산계획은 언제 존재하는가#
두 부문의 생산을 같은 기준가격으로 평가한 금액 단위로 기록합니다. \(B_{ij}\)는 \(j\)부문의 생산 한 단위에 필요한 \(i\)부문 투입 금액입니다. 고정된 기술계수와 선형 생산을 가정하고
를 씁니다. \(d=(1,1)^T\)이면
역행렬의 성분이 비음수이므로 어느 부문의 최종수요를 늘려도 다른 생산량이 줄지 않습니다. 이 성질은 단순한 가역성보다 강합니다. 예를 들어 \(B=2I\)에서는 \(I-B=-I\)가 가역이지만 양의 수요를 넣으면 음의 생산량이 나옵니다.
위 \(B\)의 고윳값은 \(1/2,-1/5\)입니다. 기술계수를 \(t\ge0\)배 하면 \(\rho(tB)=t/2\)입니다. \(0\le t<2\)에서만 모든 비음수 수요에 대한 비음수 해가 보장됩니다. 특히 \(B\mathbf1=\mathbf1/2\)이므로 같은 수요 \(d=\mathbf1\)의 해는
\(t=2\)에서 이 수요의 해는 존재하지 않습니다. 양의 왼쪽 Perron 벡터 \(y\)를 곱하면 \(y^T(I-2B)x=0\)인데 \(y^Td>0\)이어서 모순입니다. \(t>2\)의 가역인 경우에는 위 공식의 생산량이 음수이므로 경제 모형의 허용범위를 벗어납니다.
그림 87 최종수요를 각 부문 1로 고정했다. 실선은 비음수 생산이 보장되는 \(0\le t<2\)에서만 그렸다. \(t=2\)는 포함하지 않는 경계이다.#
비대각 성분이 0 이하인 실수행렬을 Z-행렬이라고 합니다. \(M=sI-B\), \(B\ge0\), \(s>\rho(B)\) 형태는 비특이 M-행렬입니다. 이는 정확히 가역인 Z-행렬 중 \(M^{-1}\ge0\)인 것들입니다. \(I-B\)가 위 조건을 만족한다는 것은 수요에서 생산으로 가는 역변환이 성분 순서를 보존한다는 뜻입니다.
정책가치 반복도 같은 식입니다. 유한 상태의 행확률행렬 \(P\), 기간별 보상 \(r\), 할인인자 \(0\le\beta<1\)에서 \(v=r+\beta Pv\)의 해는 \(\sum_{k\ge0}\beta^kP^kr\)입니다. \(P\)의 원시성은 필요 없습니다. \(\|\beta P\|_\infty=\beta<1\)이기 때문입니다. 단위는 \(r\)와 \(v\) 모두 현재가치의 금액이고, \(v\)는 상태별 조건부 가치의 열벡터입니다.
5. 양의 주행렬식과 상보성의 범위#
Z-행렬에서는 순서대로 자른 선행 주행렬식이 모두 양수인 조건도 비특이 M-행렬과 동치입니다. 앞의 생산 예에서는 \(4/5>0\), \(\det(I-B)=3/5>0\)입니다. 이 Hawkins–Simon 조건을 일반 실수행렬에 옮겨서 역행렬이 비음수라고 결론내리면 안 됩니다. \(\begin{pmatrix}1&1\\0&1\end{pmatrix}\)는 두 선행 주행렬식이 양수지만 역행렬에 \(-1\)이 있습니다.
모든 주행렬식이 양수인 행렬을 P-행렬이라고 합니다. 선행 주행렬식만 검사하는 것과 다릅니다. 조망할 일반 결과는 “P-행렬일 필요충분조건은 모든 \(q\)에 대해 \(z\ge0\), \(w=Mz+q\ge0\), \(z_iw_i=0\)의 해가 유일한 것”입니다. 일반 비대칭 행렬에 대한 이 상보성 정리는 이 단원의 외부 결과이며 아래 계산에는 사용하지 않습니다.
여기서는 이미 증명할 수 있는 대칭 양의 정부호의 경우를 다룹니다. \(M=\begin{pmatrix}2&1\\1&2\end{pmatrix}\), \(q=(-1,1)^T\)이면 비음수 제약하의 비용 \(\frac12z^TMz+q^Tz\)를 최소화하는 해는 \(z=(1/2,0)^T\)입니다. 실제로 \(w=Mz+q=(0,3/2)^T\)이므로 두 성분의 곱이 각각 0입니다. 첫 활동은 양의 수준에서 한계비용이 0이고, 둘째 활동은 시작점에서 한계비용이 양수이므로 0에 머뭅니다. 마지막 정리에서 이 계산이 왜 유일한 최적해를 판정하는지 증명합니다.
6. 직접 확인하는 계산#
import numpy as np
P = np.array([[.7, .3], [.2, .8]])
pi = np.array([.4, .6])
p = np.array([1., 0.])
for k in range(21):
expected = pi + 2.**(-k)*.6*np.array([1., -1.])
assert np.allclose(p, expected, atol=2e-15, rtol=0)
p = p @ P
B = np.array([[.2, .3], [.4, .1]])
assert np.allclose(np.linalg.solve(np.eye(2)-B, np.ones(2)), [2, 2])
M = np.array([[2., 1.], [1., 2.]])
z = np.array([.5, 0.]); w = M@z + [-1., 1.]
assert np.all(w >= 0) and np.allclose(z*w, 0)
print("전이 반복, 생산 균형, 상보성 조건 확인")
전이 반복, 생산 균형, 상보성 조건 확인
7. 연습과 전체 풀이#
1. \(p_0=(1,0)\)에서 총변동거리를 \(0.01\) 이하로 만드는 최소 기간을 구하세요.
풀이. 거리는 \(0.6\,2^{-k}\)입니다. \(2^k\ge60\)이어야 합니다. \(2^5=32<60\le64=2^6\)이므로 최소 \(k=6\)입니다.
2. 기약인 확률행렬 \(F\)의 Cesàro 평균 \(N^{-1}\sum_{k=0}^{N-1}p_0F^k\)는 어떻게 되나요?
풀이. \(N=2m\)이면 두 상태가 정확히 \(m\)번씩 있어 평균은 \((1/2,1/2)\)입니다. \(N=2m+1\)이면 평균은 \(((m+1)/(2m+1),m/(2m+1))\)입니다. 각 성분은 \(1/2\)로 수렴합니다. 원래 수열의 수렴과 평균의 수렴은 다릅니다.
3. \(A=\begin{pmatrix}4&1&0\\1&4&0\\0&0&9\end{pmatrix}\)에서 원판만으로 고윳값 개수를 분리하세요.
풀이. 앞 두 원판은 중심 4, 반지름 1로 같고 셋째는 점 9입니다. 두 집합은 떨어져 있으므로 앞 영역에는 중복도를 세어 2개, 점 9에는 1개가 있습니다. 직접 계산하면 \(3,5,9\)입니다. 원판 하나에 하나씩 배정하는 주장은 일반적으로 성립하지 않습니다.
4. 위 생산행렬에서 첫 부문 수요만 \(h\ge0\) 늘릴 때 생산 변화는 무엇인가요?
풀이. \(\Delta d=(h,0)^T\)이므로 \(\Delta x=(I-B)^{-1}\Delta d=(3h/2,2h/3)^T\)입니다. 자기 부문에는 직접·간접 수요가 함께, 둘째 부문에는 간접 수요가 반영됩니다. 선형 모형이므로 이는 근사가 아니라 정확한 차이입니다.
5. 엄격한 행 대각우세 \(A\)에서 \(\delta=\min_i(|a_{ii}|-\sum_{j\ne i}|a_{ij}|)>0\)라 할 때 \(\|A^{-1}\|_\infty\)를 제한하세요.
풀이. \(|x_i|=\|x\|_\infty\)인 행에서 \(|(Ax)_i|\ge |a_{ii}||x_i|-\sum_{j\ne i}|a_{ij}||x_j|\ge\delta\|x\|_\infty\)입니다. 따라서 \(Ax=0\)이면 \(x=0\)이고 정사각행렬이므로 가역입니다. \(x=A^{-1}b\)를 대입하면 \(\|A^{-1}b\|_\infty\le\|b\|_\infty/\delta\), 따라서 요구한 상한은 \(1/\delta\)입니다.
6. 비대칭 \(A\ge0\)와 대칭 \(A\succeq0\)의 차이를 두 예로 보이세요.
풀이. 교환행렬 \(F\)는 성분이 비음수지만 \((1,-1)F(1,-1)^T=-2\)여서 양의 준정부호가 아닙니다. \(H=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}\)는 \(x^THx=(x_1-x_2)^2\ge0\)이지만 음의 성분을 갖습니다. 두 순서는 어느 쪽도 다른 쪽을 함의하지 않습니다.
8. 지금까지의 내용을 수학의 언어로 정리해 봅시다#
앞의 인구 이동에서는 양의 고유벡터와 수렴 조건이, 생산에서는 역행렬의 부호가 필요했습니다. 지금부터 그 연결을 증명합니다. 복소 고윳값의 존재와 Jordan 형식, H0의 유한차원 콤팩트성, H8의 Gelfand 공식과 Neumann 급수는 앞 단원에서 확보한 전제입니다.
정리 1. Gershgorin과 Brauer, 분리된 원판의 개수#
\(A\in\mathbb C^{n\times n}\), \(r_i=\sum_{j\ne i}|a_{ij}|\)라 합시다. 스펙트럼은 원판 \(D_i=\{z:|z-a_{ii}|\le r_i\}\)의 합집합 안에 있습니다. \(n\ge2\)이면 스펙트럼은 위 Cassini 영역들의 합집합에도 들어갑니다. \(m\)개 원판의 합집합이 나머지 원판과 서로 만나지 않으면 그 안의 고윳값은 대수적 중복도를 세어 \(m\)개입니다.
증명. 첫 주장은 2절의 최대 성분 계산입니다. 둘째에는 고유벡터에서 가장 큰 절댓값 성분 \(x_i\)와 두 번째 \(x_j\)를 고릅니다. \(x_j\ne0\)이면
를 곱하고 양의 \(|x_ix_j|\)를 약분합니다. \(x_j=0\)이면 유일한 비영 성분의 행에서 \(\lambda=a_{ii}\)이므로 임의의 다른 \(j\)에 대해 곱이 0입니다.
개수에는 \(A(t)=\operatorname{diag}(a_{ii})+t(A-\operatorname{diag}(a_{ii}))\), \(0\le t\le1\)를 씁니다. 모든 고윳값은 원래 원판들의 합집합 안에 있고, 두 묶음 사이에는 양의 거리가 있습니다. 다항식 계수가 연속이면 근의 다중집합도 연속입니다. 이를 여기서 확인해 봅시다. \(t_l\to t\)일 때 모든 근은 위 고정 유계 집합에 있습니다. 각 다항식의 \(n\)개 근을 임의로 나열한 벡터에서 수렴 부분수열을 고를 수 있습니다. 인수분해 \(\prod_j(z-\lambda_j(t_l))\)의 계수에 극한을 취하면 극한 근들의 중복도를 포함한 곱이 \(A(t)\)의 특성다항식입니다.
따라서 근이 경계를 건너지 않고 한 묶음의 개수가 바뀔 수는 없습니다. 개수는 국소적으로 일정하고 구간은 연결되어 전체에서 일정합니다. \(t=0\)에서는 각 대각성분이 자기 원판 안에 있고 다른 묶음에는 없으므로 개수는 \(m\)입니다. ∎
정리 2. Perron 고유벡터와 원시 행렬의 극한#
\(A\ge0\)이면 \(\rho(A)\)는 비음수 고유벡터를 갖는 고윳값입니다. \(A\)가 기약이고 \(A\ne0\)이면 \(\rho(A)>0\)이고 양의 좌우 고유벡터를 가지며 이 고윳값은 대수적으로 단순합니다. \(A\)가 원시적이면 나머지 고윳값의 절댓값은 \(\rho(A)\)보다 작습니다. \(y^Tx=1\)로 정규화한 양의 좌우 Perron 벡터에 대해 \((A/\rho(A))^k\to xy^T\)입니다.
증명: 모든 성분이 양수인 경우. 최소 행합 \(a>0\)에 대해 \(A\mathbf1\ge a\mathbf1\)입니다. 귀납하여 \(A^k\mathbf1\ge a^k\mathbf1\)이므로 Gelfand 공식에서 \(\rho\ge a>0\)입니다. \(t>\rho\)에서
비음수행렬의 전체 성분 합은 최대 행합 \(\|A^k\|_\infty\) 이상이고 이것은 \(\rho^k\) 이상입니다. 따라서 \(\|u(t)\|_\infty\ge\mathbf1^Tu(t)/n\ge1/[n(t-\rho)]\)입니다. \(t\downarrow\rho\)에서 \(u(t)/\|u(t)\|_\infty\)의 수렴 부분수열을 골라 극한 \(x\)를 취합니다. \((tI-A)u(t)=\mathbf1\)을 같은 노름으로 나누면 \((\rho I-A)x=0\)이고 \(x\ge0\), \(\|x\|_\infty=1\)입니다. \(A>0\)와 \(x\ne0\)에서 \(Ax>0\)이므로 \(x>0\)입니다.
\(D=\operatorname{diag}(x)\)와 \(S=\rho^{-1}D^{-1}AD\)를 쓰면 \(S>0\), \(S\mathbf1=\mathbf1\)입니다. \(Sz=\mu z\), \(|\mu|=1\)에서 최대 절댓값 성분의 행을 보면
등호가 모두 성립해야 합니다. 모든 가중치가 양수이므로 모든 \(z_j\)의 절댓값과 위상이 같습니다. 즉 \(z=c\mathbf1\)이고 \(\mu=1\)입니다. 이로써 주변 고윳값과 그 고유공간을 정했습니다. \(A^T\)에도 같은 존재 증명을 적용해 \(y>0\)를 얻습니다. \(\rho\)에 길이 2 이상의 Jordan 사슬이 있다면 \((A-\rho I)w=cx\), \(c\ne0\)가 있어야 합니다. 왼쪽에 \(y^T\)를 곱하면 \(0=cy^Tx\)가 되어 모순입니다. 그러므로 대수적으로도 단순합니다.
증명: 일반 비음수와 기약인 경우. \(A_\epsilon=A+\epsilon\mathbf1\mathbf1^T>0\)에 위 결과를 적용합니다. 양의 고유벡터 \(x_\epsilon\)를 최대 성분 1로 정규화하고 Perron 값을 \(r_\epsilon\)라 합시다. 행합 상한으로 \(r_\epsilon\)은 유계입니다.
\(Ax_\epsilon\le r_\epsilon x_\epsilon\)이므로 가중 최대노름에서 \(\|A\|\le r_\epsilon\), 따라서 \(\rho(A)\le r_\epsilon\)입니다. \(\epsilon\downarrow0\)인 수렴 부분수열을 고르면 \(Ax=rx\), \(x\ge0\), \(\|x\|_\infty=1\), \(r\ge\rho(A)\)입니다. \(r\)는 고윳값이므로 반대 부등식도 성립하여 \(r=\rho(A)\)입니다.
기약이고 \(A\ne0\)이면 그래프에 양의 길이의 닫힌 경로가 있습니다. 경로 길이를 \(l\), 변 가중치 곱을 \(c>0\)라 하면 \((A^{kl})_{ii}\ge c^k\)이므로 Gelfand 공식에서 \(\rho(A)\ge c^{1/l}>0\)입니다. \(x_i=0\)이라면 \(\sum_j a_{ij}x_j=\rho x_i=0\)에서 \(i\)로부터 한 단계 도달하는 모든 \(j\)에 \(x_j=0\)입니다. 경로를 따라 반복하면 모든 성분이 0이어야 하므로 모순입니다. 따라서 \(x>0\)이며 전치도 기약이어서 \(y>0\)입니다.
위 확률행렬 닮음 \(S\)에서 \(Sz=z\)인 고유벡터를 생각해 봅시다. 최대 절댓값 행의 등호는 그 행의 양의 가중치가 있는 모든 \(z_j\)가 \(z_i\)와 같음을 뜻합니다. 기약성을 따라 전파하면 \(z\)는 상수벡터입니다. 따라서 Perron 고유공간은 1차원이며 왼쪽 벡터를 사용한 Jordan 사슬 모순으로 대수적으로도 단순합니다.
증명: 원시적 경우. \(A^m>0\)이면 그 양의 행렬의 주변 고윳값은 \(\rho(A)^m\) 하나뿐입니다. \(Az=\lambda z\), \(|\lambda|=\rho(A)\)이면 \(A^mz=\lambda^mz\)입니다. \(A^m\)의 주변 고유공간은 \(x\)가 생성하는 1차원이므로 \(z=cx\), 따라서 \(\lambda=\rho(A)\)입니다. \(\ker y^T\)는 \(A\)-불변이고 전체 공간은 \(\operatorname{span}(x)\oplus\ker y^T\)입니다. 둘째 공간에서 \(A/\rho(A)\)의 스펙트럼 반지름은 1 미만이므로 H8에 의해 거듭제곱이 0으로 갑니다. 첫 공간에서 항등이고, 이 직합의 사영은 \(xy^T\)이므로 극한이 증명됩니다. ∎
정리 3. 비특이 M-행렬의 동치 조건#
Z-행렬 \(M\)에 대해 다음은 동치입니다. (i) \(M=sI-B\), \(B\ge0\), \(s>\rho(B)\); (ii) \(M\)이 가역이고 \(M^{-1}\ge0\); (iii) 어떤 \(v>0\)에 대해 \(Mv>0\); (iv) 모든 선행 주행렬식이 양수. 이 조건들은 \(M\)의 모든 고윳값의 실수부가 양수라는 조건과도 동치입니다.
증명. (i)에서 \(s>0\)이고 Neumann 급수 \(M^{-1}=s^{-1}\sum_{k\ge0}(B/s)^k\ge0\)이므로 (ii)입니다. (ii)에서 \(v=M^{-1}\mathbf1\)을 택합니다. 비음수인 가역행렬에는 영행이 없으므로 각 행합이 양수이고 \(v>0\), \(Mv=\mathbf1>0\)입니다.
(iii)에서는 \(s>0\)를 모든 \(m_{ii}\) 이상으로 잡아 \(B=sI-M\ge0\)로 씁니다. \(Bv=sv-Mv<sv\)이므로 \(D=\operatorname{diag}(v)\)에 대해 \(\|D^{-1}BD\|_\infty=\max_i(Bv)_i/v_i<s\)입니다. 따라서 \(\rho(B)<s\)여서 (i)입니다.
(iii)을 주부분행렬 \(M_{JJ}\)에 제한하면 \(M_{JJ}v_J\ge(Mv)_J>0\)입니다. 빠진 비대각항이 비양수이기 때문입니다. 앞 동치로 모든 주부분행렬도 (i)를 만족합니다. 고윳값은 \(s-\lambda(B_J)\)여서 실수부가 양수입니다. 실수 고윳값은 양수이고 비실수 고윳값은 켤레쌍으로 곱이 양수이므로 행렬식은 양수입니다. 이로써 (iv)도 얻었습니다.
(iv)에서 (ii)는 차수 귀납으로 증명합니다. \(n=1\)은 양의 수의 역수입니다. \(n>1\)일 때 \(a=m_{11}>0\)이고 \(M=\begin{pmatrix}a&r^T\\c&E\end{pmatrix}\), \(r,c\le0\)라 씁니다. Schur 보원 \(S=E-ca^{-1}r^T\)도 Z-행렬이며, 각 선행 주행렬식은 \(M\)의 한 차수 큰 선행 주행렬식을 \(a\)로 나눈 것이므로 양수입니다. 귀납으로 \(S^{-1}\ge0\)이고 블록 역행렬은
각 곱의 부호를 확인하면 좌상단은 양수에 비음수를 더하고, 비대각 블록은 비양수에 마이너스를 붙인 것입니다. 마지막으로 (i)는 이미 고윳값의 실수부가 양수임을 보였습니다. 역으로 \(B=sI-M\ge0\)로 쓰면 Perron 값 \(\rho(B)\)에 대응하는 \(M\)의 실수 고윳값 \(s-\rho(B)\)가 양수여야 하므로 (i)입니다. ∎
정리 4. 대칭 양의 정부호 상보성 문제#
실수 \(M=M^T\succ0\)와 임의의 \(q\)에 대해 비음수 상보성 문제는 유일한 해를 갖습니다. 그 해는 \(z\ge0\)에서 \(f(z)=\frac12z^TMz+q^Tz\)의 유일한 최소점입니다.
증명. \(f(z)\ge\frac12\lambda_{\min}(M)\|z\|_2^2-\|q\|_2\|z\|_2\)이므로 \(\|z\|\to\infty\)에서 \(f\to\infty\)입니다. 따라서 \(f(0)\) 이하인 비음수 부분수준집합은 비어 있지 않은 닫힌 유계집합이고 최소점이 존재합니다. 서로 다른 \(u,v\)와 \(0<t<1\)에 대해
이므로 두 최소점은 있을 수 없습니다. 최소점에서 \(w=Mz+q\)라 합시다. \(z_i>0\)이면 양·음의 작은 좌표변화가 모두 허용되어 \(w_i=0\)입니다. \(z_i=0\)이면 양의 변화에 대한 우미분이 \(w_i\ge0\)이어야 합니다. 따라서 상보성 조건이 필요합니다. 역으로 그 조건을 만족하면 임의의 \(u\ge0\)에서
\(u\ne z\)이면 둘째 항이 양수이므로 충분성과 유일성도 확인됩니다. ∎
비음수성과 연결 구조는 장기 분포와 양의 해에 관한 결론을 보강합니다. 다음 장부터는 이러한 수학적 대상을 유한 정밀도의 수로 계산할 때 생기는 오차를 따로 분석합니다. N1로 이어 읽기.