알고리즘 수학 기본-행렬

Jul 10, 2021

알고리즘을 위한 수학 - 행렬 (Matrices)

---

Introduction to Algorithm, 3rd, Cormen을 토대로 정리한 내용입니다. 일부 표기나 개념이 기존의 수학과 다를 수도 있으므로, 여기서 배운 내용은 단순 해당 책(Introduction to Algorithm, 3rd, Cormen)의 부록으로 취급해야한다.

이 장에서는 행렬의 표기법, 정의, 속성 같은 기본적인 것만 배운다.

행렬과 행렬 연산 (Matrices and matrix operations)

---

행렬과 벡터(Matrices and vectors)

---

행렬(matrix)는 숫자들의 정방형 배열이다.
\(A=\begin{pmatrix} a_{11}&a_{12} &a_{13} \\ a_{21}&a_{22} &a_{23} \\ \end{pmatrix} =\begin{pmatrix} 1&2 &3 \\ 4&5 &6 \\ \end{pmatrix}\)
위의 예시는 $i=1,2, j=1,2,3$인 $2 \times 3$행렬 $A=(a_{ij})$로, $a_{ij}$는 i열 j행의 원소를 의미한다. 주로 행렬은 대문자, 행렬 내의 원소는 소문자로 표기하면 예를 들어 $\R^{m\times n}$은 $m\times n$ 크기의 실수 행렬을 의미한다.

A의 전치 행렬(transpose matix)는 $A^T$로 표기하며, 행렬 A의 열과 행을 서로 맞바꾼 형태의 행렬이며 예를 들면 다음과 같다.
\(A^T=\begin{pmatrix} 1&4 \\ 2&5 \\ 3&6 \\ \end{pmatrix}\)

벡터(vector)는 숫자의 1차원 행렬로 예를 들면 다음과 같은 형태는 크기가 3인 벡터이며, 크기가 n일때의 벡터를 n-벡터라고도 부른다.
\(x=\begin{pmatrix} 2 \\ 3 \\ 5 \\ \end{pmatrix}\)
벡터는 주로 소문자로 표기하며, i번째 원소는 $x_i$같은 형태로 표기한다. 많은 벡터의 표준적인 형태는 열 벡터(column vector)로, 위와 같은 형태이며 $n \times 1$ 행렬 이라고 표기하며, 그에 따른 전치행렬인 행 벡터(row vector)는 $x^T=\begin{pmatrix} 2&3 &5 \end{pmatrix}$같은 형태이며, $1\times n$ 형태이다.

단위 벡터(unit vector) $e_i$는 i번째 원소가 1이고 나머지 모든 원소가 0인 벡터이다. 단위 벡터의 크기는 제각기가 될 수 있으며, 보통 문맥에 사용하는 다른 행렬과 같은 크기이다.

영 행렬(zero matrix)은 모든 원소가 0인 행렬이다. 그러한 행렬은 보통 0으로 표기하며, 실제 숫자 0과 동일하지만 문맥에 따라 구분하며, 크기 또한 그러하다.

정방 행렬(Square matrices)

---

정방 행렬은 $n \times n$ 꼴의 행렬로, 몇몇 특별한 형태의 행렬이 존재한다.

대각 행렬 (diagonal matrix)

\[diag(a_{11},a_{22},\dots,a_{nn})=\begin{pmatrix} a_{11}&0&\dots&0 \\ 0&a_{22}&\dots&0 \\ \vdots & \vdots&\ddots&\vdots \\ 0&0&\dots&a_{nn} \\ \end{pmatrix}\]

대각 행렬은 $i\neq j$인 곳에서 $a_{ij}=0$인 행렬로 위와 같은 형태를 하고 있다.

항등 행렬 (identity matrix)

\[I_n=diag(1,1,\dots,1)=\begin{pmatrix} 1&0&\dots&0 \\ 0&1&\dots&0 \\ \vdots & \vdots&\ddots&\vdots \\ 0&0&\dots&1 \\ \end{pmatrix}\]

$n\times n$ 항등 행렬 $I_n$은 대각선 원소가 모두 1인 대각 행렬이며, n의 크기를 가지고 있다.

항등행렬의 i번째 열은 단위 벡터 $e_i$이다.

삼중 대각 행렬 (tridiagonal matrix)

\[T=\begin{pmatrix} t_{11}&t_{12}&0&0&\dots&0&0&0 \\ t_{21}&t_{22}&t_{23}&0&\dots&0&0&0 \\ 0 & t_{32}&t_{33}&t_{34}&\dots&0&0&0 \\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\ 0&0&0&0&\dots&t_{n-2,n-2}&t_{n-2,n-1}&0\\ 0&0&0&0&\dots&t_{n-1,n-2}&t_{n-1,n-1}&t_{n-1,n}\\ 0&0&0&0&\dots&0&t_{n,n-1}&t_{nn}\\ \end{pmatrix}\]

삼중 대각 행렬 T는 $

i-j

>1$일 때, $t_{ij}=0$인 행렬이다. 0이 아닌 원소는 대각선 원소와 대각선 원소의 바로 위 또는 아래 원소들 뿐이다.

상삼각 행렬 (upper-triangular matrix)

\[U=\begin{pmatrix} u_{11}&u_{12}&\dots&t_{1n} \\ 0&u_{22}&\dots&u_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\dots&u_{nn} \end{pmatrix}\]

상삼각 행렬 U는 $i>j$일 때, $u_{ij}=0$인 행렬로, 대각선 원소보다 아래의 원소들은 모두 0인 행렬이다.

상삼각 행렬의 원소가 모두 0 아니면 1일 경우, 단위 상삼각 행렬(unit upper-triangular matrix)이라고 불린다.

하삼각 행렬 (lower-triangular matrix)

\[L=\begin{pmatrix} l_{11}&0&\dots&0\\ l_{21}&l_{22}&\dots&0\\ \vdots&\vdots&\ddots&\vdots\\ l_{n1}&l_{n2}&\dots&l_{nn} \end{pmatrix}\]

하삼각 행렬 L은 $i<j$일 때, $l_{ij}=0$인 행렬로, 대각선 원소보다 위의 원소들은 모두 0인 행렬이다.

하삼각 행렬의 원소가 모두 0 아니면 1일 경우, 단위 하삼각 행렬(unit lower-triangular matrix)이라고 불린다.

순열 행렬 (permutation matrix)

\[P=\begin{pmatrix} 0&1&0&0&0\\ 0&0&0&1&0\\ 1&0&0&0&0\\ 0&0&0&0&1\\ 0&0&1&0&0 \end{pmatrix}\]

순열 행렬 P는 각 열이나 행에 단 하나의 1만 존재하고, 나머지는 0인 행렬이다.

이 순열 행렬에 벡터를 곱하면 원소들의 재배치가 일어나기 때문에 이를 순열 행렬이라고 부른다.

대칭 행렬 (symmetirc matrix)

\[P=\begin{pmatrix} 1&2&3\\ 2&6&4\\ 3&4&5\\ \end{pmatrix}\]

대칭 행렬은 $A=A^T$를 만족하는 행렬이다.

기본 행렬 연산 (Basic matrix operations)

---

행렬과 벡터의 원소들은 실수, 복소수, 소수의 모듈로 결과 등 같은 수계(number system)에서 가져온 숫자로 이루어져 있다. 수계는 숫자들이 어떻게 더해지고 곱해지는지 정의하며, 이를 더욱 확장하여 행렬의 연산을 정의할 수 있다.

행렬의 합과 차(matrix addtion and subtraction)

행렬의 합(matrix addtion)은 다음과 같은 방법으로 이루어진다.

만약, 행렬 $A=(a_{ij}), B=(b_{ij})$ 둘 모두 $m\times n$행렬이라면, 그 둘의 합행렬 $C=(c_{ij})=A+B$은 마찬가지로 $m\times n$ 행렬이다.

또한, 행렬 C의 원소는 $c_{ij}=a_{ij}+b_{ij}$이며, 즉, 행렬 간의 합은 원소 수준에서 이루어짐을 알 수 있다.

영행렬의 덧셈의 경우 식 $A+0=A=0+A$이 성립한다.

$\lambda$가 숫자이고, $A=(a_{ij})$가 행렬일 경우, $\lambda A=(\lambda a_{ij})$은 스칼라 곱(scalar multiple)이라고 하여, 행렬 A의 각 원소들에 $\lambda$만큼 곱하면 된다.

만약 행렬에 -1을 곱한 $-$A는 마찬가지로 각 원소에 -1을 곱한것과 같으며 $A+(-A)=0=(-A)+A$를 만족한다.

또한, $A-B=A+(-B)$를 통해서 행렬의 차(matrix subtraction) 또한 정의할 수 있다.

행렬의 곱(matrix multiplication)

행렬의 곱(matrix multiplication)은 다음과 같이 정의할 수 있다. 두 행렬을 곱하려면, 두 행렬 A와 B가 서로 호환되어야(compatible)하며, 이는 A의 열의 갯수와 B의 행의 갯수가 동일함을 의미한다.

만약, 행렬 $A=(a_{ik})$가 $m\times n$이고, 행렬 $B=(b_{kj})$가 $n\times p$이면, 곱의 결과 $C=AB$는 $m\times p$가 된다.

이때, 행렬 C의 각 원소는 다음과 같이 계산된다.
\(c_{ij}=\sum^n_{k=1}a_{ik}b_{kj}\)
행과 열의 크기가 동일한 정방 행렬 곱 또한 마찬가지로 진행되며, 정방 행렬의 크기를 $n\times n$이라고 할때, $n^3$번의 곱셈과 $n^2(n-1)$번의 덧셈을 시행하므로, $\Theta(n^3)$만큼의 시간복잡도를 가지게 된다.

항등 행렬 $I_m$은 $I_mA=AI_n=A$과 같이 곱의 결과가 동일한 행렬이다.

영행렬을 행렬에 곱하면 $A0=0$와 같이 영행렬이 나온다.

행렬 곱은 $A(BC)=(AB)C$처럼 교환법칙이 성립하며, 덧셈도 마찬가지이다.

\[A(B+C)=AB+AC\\ (B+C)D=BD+CD\]

하지만 크기가 1 이상인 정방행렬은 교환법칙이 성립하지 않는다. 예를 들어 아래와 같은 정방 행렬이 둘 있다면,

$A=\begin{pmatrix}0&1\0&0\end{pmatrix},\ B=\begin{pmatrix}0&0\1&0\end{pmatrix}$

곱 행렬의 두 결과는 다음과 같다.

$AB=\begin{pmatrix}1&0\0&0\end{pmatrix}$, $BA=\begin{pmatrix}0&0\0&1\end{pmatrix}$

행렬-벡터 간 곱(product)이나 벡터-벡터 간 곱은 벡터를 $n\times 1$ 또는 $1\times n$의 행렬로 간주하며, $m \times n$ 행렬과 n-벡터의 곱은 m-벡터가 된다.

만약 두 n-벡터 x, y 간의 곱은 아래와 같이 진행하며, $xy$의 결과는 하나의 숫자, 정확히는 $1\times 1$ 크기의 행렬이 나오며, 이를 두 벡터간의 내적(inner product)이라고 한다.

\[x^Ty=\sum^n_{i=1}x_iy_i\]

행렬 $xy^T$는 $n\times n$ 크기의 행렬이며, 이를 x와 y 간의 외적(outer product)이라고 하며, 외적의 원소의 값 $z_{ij}=x_iy_j$이다.

n-벡터의 (유클리드) 노름 ((euclidean) norm) $|x|$은 아래와 같이 정의되며, n-차원 유클리드 공간에서의 x의 길이를 의미한다.
\(\|x\|=(x_1^2+x_2^2+\cdots+x_n^2)^{1/2}=(x^Tx)^{1/2}\)

기본 행렬 성질(Basic matrix properties)

역행렬(inverse), 일차 독립(linear independence), 일차 종속(linear dependence), 행렬 계수(rank)와 행렬 식(determinants), 정부호 행렬(positive-definite matrix) 등에 대해 알아본다.

역행렬(Matrix inverses)

역행렬은 $A^{-1}$으로 표현되며, $AA^{-1}=I_n=A^{-1}A$을 만족하는 성질을 가지고 있다. 예를 들면 아래와 같다.

\[\begin{pmatrix}1&1\\1&0\end{pmatrix}^{-1}=\begin{pmatrix}0&1\\1&-1\end{pmatrix}\]

영행렬이 아닌 정방행렬들은 역행렬을 가지고 있지 않은 경우가 존재하며, 이를 비가역(noninvertible) 행렬 또는 특이(singualr) 행렬이라고 하며, 예시로 $\begin{pmatrix}1&0\1&0\end{pmatrix}$가 존재한다. 반대로 역행렬이 존재하면 가역(invertible) 행렬, 비특이(nonsingular) 행렬, 정칙(regular) 행렬이라고 한다.

한 행렬의 역행렬이 존재하면, 역행렬은 유일하며, 비특이 행렬 A와 B가 같은 $n \times n$크기라면, $(BA)^{-1}=A^{-1}B^{-1}$이 성립한다.

또한 역행렬 또한 $(A^{-1})^T=(A^T)^{-1}$와 같이 전치행렬이 존재한다.

만약, 벡터들의 모임 $x_1, x_2,\dots,x_n$이 존재할 때, $c_1x_1+c_2x_2+\cdots+c_nx_n=0$을 만족하는 하나라도 0이 아닌 계수들 $c_1,c_2,\dots, c_n$가 존재하면, 일차 종속(linear dependence)이라고 한다.

예를 들어 $x_1=\begin{pmatrix}1&2&3\end{pmatrix},x_2=\begin{pmatrix}2&6&4\end{pmatrix},x_3=\begin{pmatrix}4&11&9\end{pmatrix}$의 경우, $2x_1+3x_2-2x_3=0$이 성립하므로, 일차 종속이다.

반대의 경우에는 일차 독립(linear independence)이라고 하며, 예를 들어 항등 행렬의 각 열들은 일차 독립적이다.

행렬 랭크

영 벡터가 아닌 $m\times n$ 행렬 A의 열 랭크(column rank)는 A 행렬의 일차 독립인 열 중 최대 크기이다. 비슷하게, 행 랭크(row rank)는 A 행렬의 일차 독립인 행 중 최대 크기이다. 놀랍게도 행 랭크와 열 랭크는 언제나 동일하므로, 간단하게 랭크(rank)라고도 부른다.

$m\times n$ 행렬의 랭크는 0와 $\min(m,n)$ 사이이며, 예를 들어 크기가 0인 행렬의 랭크는 0이며, $n\times n$의 항등 행렬의 랭크는 n이다. 랭크의 또 다른 정의는 영 행렬이 아닌 $m\times n$ 크기 행렬 A의 랭크는 $A=BC$를 만족하는 $m\times r$ 크기 행렬 B와 $r \times n$크기 행렬 C가 존재할 때, 최대한 작은 r이다.

정방 $n\times n$ 행렬의 랭크가 n이라면, 풀 랭크(full rank)라고 하며, $m\times n$ 행렬의 랭크가 n일 경우, 풀 열 랭크라고 한다.

랭크의 성질

다음은 랭크의 정리에 대해 알아보자.

정리(Theorem) 1

정방 행렬이 비특이 행렬일 경우 풀 랭크이다.

정리(Theorem) 2

행렬 A에 대한 널 벡터(null vector)는 $Ax=0$을 만족하는 영이 아닌 벡터 x이다.

행렬 A가 널 벡터를 가지고 있지 않으면, 풀 열 랭크(full column rank)를 가지고 있다.

따름 정리(Corollary) 3

정방 행렬 A가 널 벡터를 가지고 있으면 특이 행렬이다.

크기가 1보다 큰 $n\times n$크기의 행렬 A의 ij번째 소행렬식(minor)은 i번째 행과 j번째 열이 삭제된 $(n-1)\times(n-1)$ 행렬 $A_{[ij]}$이며, 행렬식(determinant, $\det(A)$)은 아래와 같이 소행렬식을 이용해 재귀적으로 정의 된다.

\[\det(A)=\left{\begin{matrix} a_{11}&if\ n=1\ \sum^n_{j=1}(-1)^{1+j}a_{1j}\det(A_{[1j]})&if\ n>1 \end{matrix}\right.\]

식 $(-1)^{i+j}\det(A_{[ij]})$은 원소 $a_{ij}$의 여인수(cofactor)라고 부른다.

정리(Theorem) 4 (행렬식 성질)

정방 행렬 A의 행렬식은 다음과 같은 성질을 가지고 있다.

• 만약 행렬 A의 어느 행이나 열이 0이라면 $\det(A)=0$이다.
• 행렬 A의 어떤 열이나 행의 원소가 $\lambda$만큼 곱해지면, A의 행렬식 또한, $\lambda$ 로 곱해진다.
• 한 행의 원소가 다른 행의 원소로 더해지거나 한 열의 원소가 다른 열의 원소로 더해져도, A의 행렬식은 변하지 않는다.
• A의 행렬식은 A의 전치행렬 $A^T$의 행렬식과 동일하다. ($\det(A)=\det(A^T)$)
• 어떤 두 행이 서로 바뀌거나 어떤 두 열이 서로 바뀌면 A의 행렬식에 -1을 곱한 것($-\det(A)$)과 같다.
• 두 정방 행렬 A와 B에 대해 $\det(AB)=\det(A)\det(B)$

정리(Theorem) 5

만일 $\det(A)=0$이면, $n\times n$ 행렬 A는 특이 행렬이다.

정부호 행렬(positive-definite matrix)

$x\neq0$인 모든 n-벡터에 대해서 $x^TAx>0$를 성립하면 행렬 A는 정부호행렬(positive-definite matrix)이다.

예를 들어, 항등 행렬은 영벡터가 아닌 벡터 $x=\begin{pmatrix}x_1&x_2&\cdots x_n\end{pmatrix}^T$에 대해 다음이 성립하므로, 정부호 행렬이다.
\(x^TI_nx=x^Tx=\sum^n_{i=1}x^2_i>0\)

Theorem 6

풀 열 랭크를 가진 모든 행렬 A에서, $A^TA$ 행렬은 언제나 정부호 행렬이다.

증명

$x$가 영벡터가 아닌 모든 벡터에서 $x^T(A^TA)x>0$를 충족해야하며, 모든 x에서 다음이 성립한다.

$x^T(A^TA)x=(Ax)^T(Ax)=|Ax|^2$

이떄, $|Ax|^2$은 벡터 $Ax$의 요소들의 제곱의 합이며, 언제나 $|Ax|^2\ge0$를 만족한다.

만약, $|Ax|^2=0$이라면, Ax의 모든 원소는 0이며, 곧 $Ax=0$이 된다.

해열 A가 풀 열 랭크를 가지므로, $Ax=0$은 정리 2번에 의해 $x=0$을 의미하며, 따라서 $A^TA$는 정부호 행렬이 된다.