MCP๋กœ ์—ฐ๊ฒฐ โ†’

๊ณ„์‚ฐ ์ž…๋ ฅ

๊ณต์‹

๊ด‘๊ณ 

๊ฒฐ๊ณผ

Matrix A to the power n (A2)
7 10
15 22
ํ–‰๋ ฌ ํฌ๊ธฐ 2 x 2
์ง€์ˆ˜ n 2

ํ–‰๋ ฌ ๊ฑฐ๋“ญ์ œ๊ณฑ ๊ณ„์‚ฐ๊ธฐ๋ž€?

์ด ๋„๊ตฌ๋Š” ์ •์‚ฌ๊ฐํ–‰๋ ฌ A๋ฅผ ์ •์ˆ˜ n๋งŒํผ ๊ฑฐ๋“ญ์ œ๊ณฑํ•œ ๊ฐ’, ์ฆ‰ \(A^{n}\)์„ ๊ตฌํ•ด ์ค๋‹ˆ๋‹ค. ํ–‰๋ ฌ์„ ์ž๊ธฐ ์ž์‹ ๊ณผ n๋ฒˆ ๊ณฑํ•œ ๋’ค ๊ทธ ๊ฒฐ๊ณผ ํ–‰๋ ฌ์„ ๋ณด์—ฌ ์ค๋‹ˆ๋‹ค. ์‹ค์ˆ˜ ์„ฑ๋ถ„์œผ๋กœ ์ด๋ฃจ์–ด์ง„ 2x2, 3x3, 4x4 ํ–‰๋ ฌ์—์„œ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค. ํ–‰๋ ฌ ๊ฑฐ๋“ญ์ œ๊ณฑ์€ ์„ ํ˜•๋Œ€์ˆ˜ ๊ณณ๊ณณ์—์„œ ๋“ฑ์žฅํ•ฉ๋‹ˆ๋‹ค. ๋งˆ๋ฅด์ฝ”ํ”„ ์—ฐ์‡„์™€ ์ „์ดํ–‰๋ ฌ, ๊ทธ๋ž˜ํ”„ ์ธ์ ‘ํ–‰๋ ฌ์˜ ๊ฑฐ๋“ญ์ œ๊ณฑ(๊ฒฝ๋กœ ๊ฐœ์ˆ˜ ์„ธ๊ธฐ), ์ด์‚ฐ ๋™์—ญํ•™๊ณ„, ๊ทธ๋ฆฌ๊ณ  ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด ๊ฐ™์€ ์ ํ™”์‹์ด ๋Œ€ํ‘œ์ ์ธ ์˜ˆ์ž…๋‹ˆ๋‹ค.

์‚ฌ์šฉ ๋ฐฉ๋ฒ•

๋จผ์ € ํ–‰๋ ฌ ํฌ๊ธฐ๋ฅผ ๊ณ ๋ฅด๊ณ , ๊ฒฉ์ž์˜ ๊ฐ ์นธ์— A์˜ ์„ฑ๋ถ„์„ ํ•˜๋‚˜์”ฉ ์ž…๋ ฅํ•ฉ๋‹ˆ๋‹ค(์†Œ์ˆ˜์™€ ์Œ์ˆ˜ ๋ชจ๋‘ ๊ฐ€๋Šฅ). ๊ทธ๋Ÿฐ ๋‹ค์Œ ์ •์ˆ˜ ์ง€์ˆ˜ n์„ ์ž…๋ ฅํ•˜๊ณ  ๊ณ„์‚ฐ ๋ฒ„ํŠผ์„ ๋ˆ„๋ฅด์„ธ์š”. n = 0์ด๋ฉด ๋‹จ์œ„ํ–‰๋ ฌ์ด, n = 1์ด๋ฉด A๊ฐ€ ๊ทธ๋Œ€๋กœ ๋‚˜์˜ค๋ฉฐ, n โ‰ฅ 2์ด๋ฉด ๋ฐ˜๋ณต ๊ณฑ์…ˆ ๊ฒฐ๊ณผ๋ฅผ ์–ป์Šต๋‹ˆ๋‹ค. A๊ฐ€ ์—ญํ–‰๋ ฌ์„ ๊ฐ€์ง„๋‹ค๋ฉด(๊ฐ€์—ญํ–‰๋ ฌ) ์Œ์ˆ˜ n๋„ ์ž…๋ ฅํ•  ์ˆ˜ ์žˆ๋Š”๋ฐ, ์ด ๊ฒฝ์šฐ ๋จผ์ € ์—ญํ–‰๋ ฌ์„ ๊ตฌํ•œ ๋’ค |n|์ œ๊ณฑ์„ ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค.

๊ณ„์‚ฐ ๊ณต์‹

๊ฑฐ๋“ญ์ œ๊ณฑ์€ ์žฌ๊ท€์ ์œผ๋กœ ์ •์˜๋ฉ๋‹ˆ๋‹ค. \(A^{0} = I\)(๋‹จ์œ„ํ–‰๋ ฌ), \(A^{1} = A\), ๊ทธ๋ฆฌ๊ณ  \(A^{n} = A \cdot A^{n-1}\)์ž…๋‹ˆ๋‹ค.

$$A^{\,n} = \underbrace{A \cdot A \cdots A}_{n\ \text{times}}$$

๋‘ jร—j ํ–‰๋ ฌ์˜ ๊ณฑ \(C = A \cdot B\)์˜ ์„ฑ๋ถ„์€ \(C[i][k] = \sum A[i][m] \cdot B[m][k]\)๋กœ ๊ตฌํ•ฉ๋‹ˆ๋‹ค. ์ด ๊ณ„์‚ฐ๊ธฐ๋Š” ํšจ์œจ์„ ์œ„ํ•ด '์ œ๊ณฑ์„ ์ด์šฉํ•œ ๊ฑฐ๋“ญ์ œ๊ณฑ(exponentiation by squaring)' ๋ฐฉ์‹์„ ์“ฐ์ง€๋งŒ, ๊ฒฐ๊ณผ๋Š” ๋‹จ์ˆœ ๋ฐ˜๋ณต ๊ณฑ์…ˆ๊ณผ ์™„์ „ํžˆ ๊ฐ™์Šต๋‹ˆ๋‹ค. ํ–‰๋ ฌ ๊ฑฐ๋“ญ์ œ๊ณฑ์€ A๊ฐ€ ์ •์‚ฌ๊ฐํ–‰๋ ฌ(ํ–‰์˜ ์ˆ˜ = ์—ด์˜ ์ˆ˜)์ผ ๋•Œ๋งŒ ์ •์˜๋ฉ๋‹ˆ๋‹ค.

A์˜ n์ œ๊ณฑ์„ ํ–‰๋ ฌ A์˜ n๊ฐœ ๋ณต์‚ฌ๋ณธ์„ ๋ฐ˜๋ณตํ•ด์„œ ๊ณฑํ•˜๋Š” ๊ฒƒ์œผ๋กœ ๋‚˜ํƒ€๋‚ธ ๋„์‹
ํ–‰๋ ฌ์˜ ๊ฑฐ๋“ญ์ œ๊ณฑ Aโฟ์€ ํ–‰๋ ฌ A๋ฅผ ์ž๊ธฐ ์ž์‹ ๊ณผ n๋ฒˆ ๊ณฑํ•˜๋Š” ๊ฒƒ์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.

์˜ˆ์ œ ํ’€์ด

A = [[1, 2], [3, 4]]์ด๊ณ  n = 2๋ผ๊ณ  ํ•ฉ์‹œ๋‹ค. ๊ทธ๋Ÿฌ๋ฉด \(A^{2} = A \cdot A\)์ด๋ฉฐ \(c_{11} = 1 \cdot 1 + 2 \cdot 3 = 7\), \(c_{12} = 1 \cdot 2 + 2 \cdot 4 = 10\), \(c_{21} = 3 \cdot 1 + 4 \cdot 3 = 15\), \(c_{22} = 3 \cdot 2 + 4 \cdot 4 = 22\)๊ฐ€ ๋˜์–ด \(A^{2} = [[7, 10], [15, 22]]\)์ž…๋‹ˆ๋‹ค. ํ•œ ๋ฒˆ ๋” ์ œ๊ณฑํ•˜๊ฑฐ๋‚˜(๋˜๋Š” \(A^{3} = A^{2} \cdot A\)๋ฅผ ๊ณ„์‚ฐํ•˜๋ฉด) \(A^{3} = [[37, 54], [81, 118]]\)์„ ์–ป์Šต๋‹ˆ๋‹ค.

2x2 ํ–‰๋ ฌ์„ ์ œ๊ณฑํ•˜์—ฌ ๊ฒฐ๊ณผ ํ–‰๋ ฌ์„ ๊ตฌํ•˜๋Š” ํ’€์ด ์˜ˆ์ œ
2x2 ํ–‰๋ ฌ์„ ์ž๊ธฐ ์ž์‹ ๊ณผ ๊ณฑํ•˜์—ฌ Aยฒ๋ฅผ ๊ณ„์‚ฐํ•˜๊ธฐ.

์ž์ฃผ ๋ฌป๋Š” ์งˆ๋ฌธ

n = 0์ด๋ฉด ๋ฌด์—‡์ด ๋‚˜์˜ค๋‚˜์š”? ๊ด€๋ก€์— ๋”ฐ๋ผ ๊ฐ™์€ ํฌ๊ธฐ์˜ ๋‹จ์œ„ํ–‰๋ ฌ I๊ฐ€ ๋‚˜์˜ต๋‹ˆ๋‹ค.

์Œ์ˆ˜ ์ง€์ˆ˜๋ฅผ ์จ๋„ ๋˜๋‚˜์š”? A๊ฐ€ ๊ฐ€์—ญํ–‰๋ ฌ(ํ–‰๋ ฌ์‹ โ‰  0)์ด๋ผ๋ฉด ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. \(A^{-k}\)๋Š” \(\left(A^{-1}\right)^{k}\)์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

$$A^{\,n} = \left(A^{-1}\right)^{\left|n\right|},\quad \det(A) \neq 0$$

ํ–‰๋ ฌ์‹์ด 0์ด๋ฉด ๊ฒฐ๊ณผ๊ฐ€ ์ •์˜๋˜์ง€ ์•Š์œผ๋ฉฐ, ๊ณ„์‚ฐ๊ธฐ๊ฐ€ ์ด๋ฅผ ์•Œ๋ ค ์ค๋‹ˆ๋‹ค.

์™œ ์ผ๋ถ€ ์„ฑ๋ถ„์— ์•„์ฃผ ์ž‘์€ ์†Œ์ˆ˜๊ฐ€ ํ‘œ์‹œ๋˜๋‚˜์š”? ๊ฑฐ๋“ญ์ œ๊ณฑ์ด ํฌ๊ฑฐ๋‚˜ ์„ฑ๋ถ„ ๊ฐ’์ด ํด ๋•Œ ๋ถ€๋™์†Œ์ˆ˜์  ๋ฐ˜์˜ฌ๋ฆผ ์˜ค์ฐจ๊ฐ€ ๋ˆ„์ ๋  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฒฐ๊ณผ๋Š” ์•ฝ 14์ž๋ฆฌ ์œ ํšจ์ˆซ์ž๋กœ ๋ฐ˜์˜ฌ๋ฆผ๋ฉ๋‹ˆ๋‹ค.

์ตœ์ข… ์—…๋ฐ์ดํŠธ: