무한서고

피보나치 수열을 선형대수로 풀어보자

 
피보나치 수열 해체에 멱급수가 끝인 줄 알았건만... 또 새로운 insight로 선형대수로도 풀어볼 수 있게 됐네요..
1. 계차의 등비수열로 풀기
2. 특성방정식으로 풀기
3. 멱급수로 풀기
 
 

1. 선형대수로 풀 수 있다고?

우리는 이미 앞에서 피보나치 수열의 일반항도 구했고, 여러 방법으로 구해보기도 하였습니다.
이 과정을 선형대수로도 할 수 있다는 것이 이 포스팅의 골자가 되겠네요.
 
 

2. 어떻게 풀건데?

2-1. 피보나치 수열을 선형대수적으로 나타내기

일단 수열 $ F_n $을 선형대수적으로 정의해봅시다.
$ F_n = F_{n-1} + F_{n-2} $를
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = \underbrace{\begin{bmatrix} 1&1\\1&0 \end{bmatrix}}_{\mathsf{Companion \; Matrix}} \begin{bmatrix} F_{n-1}\\F_{n-2} \end{bmatrix} $
이렇게 표현 가능합니다. 여기서 잘 보면 $ F_n $과 $ F_{n-1} $ 사이에 생기는 행렬을 Companion matrix(동반 행렬)이라고 하는데, 어떻게 저렇게 표현되는지는 사실 간단합니다.
일단 그냥 $ F_n $을 $ F_n $과 $ F_{n-1} $을 성분으로 갖는 열벡터로 정의합시다.(선형대수에서 벡터의 의미는 열이나 행 하나로 정의된 행렬을 뜻합니다)
$ \overrightarrow{F_n} = \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} $
이 될 것이고, 여기서 $ F_n = F_{n-1} + F_{n-2} $라는 피보나치 수열의 정의를 이용하면
$ \overrightarrow{F_n} = \begin{bmatrix} F_{n-1}+F_{n-2}\\F_{n-1} \end{bmatrix} $
덧셈의 항등원인 0까지 넣어주면
$ \overrightarrow{F_n} = \begin{bmatrix} F_{n-1}+F_{n-2}\\F_{n-1}+0 \end{bmatrix} $
좀 더 보기 편하게 곱셈의 항등원 1도 표시해주죠
$ \overrightarrow{F_n} = \begin{bmatrix} 1 \cdot F_{n-1}+1 \cdot F_{n-2}\\ 1 \cdot F_{n-1}+ 0 \cdot F_{n-2} \end{bmatrix} $
행렬의 곱셈공식을 생각해서 분리해보면
$ \overrightarrow{F_n} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} \begin{bmatrix} F_{n-1}\\F_{n-2} \end{bmatrix} $
여기서
$ \overrightarrow{F_n} = \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} $
이므로
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} \begin{bmatrix} F_{n-1}\\F_{n-2} \end{bmatrix} $
이렇게 유도가 됩니다. 그리고 이를 벡터로 표기하면
$ \overrightarrow{F_n} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} \overrightarrow{F_{n-1}} $
이렇게도 표현할 수 있겠죠?
 

2-2. 피보나치 수열을 변환하기

자, 그럼 아주 재밌게도 $ F_n $과 $ F_{n-1} $ 사이에는 companion matrix의 곱만큼 차이가 납니다.
가령, $ F_{n-1} $을 표현해보아도
$ \overrightarrow{F_{n-1}} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} \overrightarrow{F_{n-2}} $
일 것이고, 이를 위 식에 대입을 하면
$ \overrightarrow{F_n} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} \overrightarrow{F_{n-1}} $
$ \overrightarrow{F_{n-1}} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} \overrightarrow{F_{n-2}} $
$ \overrightarrow{F_n} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} \overrightarrow{F_{n-2}} $
$ \overrightarrow{F_n} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix}^2 \cdot \overrightarrow{F_{n-2}} $
가 되겠고, 이제 조금 표기의 편의성을 위해 companion matrix를 A라고 놓으면
$ \overrightarrow{F_n} = A^2 \cdot \overrightarrow{F_{n-2}} $
라고 표기할 수 있겠습니다. 자, 다시 돌아가서 $ F_n $과 $ F_{n-1} $ 사이에는 companion matrix의 곱만큼 차이가 난다고 했습니다.
그렇다면 이를 이용하면 $ F_n $을 $ F_{1} $으로 표현도 가능하겠네요?
그렇다면 companion matrix A는 n-1번 곱해지면 되겠습니다.
$ \overrightarrow{F_n} = A^{n-1} \cdot \overrightarrow{F_{1}} $
열벡터를 풀어서 행렬로 보게 된다면
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = A^{n-1} \cdot \begin{bmatrix} F_{1}\\F_{0} \end{bmatrix} $
여기서 $ F_1 = 1, \; F_0 = 0 $이므로,
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = A^{n-1} \cdot \begin{bmatrix} 1\\0 \end{bmatrix} $
이렇게 깔끔하게 정리가 되겠네요!
여기까지는 아주 순조롭습니다! 여기까지는...
 
자, 여기서 어려움에 봉착합니다.
행렬의 곱은 일반 적인 대수적 곱이랑은 다르다고 했습니다.
그렇다면 곱으로 연결되어있는 행렬, 즉 행렬의 거듭제곱은 쉬울까요? 각 요소에다가 각자 다 거듭제곱을 붙여주면 되는걸까요?
아뇨.. 일반적으로는 매우 어렵습니다. 대수의 거듭제곱처럼 쉬웠으면 얼마나 좋을까요..
그렇다고 거듭제곱으로 압축표기된 행렬을 쫙 풀어놓고 하나하나 곱하고 있자니 그것도 조금 메롱합니다..
물론 앞의 몇번을 반복하고 수학적 귀납법으로 이런 규칙이 있다!하고 찾은 뒤 적용해주어도 괜찮지만, 우리는 뭔가 좀 더 신박한 방법을 찾아보려 합니다.
그렇다면 행렬을 일반 대수처럼, '행렬의 거듭제곱 = 요소의 거듭제곱'으로 나타낼 수 있는 행렬이 있을까요?
 
예, 행렬의 곱셈에 대해 조금만 생각해보면, '대각행렬'은 자기 자신이 속한 행과 열 중에서 자기 자신을 제외한 다른 요소들이 전부 0이므로 행렬의 곱셈을 수행하여도 자기 자신의 거듭제곱만 결과로 나타나게 됩니다! 즉,
$ \begin{bmatrix} 1&0\\0&2 \end{bmatrix}^2 = \begin{bmatrix} 1&0\\0&2 \end{bmatrix}\begin{bmatrix} 1&0\\0&2 \end{bmatrix} = \begin{bmatrix} 1&0\\0&4 \end{bmatrix} = \begin{bmatrix} 1^2&0\\0&2^2 \end{bmatrix} $
오! 결국 행렬의 거듭제곱을 요소의 거듭제곱으로 표현할 수 있는 방법을 찾았습니다!
그럼 행렬을 대각행렬로 바꿔주면 되겠네요!? 근데.. 어떻게 해야하죠...?
 
여기서 나오는 개념이 바로 '대각화'입니다.
연역적으로 너무나도 당연하게 한 행렬을 대각행렬로 바꿔주는 작업이죠.
그런데, 딱 봐도 뭔가 그럴싸해보이는 작업이 맨입으로 가능할까요? 아니겠죠...
그래서 대각화에 앞서서 바로 '고유값 분해(eigen decomposition)'가 필요합니다.
갑자기 뭔가 난이도가 엄청 뛴 느낌입니다.
 

2-3. 대각화를 위한 고유값 분해

간단하게 고유값 분해를 설명하자면, '어떤 행렬을 어떤 벡터에 곱한 값이 그 어떤 벡터의 상수배 만큼과 같은 그 어떤 벡터와 상수 찾기'라고 생각하시면 됩니다.
좀 더 설명해보자면, 행렬의 곱은 기본적으로 어떤 공간에서의 좌표변환 역할을 합니다.
그러나 이 행렬의 변환을 거쳐도 변하지 않는 그런 벡터를 찾는 것이 고유벡터(아이젠 벡터, eigen vector)를 찾는 과정입니다.
그리고 물론 이 벡터는 변환을 거쳐서 특정 상수배만큼 길이가 길어지거나 짧아질텐데, 바로 그런 상수를 찾는 것이 고유값(아이젠 벨류, eigen value)을 찾는 과정입니다.
그리고 이둘이 한번에 이루어지기때문에 고유값분해라고 명명지어진 것이죠.
그럼 실제로 한번 어떻게 이루어지는지 봐 볼까요?
아, 참고로 고유값 분해는 정방행렬에서만 적용된답니다. 이를 확장한게 특이값 분해(singular value decomposition)죠.
 
자, 일단 '어떤 행렬과 곱한 열벡터' 즉, '행렬변환을 한 열벡터'라는 식을 세워봅시다.
지금 쓰는 A 행렬은 위에서의 companion matrix였던 A행렬과 다른 행렬입니다.
$ A \cdot \overrightarrow{v} $
그리고, '상수배만큼 변한 열벡터'도 식으로 세워보죠
$ \lambda \cdot \overrightarrow{v} $
이젠 이 둘을 합쳐 동치로 놓습니다. 뜻은 아까 말했듯 'A 행렬 변환을 거친 벡터 = 특정 상수배 만큼 변한 벡터'입니다. 결국 벡터의 방향은 바뀌지 않고 크기만 바뀐셈이죠
$ A \cdot \overrightarrow{v} = \lambda \cdot \overrightarrow{v} $
그리고 이걸 풀기위해 이항하여 =0으로 바꿔줍니다.
$ A \cdot \overrightarrow{v} - \lambda \cdot \overrightarrow{v} = 0 $
공통된 벡터를 묶어줍니다. 행렬에서는 곱하는 방향이 중요하기 때분에(교환법칙 성립 x) 같은 방향으로 묶어줍니다.
$ (A - \lambda) \overrightarrow{v} = 0 $
근데 여기서 문제가 생깁니다. A는 행렬이고, $ \lambda $는 스칼라거든요..
그럼 어떻게 처리해줘야할까요? 행렬을 스칼라로? 스칼라를 행렬로?
 
네, 스칼라 값을 행렬로 변환해줘야합니다.
왜냐하면 지금 저희는 어떤 변환을 하더라도 변하지 않는 벡터를 찾는 중이니까요, 어떤 변환을 하는 행렬을 찾아야죠
그러면 $ \lambda $를 어떻게 행렬로 변환 할 것이냐...
일단 행렬의 뺄셈을 하려면 행렬의 크기가 맞아야겠죠?
그럼 이 스칼라 값에 어떤 행렬을 곱해주면 될텐데.. 어떤 행렬을 곱해줄까요..? 그냥 A행렬과 크기만 맞는 행렬이면 다 되는 걸까요?
 
물론 아니겠죠..! 스칼라 값을 어떤 행렬 공간에서 동일하게 작용하는 행렬로 확장하려면 단위행렬을 곱해줘야 합니다.
좀 더 정확하게 말하자면 [단위행렬은 '모든 벡터를 자기 자신으로 보존'하는 유일한 선형변환]이기 때문입니다.
어떻게 보자면 곱셈의 항등원과 같은 뜻입니다.
자, 이렇게 알아냈으니 다시 식을 써보죠
$ (A - \lambda \cdot I) \overrightarrow{v} = 0 $
네, 이게 바로 고유값 분해의 식입니다.
 
그리고 여기서 잘 보자면, 결국 $ (A - \lambda \cdot I) $가 0이거나, $ \overrightarrow{v} $가 0이어야지만이 이 식이 성립함을 알 수 있습니다.
그런데, 저희는 처음 시작부터 고유 벡터 $ \overrightarrow{v} $가 있다! 하고 가정을 하고 출발했으니까 $ \overrightarrow{v} $는 0이 되면 안됩니다. 결국, $ (A - \lambda \cdot I) $가 0이 되어야 하는데... 이게 0이 되는걸 어떻게 찾을 수 있을까요?
행렬을 단 하나의 스칼라 값으로 바꾸는 방법은 여러가지가 있지만, 그 중에서도 행렬식(determinant)이 가장 대표적입니다.
 

그냥 간단하게 스칼라 값으로 바꾼다고 했지만, 사실 고등학교정도의 행렬을 배웠던 사람이라면 행렬식은 좀 익숙할 겁니다.
바로 역행렬을 만들때 필요한 친구이기 때문인데요, 고등학교에서는 역행렬을 만들 때, $ \begin{pmatrix} a&b\\c&d \end{pmatrix}^{-1} = \frac{1}{ad-bc} \begin{pmatrix} d&-b\\-c&a \end{pmatrix} $로 배웠을 거에요.
그리고 사실 $ ad-bc $가 행렬식(determinant)이죠.
그리고 여기서 '행렬식이 0이면, 역행렬이 없다' = '역행렬이 존재하려면 행렬식이 0이면 안된다'는 결론이 나옵니다.
결국 이 문제에서도 $ (A - \lambda \cdot I) $가 역행렬이 있으면 안되기 때문에 $ det(A - \lambda \cdot I) $(행렬식 연산을 det라고 줄여서 표기합니다)가 0인 것을 찾는 겁니다.
여담으로 $ (A - \lambda \cdot I) $가 역행렬이 된다면,
$ (A - \lambda \cdot I)^{-1} (A - \lambda \cdot I) \overrightarrow{v} = (A - \lambda \cdot I)^{-1} \cdot 0 $
$ \overrightarrow{v} = 0 $
즉, 고유벡터가 영벡터가 되어버리므로 결국 저희가 세웠던 가정이 맞지 않게되어버립니다.

 
행렬식은 이미 아시다시피 2차는 아주 간단하게 $ \begin{pmatrix} a&b\\c&d \end{pmatrix} $ 행렬에서 $ ad-bc $입니다.
3차부터 복잡해지지만, 일단 저희는 지금 피보나치 수열을 구하는 수준에서 2차까지 알아보겠습니다.
 
자 그럼 다시 돌아와서, 우리는 지금 companion matrix를 대각화 하고 싶고, 그래서 방법을 찾다보니 우선 고유값 분해를 해야한다는 걸 알았습니다.
그러면 companion matrix를 고유값 분해합시다.
$ (A - \lambda \cdot I) \overrightarrow{v} = 0 $
여기서 A는 현재 companion matrix의 A입니다.
$ det(A - \lambda \cdot I) = 0 $이면 된다고 했습니다.
일단, 실제값으로 바꿔보죠
$ det( \begin{bmatrix} 1&1\\1&0 \end{bmatrix} - \lambda \cdot \begin{bmatrix} 1&0\\0&1 \end{bmatrix} ) = 0$
$ det( \begin{bmatrix} 1&1\\1&0 \end{bmatrix} - \begin{bmatrix} \lambda&0\\0&\lambda \end{bmatrix} ) =0 $
$ det( \begin{bmatrix} 1-\lambda&1\\1&-\lambda \end{bmatrix} ) =0 $
 
여기서 행렬식 연산을 해줍니다. $ ad-bc $
$ (1-\lambda)(-\lambda)-1 = 0 $
$ \lambda^2 - \lambda -1 = 0 $
풀어주면 되겠죠? 근의 공식에 넣어서 풀어주면 됩니다. 여기까지 오면서 정말 많이 풀었으니까(다른 포스팅에서 피보나치 수열 풀던 가락..) 여기서는 그냥 바로 뿅 가겠습니다.
$ \lambda = \frac{1+\sqrt5}{2} \; or \; \frac{1-\sqrt5}{2} $
$ \lambda_1 = \frac{1+\sqrt5}{2}, \; \lambda_2 = \frac{1-\sqrt5}{2} $
이렇게 놓을 수 있겠네요!
고유값(eigen value) 찾았습니다!
 
그럼이제 고유벡터를 찾아야겠죠?
고유벡터의 요소를 ab라고 놓으면,
$ \overrightarrow{v} = \begin{bmatrix} a\\b \end{bmatrix} $
$ \lambda $값이 두개였으니까 하나만 살펴보죠
$ (A - \lambda_1 \cdot I) \overrightarrow{v_1} = 0 $ 이므로,
$ \begin{bmatrix} 1-\lambda_1&1\\1&-\lambda_1 \end{bmatrix} \begin{bmatrix} a\\b \end{bmatrix} = 0 $ 이겠네요.
풀면,
$ \begin{cases} (1-\lambda_1)a+b = 0 \\ a-\lambda_1 b = 0 \end{cases} $
결국, $ a = \lambda_1 b $이고
$ \overrightarrow{v_1} = \begin{bmatrix} \lambda_1 b\\b \end{bmatrix} $
여기서 고유벡터는 방향만 나타내주면 되는 성분이니 그냥 가장 간단하게 b에다가 1 대입하면
$ \overrightarrow{v_1} = \begin{bmatrix} \lambda_1 \\1 \end{bmatrix} $
요렇게 정리가 됩니다. $ \lambda_2 $에 대해서 정리해도 똑같죠!
고유벡터(eigen vector) 찾았습니다!

위에서 왜 연립방정식 안푸냐... 하시는 분들도 계실텐데.. 두번째 식 $ a = \lambda_1 b $을 첫번째 식에 대입해서 풀어보시면 그냥 의미없이 $ b \cdot 0 = 0 $이런 결과를 얻으실 겁니다...

 
자, 그리고 이제 이 고유벡터를 column으로 stack한 새로운 행렬 P를 정의해보죠.(열벡터를 쌓아서 행렬 만들기는 흔한 조작중에 하나입니다)
$ P = \begin{bmatrix} v_1&v_2 \end{bmatrix} = \begin{bmatrix} \lambda_1&\lambda_2\\1&1 \end{bmatrix} $
자, 이제 대각화를 할 준비를 마쳤습니다.
어휴.. 쓰다보니까 진짜 엄청 기네요! 잘 따라와주세요!(사실 보통은 따로따로 파편적으로 공부하지만 이렇게 한번에 쭉 보는것도 도움이 된답니다!)
 

2-4. 드디어 대각화

자, 우리의 염원이던 '행렬의 거듭제곱 = 요소의 거듭제곱 그러나 답은 바뀌지 않는'을 찾기위한 여정의 막바지 입니다.
일단 우리는 companion matrix인 A를 알고있고, 고유벡터를 쌓아서 만든 P라는 matrix를 알고있습니다.
일단 이 두개. 곱해보죠.
$ AP = A \begin{bmatrix} v_1 & v_2 \end{bmatrix} $
자, 혹시 여기서 설명이 조금 헛갈리시면 행렬곱셈 개념정리를 한번 참조해주시기 바랍니다.
matrix와 column끼리 곱한 column을 모아도 행렬의 곱셈이 성립한다고 했습니다.
그렇다면 여기서 이렇게 식을 변형할 수 있겠네요?
$ AP = \begin{bmatrix} A \cdot v_1 & A \cdot v_2 \end{bmatrix} $
근데 위에서 우리는 고유값 분해를 했습니다.
고유값 분해식은
$ A \cdot \overrightarrow{v} = \lambda \cdot \overrightarrow{v} $
이거였죠.
어? 얘를 또 변형 가능해보입니다?
$ AP = \begin{bmatrix} A \cdot v_1 & A \cdot v_2 \end{bmatrix} =  \begin{bmatrix} \lambda_1 \cdot v_1 & \lambda_2 \cdot v_2 \end{bmatrix} $
 
자, 여기서 아까 [단위행렬은 '모든 벡터를 자기 자신으로 보존'하는 유일한 선형변환]이라고 했습니다.
즉, 이 단위행렬에 어떤 벡터하나가 곱해졌을 때 자기 자신이 나온다는 말이죠.
그럼 이 단위행렬이 스칼라배가 되면, 당연히 어떤 벡터도 방향은 그대로이고 스칼라배가 된 벡터가 나오겠죠?
자, 근데 여기서 벡터가 쌓인 행렬이 곱해지면 어떻게 될까요?
 
가령
$ \begin{bmatrix} v_1 & v_2 \end{bmatrix} \begin{bmatrix} 1&0 \\ 0&1 \end{bmatrix} = \begin{bmatrix} v_1 & v_2 \end{bmatrix} $
이건 자명하죠? 결국 [단위행렬은 '모든 벡터를 자기 자신으로 보존'하는 유일한 선형변환]이 맞네요
그렇다면 일정 스칼라배 한건?
$ \begin{bmatrix} v_1 & v_2 \end{bmatrix} \begin{bmatrix} 5&0 \\ 0&5 \end{bmatrix} = \begin{bmatrix} 5 \cdot v_1 & 5 \cdot v_2 \end{bmatrix} $
오, 역시 벡터의 배수배가 되는군요? 그럼 좀 더 나아가서 단위행렬이 아니라, 대각선으로 다른 값을 주면 각 벡터마다 곱해지는 배수가 달라지겠네요?
$ \begin{bmatrix} v_1 & v_2 \end{bmatrix} \begin{bmatrix} 2&0 \\ 0&5 \end{bmatrix} = \begin{bmatrix} 2 \cdot v_1 & 5 \cdot v_2 \end{bmatrix} $
오~ 그럼 다시 돌아가서
$ AP = \begin{bmatrix} \lambda_1 \cdot v_1 & \lambda_2 \cdot v_2 \end{bmatrix} $
이친구를 다시 보면...
오!
$ AP = \begin{bmatrix} v_1 & v_2 \end{bmatrix} \begin{bmatrix} \lambda_1 & 0\\ 0 & \lambda_2 \end{bmatrix} $
이렇게 변환이 되겠군요!
그리고 우리는 이 결과로부터 아주 재밌는 결과도 같이 얻었습니다! 네! 결국 대각선인 행렬을 찾아냈어요!
 
이 대각선 행렬을 D라고 해볼께요!
그럼 수식은
$ AP = A \begin{bmatrix} v_1 & v_2 \end{bmatrix} = \begin{bmatrix} A \cdot v_1 & A \cdot v_2 \end{bmatrix} =  \begin{bmatrix} \lambda_1 \cdot v_1 & \lambda_2 \cdot v_2 \end{bmatrix} = \begin{bmatrix} v_1 & v_2 \end{bmatrix} \begin{bmatrix} \lambda_1 & 0\\ 0 & \lambda_2 \end{bmatrix} = PD $
$ AP = PD $가 되겠죠!
여기서 P의 역행렬을 좌우변 모두 곱해주면!
$ A = PDP^{-1} $
와! 결국 companion matrix를 연역적 방법으로 대각행렬로 변환하는데 성공하였습니다!!!
 
그리고 이 변형에는 아주 재밌는 특성이 있는데요
$ A^2 = (PDP^{-1}) \cdot (PDP^{-1}) $이 되잖아요? 근데 $ P^{-1}P $는 상쇄되니까
$ A^2 = PDDP^{-1}  = PD^2P^{-1} $이 되면서, 결국 대각행렬만 제곱이 되는 꼴이 된답니다!
그럼 대각행렬의 거듭제곱은 뭐다? 요소의 거듭제곱으로 나타낼 수 있다!
와! 해결!
그럼 우리 companion matrix의 거듭제곱 문제가 해결되었어요!
 

2-5. 대각행렬로 다시나타내기

아까 
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = A^{n-1} \cdot \begin{bmatrix} 1\\0 \end{bmatrix} $
요렇게 깔끔하게 정리된 식을 얻었으나, 결국 companion matrix의 거듭제곱에 막혔던 것을 이번에 우리는 쉽게 파고들 수 있습니다.
$ A^{n-1} = PD^{n-1}P^{-1} $
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = PD^{n-1}P^{-1} \cdot \begin{bmatrix} 1\\0 \end{bmatrix} $
이제 진짜로 식을 풀어봅시다
 
 

3. 결론

여기서 $ P^{-1} $은
$ P^{-1} = \frac{1}{\lambda_1 - \lambda_2} \begin{bmatrix} 1&-\lambda_2 \\ -1 & \lambda_1 \end{bmatrix} $
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = \overbrace{\begin{bmatrix} \lambda_1 & \lambda_2 \\ 1&1 \end{bmatrix}}^P \overbrace{\begin{bmatrix} \lambda_1^{n-1}&0\\0&\lambda_2^{n-1} \end{bmatrix}}^{D^{n-1}} \cdot \overbrace{\frac{1}{\lambda_1 - \lambda_2} \begin{bmatrix} 1&-\lambda_2 \\ -1 & \lambda_1 \end{bmatrix}}^{P^{-1}} \cdot \begin{bmatrix} 1\\0 \end{bmatrix} $
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = \frac{1}{\lambda_1 - \lambda_2} \cdot \begin{bmatrix} \lambda_1 & \lambda_2 \\ 1&1 \end{bmatrix}\begin{bmatrix} \lambda_1^{n-1}&0\\0&\lambda_2^{n-1} \end{bmatrix} \begin{bmatrix} 1&-\lambda_2 \\ -1 & \lambda_1 \end{bmatrix} \cdot \begin{bmatrix} 1\\0 \end{bmatrix} $
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = \frac{1}{\lambda_1 - \lambda_2} \cdot \begin{bmatrix} \lambda_1^{n}&\lambda_2^{n} \\ \lambda_1^{n-1}&\lambda_2^{n-1}\end{bmatrix} \begin{bmatrix} 1&-\lambda_2 \\ -1 & \lambda_1 \end{bmatrix} \cdot \begin{bmatrix} 1\\0 \end{bmatrix} $
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = \frac{1}{\lambda_1 - \lambda_2} \cdot \begin{bmatrix} \lambda_1^{n}&\lambda_2^{n} \\ \lambda_1^{n-1}&\lambda_2^{n-1}\end{bmatrix} \begin{bmatrix} 1\\-1 \end{bmatrix} $
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = \frac{1}{\lambda_1 - \lambda_2} \cdot \begin{bmatrix} \lambda_1^{n}-\lambda_2^{n} \\ \lambda_1^{n-1}-\lambda_2^{n-1}\end{bmatrix} $
그리고 여기서 우리는 $ F_n $ 성분만 필요하므로 (개념적으로는 1번 요소만 꺼내서 쓰면 될 것이고, 수식적으로는 양변에 [1 0]을 곱해주면 될 것이다)
$ F_n = \frac{1}{\lambda_1 - \lambda_2} (\lambda_1^{n}-\lambda_2^{n}) $
여기서, $ \lambda_1 = \frac{1+\sqrt5}{2}, \; \lambda_2 = \frac{1-\sqrt5}{2} $이므로
 
$ F_n = \frac{1}{\sqrt5} \left(\left(\frac{1+\sqrt5}{2}\right)^{n}-\left(\frac{1-\sqrt5}{2}\right)^{n}\right) $
 
와! 선형대수로 피보나치 수열 풀기 성공!

선형대수[Linear Algebra]: 행렬곱셈(Matrix multiplication)의 개념 정리

1. 서론

선형대수를 하면서 사실 제일 큰게 수를 다루는 '감각'이 아닌가 싶다.

'엄밀하게 왜이래?'를 따지는 것도 중요하지만, 사실은 약간 '어~ 이게 이러니까 이렇게 되네? 오 쫌 재밌네?'하면서 받아들이고 사용하다보면 나중에 크게 이해되는 때가 오기도 한다.(그리고 그건 어떤 내부적이든 외부적이든 깨달음의 순간이 왔을 때 익숙했었어야지만이 깨달을 수 있다는 부분이기도 하다..)

그리고 선형대수는 아주 재밌게도, 직관적으로 '어 이거 되는거 아냐?'했을 때 되는 경우가 굉장히 많다. 사실 그래서 선대 수학자들이 '이게 왜 돼!?!?'하면서 연구를 더욱 더 심도있게 진행시키지 않았을까~ 하는 생각도 든다.

그래서 결론은 다른 고급(?)선형대수를 들어가기 전에, 가장 기본적인 행렬 곱셈의 개념부터 한번 정리하고 가면 좋겠다고 생각을 했다.

우리가 흔하게 아는 고등학교 때 배웠던 요소별로 채워넣는 행렬곱셈 말고도 행렬을 가로로(열로) 세로로(행으로) 찢어서 계산도 가능하다는 아주 재밌는 사실이 있기 때문이다.

2. 행렬의 곱셈방식은 몇가지?

그렇다면 행렬의 곱셈방식은 몇가지나 있을까?

물론 '방식'이 여러가지 인거지, '답'은 하나다.

결론부터 말하자면 곱셈방식은 사실 네가지다.

행렬을 행과 열로 찢어서 조합할 수 있다고 하면, 꽤나 많은 경우의 수가 나오겠지만

행렬곱셈을 수행하면 그 대원칙인 $ \sum row * column $가 수행되고, 따라서 (n x m) * (m x k) = (n x k)의 행렬이 나온다는 것만 알고 있으면 경우의 수는 사실 아래의 네가지로 귀결된다.

행(row) * 열(column), 행렬(matrix) * 열(column), 행(row) * 행렬(matrix), 열(column) * 행(row)

두 행렬을 모두 행과 열로 찢어서 곱해 볼 수 있는 두가지 방식이 있을 것이고

또 다른 하나는 한 행렬 전체를 다른 행렬을 찢어서 곱해볼 수 있을 것이다.

그렇다면 남은 건 하나. '진짜 되는가?'이다.

사실 '개념'적으로 저렇게 나눠 놓은거지, 사실 실제 계산을 하면 결국 $ \sum row * column $이 수행되기때문에 결과는 항상 모두 같을 수 밖에 없다. 다만 저런 개념을 알고 있으면 행렬 곱셈을 조작할 때 좀더 자유롭게 조작이 가능해진다는 장점?

3. 간단한 행렬로 진짜 되는지 보기

$ A = \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix} $

$ B = \begin{bmatrix} 1&2\\ 1&3 \end{bmatrix} $

두 행렬을 가지고 $ A * B = C $를 해 볼 예정입니다.

3-1. row * column

가장 기본적인 행렬 곱셈 방식이죠.

$ C = \begin{bmatrix} a_{11}*b_{11}+a_{12}*b_{21}&a_{11}*b_{12}+a_{12}*b_{22}\\ a_{21}*b_{11}+a_{22}*b_{21}&a_{21}*b_{12}+a_{22}*b_{22} \end{bmatrix} $

$ \quad \, = \begin{bmatrix} 1*1+2*1&1*2+2*3\\ 3*1+4*1&3*2+4*3 \end{bmatrix} $

$ \quad \, = \begin{bmatrix} 3&8\\ 7&18 \end{bmatrix} $

3-2. matrix * column

여기서부터 재밌어집니다. matrix*column은 결과를 column으로 내보내고, 그렇기 때문에 결과에서 column으로 stack됩니다.

$ C = \begin{bmatrix} A*\begin{bmatrix} 1\\1 \end{bmatrix} & A*\begin{bmatrix} 2\\3 \end{bmatrix} \end{bmatrix} $

$ \quad \, = \begin{bmatrix} \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix}*\begin{bmatrix} 1\\1 \end{bmatrix} & \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix}*\begin{bmatrix} 2\\3 \end{bmatrix} \end{bmatrix} $

$ \quad \, = \begin{bmatrix} 3&8\\ 7&18 \end{bmatrix} $

3-3. row * matrix

row * matrix는 결과를 row로 내보내고, 결과적으로 row로 stack됩니다.

$ C = \begin{bmatrix} \begin{bmatrix} 1&2 \end{bmatrix}*B \\ \begin{bmatrix} 3&4 \end{bmatrix}*B \end{bmatrix} $

$ \quad \, = \begin{bmatrix} \begin{bmatrix} 1&2 \end{bmatrix} * \begin{bmatrix} 1&2\\ 1&3 \end{bmatrix} \\ \begin{bmatrix} 3&4 \end{bmatrix} * \begin{bmatrix} 1&2\\ 1&3 \end{bmatrix} \end{bmatrix} $

$ \quad \, = \begin{bmatrix} 3&8\\ 7&18 \end{bmatrix} $

3-4. column * row

두 행렬을 일반적인 행렬 곱셈 방식인 row*column이 아닌 반대로 column*row로 찢어서 계산합니다.

위의 행렬을 기준으로 보면 column*row로 계산하게되면 (2, 1) x (1, 2)가 되므로 (2, 2)의 확장이 일어나는 것과 마찬가지 결과가 생깁니다.

찢어서 계산했을 때 matrix가 2x2로 확장되므로, 결과값을 더해줍니다.

$ C = \begin{bmatrix} 1\\3 \end{bmatrix}*\begin{bmatrix} 1&2 \end{bmatrix} + \begin{bmatrix} 2\\4 \end{bmatrix}*\begin{bmatrix} 1&3 \end{bmatrix} $

$ \quad \, = \begin{bmatrix} 1&2\\3&6 \end{bmatrix} + \begin{bmatrix} 2&6\\4&12 \end{bmatrix} $

$ \quad \, = \begin{bmatrix} 3&8\\ 7&18 \end{bmatrix} $

4. 결론

이것으로 결국 어떤 방식으로 곱하든 결과는 같다는 걸 알았습니다.

반대로, 결과가 같다면 여러 방법으로 행렬의 곱셈을 조작해 볼 수 있습니다.