Lecture 13: Orthogonality

Based on Introduction to Linear Algebra by Gilbert Strang (opens in a new tab)

Orthogonality of Four Subspaces

Vektor Ortogonal memiliki dot-product bernilai nol $v^Tw = 0$ . Maka $||v||^2 + ||w||^2 = ||v+w||^2 = ||v-w||^2$ .
Subspace $V$ dan $W$ ortogonal jika $\forall_{v \in V}\forall_{w \in W} (v^Tw=0)$ .
Row space dari $A$ ortogonal dengan nullspacenya. Column space ortogonal dengan left-nullspacenya.
Pasangan dimensi memenuhi persamaan $r + (n - r) = n$ sementara pasangan lainnya memenuhi $r + (m - r) = m$ .
Row space dan nullspace adalah komplemen ortogonal, dalam artian setiap $x \in \mathbb{R}^n$ terpecah menjadi $x_{row} + x_{null}$ .

💡

\text{Orthogonal Subspaces: } \forall_{v \in V}\forall_{w \in W} (v^Tw=0)

Dalam kehidupan nyata, misalkan dinding dan lantai. Mereka terlihat saling tegak lurus (orthogonal), namun sebenarnya TIDAK.

⚠️

Tidak mungkin tegak lurus dua hal apabila $\texttt{dim}(V) + \texttt{dim}(W) > \texttt{dim(space)}$ .

Fundamental Theorem of Linear Algebra pt. 2

$N(A)$ adalah komplemen ortogonal dari $C(A^T)$ dalam $\mathbb{R}^n$ .

$N(A^T)$ adalah komplemen ortogonal dari $C(A)$ dalam $\mathbb{R}^m$ .

Setiap matriks dengan rank $r$ pasti memiliki $r \times r$ submatriks yang dapat diinvers.

Sebuah baris dalam $A$ tidak bisa menjadi nullspace dari $A$ . Vektor satu-satunya yang menjadi subspace di 2 ortogonal adalah vektor nol.

💡

Jika sebuah vektor $v$ ortogonal terhadap dirinya sendiri, maka $v$ adalah vektor nol.

Combining Bases from Subspaces

Properti independensi saling berimplikasi:

Setiap $n$ independen vektor di $\mathbb{R}^n$ harus span $\mathbb{R}^n$ . Maka mereka adalah basis.
Setiap $n$ vektor yang span $\mathbb{R}^n$ harus independen. Maka mereka adalah basis.
Jika $n$ kolom dari $A$ independen, mereka span $\mathbb{R}^n$ . Maka $Ax = b$ memiliki solusi.
Jika $n$ kolom dari $A$ span $\mathbb{R}^n$ , mereka independen. Maka $Ax = b$ memiliki solusi unik.

⚠️

Setiap $x$ adalah jumlahan dari $x_{row}$ dan $x_{null}$ .

Review of the Key Ideas

Subspace $V$ dan $W$ ortogonal jika $\forall_{v \in V}\forall_{w \in W} (v^Tw=0)$ .
$V$ dan $W$ adalah komplemen ortogonal jika $V$ dan $W$ ortogonal dan $\text{dim}V + \text{dim}W = n$ .
Row space dari $A$ ortogonal dengan nullspacenya. Column space ortogonal dengan left-nullspacenya.
Setiap $n$ independen vektor di $\mathbb{R}^n$ harus span $\mathbb{R}^n$ .
Setiap $n$ vektor yang span $\mathbb{R}^n$ harus independen.

Lecture 13.5: Projections

Based on Introduction to Linear Algebra by Gilbert Strang (opens in a new tab)

Projections

Proyeksi dari $b$ ke $a$ adalah poin terdekat $p = \frac{a^Tb}{a^Ta}a$ .
Error dari proyeksi $e = b - p$ tegak lurus dengan $a$ . Segitiga siku-siku $b\ p\ e$ memiliki properti $||b||^2 = ||p||^2 + ||e||^2$ .
Proyeksi dari $b$ ke subspace $S$ adalah vektor terdekat ke $P$ di $S$ . $b - p$ tegak lurus dengan $S$ .
$A^TA$ dapat diinvers (dan simetris) hanya jika $A$ memiliki kolom independen. $N(A^TA) = N(A)$ .
Proyeksi $b$ ke $C(A)$ adalah vektor $p = A(A^TA)^{-1}A^Tb$ .
Matriks proyeksi ke $C(A)$ adalah $\fbox{$P = A(A^TA)^{-1}A^T$}$ . Dimana $p = Pb$ dan $P^2 = P = P^T$ .

💡

\text{Matriks proyeksi ke }z: P_1 = \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix}

\text{Matriks proyeksi ke }xy: P_2 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix}

Projection onto a Line

Proyeksi dari $b$ ke $a$ adalah dengan vektor

p = \hat{x}a = \frac{a^Tb}{a^Ta}a

Dengan kasus spesial:

Jika $b = a$ maka $\hat{x} = 1$ . Proyeksinya adalah ke diri sendiri $Pa = a$ .
Jika $b \perp a$ maka $a^Tb = 0$ . Proyeksinya adalah nol $Pb = 0$ .

Contoh

Proyeksikan $b = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}$ ke $a = \begin{bmatrix} 1 \\ 2 \\ 4 \end{bmatrix}$ .

Jawab

\hat{x} = \frac{a^Tb}{a^Ta} = \frac{7}{21} = \frac{1}{3}

Sehingga proyeksi ke $a$ adalah

p = \frac{1}{3}a = \begin{bmatrix} \frac{1}{3} \\ \frac{2}{3} \\ \frac{4}{3} \end{bmatrix}

💡

Matriks proyeksi $P$

P = \frac{aa^T}{a^Ta}

Temukan matriks proyeksi dari problem sebelumnya!

Jawab

Kalikan kolom $a$ dengan baris $a^T$ lalu dibagi dengan $a^Ta$ .

P = \frac{1}{21}\begin{bmatrix} 1 \\ 2 \\ 4 \end{bmatrix}\begin{bmatrix} 1 & 2 & 4 \end{bmatrix} = \frac{1}{21}\begin{bmatrix} 1 & 2 & 4 \\ 2 & 4 & 8 \\ 4 & 8 & 16 \end{bmatrix}

Bila dibuktikan dengan $Pb$ akan menghasilkan $p$ :

Pb = \frac{1}{21}\begin{bmatrix} 1 & 2 & 4 \\ 2 & 4 & 8 \\ 4 & 8 & 16 \end{bmatrix}\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} \frac{1}{3} \\ \frac{2}{3} \\ \frac{4}{3} \end{bmatrix}

Projection onto a Subspace

Kombinaisi $p = \hat{x}_1a_1 + \hat{x}_2a_2 + \dots + \hat{x}_na_n$ adalah proyeksi dari $b$ ke subspace $S$ .

💡

Mencari $\hat{x}(n \times 1)$ :

\fbox{ $A^T(b - A\hat{x}) = 0$ or $A^TA\hat{x} = A^Tb$ }

Matriks $A^TA$ berukuran $n \times n$ dan simetris. Jika $A$ memiliki kolom independen, maka $A^TA$ dapat diinvers. Solusinya adalah $\hat{x} = (A^TA)^{-1}A^Tb$ . Proyeksi dari $b$ ke $S$ adalah $p$ :

💡

Mencari $p(m \times 1)$ :

\fbox{ $p = A\hat{x} = A(A^TA)^{-1}A^Tb$ }

Matriks proyeksi $P$ mengalikan dengan $b$ :

💡

Mencari $P(m \times m)$ :

\fbox{ $P = A(A^TA)^{-1}A^T$ }

Jika dibandingkan dengan proyeksi ke garis, maka $A$ adalah vektor $a$ dan $A^TA$ adalah $a^Ta$ . Namun jika dengan angka dibagi, dengan matriks diinvers.

💡

Untuk $n = 1$ :

\hat{x} = \frac{a^Tb}{a^Ta} \quad\text{ dan } \quad p = \frac{a^Tb}{a^Ta}a \quad\text{ dan }\quad P = \frac{aa^T}{a^Ta}

$A^TA$ dapat diinvers (dan simetris) hanya jika $A$ memiliki kolom independen $\implies A^TA$ persegi, simetris, dan invertible.

Review of the Key Ideas

Proyeksi dari $b$ ke $a$ adalah poin terdekat $p = a\hat{x} = \frac{a^Tb}{a^Ta}a$ .
Matriks proyeksi rank satu $P = \frac{aa^T}{a^Ta}$ dikalikan $b$ untuk menghasilkan $p$ .
Proyeksi dari $b$ ke subspace $S$ $e = b - p$ tegak lurus dengan $S$ .
Jika $A$ full rank $n$ , maka persamaan $A^TA\hat{x} = A^Tb$ memiliki solusi $\hat{x}$ dan $p = A\hat{x}$ .
Matriks proyeksi $P = A(A^TA)^{-1}A^T$ bersifat $P^T = P$ dan $P^2 = P$ , serta $Pb = p$ .

Lecture 12: The Four Fundamental Subspaces Lecture 14: Least Squares Approximations and Orthonormal Bases