Sercan'in guzel cevap(lar)indan sonra ben de bir ksky girisiminde bulunmak istiyorum. En basit yontem degil belki ama tatli bir yontem. Bu yanit neden lineer cebir etiketi kullandigimi da aciklayacak.
Fibonacci dizisi ve matrisler
$$A = \begin{bmatrix} 1 & 1 \\ 1 &0\end{bmatrix} \quad ; \quad x_n = \begin{bmatrix} f_{n+1} \\ f_n \end{bmatrix}$$ olsun. Fibonacci dizisini bu bilgiyle yeniden kodlayalim:
$$x_{n} = \begin{bmatrix}f_{n+1} \\ f_{n} \end{bmatrix} = \begin{bmatrix} f_{n} + f_{n-1} \\ f_{n} \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} \begin{bmatrix} f_{n} \\ f_{n-1} \end{bmatrix} = Ax_{n-1} $$ve bu islemi tekrar tekrar yapip $$x_{n} = A^n x_0$$ oldugunu gozlemleyelim. Soruyu cevapladik. $f_{n}$'i bulmak icin $A^n$'i hesaplayip bu matrisi $x_0$ ile carpmamiz lazim (Aslinda $A^{n-1}$'i hesaplamak yeterli tabii ama maksat indeksler guzel olsun).
Simdi hesaplamalari yapalim.
Bir matrisin kuvvetlerini hesaplamak
Elimizde herhangi bir matris olsun. Bu matrisin herhangi bir kuvvetini nasil hesaplayabiliriz? Matris carpimi halihazirda oldukca zaman alan bir is. Siradan bir $3 \times 3$ matrisin karesini almak bile -bilgisayar degilsek- hic kolay degil. Bazen sansli olabiliyoruz ama. Ornegin, $$A = \begin{bmatrix} a & 0 & 0 \\ 0 & b & 0 \\ 0 &0 & c \end{bmatrix} $$ ise $$A^2 = \begin{bmatrix} a^2 & 0 & 0 \\ 0 & b^2 & 0 \\ 0 &0 & c^2 \end{bmatrix}$$ oluyor. Daha da devam edersek $A^n$ matrisininin kosegeninde $a^n, b^n, c^n$ olan kosegen matris oldugunu gormek zor degil. Ama elimizdeki matris her zaman icin bu kadar guzel calismak zorunda degil. Isteyen $$\begin{bmatrix} 1 &2 &3 \\ 4 & 5& 6 \\ 7 & 8 & 9 \end{bmatrix}$$ matrisinin kubunu hesaplasin ve gorsun.
Ozdegerler ve Ozvektorler - Kosegenlestirme
$T : \mathbb{C}^n \to \mathbb{C}^n$ (isterseniz $\mathbb{C}$ yerine $\mathbb{R}$ alabilirsiniz) lineer bir fonksiyon olsun. Diyelim ki oldukca sansliyiz ve lineer bagimsiz $n$ tane ozvektorumuz var: $v_1, v_2, \ldots, v_n$. Standart lineer cebir bilgimizle $\{v_ 1, v_2 \ldots, v_n\}$ kumesinin $\mathbb{C}^n$ (isterseniz $\mathbb{R}^n$) icin bir taban oldugunu soyleyebiliriz. Yine standart lineer cebir bilgimizle bu lineer fonksiyonun bu tabana gore matrisini yazarsak bu matrisin bir kosegen matris oldugunu gorebiliriz (isteyen ornek yazip deneyebilir!). Taban degistirme formulunu kullanirsak, $A$ bu lineer fonksiyonun standart tabandaki matrisi, $S$ standart tabandan ozvektorlerden olusan tabana gecme matrisi ve $K$ yukaridaki kosegen matris olmak uzere $$A = S^{-1}KS$$ esitligini gorebiliriz. Yani, once taban degistir, yeni tabanda kosegen matrisle isini yap, sonra tabanini geri degistir.
Dikkat ederseniz $$A ^2 = S^{-1}KSS^{-1}KS = A^2 = S^{-1}K^2 S$$ ve ayni sekilde $$A^m = S^{-1} K^m S$$ demek ki kosegen bir matris olmasak bile, bu durumda kosegen $K$ matrisi ile buyuk kuvvetleri hesaplayip soldan $S^{-1}$ ve sagdan $S$ ile carparak kuvvetleri kolayca hesaplamak kolay.
Sonuc olarak, eger elimizdeki matrisin ozvektorleri taban olusturuyorsa, o zaman yuksek kuvvetleri almak o kadar da zor degil!
Ya bu kadar sansli degilsek?
Simdi kendimizi $\mathbb{C}^n$ durumuna kisitlayalim ve $n \times n$ bir matris dusunelim. Cebirin temel teoreminden dolayi $n$ adet ozdegerimiz oldugunu biliyoruz cunku karakteristik polinomumuz derecesi $n$ olan bir polinom. Ama bu ozdegerler birbirinden farkli olmak zorunda degiller, ornegin karakteristik polinom icerisinde $(x - 2)^2$ carpani varsa, $2$ ozdegeri birden fazla sayiliyor. Yukaridaki ilk durumda sansliydik ve ozdegerlerimiz kac defa sayiliyorsa, o kadar lineer bagimsiz ozvektor bulabiliyorduk ve ozdegerler bir taban olusturuyordu. Ama $$\begin{bmatrix} 1 & 1 \\ 0 & 1\end{bmatrix}$$ matrisinden de gorebilecegimiz gibi bu her zaman mumkun degil. Ama sorun degil. Yine de bir cozum yolu var: Jordan formu.
Buraya 8000 karakterden uzun yazamayacagim icin buraya hic girmeyecegim.
Soruya geri donelim
$$A = \begin{bmatrix} 1 & 1 \\ 1 & 0\end{bmatrix}$$ matrisinin ozdegerleri nelerdir? $$\det\begin{bmatrix}1 - x & 1 \\ 1 & -x \end{bmatrix} = (1-x)(-x) - 1 = x^2 - x - 1$$ oldugu icin ozdegerlerimiz Sercan'in cevabindaki $\phi$ ve $\bar{\phi}$. Peki ozdegerler nelerdir? Biraz hesaplama ile $$v_{\phi}=\begin{bmatrix} \phi \\ 1 \end{bmatrix} \quad ; \quad v_{\bar{\phi}}\begin{bmatrix} \bar{\phi} \\ 1 \end{bmatrix}$$ oldugunu bulabiliriz. O halde $$A^n x_0 = \begin{bmatrix} \phi & \bar{\phi} \\ 1 & 1\end{bmatrix}^{-1} \begin{bmatrix} \phi & 0 \\ 0 & \bar{\phi} \end{bmatrix} \begin{bmatrix} \phi & \bar{\phi} \\ 1 & 1\end{bmatrix}\begin{bmatrix} 1 \\ 0 \end{bmatrix}$$ Bunu korkmadan akillica hesaplayip ikinci girdisine bakarsak Sercan ve Okkes Dulgerci'nin cavaplarindaki $$f_n = \frac{(1 + \sqrt{5})^n - (1 - \sqrt{5})^n}{2^n \sqrt{5}}$$ formulune ulasiyoruz.