선형대수(Linear algebra)

연립일차방정식과 역행렬(Linear systems and inverse matrices)

Ax = b는 두 직선의 교점(행 그림)이자, 열들을 몇 개씩 더해 b를 만드는 문제(열 그림)다. det ≠ 0이면 역행렬⁠(inverse matrix)⁠이 되돌린다.

A\vec x = \vec b \;\Rightarrow\; \vec x = A^{-1}\vec b, \quad A^{-1} = \frac{1}{ad - bc}\begin{bmatrix} d & -b \\ -c & a \end{bmatrix}

먼저 보면 좋은 개념행렬 행렬식

연립방정식 $ax + by = e,\ cx + dy = f$ 는 두 그림으로 볼 수 있습니다. 왼쪽은 행 그림입니다. 각 방정식이 직선이고 해는 교점입니다. 오른쪽은 열 그림입니다. 행렬⁠(matrix)⁠의 두 열을 각각 x개, y개 이어 붙여 목표 $\vec b$ 에 닿는 조합을 찾습니다. 오른쪽의 목표점 b를 끌어 보세요. 지금 해는 입니다.

왼쪽: 두 직선과 교점. 오른쪽: 초록 열 x개 + 빨간 열 y개 = b. 둘은 같은 방정식입니다.

행렬을 로 바꿔 보세요. 행렬식⁠(determinant)⁠이 0이면 두 직선이 평행하거나 아예 겹치고, 두 열이 한 직선 위에 놓여 평면을 다 덮지 못합니다. b가 그 직선 위에 없으면 해가 없고, 있으면 해가 무한히 많습니다. 행렬식이 0이 아니면 변환은 전단사⁠(bijective)⁠, 곧 평면의 점들을 빠짐없이 하나씩 짝지어 보냅니다. 그러니 거꾸로 되돌리는 변환이 있고, 그 행렬이 역행렬 $A^{-1}$ 입니다. 2×2에서는 $A^{-1} = \frac{1}{ad - bc}\begin{bmatrix} d & -b \\ -c & a \end{bmatrix}$ 로, 행렬식 $ad - bc$ 로 나누는 꼴입니다. 행렬식이 0이면 이 공식을 쓸 수 없고, 실제로 역행렬도 없습니다. 여러 점이 한 점으로 겹쳐 보내지니 어느 점으로 되돌릴지 정할 수 없기 때문입니다.

해를 정수⁠(integer)⁠로만 허락하면 전혀 다른 문제가 됩니다. $ax + by = c$ (a, b는 둘 다 0은 아닌 정수)의 정수해는 a와 b의 최대공약수⁠(greatest common divisor)⁠ $\gcd(a,b)$ 가 c를 나눌 때만 있습니다. 예를 들어 $6x + 4y = 3$ 은 좌변이 언제나 짝수라서 정수해가 없고, $6x + 4y = 2$ 는 $x = 1, y = -1$ 이라는 해가 있습니다. 해는 유클리드 호제법⁠(Euclidean algorithm)⁠을 거꾸로 따라가 찾습니다.

반대로 방정식이 미지수보다 많으면 보통 모든 식을 만족하는 해가 없습니다. 이때 오차 제곱의 합이 가장 작은 답을 고르는 것이 최소제곱 회귀⁠(least-squares regression)⁠입니다. 그 답은 오차 벡터⁠(vector)⁠가 A의 모든 열과 수직이라는 조건 $A^{\mathsf T}A\,\vec x = A^{\mathsf T}\vec b$ (정규방정식⁠, normal equations⁠)를 풀어 얻고, 이것은 b를 A의 열공간⁠(column space)⁠에 정사영⁠(orthogonal projection)⁠하는 일과 같습니다.

식이 셋 이상이면 한 식에 수를 곱해 다른 식에서 빼는 조작으로 변수를 하나씩 지워 나가는 가우스 소거법⁠(Gaussian elimination)⁠이 표준입니다.

등식 대신 부등식이 들어가면 또 다른 분야가 열립니다. 1781년 프랑스 수학자 가스파르 몽주는 흙더미를 구덩이로 옮길 때 흙을 나른 거리의 합을 가장 작게 하는 방법을 물었습니다. 1942년 레오니트 칸토로비치는 이 문제를 '출발지 i에서 도착지 j로 옮길 흙의 양'을 미지수로 두고, 옮기는 양이 음수가 아니고 있는 흙과 필요한 흙의 양이 맞아야 한다는 일차 등식·부등식 아래에서 비용을 최소로 하는 문제로 다시 썼습니다. 이런 문제를 선형 계획법⁠(linear programming)⁠이라 합니다(최적 수송⁠, optimal transport⁠).

관련된 시대와 장소조선의 산학

이 개념이 나오는 큰 생각쌍대성 선형화: 휘어진 것을 곧게 보기

이 개념이 나오는 긴 글

정수론과 암호 나머지로 지키는 비밀 한 번도 만난 적 없는 두 사람이 모두가 엿듣는 통신망에서 비밀 열쇠를 맞출 수 있을까? 답은 시계의 산수와 1640년 페르마의 정리에 있다. 최소제곱과 선형대수 잃어버린 소행성 1801년, 발견 몇 주 만에 태양 뒤로 사라진 세레스. 스물네 살의 가우스는 흩어진 관측값에서 궤도를 되찾았다. 그래프 이론 일곱 다리의 도시 쾨니히스베르크의 일곱 다리를 한 번씩만 건너 산책할 수 있을까? 오일러는 지도를 지우고 점과 선만 남겼다. 통계와 인과 담배와 폐암 상관관계는 인과관계가 아니라고들 한다. 그렇다면 담배가 폐암을 일으킨다는 것은 어떻게 알게 되었을까? 신경망과 기계 학습 배우는 기계 예를 보여 주면 규칙을 스스로 찾는 기계. 1958년의 퍼셉트론에서 오늘의 심층 신경망까지, 그 밑바닥에는 미분과 연쇄법칙이 있다. 역문제 거꾸로 푸는 문제는 왜 어려운가 원인에서 결과를 계산하기는 쉽다. 흐린 사진, CT, 블랙홀 사진은 왜 결과에서 원인을 되찾기 어려웠을까? 작은 특잇값이 잡음을 키우는 벽과, 정규화·릿지 회귀·베이즈 사전확률이 사실은 같은 처방이라는 이야기.

이 개념 위에 세워진 것

가우스 소거법 열공간 선형 계획법 역문제와 잘 놓인 문제

이 개념을 언급하는 페이지

선형변환
… 크게 확대하면 선형변환처럼 보입니다(국소 선형성). 변환된 결과를 보고 원래 벡터를 거꾸로 찾는 문제가연립일차방정식입니다. 평면의 모든 점을 한 직선 위로 수직으로 내려 버리는 선형변환은 정사영입니다. 변환이 보낼 수 …
행렬
… 이고, 둘째 성분은 둘째 행과의 내적입니다. 거꾸로 결과 b를 알고 Av = b가 되는 v를 찾는 문제가연립일차방정식입니다. 그 연립방정식을 푸는 표준 방법이 가우스 소거법입니다. 한 행에 수를 곱해 다른 행에서 빼는 …
행렬식
… 셀 때). 행렬식이 0이 아니면 변환을 되돌릴 수 있고, 2×2 역행렬 공식은 행렬식으로 나누는 꼴입니다(연립일차방정식과 역행렬). 회전 행렬의 행렬식은 \cos^2\theta + \sin^2\theta 이고, 이것이 1이라는 …
최소제곱 회귀
… A^\top A\,\vec\beta = A^\top \vec y 가 나오고, 이것은 미지수 두 개짜리연립일차방정식이라 바로 풀 수 있습니다. 단, x값이 모두 같으면 \vec x 와 \vec 1 이 한 방향이 되어 …
단사·전사·전단사
… 하고), 정사각행렬에서는 전단사인 것이 역행렬이 있다는 것, 곧 행렬식이 0이 아니라는 것과 같습니다(연립일차방정식과 역행렬). 전단사는 세기의 도구이기도 합니다. 똑같은 사탕 n개를 k명에게 나누는 방법(한 개도 못 받는 사람이 …
도박꾼의 파산
… p = \tfrac12 이면 각 값이 양옆의 평균이라 그래프가 직선입니다. 이 식 N−1개를 모으면연립일차방정식이 됩니다. 출발점 k마다 목표에 닿을 확률. 흰 점선은 공정한 게임의 직선 k/N, 노란 점은 지금 …
가우스 소거법
연립일차방정식을 푸는 가장 기본적인 방법입니다. 식에서 계수만 떼어 행렬 모양의 표(첨가행렬)로 적고, 세 가지 행 …
열공간
… a_1 + x_2\vec a_2 , 곧 열들 을 x_1 배, x_2 배 해서 이어 붙인 벡터가 됩니다(열 그림). \vec x 를 모든 값으로 바꿔 가며 얻는 벡터 전체가 열공간 입니다. 아래 행렬은 열이 2개, …
평행선 공준
… 한없이 커집니다. 식으로 보면, 두 직선이 만나는지 묻는 것은 두 직선의 방정식을 함께 만족하는 점, 곧연립일차방정식의 해가 있는지 묻는 것입니다. 계수의 행렬식이 0이면 해가 하나로 정해지지 않는데, 이것이 두 직선이 …
페이지랭크
… G를 곱해도 변하지 않는 벡터, 곧 G의 고유값 1에 대한 고유벡터가 페이지랭크입니다. 같은 벡터를연립일차방정식(I - dM)\,r = \tfrac{1-d}{n}\mathbf 1 의 해로 구할 수도 있지만, 페이지가 …
마할라노비스 거리
… 차이 벡터 \vec v 로 \vec v^\top \Sigma^{-1} \vec v , 곧 \Sigma 의역행렬로 계산합니다. 그 뜻은 좌표를 보면 드러납니다. \Sigma^{-1/2} 라는 선형변환을 걸면 …
과적합
… 0이 됩니다. 계수 12개짜리 다항식으로 12개 점을 정확히 지나는 것은 미지수 12개, 식 12개인연립일차방정식이고, 점들의 x값이 모두 다르면 답이 꼭 하나 있기 때문입니다. 그러나 그 곡선은 점 사이에서 크게 …
다항식
… 과적합이 일어나서, 알맞은 차수는 흔히 교차 검증으로 고릅니다. 어느 경우든 계수를 구하는 일은연립일차방정식을 푸는 일입니다. 이어지는 곳. 행렬 A의 고유값은 특성다항식 det(A − λI)의 …
선형 계획법
… 정리의 특별한 경우이고, 흙을 옮기는 가장 싼 방법은 최적 수송입니다. 부등식 대신 등식 제약만 있으면연립일차방정식이 되고, 목표가 매끄러운 곡면이면 기울기를 따라 내려가는 경사 하강법과 제약마다 승수를 붙이는 …
특잇값 분해
… 민감한가. 정사각 행렬에서 \sigma_1/\sigma_n 을 조건수라 합니다. 타원이 길쭉할수록 크고,연립방정식A\vec x = \vec b 를 풀 때 b의 상대 오차가 x에서 최대 이만큼 부풀 수 있습니다. 지금 …
보편 성질: 곱, 쌍대곱, 극한
… = g(x)\} , 곧 방정식의 해집합이고, 선형 사상이라면 f − g로 0이 되는 벡터들의 공간입니다(연립일차방정식). f: A → C, g: B → C의 극한(당김)은 \{(a, b) : f(a) = g(b)\} 로, …
역문제와 잘 놓인 문제
… 눈으로 볼 수 있습니다. 조건수만큼의 불어남은 문제 자체의 성질이라 어떤 풀이법도 피할 수 없습니다.연립방정식을 소거법으로 풀 때 피벗을 고르는 까닭은, 계산 과정이 반올림 오차를 그보다 더 키우지 않게 하려는 …

이 페이지가 가리키는 개념

열공간 단사·전사·전단사 최대공약수와 유클리드 호제법 최소제곱 회귀 정사영 가우스 소거법 가스파르 몽주 레오니트 칸토로비치 선형 계획법 최적 수송