3 Inseok Kong Schedule

Linear Algebra 2: Linear Combinations, Span, and Matrix Multiplication

선형 결합과 벡터 방정식, 벡터들의 span과 Ax = b가 해를 갖는 조건, 그리고 행렬 곱셈을 바라보는 네 가지 관점을 정리한다.

선형 결합, 벡터 방정식, span

▶ 08강

선형 결합

\(\mathbb{R}^n\)의 벡터 \(\mathbf{v}_1, \dots, \mathbf{v}_p\)와 스칼라 \(c_1, \dots, c_p\)가 주어질 때, 벡터

\[\mathbf{y} = c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \cdots + c_p \mathbf{v}_p\]

를 \(\mathbf{v}_1, \dots, \mathbf{v}_p\)의 선형 결합(linear combination)이라 하고, \(c_1, \dots, c_p\)를 가중치(weight) 또는 계수라 한다. 가중치는 스칼라라서 일반체로, 벡터는 굵은 글씨로 쓴다. 가중치로는 0이나 음수를 포함해 어떤 실수든 쓸 수 있다.

벡터 방정식

Linear Algebra 1의 수명 예측 시스템으로 돌아가 보자. 앞에서는 \(A\)를 행 단위로 읽었다. 각 행이 방정식 하나였다. 이번에는 열 단위로 읽는다. 각 열은 세 사람의 특징 하나(몸무게, 키, 흡연 여부)를 모은 벡터다.

\[x_1 \begin{bmatrix} 60 \\ 65 \\ 55 \end{bmatrix} + x_2 \begin{bmatrix} 5.5 \\ 5.0 \\ 6.0 \end{bmatrix} + x_3 \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 66 \\ 74 \\ 78 \end{bmatrix}\]

스칼라 곱을 각 벡터 안으로 분배하고 성분끼리 더하면 좌변은

\[\begin{bmatrix} 60 x_1 + 5.5 x_2 + 1 \cdot x_3 \\ 65 x_1 + 5.0 x_2 + 0 \cdot x_3 \\ 55 x_1 + 6.0 x_2 + 1 \cdot x_3 \end{bmatrix}\]

이 되고, 원래의 세 방정식과 정확히 같다. 따라서 같은 연립방정식을 세 가지 방식으로 쓸 수 있다.

  1. 선형 방정식 여러 개로,
  2. 행렬 방정식 \(A\mathbf{x} = \mathbf{b}\)로,
  3. 벡터 방정식(vector equation) \(x_1 \mathbf{a}_1 + x_2 \mathbf{a}_2 + x_3 \mathbf{a}_3 = \mathbf{b}\)로. 여기서 \(\mathbf{a}_j\)는 \(A\)의 열이다.

벡터 방정식은 “\(\mathbf{b}\)가 \(A\)의 열들의 선형 결합인가, 그렇다면 가중치는 무엇인가”를 묻는다. 이 관점이 해의 존재를 판단하는 열쇠다.

Span

\(\mathbf{v}_1, \dots, \mathbf{v}_p\)의 생성 공간(span)은 이 벡터들로 만들 수 있는 모든 선형 결합의 집합이다.

\[\operatorname{Span}\{\mathbf{v}_1, \dots, \mathbf{v}_p\} = \{\, c_1 \mathbf{v}_1 + \cdots + c_p \mathbf{v}_p \;:\; c_1, \dots, c_p \in \mathbb{R} \,\}\]

예시. \(\mathbf{v}_1 = (1, 2, 3)\), \(\mathbf{v}_2 = (2, 3, 4)\)라 하자. \(\operatorname{Span}\{\mathbf{v}_1, \mathbf{v}_2\}\)의 원소 몇 개는 다음과 같다.

  • 가중치 \((1, 1)\): \(\mathbf{v}_1 + \mathbf{v}_2 = (3, 5, 7)\)
  • 가중치 \((1, 0)\): \(\mathbf{v}_1 = (1, 2, 3)\) 자신
  • 가중치 \((0, 0)\): 영벡터 \((0, 0, 0)\)
  • 가중치 \((-2, 1)\): \(-2\mathbf{v}_1 + \mathbf{v}_2 = (0, -1, -2)\)

가능한 모든 가중치에 대한 결과를 모은 것이 span이다.

해의 존재. 벡터 방정식 관점에서 다음이 성립한다.

\[A\mathbf{x} = \mathbf{b} \text{ has a solution} \iff \mathbf{b} \in \operatorname{Span}\{\mathbf{a}_1, \dots, \mathbf{a}_n\}\]

즉 \(\mathbf{b}\)가 \(A\)의 열들의 span 안에 있을 때, 그리고 그때에만 해가 존재한다.

Span과 벡터 방정식의 기하학적 의미

▶ 09강

벡터의 덧셈과 스칼라 곱

벡터를 원점에서 시작하는 화살표로 그린다. 합 \(\mathbf{v}_1 + \mathbf{v}_2\)는 \(\mathbf{v}_1\)과 \(\mathbf{v}_2\)를 두 변으로 하는 평행사변형의 맞은편 꼭짓점이다(고등학교 물리의 평행사변형법). 스칼라 곱은 방향은 그대로 두고 길이를 바꾼다. \(2\mathbf{v}\)는 길이가 두 배이고, \(-\mathbf{v}\)는 반대 방향을 가리킨다.

선형 결합 \(c_1\mathbf{v}_1 + c_2\mathbf{v}_2\)는 둘을 합친 것이다. 각 변을 가중치만큼 늘리거나 줄인 뒤, 그 평행사변형의 맞은편 꼭짓점을 취한다. 예를 들어 \(2\mathbf{v}_1 + \mathbf{v}_2\)는 \(\mathbf{v}_1\) 쪽 변을 두 배로 늘린 평행사변형에서 얻는다. 가중치가 \((0, 0)\)이면 원점이 되므로 span은 항상 원점을 포함한다.

The linear combination 2v1 + v2 as the far corner of a parallelogram \(\mathbf{v}_1 = (2, 1)\), \(\mathbf{v}_2 = (1, 2)\)의 선형 결합 \(2\mathbf{v}_1 + \mathbf{v}_2 = (5, 4)\). 회색 점은 정수 가중치로 만든 결합들이다.

파란 변을 \(\mathbf{v}_1\)에서 \(2\mathbf{v}_1 = (4, 2)\)까지 늘리고, 빨간 변 \(\mathbf{v}_2\)는 그대로 둔 평행사변형을 그리면 맞은편 꼭짓점이 보라색 화살표의 끝 \((5, 4)\)이다. 성분으로 계산해도 \(2(2, 1) + (1, 2) = (5, 4)\)이다.

회색 점들은 \(c_1, c_2\)를 정수로만 바꿔 가며 찍은 결합인데, 이미 평면 전체에 고르게 퍼져 있다. 가중치를 실수 전체로 넓히면 점 사이의 빈틈이 모두 메워진다. 이 그림의 두 벡터는 같은 직선 위에 있지 않으므로 span은 평면 \(\mathbb{R}^2\) 전체다.

Span의 모양

  • 영이 아닌 벡터 하나. \(\operatorname{Span}\{\mathbf{v}\}\)는 모든 스칼라배 \(c\mathbf{v}\)이다. \(\mathbf{v}\)의 길이는 중요하지 않고 방향만 중요하며, \(c\)는 양수도 음수도 될 수 있다. 따라서 span은 원점을 지나는 직선이다.
  • 같은 직선 위에 있지 않은 \(\mathbb{R}^3\)의 벡터 두 개. 두 가중치를 바꾸면 모든 평행사변형의 꼭짓점을 훑게 된다. span은 원점을 지나는 평면이다.
  • 한 평면 위에 있지 않은 \(\mathbb{R}^3\)의 벡터 세 개. 벡터 세 개의 결합은 평행육면체(parallelepiped), 즉 평행사변형의 3차원 버전의 맞은편 꼭짓점이다. 세 모서리의 길이를 조절하면 그 꼭짓점을 어떤 점에든 놓을 수 있다. span은 \(\mathbb{R}^3\) 전체다.

Span of one vector is a line, span of two vectors is a plane in R3 앞 절의 \(\mathbf{v}_1 = (1, 2, 3)\), \(\mathbf{v}_2 = (2, 3, 4)\). 하나의 span은 직선, 둘의 span은 원점을 지나는 평면이다.

왼쪽 그림의 연한 파란 선은 \(c\mathbf{v}_1\)을 모든 실수 \(c\)에 대해 모은 것이다. 음수 \(c\)는 원점 반대편으로 뻗는다. 오른쪽 그림에 \(\mathbf{v}_2\)를 더하면 span이 노란 평면으로 넓어진다. 앞 절에서 계산한 \(\mathbf{v}_1 + \mathbf{v}_2 = (3, 5, 7)\)과 \(-2\mathbf{v}_1 + \mathbf{v}_2 = (0, -1, -2)\)(보라색 점)도 이 평면 위에 있다. 이 평면의 방정식은 \(-x_1 + 2x_2 - x_3 = 0\)이고, 두 점 모두 이 식을 만족한다.

두 벡터의 방향이 꽤 비슷해도 같은 직선 위에만 있지 않으면 평면 하나를 통째로 span한다. 평면 밖의 점, 예를 들어 \((1, 0, 0)\)은 어떤 가중치로도 만들 수 없다.

벡터 방정식 풀기를 그림으로 보기

\(x_1\mathbf{a}_1 + x_2\mathbf{a}_2 + x_3\mathbf{a}_3 = \mathbf{b}\)를 푼다는 것은, 목표점 \(\mathbf{b}\)와 고정된 세 방향 \(\mathbf{a}_1, \mathbf{a}_2, \mathbf{a}_3\)가 주어질 때, 평행육면체의 맞은편 꼭짓점이 정확히 \(\mathbf{b}\)에 오도록 각 모서리를 얼마나 늘릴지 찾는 일이다. 가중치 \(x_j\)가 바로 그 늘이는 배율이다.

  • 열들이 공간 전체를 span하면 어떤 \(\mathbf{b}\)에도 도달할 수 있으므로 해가 항상 존재한다.
  • 열들이 더 작은 집합(평면이나 직선)만 span하면, \(\mathbf{b}\)가 마침 그 안에 있을 때만 해가 존재한다.

예시: 특징 하나를 빼기. 수명을 몸무게와 키만으로 예측한다고 하자. 열은 \(\mathbb{R}^3\)의 \((60, 65, 55)\)와 \((5.5, 5.0, 6.0)\)이다. 이 둘의 span은 얇은 평면이다. 목표 \(\mathbf{b} = (66, 74, 78)\)은 이 평면 밖에 있다. 처음 두 방정식에서 \(x_1 \approx 1.34\), \(x_2 \approx -2.61\)이 정해지는데, 이를 세 번째 방정식에 넣으면 78이 아니라 약 58이 나온다. 따라서 해가 없다.

\(\mathbb{R}^3\) 전체를 덮으려면 벡터가 최소 3개 필요하다. 벡터를 하나씩 추가해 보면, 하나는 직선, 둘은 평면을 span하고, 그 평면 밖의 세 번째 벡터가 들어와야 공간 전체가 채워진다. 열의 개수가 공간의 차원보다 적으면(방정식이 미지수보다 많으면) 대개 해가 없다. \(\mathbf{b}\)가 운 좋게 span 안에 있을 때만 해가 있다.

여기서 공간의 차원은 각 열의 성분 개수, 즉 방정식의 개수다. 쓸 수 있는 재료 벡터의 개수는 열의 개수, 즉 미지수의 개수다.

예시: 같은 직선 위의 두 열

Linear Algebra 1의 특이 행렬 시스템을 보자.

\[x_1 \begin{bmatrix} 1 \\ 3 \end{bmatrix} + x_2 \begin{bmatrix} 2 \\ 6 \end{bmatrix} = \mathbf{b}\]

공간은 \(\mathbb{R}^2\)이고 벡터가 두 개 있지만, \((2, 6) = 2(1, 3)\)이라 같은 직선 위에 있다. 이 둘로 만든 평행사변형은 모두 그 직선 위로 납작하게 눌린다. 따라서 span은 평면 전체가 아니라 방향 \((1, 3)\)의 원점을 지나는 직선뿐이다.

  • \(\mathbf{b} = (4, 12)\)는 그 직선 위에 있으므로 해가 있다(사실 무수히 많다).
  • \(\mathbf{b} = (4, 10)\)은 직선 밖에 있으므로 해가 없다.

Two collinear columns span only a line; (4, 12) is on it, (4, 10) is not 두 열 \((1, 3)\), \((2, 6)\)의 span은 기울기 3인 직선 하나다. \((4, 12)\)는 그 위에, \((4, 10)\)은 그 밖에 있다.

빨간 화살표 \(\mathbf{a}_2\)는 파란 화살표 \(\mathbf{a}_1\)을 정확히 두 배 늘린 것이라 새로운 방향을 더하지 못한다. 그래서 두 열로 만든 결합은 모두 연한 파란 직선 \(y = 3x\) 위에 머문다. 초록 점 \((4, 12)\)는 \(12 = 3 \cdot 4\)이므로 직선 위에 있고 해가 존재한다. 보라색 점 \((4, 10)\)은 직선에서 2만큼 아래에 떨어져 있어 어떤 가중치로도 닿을 수 없다.

모든 경우에 적용되는 원칙은 하나다. \(\mathbf{b}\)가 열들의 span 안에 있을 때, 그리고 그때에만 해가 존재한다.

행렬 곱셈의 네 가지 관점

▶ 10강

관점을 바꾸는 이유

연립방정식 \(x + 2y = 4\), \(3x + 6y = 12\)를 스칼라 방정식으로 쓰면 방정식마다 곱셈과 덧셈을 따로 세야 하고, 모두 곱셈 4번과 덧셈 2번이다. 벡터 방정식 \(x\begin{bmatrix}1\\3\end{bmatrix} + y\begin{bmatrix}2\\6\end{bmatrix} = \begin{bmatrix}4\\12\end{bmatrix}\)로 쓰면 스칼라-벡터 곱 2번과 벡터 덧셈 1번이고, 방정식 개수와 무관해진다. \(A\mathbf{x} = \mathbf{b}\)로 쓰면 행렬-벡터 곱 한 번이다. 단계마다 작은 연산 여러 개가 더 큰 연산 몇 개로 묶인다. 이런 큰 단위로 생각하면 더 어려운 개념도 쉽게 보인다.

행렬 곱셈은 네 가지 방식으로 읽을 수 있다. 다음 예시를 쓴다.

\[A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ 5 & 6 \end{bmatrix}, \qquad B = \begin{bmatrix} 1 & -1 \\ 2 & 0 \end{bmatrix}, \qquad AB = \begin{bmatrix} 5 & -1 \\ 11 & -3 \\ 17 & -5 \end{bmatrix}\]

관점 1: 내적

\(AB\)의 \((i, j)\) 성분은 \(A\)의 \(i\)번째 행과 \(B\)의 \(j\)번째 열의 내적이다. 예를 들어 \((2, 1)\) 성분은 \(3 \cdot 1 + 4 \cdot 2 = 11\)이다. 표준 정의이지만, 여섯 개의 성분을 각각 따로 계산하는 시각이다.

관점 2: 열의 선형 결합

먼저, 행렬과 벡터의 곱은 행렬의 열들을 벡터의 성분을 가중치로 하여 선형 결합한 것이다.

\[A\mathbf{x} = x_1 \mathbf{a}_1 + x_2 \mathbf{a}_2 + \cdots + x_n \mathbf{a}_n\]

따라서 \(A\mathbf{x}\)는 항상 \(\operatorname{Span}\{\mathbf{a}_1, \dots, \mathbf{a}_n\}\) 안에 있다. 어떤 \(\mathbf{x}\)를 곱해도 이 span 밖의 벡터는 만들 수 없다.

행렬과 행렬의 곱에서 \(AB\)의 \(j\)번째 열은 \(A\)와 \(B\)의 \(j\)번째 열의 곱이다.

\[AB = A \begin{bmatrix} \mathbf{b}_1 & \cdots & \mathbf{b}_p \end{bmatrix} = \begin{bmatrix} A\mathbf{b}_1 & \cdots & A\mathbf{b}_p \end{bmatrix}\]

\(AB\)의 모든 열은 \(A\)의 같은 열들의 선형 결합이고, 가중치만 \(B\)의 각 열에서 따로 가져온다. 예시에서

\[\text{col}_1(AB) = 1 \begin{bmatrix} 1 \\ 3 \\ 5 \end{bmatrix} + 2 \begin{bmatrix} 2 \\ 4 \\ 6 \end{bmatrix} = \begin{bmatrix} 5 \\ 11 \\ 17 \end{bmatrix}, \qquad \text{col}_2(AB) = -1 \begin{bmatrix} 1 \\ 3 \\ 5 \end{bmatrix} + 0 \begin{bmatrix} 2 \\ 4 \\ 6 \end{bmatrix} = \begin{bmatrix} -1 \\ -3 \\ -5 \end{bmatrix}\]

이다. 즉 \(AB\)의 열은 모두 \(A\)의 열들의 span 안에 있다.

관점 3: 행의 선형 결합

\(A\mathbf{x}\)를 전치하면 \((A\mathbf{x})^T = \mathbf{x}^T A^T\)이다. \(A\)의 열이 \(A^T\)의 행이 되므로, 행 벡터와 행렬의 곱은 행렬의 행들의 선형 결합이다.

\[\mathbf{x}^T B = x_1 \,\text{row}_1(B) + x_2 \,\text{row}_2(B) + \cdots\]

행렬과 행렬의 곱에서 \(AB\)의 \(i\)번째 행은 \(A\)의 \(i\)번째 행과 \(B\)의 곱이다. 따라서 \(AB\)의 모든 행은 \(B\)의 같은 행들의 선형 결합이고, 가중치는 \(A\)의 각 행에서 가져온다.

\[\text{row}_1(AB) = 1 \begin{bmatrix} 1 & -1 \end{bmatrix} + 2 \begin{bmatrix} 2 & 0 \end{bmatrix} = \begin{bmatrix} 5 & -1 \end{bmatrix}\]

관점 2와 3은 서로 거울상이다. 왼쪽 행렬의 열에 주목하느냐, 오른쪽 행렬의 행에 주목하느냐의 차이다.

관점 4: 외적의 합

\(A\)의 \(k\)번째 열과 \(B\)의 \(k\)번째 행을 짝짓는다. \(A\)가 \(m \times n\), \(B\)가 \(n \times p\)이면 짝은 정확히 \(n\)개이고, 각 짝은 \(m \times p\) 외적을 만든다. 이들을 모두 더하면 \(AB\)이다.

\[AB = \sum_{k=1}^{n} \mathbf{a}_k \, \text{row}_k(B)\]

예시에서

\[AB = \begin{bmatrix} 1 \\ 3 \\ 5 \end{bmatrix} \begin{bmatrix} 1 & -1 \end{bmatrix} + \begin{bmatrix} 2 \\ 4 \\ 6 \end{bmatrix} \begin{bmatrix} 2 & 0 \end{bmatrix} = \begin{bmatrix} 1 & -1 \\ 3 & -3 \\ 5 & -5 \end{bmatrix} + \begin{bmatrix} 4 & 0 \\ 8 & 0 \\ 12 & 0 \end{bmatrix} = \begin{bmatrix} 5 & -1 \\ 11 & -3 \\ 17 & -5 \end{bmatrix}\]

이다. \((1,1)\) 성분 \(1 \cdot 1 + 2 \cdot 2\)에서 첫 번째 곱은 첫 번째 외적에서, 두 번째 곱은 두 번째 외적에서 온다. 그래서 외적의 합이 내적 정의와 일치한다.

랭크 1 외적

외적 하나는 특별하다.

\[\mathbf{u}\mathbf{v}^T = \begin{bmatrix} 1 \\ 2 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \end{bmatrix}\]
  • 열 관점: 열은 \(1\mathbf{u}\), \(2\mathbf{u}\), \(3\mathbf{u}\)로 모두 \(\mathbf{u} = (1, 2)\)의 스칼라배다. 모두 벡터 하나의 span인 직선 위에 있다.
  • 행 관점: 행은 \(1\mathbf{v}^T\), \(2\mathbf{v}^T\)로 모두 \((1, 2, 3)\)의 스칼라배다.

\(\mathbf{u}\)와 \(\mathbf{v}\)가 아무리 길어도 열 전체를 span하는 데 벡터 하나면 충분하다. 이런 행렬의 랭크(rank)는 1이다. 열들을 span하는 데 필요한 벡터의 개수인 랭크는 Linear Algebra 3에서 정확히 정의한다. 관점 4에 따르면 모든 행렬 곱은 랭크 1 행렬들의 합이다.

저랭크 행렬 분해

\(500 \times 1400\) 데이터 행렬을 생각하자. 샘플이 500개이고 각 샘플을 1400개의 특징으로 나타낸 것이다(실제로 흔한 모양이다). 1400개의 열은 \(\mathbb{R}^{500}\)의 점이다. 그런데 이 열들이 모두 단 두 벡터 \(\mathbf{c}_1, \mathbf{c}_2\)의 선형 결합으로 표현된다고 하자. 그러면 열 관점에 의해

\[\underbrace{A}_{500 \times 1400} = \underbrace{\begin{bmatrix} \mathbf{c}_1 & \mathbf{c}_2 \end{bmatrix}}_{500 \times 2} \; \underbrace{R}_{2 \times 1400}\]

이다. \(R\)의 \(j\)번째 열에는 \(A\)의 \(j\)번째 열을 만드는 두 가중치가 들어 있다. \(\mathbb{R}^{500}\) 어디에나 흩어져 있을 수 있었던 데이터가 사실은 얇은 평면 하나 안에 들어 있는 것이다.

두 인수를 곱하기는 쉽다. 반대로 \(A\)만 보고 이런 인수를 찾는 것은 훨씬 어렵다. \(x^2 - x - 12 = (x - 4)(x + 3)\)을 전개하기보다 인수분해하기가 더 어려운 것과 같다. 이 문제가 저랭크 행렬 분해(low-rank matrix factorization)이며 머신러닝에서 널리 쓰인다.

  • 추천 시스템(사용자 \(\times\) 아이템 행렬)
  • 토픽 모델링: 뉴스나 트윗으로 만든 큰 단어-문서 행렬을 분해하면 기저 벡터들이 주제를 드러낸다(예: 오디션 프로그램의 가창력에 관한 단어 묶음).
  • 이미지 스타일 변환(style transfer) 같은 컴퓨터 비전의 관련 문제

정리

  • 선형 결합 \(c_1\mathbf{v}_1 + \cdots + c_p\mathbf{v}_p\)는 벡터를 늘리고 더한 것이고, span은 가능한 모든 선형 결합의 집합이다.
  • 선형 시스템은 방정식들, 행렬 방정식 \(A\mathbf{x} = \mathbf{b}\), 벡터 방정식 \(x_1\mathbf{a}_1 + \cdots + x_n\mathbf{a}_n = \mathbf{b}\)의 세 가지 형태로 쓸 수 있다.
  • \(A\mathbf{x} = \mathbf{b}\)는 \(\mathbf{b}\)가 \(A\)의 열들의 span 안에 있을 때, 그리고 그때에만 해를 갖는다.
  • 기하학적으로 벡터 하나의 span은 직선, 평행하지 않은 두 벡터의 span은 평면, 한 평면에 있지 않은 세 벡터의 span은 \(\mathbb{R}^3\) 전체다. 해를 구하는 것은 평행사변형(평행육면체)의 맞은편 꼭짓점이 \(\mathbf{b}\)에 오도록 변을 늘이는 것이다.
  • 행렬 곱셈에는 네 가지 관점이 있다. 내적(성분), \(A\)의 열의 결합(\(AB\)의 열), \(B\)의 행의 결합(\(AB\)의 행), 외적의 합.
  • 외적 \(\mathbf{u}\mathbf{v}^T\)는 랭크 1이다. 큰 행렬을 얇은 인수들의 곱으로 나타내는 저랭크 행렬 분해는 추천, 토픽 모델링 등의 핵심 도구다.