Machine Learning Foundations (BSCS2004) formula sheet

$\text{Use ML only when BOTH conditions hold:} \\ \textbf{Condition 1:} \quad \text{Human labor} \xrightarrow{\text{fails due to}} \underbrace{\text{scale / speed}_{\text{(scale/speed failure)}}}{} \\ \quad \text{AND programming} \xrightarrow{\text{fails because}} \text{the rule cannot be written in code} \\ \textbf{Condition 2:} \quad \underbrace{\text{Sufficient data is available}}_{\text{(data availability)}} \;+\; \text{structural hope the rule exists}$

$\hat{p} = 0.5 \times \text{area} - \text{distance}$

$y = \begin{cases} \text{close} & \text{if } 2 \times \text{rooms} - \text{price} < 1 \\ \text{far} & \text{otherwise} \end{cases}$

$P(\text{config}) \in [0,\, 1]$

$\text{price} = A \times \text{area} + B \times \text{rooms} + C \times \text{distance}$

$\widehat{\text{price}} = A \times \text{area} + B \times \text{rooms} + C \times \text{distance}$

$x = (x_1, x_2, \ldots, x_d) \in \mathbb{R}^d$

$\mathbb{1}(P) = \begin{cases} 1 & \text{if predicate } P \text{ is true} \\ 0 & \text{if predicate } P \text{ is false} \end{cases}$

$\text{Training data: } (x^1, y^1),\, (x^2, y^2),\, \ldots,\, (x^n, y^n)$

$f : \mathbb{R}^d \to \mathbb{R}, \quad \text{goal: } f(x^i) \approx y^i \text{ for all } i = 1, \ldots, n$

$\text{loss}(f) = \frac{1}{n}\sum_{i=1}^{n}\bigl(f(x^i) - y^i\bigr)^2$

$f(x) = w_1 x_1 + w_2 x_2 + \cdots + w_d x_d + b = w^T x + b$

$L(f) = \frac{1}{n} \sum_{i=1}^{n} \mathbb{1}[f(x_i) \neq y_i]$

$\text{sign}(z) = \begin{cases} +1 & \text{if } z > 0 \\ -1 & \text{if } z < 0 \end{cases}$

$f(x) = \text{sign}(w^T x + b)$

$L(f) = \frac{1}{6}\sum_{i=1}^{6}\mathbb{1}[f(x_i)\neq y_i] = \frac{0}{6} = 0 \qquad L(g) = \frac{1}{6}\sum_{i=1}^{6}\mathbb{1}[g(x_i)\neq y_i] = \frac{1}{6}$

$f : \mathbb{R}^D \to \mathbb{R}^{d'}, \quad d' \ll D$

$g : \mathbb{R}^{d'} \to \mathbb{R}^D$

$g\!\left(f(x_i)\right) = x_i \quad \text{(ideal goal)}$

$\|g(f(x_i)) - x_i\|^2 = \sum_{j=1}^{D}\bigl(g(f(x_i))_j - (x_i)_j\bigr)^2$

$\mathcal{L}(f,\,g) = \frac{1}{n}\sum_{i=1}^{n}\|g(f(x_i)) - x_i\|^2$

$\mathcal{L}(f,g) = \frac{1}{n}\sum_{i=1}^{n}\|g(f(x_i)) - x_i\|^2$

$P : \mathbb{R}^d \to \mathbb{R}^+, \quad P(x) \geq 0 \text{ for all } x, \quad \sum_{x} P(x) = 1 \; (\text{or } \int P(x)\, dx = 1)$

$\mathcal{L}(P) = \frac{1}{n} \sum_{i=1}^{n} \bigl(-\log P(x_i)\bigr)$

$\mathcal{L}(P_1) = -\frac{1}{4}\Bigl[\log\tfrac{1}{10} + \log\tfrac{1}{10} + \log\tfrac{1}{10} + \log\tfrac{1}{10}\Bigr] = -\log\tfrac{1}{10} = \log 10 \approx 2.303$

$\hat{\theta} = \arg\min_{\theta} \frac{1}{n} \sum_{i=1}^{n} \left(-\log P_{\theta}(x_i)\right)$

$d(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\| = \sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2 + \cdots + (x_d - y_d)^2}$

$d(x, y) = \|x - y\| = \sqrt{\sum_{i=1}^{d}(x_i - y_i)^2}$

$B(x,\epsilon) = \{\, y \in \mathbb{R}^d \mid d(x, y) < \epsilon \,\} \qquad \overline{B}(x,\epsilon) = \{\, y \in \mathbb{R}^d \mid d(x, y) \leq \epsilon \,\}$

$A^c = V \setminus A = \{x \in V : x \notin A\}$

$\forall \quad \exists \quad \Rightarrow \quad \Leftrightarrow$

$\lim_{i \to \infty} x_i = x^* \quad \Longleftrightarrow \quad \forall\,\epsilon > 0,\; \exists \text{ integer } N \text{ such that } x_n \in B(x^*, \epsilon) \text{ for all } n \geq N$

$d(x_n, x^*) = \sqrt{\left(1+\tfrac{4}{2^n}-1\right)^2 + \left(3-\tfrac{4}{2^n}-3\right)^2}$

$5u = 5 \cdot (1,\,2,\,3) = (5,\,10,\,15)$

$7v = 7 \cdot (4,\,0,\,-1) = (28,\,0,\,-7)$

$5u + 7v = (5+28,\;10+0,\;15+(-7)) = (33,\;10,\;8)$

$u \in V,\; v \in V,\; \alpha,\beta \in \mathbb{R} \;\Longrightarrow\; \alpha u + \beta v \in V$

$x \cdot y \;=\; x^T y \;=\; \sum_{i=1}^{d} x_i y_i$

$\|x\|^2 \;=\; x \cdot x \;=\; x^T x \;=\; \sum_{i=1}^{d} x_i^2$

$x \perp y \iff x \cdot y = \sum_{i=1}^{d} x_i y_i = 0$

$u \cdot w = (1)(1) + (0)(-2) + (-1)(-1) = 1 + 0 + 1 = 2$

$f : A \to B, \quad x \mapsto f(x)$

$G_f = \{\,(x,\; f(x)) \mid x \in \mathbb{R}^d\,\}\;\subseteq\; \mathbb{R}^{d+1}$

$f: \mathbb{R} \to \mathbb{R}, \quad f(x) = x^2$

$G_f = \{\,(x,\, x^2) \mid x \in \mathbb{R}\,\} \;\subset\; \mathbb{R}^2$

$\text{Contour at level } c: \quad \{(x_1, x_2) \in \mathbb{R}^2 \mid f(x_1, x_2) = c\}$

$x_1^2 + x_2^2 = c \quad \Longleftrightarrow \quad \text{circle of radius } \sqrt{c} \text{ centred at the origin}$

$\lim_{i \to \infty} x_i = x^* \implies \lim_{i \to \infty} f(x_i) = f(x^*)$

$\lim_{i \to \infty} x_i = x^* \implies \lim_{i \to \infty} f(x_i) = f(x^*) \quad \text{(must hold for EVERY such sequence)}$

$\frac{f(x) - f(x^*)}{x - x^*}$

$f'(x^*) = \lim_{h \to 0} \frac{f(x^* + h) - f(x^*)}{h}$

$f'(x^*) = \lim_{x \to x^*} \frac{f(x) - f(x^*)}{x - x^*} \quad \xrightarrow{x \approx x^*} \quad f'(x^*) \approx \frac{f(x) - f(x^*)}{x - x^*}$

$f(x) \approx \underbrace{f(x^*)}_{\text{height at base point}} + \underbrace{f'(x^*)}_{\text{slope}} \cdot (x - x^*) \qquad \text{for } x \approx x^*$

$f(x) \approx f(0) + f'(0)\cdot x \quad \text{(valid near } x = 0\text{)}$

$\begin{array}{lllll} \textbf{Function} & f(0) & f'(x) & f'(0) & \textbf{Approximation near }x=0 \\ \hline \sin x & 0 & \cos x & 1 & \sin x \approx x \\ e^x & 1 & e^x & 1 & e^x \approx 1+x \\ \log(1+x) & 0 & \tfrac{1}{1+x} & 1 & \log(1+x) \approx x \\ (1+x)^r & 1 & r(1+x)^{r-1} & r & (1+x)^r \approx 1+rx \end{array}$

$(1+x)^r \approx 1 + rx \quad \text{when } x \approx 0$

$g(x) \approx g(0) + x\,g'(0), \qquad h(x) \approx h(0) + x\,h'(0)$

$f'(0) = g'(0)\,h(0) + h'(0)\,g(0)$

$g\!\left(h(0)+h'(0)x\right) \approx g(h(0)) + g'(h(0))\,\underbrace{[h(0)+h'(0)x - h(0)]}_{h'(0)\,x} = g(h(0)) + g'(h(0))\,h'(0)\,x$

$f'(0) = g'(h(0))\cdot h'(0)$

$f(x) \approx f(x^*) + f'(x^*)(x - x^*) + \frac{1}{2}f''(x^*)(x - x^*)^2$

$L_{x^*}f = f(x^*) + f'(x^*)(x - x^*)$

$x^* \text{ is a critical point of } f \iff f'(x^*) = 0$

$f''(x^*) = \frac{d^2 f}{dx^2}\bigg|_{x=x^*}$

$\text{At a critical point } x^* \text{ where } f'(x^*)=0:\quad \begin{cases} f''(x^*)>0 & \Rightarrow \text{local minimum}\\ f''(x^*)<0 & \Rightarrow \text{local maximum}\\ f''(x^*)=0 & \Rightarrow \text{inconclusive} \end{cases}$

$f'(x) = 3x^2 - 3$

$f''(x) = 6x$

$\text{Line through } u \in \mathbb{R}^d \text{ along } v \in \mathbb{R}^d = \{\, x \in \mathbb{R}^d : x = u + \alpha v,\ \alpha \in \mathbb{R} \,\}$

$\text{Line through } u,\, u' \;=\; \{\, x \in \mathbb{R}^d : x = u + \alpha(u' - u),\; \alpha \in \mathbb{R} \,\}$

$H = \left\{ x \in \mathbb{R}^d : w^T x = b \right\} = \left\{ x \in \mathbb{R}^d : \sum_{i=1}^{d} w_i x_i = b \right\}$

$\mathbf{v} = \mathbf{u'} - \mathbf{u} = (1,2,3) - (0,0,0) = (1,2,3)$

$\frac{\partial f}{\partial x_i}(v) = \lim_{\alpha \to 0} \frac{f(v + \alpha\, e_i) - f(v)}{\alpha}$

$\nabla f(v) = \begin{pmatrix} \dfrac{\partial f}{\partial x_1}(v) \\[6pt] \dfrac{\partial f}{\partial x_2}(v) \\ \vdots \\ \dfrac{\partial f}{\partial x_d}(v) \end{pmatrix} \qquad \text{(column vector, } d \text{ entries)}$

$\underbrace{f(x)}_{\text{true value}} \approx \underbrace{f(x^*)}_{\text{value at base}} + \underbrace{f'(x^*)}_{\text{slope}} (x - x^*) \quad \text{(1-D, recall)}$

$L_v f(x) \;=\; f(v) + \nabla f(v)^T (x - v) \;=\; f(v) + \sum_{i=1}^{d} \frac{\partial f}{\partial x_i}(v)\,(x_i - v_i)$

$\{x \in \mathbb{R}^d : L_v f(x) = f(v)\} = \{x \in \mathbb{R}^d : \nabla f(v)^T x = \nabla f(v)^T v\}$

$D_u f(v) = \lim_{\alpha \to 0} \frac{f(v + \alpha u) - f(v)}{\alpha}$

$D_u f(v) = \nabla f(v)^T u$

$-\|a\|\,\|b\| \;\leq\; a^T b \;\leq\; \|a\|\,\|b\|$

$u^{\star}_{\text{ascent}} = \frac{\nabla f(v)}{\|\nabla f(v)\|}$

$\nabla f(v)^T u < 0 \quad \Longleftrightarrow \quad u \text{ is a descent direction at } v$

$\text{If } f(x) \text{ is minimised (or maximised) at } v, \quad \nabla f(v) = \mathbf{0}$

$C(A) = \{ A\mathbf{x} : \mathbf{x} \in \mathbb{R}^n \} = \operatorname{span}(\mathbf{u}_1, \mathbf{u}_2, \ldots, \mathbf{u}_n)$

$N(A) = \{ \mathbf{x} \in \mathbb{R}^n : A\mathbf{x} = \mathbf{0} \}$

$\operatorname{rank}(A) + \operatorname{nullity}(A) = n$

$R(A) = C(A^T) = \operatorname{span}(\text{rows of } A)$

$N(A^T) = \{ \mathbf{y} \in \mathbb{R}^m : A^T \mathbf{y} = \mathbf{0} \} = \{ \mathbf{y} : \mathbf{y}^T A = \mathbf{0}^T \}$

$\underbrace{\dim C(A)}_{r} + \underbrace{\dim N(A)}_{n-r} = n \qquad \underbrace{\dim R(A)}_{r} + \underbrace{\dim N(A^T)}_{m-r} = m$

$\|x\| = \sqrt{x_1^2 + x_2^2 + \cdots + x_n^2}$

$\|x\|^2 + \|y\|^2 = \|x\|^2 + \|y\|^2 + 2\,x^Ty \implies x^Ty = 0$

$x^T y = \sum_{i=1}^{n} x_i y_i = x_1 y_1 + x_2 y_2 + \cdots + x_n y_n$

$\text{Vectors } u, v \text{ are orthonormal if } u^T v = 0 \quad \text{and} \quad \|u\| = 1, \quad \|v\| = 1$

$U \perp V \;\iff\; x^T y = 0 \quad \forall\, x \in U,\; \forall\, y \in V$

$\text{C}(A^T) \perp \text{N}(A) \quad \Longleftrightarrow \quad r^T x = 0 \text{ for every } r \in \text{C}(A^T),\; x \in \text{N}(A)$

$Ax = \begin{pmatrix} r_1^T x \\ r_2^T x \\ \vdots \\ r_m^T x \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix}$

$v = c_1 r_1 + c_2 r_2 + \cdots + c_m r_m \implies v^T x = c_1 (r_1^T x) + c_2 (r_2^T x) + \cdots + c_m (r_m^T x) = c_1 \cdot 0 + c_2 \cdot 0 + \cdots + c_m \cdot 0 = 0$

$\boxed{\text{C}(A^T) \perp \text{N}(A)} \qquad \text{and} \qquad \boxed{\text{C}(A) \perp \text{N}(A^T)}$

$p = \hat{x}\, a, \qquad e = b - p = b - \hat{x}\, a$

$a^T(b - \hat{x}\,a) = 0$

$\hat{x} = \frac{a^T b}{a^T a}$

$p = \hat{x}\,a = \frac{a^T b}{a^T a}\,a$

$p \;=\; \hat{x}\,a \;=\; \frac{a^T b}{a^T a}\,a \;=\; \frac{a\,a^T}{a^T a}\,b \;=\; P\,b$

$P \;=\; \frac{a\,a^T}{a^T a}$

$\|e\|^2 = \left\| b - p \right\|^2 \geq 0$

$(a^T b)^2 \;\leq\; (a^T a)(b^T b) \quad\Longleftrightarrow\quad |a^T b| \;\leq\; \|a\|\,\|b\|$

$P^T = \left(\frac{aa^T}{a^Ta}\right)^T = \frac{(aa^T)^T}{a^Ta} = \frac{aa^T}{a^Ta} = P$

$P^2 = \frac{aa^T}{a^Ta}\cdot\frac{aa^T}{a^Ta} = \frac{a(a^Ta)a^T}{(a^Ta)^2} = \frac{aa^T}{a^Ta} = P$

$E = \sum_{i=1}^{m}(a_i x - b_i)^2$

$E = (2x - b_1)^2 + (3x - b_2)^2 + (4x - b_3)^2$

$\hat{x} = \frac{2b_1 + 3b_2 + 4b_3}{2^2 + 3^2 + 4^2} = \frac{2b_1 + 3b_2 + 4b_3}{29}$

$e \perp \text{col}(A) \quad \Longleftrightarrow \quad a_i^T e = 0 \text{ for every column } a_i \text{ of } A$

$A^T e = 0 \quad \Longrightarrow \quad A^T(b - A\hat{x}) = 0$

$A^T e = 0 \\[6pt] \Rightarrow\quad A^T(b - A\hat{x}) = 0 \\[6pt] \Rightarrow\quad A^T b - A^T A\hat{x} = 0 \\[6pt] \Rightarrow\quad \boxed{A^T A\,\hat{x} = A^T b}$

$\hat{x} = (A^T A)^{-1} A^T b$

$P = A(A^T A)^{-1} A^T, \qquad p = Pb$

$P^T = \bigl(A(A^T A)^{-1} A^T\bigr)^T$

$P^T = P \quad \text{and} \quad P^2 = P \;\iff\; P \text{ is an orthogonal projection matrix}$

$\hat{\theta},\hat{\theta}' = \arg\min_{\theta,\theta'} \sum_{i=1}^{m}\bigl(b_i - \theta x_i - \theta'\bigr)^2$

$\underbrace{\begin{pmatrix} -1 & 1 \\ 2 & 1 \\ 1 & 1 \end{pmatrix}}_{A} \underbrace{\begin{pmatrix} \theta \\ \theta' \end{pmatrix}}_{\hat{\theta}} = \underbrace{\begin{pmatrix} 1 \\ 1 \\ 3 \end{pmatrix}}_{b}$

$A^T A\, \hat{\theta} = A^T b$

$b \notin \text{col}(A) \implies A\theta = b \text{ is inconsistent}$

$A^T A = \begin{pmatrix} \mathbf{a}_1^T\mathbf{a}_1 & \mathbf{a}_1^T\mathbf{a}_2 \\ \mathbf{a}_2^T\mathbf{a}_1 & \mathbf{a}_2^T\mathbf{a}_2 \end{pmatrix}$

$\begin{pmatrix}6&2\\2&3\end{pmatrix}\begin{pmatrix}\hat{\theta}\\\hat{\theta}'\end{pmatrix} = \begin{pmatrix}6\\5\end{pmatrix} \quad\Longrightarrow\quad \begin{cases}6\hat{\theta}+2\hat{\theta}'=6\\2\hat{\theta}+3\hat{\theta}'=5\end{cases}$

$\hat{\theta} = \frac{4}{7}, \quad \hat{\theta}' = \frac{9}{7} \quad\Longrightarrow\quad \text{best-fit line: } \hat{b}(x) = \frac{4}{7}x + \frac{9}{7}$

$e = b - A\hat{\theta}$

$A^T e = A^T(b - A\hat{\theta}) = 0$

$L(\theta) = \sum_{i=1}^{n} (x_i^T \theta - y_i)^2$

$A = \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix}, \quad \theta = \begin{pmatrix} \theta_1 \end{pmatrix}, \quad Y = \begin{pmatrix} 2.1 \\ 3.9 \\ 6.2 \end{pmatrix}$

$A\theta - Y = \begin{pmatrix} x_1^T\theta - y_1 \\ x_2^T\theta - y_2 \\ x_3^T\theta - y_3 \end{pmatrix} = \begin{pmatrix} \theta_1 - 2.1 \\ 2\theta_1 - 3.9 \\ 3\theta_1 - 6.2 \end{pmatrix}$

$L(\theta) = \frac{1}{2}(A\theta - Y)^T(A\theta - Y)$

$\nabla_{\theta} L = A^T A\,\theta - A^T Y$

$A^T A\,\theta = A^T Y$

$\text{null}(A) = \text{null}(A^T A)$

$\theta^* = (A^T A)^{-1} A^T Y \quad \text{exists and is unique} \iff A \text{ is full rank}$

$A = \begin{pmatrix} 1 & 1 \\ 2 & 1 \\ 3 & 1 \end{pmatrix}, \quad Y = \begin{pmatrix} 2 \\ 3 \\ 5 \end{pmatrix}$

$\log L(\theta) = \underbrace{\frac{n}{2}\log\beta - \frac{n}{2}\log 2\pi}_{\text{constants, no }\theta} \;-\; \frac{\beta}{2}\sum_{i=1}^{n}(y_i - \theta^T x_i)^2$

$\phi(x) = \begin{pmatrix} 1 \\ x \\ x^2 \\ \vdots \\ x^m \end{pmatrix} \in \mathbb{R}^{m+1}$

$A = \begin{pmatrix} 1 & x_1 & x_1^2 \\ 1 & x_2 & x_2^2 \\ 1 & x_3 & x_3^2 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 2 & 4 \\ 1 & 3 & 9 \end{pmatrix}$

$\theta = \begin{pmatrix} \theta_0 \\ \theta_1 \\ \theta_2 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \quad \Longrightarrow \quad \hat{y}(x) = 0 + 0\cdot x + 1\cdot x^2 = x^2$

$\bar{L}(\theta) = \sum_{i=1}^{n}(x_i^T\theta - y_i)^2 + \lambda\|\theta\|^2$

$\theta_{\text{ridge}} = (A^T A + \lambda I)^{-1} A^T Y$

$A\mathbf{x} = \lambda \mathbf{x}$

$Ax = \lambda x \;\Longrightarrow\; (A - \lambda I)x = 0 \;\Longrightarrow\; \det(A - \lambda I) = 0$

$\lambda_1 + \lambda_2 = \text{tr}(A) = a_{11} + a_{22}, \qquad \lambda_1 \cdot \lambda_2 = \det(A)$

$\text{null}(A - \lambda I) \;=\; \{\, x \neq 0 \mid (A - \lambda I)\,x = 0 \,\}$

$\det(A - \lambda I) = \det\!\begin{bmatrix} 3-\lambda & 1 \\ 1 & 3-\lambda \end{bmatrix} = (3-\lambda)^2 - 1 = \lambda^2 - 6\lambda + 8 = 0$

$\lambda_1 + \lambda_2 = \operatorname{trace}(A) = 6 \qquad \lambda_1 \cdot \lambda_2 = \det(A) = 8$

$\underbrace{\begin{bmatrix}3&1\\1&3\end{bmatrix}}_{A}\underbrace{\begin{bmatrix}1\\1\end{bmatrix}}_{x_1} = \begin{bmatrix}4\\4\end{bmatrix} = 4\begin{bmatrix}1\\1\end{bmatrix} = \lambda_1 x_1 \quad\checkmark$

$\underbrace{\begin{bmatrix}3&1\\1&3\end{bmatrix}}_{A}\underbrace{\begin{bmatrix}1\\-1\end{bmatrix}}_{x_2} = \begin{bmatrix}2\\-2\end{bmatrix} = 2\begin{bmatrix}1\\-1\end{bmatrix} = \lambda_2 x_2 \quad\checkmark$

$\det(A - \lambda I) = \det\begin{bmatrix} -\lambda & -1 \\ 1 & -\lambda \end{bmatrix} = (-\lambda)(-\lambda) - (-1)(1) = \lambda^2 + 1 = 0$

$A \text{ is diagonalizable} \iff \exists \text{ invertible } S \text{ such that } S^{-1}AS = \Lambda, \quad \Lambda = \begin{pmatrix} \lambda_1 & & \\ & \ddots & \\ & & \lambda_n \end{pmatrix}$

$S = \begin{bmatrix} x_1 & x_2 & \cdots & x_n \end{bmatrix}, \qquad \Lambda = \begin{bmatrix} \lambda_1 & & \\ & \ddots & \\ & & \lambda_n \end{bmatrix}$

$\begin{aligned} AS &= A[x_1 \; x_2 \; \cdots \; x_n] \\[4pt] &= [Ax_1 \; Ax_2 \; \cdots \; Ax_n] \quad \text{(apply } A \text{ to each column)} \\[4pt] &= [\lambda_1 x_1 \; \lambda_2 x_2 \; \cdots \; \lambda_n x_n] \quad \text{(eigenvector equation: } Ax_i = \lambda_i x_i \text{)} \\[4pt] &= [x_1 \; x_2 \; \cdots \; x_n] \begin{bmatrix} \lambda_1 & & \\ & \ddots & \\ & & \lambda_n \end{bmatrix} \quad \text{(factor out the scalars into a diagonal matrix)} \\[4pt] &= S\Lambda \end{aligned}$

$AS = S\Lambda \;\xrightarrow{\text{multiply left by }S^{-1}}\; S^{-1}AS = \Lambda$

$c_1 x_1 + c_2 x_2 = \mathbf{0} \quad \cdots\text{(Eq. 1)}$

$A(c_1 x_1 + c_2 x_2) = \mathbf{0} \implies c_1 \lambda_1 x_1 + c_2 \lambda_2 x_2 = \mathbf{0} \quad \cdots\text{(Eq. 2)}$

$\text{Eq. 2} - \lambda_2 \cdot \text{Eq. 1}: \quad c_1(\lambda_1 - \lambda_2)\,x_1 = \mathbf{0}$

$\lambda_1, \lambda_2, \ldots, \lambda_n \text{ all distinct} \implies x_1, x_2, \ldots, x_n \text{ linearly independent} \implies A \text{ is diagonalizable}$

$AS = S\Lambda \;\Longrightarrow\; A\,y_i = \lambda_i\, y_i \quad (i = 1,\ldots,n)$

$A^k = S\,\Lambda^k\,S^{-1}, \qquad \Lambda^k = \operatorname{diag}(\lambda_1^k,\,\lambda_2^k,\,\ldots,\,\lambda_n^k)$

$\begin{pmatrix} F_{k+2} \\ F_{k+1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{k+1} \\ F_k \end{pmatrix}$

$u_k = A^k\, u_0, \quad u_k = \begin{pmatrix} F_{k+1} \\ F_k \end{pmatrix}, \quad A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}, \quad u_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$

$A^k x_i = \lambda_i^k\, x_i$

$u_k = A^k u_0 = C_1\,\lambda_1^k\, x_1 + C_2\,\lambda_2^k\, x_2 + \cdots + C_n\,\lambda_n^k\, x_n$

$\det(A - \lambda I) = (1-\lambda)(-\lambda) - (1)(1)$

$= -\lambda + \lambda^2 - 1 = \lambda^2 - \lambda - 1 = 0$

$\lambda = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} = \frac{1 \pm \sqrt{1 + 4}}{2} = \frac{1 \pm \sqrt{5}}{2}$

$\lambda_1 = \frac{1+\sqrt{5}}{2} \approx 1.618 \quad (\text{the golden ratio } \phi), \qquad \lambda_2 = \frac{1-\sqrt{5}}{2} \approx -0.618$