Vector Spaces, Basis & Dimension

Struktur Abstrak di Balik Data

Why This Matters for Your Work

Vector spaces adalah bahasa yang tepat untuk membicarakan hal-hal seperti:

Column space of $X$: apakah $\mathbf{y}$ bisa diprediksi sempurna oleh $X$? Jawabannya: ya, jika dan hanya jika $\mathbf{y} \in C(X)$.
OLS sebagai proyeksi: fitted values $\hat{\mathbf{y}}$ adalah proyeksi ortogonal $\mathbf{y}$ ke $C(X)$. Residuals $\mathbf{e}$ berada di orthogonal complement dari $C(X)$.
Identifiability: model teridentifikasi $\iff$ $X$ full column rank $\iff$ $\dim(C(X)) = p$.
Degrees of freedom: $df_{residual} = n - p = \dim(\text{orthogonal complement of } C(X))$.
Factor models: latent factors $\mathbf{f}$ span suatu subspace; factor loadings $\Lambda$ menghubungkan subspace laten ke observable space.

1 1. Vector Space: Definisi

Definisi: Vector Space

Himpunan $V$ dengan operasi penjumlahan ($+$) dan perkalian skalar ($\cdot$) disebut vector space atas $\mathbb{R}$ jika memenuhi 8 aksioma:

Aksioma penjumlahan (untuk $\mathbf{u}, \mathbf{v}, \mathbf{w} \in V$): 1. Closure: $\mathbf{u} + \mathbf{v} \in V$ 2. Commutativity: $\mathbf{u} + \mathbf{v} = \mathbf{v} + \mathbf{u}$ 3. Associativity: $(\mathbf{u} + \mathbf{v}) + \mathbf{w} = \mathbf{u} + (\mathbf{v} + \mathbf{w})$ 4. Zero vector: $\exists \mathbf{0} \in V$ s.t. $\mathbf{v} + \mathbf{0} = \mathbf{v}$ 5. Additive inverse: $\exists (-\mathbf{v}) \in V$ s.t. $\mathbf{v} + (-\mathbf{v}) = \mathbf{0}$

Aksioma perkalian skalar (untuk $c, d \in \mathbb{R}$, $\mathbf{u}, \mathbf{v} \in V$): 6. Closure: $c\mathbf{v} \in V$ 7. Distributivity (scalar): $c(\mathbf{u} + \mathbf{v}) = c\mathbf{u} + c\mathbf{v}$ 8. Distributivity (vector): $(c+d)\mathbf{v} = c\mathbf{v} + d\mathbf{v}$ 9. Associativity: $c(d\mathbf{v}) = (cd)\mathbf{v}$ 10. Identity: $1 \cdot \mathbf{v} = \mathbf{v}$

Contoh-contoh vector space yang relevan: - $\mathbb{R}^n$: vektor kolom dengan $n$ komponen — yang paling kita pakai - $\mathbb{R}^{m \times n}$: semua matriks $m \times n$ - Ruang fungsi kontinu $C([0,1])$: relevant untuk functional data analysis - Ruang polinomial berderajat ≤ $k$: relevant untuk polynomial regression

2 2. Subspaces

Definisi: Subspace

Subset $W \subseteq V$ adalah subspace jika: 1. $\mathbf{0} \in W$ (berisi zero vector) 2. Closed under addition: $\mathbf{u}, \mathbf{v} \in W \Rightarrow \mathbf{u} + \mathbf{v} \in W$ 3. Closed under scalar multiplication: $\mathbf{v} \in W, c \in \mathbb{R} \Rightarrow c\mathbf{v} \in W$

Ekuivalen: $W$ closed under semua kombinasi linear — jika $\mathbf{v}_1, \ldots, \mathbf{v}_k \in W$ maka $c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k \in W$ untuk semua $c_i \in \mathbb{R}$.

Contoh subspace di $\mathbb{R}^n$: - $\{\mathbf{0}\}$: trivial subspace - $\mathbb{R}^n$: full space - Line melalui titik asal: $\{t\mathbf{v} : t \in \mathbb{R}\}$ - Plane melalui titik asal: $\{s\mathbf{u} + t\mathbf{v} : s, t \in \mathbb{R}\}$

Perhatian: Line yang tidak melalui titik asal bukan subspace (karena tidak mengandung $\mathbf{0}$). Ini artinya hyperplanes dalam econometrics yang tidak pass through origin bukan subspace biasa — mereka affine subspaces.

3 3. Empat Subspace Fundamental dari Matriks

Ini adalah salah satu hasil paling elegan dalam linear algebra, dikembangkan oleh Gilbert Strang.

Untuk matriks $A \in \mathbb{R}^{m \times n}$, ada empat subspace fundamental:

Definisi: Four Fundamental Subspaces

1. Column space $C(A) \subseteq \mathbb{R}^m$: \[C(A) = \{\mathbf{b} : \mathbf{b} = A\mathbf{x} \text{ untuk suatu } \mathbf{x} \in \mathbb{R}^n\}\] = span dari kolom-kolom $A$. Ini adalah set semua $\mathbf{b}$ yang menyebabkan $A\mathbf{x} = \mathbf{b}$ punya solusi.

2. Null space $N(A) \subseteq \mathbb{R}^n$: \[N(A) = \{\mathbf{x} : A\mathbf{x} = \mathbf{0}\}\] = solusi dari sistem homogeneous. Mengukur “redundansi” dalam $A$.

3. Row space $C(A^T) \subseteq \mathbb{R}^n$: \[C(A^T) = C(A^T) = \text{span of rows of } A\] = span dari baris-baris $A$.

4. Left null space $N(A^T) \subseteq \mathbb{R}^m$: \[N(A^T) = \{\mathbf{y} : A^T\mathbf{y} = \mathbf{0}\}\]

Dimensi (rank-nullity theorem): - $\dim(C(A)) = \dim(C(A^T)) = \text{rank}(A)$ - $\dim(N(A)) = n - \text{rank}(A)$ - $\dim(N(A^T)) = m - \text{rank}(A)$

Fundamental orthogonality: \[C(A) \perp N(A^T) \quad (\text{dalam } \mathbb{R}^m)\] \[C(A^T) \perp N(A) \quad (\text{dalam } \mathbb{R}^n)\]

Interpretasi untuk OLS: $A = X \in \mathbb{R}^{n \times p}$: - $C(X)$: semua possible fitted values (subspace $p$-dimensi dalam $\mathbb{R}^n$) - $N(X^T) = C(X)^\perp$: residuals harus berada di sini ($\mathbf{e} \perp C(X)$) - $C(X^T)$: row space — “information space” dari features - $N(X)$: null space — directions in feature space that produce zero fitted values

4 4. Linear Independence

Definisi: Linear Independence

Vektor-vektor $\mathbf{v}_1, \ldots, \mathbf{v}_k$ linearly independent jika: \[c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_k\mathbf{v}_k = \mathbf{0} \Rightarrow c_1 = c_2 = \cdots = c_k = 0\]

Artinya: tidak ada vektor yang bisa ditulis sebagai kombinasi linear vektor-vektor lainnya.

Linearly dependent: ada $c_i \neq 0$ sedemikian sehingga $c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k = \mathbf{0}$.

Cara mudah check: buat matriks dengan vektor sebagai kolom → linearly independent $\iff$ rank = k.

Contoh mudah: - $\mathbf{v}_1 = \begin{bmatrix}1\\0\end{bmatrix}$, $\mathbf{v}_2 = \begin{bmatrix}0\\1\end{bmatrix}$: independent (basis standard $\mathbb{R}^2$) - $\mathbf{v}_1 = \begin{bmatrix}1\\2\end{bmatrix}$, $\mathbf{v}_2 = \begin{bmatrix}2\\4\end{bmatrix}$: dependent ($\mathbf{v}_2 = 2\mathbf{v}_1$)

Di econometrics: variabel dummy trap! Kalau kamu include dummy untuk semua kategori PLUS intercept, kolom-kolom $X$ linearly dependent. Contoh: $D_1 + D_2 + \cdots + D_k = \mathbf{1}$ (vektor constant) = intercept column. Perfect multicollinearity.

5 5. Basis dan Dimensi

Definisi: Basis dan Dimensi

Basis dari vector space $V$ adalah kumpulan vektor $\{\mathbf{b}_1, \ldots, \mathbf{b}_k\}$ yang: 1. Linearly independent 2. Spans $V$ (setiap vektor di $V$ bisa ditulis sebagai kombinasi linear)

Dimensi $\dim(V)$ adalah jumlah vektor dalam basis mana pun. Semua basis dari $V$ punya jumlah vektor yang sama.

Standard basis dari $\mathbb{R}^n$: $\mathbf{e}_1 = (1,0,\ldots,0)^T$, $\mathbf{e}_2 = (0,1,0,\ldots,0)^T$, …, $\mathbf{e}_n = (0,\ldots,0,1)^T$.

5.1 Rank-Nullity Theorem

Definisi: Rank-Nullity Theorem

Untuk $A \in \mathbb{R}^{m \times n}$: \[\underbrace{\dim(C(A))}_{\text{rank}(A)} + \underbrace{\dim(N(A))}_{\text{nullity}(A)} = n\]

Interpretasi: dari $n$ “input dimensions” (kolom-dimensi dari $\mathbb{R}^n$), sebagian “survive” (contribute ke output) dan sebagian “collapse ke nol” (null space). Jumlahnya harus $n$.

Untuk OLS: $X \in \mathbb{R}^{n \times p}$. - Kalau $\text{rank}(X) = p$ (full column rank): $\dim(N(X)) = 0$ → hanya solusi trivial $\boldsymbol{\beta} = \mathbf{0}$ dalam null space → unique OLS solution. - Kalau $\text{rank}(X) = r < p$ (rank deficient): $\dim(N(X)) = p - r > 0$ → ada $(p-r)$-dimensi worth of $\boldsymbol{\beta}$ values yang give zero prediction → infinite OLS solutions.

6 6. Worked Example: Menemukan Basis dan Dimensi

Worked Example: Column Space dan Null Space

Temukan basis dan dimensi dari column space dan null space untuk: \[A = \begin{bmatrix}1 & 2 & 1 & -1 \\ 2 & 4 & 2 & -2 \\ 1 & 3 & 4 & 1\end{bmatrix}\]

6.1 Row Reduce ke RREF

Augmented matrix (hanya $A$, tanpa $\mathbf{b}$): \[\begin{bmatrix}1 & 2 & 1 & -1 \\ 2 & 4 & 2 & -2 \\ 1 & 3 & 4 & 1\end{bmatrix}\]

$R_2 \leftarrow R_2 - 2R_1$: \[\begin{bmatrix}1 & 2 & 1 & -1 \\ 0 & 0 & 0 & 0 \\ 1 & 3 & 4 & 1\end{bmatrix}\]

$R_3 \leftarrow R_3 - R_1$: \[\begin{bmatrix}1 & 2 & 1 & -1 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 3 & 2\end{bmatrix}\]

$R_2 \leftrightarrow R_3$: \[\begin{bmatrix}1 & 2 & 1 & -1 \\ 0 & 1 & 3 & 2 \\ 0 & 0 & 0 & 0\end{bmatrix}\]

$R_1 \leftarrow R_1 - 2R_2$ (RREF): \[\begin{bmatrix}1 & 0 & -5 & -5 \\ 0 & 1 & 3 & 2 \\ 0 & 0 & 0 & 0\end{bmatrix}\]

Pivot columns: 1 dan 2. Free variables: $x_3$ dan $x_4$.

Rank = 2 (jumlah pivot).

6.2 Column Space

Basis untuk $C(A)$: kolom-kolom pivot dari matriks asli $A$ (bukan RREF): \[\text{basis}(C(A)) = \left\{\begin{bmatrix}1 \\ 2 \\ 1\end{bmatrix}, \begin{bmatrix}2 \\ 4 \\ 3\end{bmatrix}\right\}\]

$\dim(C(A)) = 2$. (Note: ini subspace dari $\mathbb{R}^3$.)

6.3 Null Space

Dari RREF, express pivot variables dalam free variables ($x_3 = s$, $x_4 = t$): - Baris 2: $x_2 + 3s + 2t = 0 \Rightarrow x_2 = -3s - 2t$ - Baris 1: $x_1 - 5s - 5t = 0 \Rightarrow x_1 = 5s + 5t$

Solusi umum: \[\mathbf{x} = \begin{bmatrix}5s + 5t \\ -3s - 2t \\ s \\ t\end{bmatrix} = s\begin{bmatrix}5 \\ -3 \\ 1 \\ 0\end{bmatrix} + t\begin{bmatrix}5 \\ -2 \\ 0 \\ 1\end{bmatrix}\]

Basis untuk $N(A)$: \[\left\{\begin{bmatrix}5 \\ -3 \\ 1 \\ 0\end{bmatrix}, \begin{bmatrix}5 \\ -2 \\ 0 \\ 1\end{bmatrix}\right\}\]

$\dim(N(A)) = 2$.

Verifikasi rank-nullity: $\dim(C(A)) + \dim(N(A)) = 2 + 2 = 4 = n$ ✓

library(pracma)

A <- matrix(c(1,2,1,-1,2,4,2,-2,1,3,4,1), nrow=3, byrow=TRUE)

# RREF
rref(A)

# Rank
qr(A)$rank  # 2

# Null space basis
nullspace(A)
# Should give two vectors spanning N(A)

# Column space: columns corresponding to pivot positions
pivot_cols <- c(1, 2)  # from RREF analysis
col_space_basis <- A[, pivot_cols]
print(col_space_basis)

7 7. Koneksi ke OLS: Column Space dan Identifiability

Connection: OLS dan Four Fundamental Subspaces

Dalam OLS, $\mathbf{y} \in \mathbb{R}^n$ dan $X \in \mathbb{R}^{n \times p}$:

Fitted values $\hat{\mathbf{y}} = X\hat{\boldsymbol{\beta}} \in C(X)$

Ini adalah proyeksi ortogonal $\mathbf{y}$ ke $C(X)$. Karena proyeksi selalu unik, $\hat{\mathbf{y}}$ unik bahkan ketika $\hat{\boldsymbol{\beta}}$ tidak.

Residuals $\mathbf{e} = \mathbf{y} - \hat{\mathbf{y}} \in N(X^T)$

Karena $C(X) \perp N(X^T)$: $\hat{\mathbf{y}} \perp \mathbf{e}$, dan $X^T\mathbf{e} = \mathbf{0}$ (OLS normal equations).

Degrees of freedom: - Model df = $\dim(C(X)) = \text{rank}(X)$ - Residual df = $\dim(N(X^T)) = n - \text{rank}(X)$

Identifiability: $\hat{\boldsymbol{\beta}}$ unik $\iff$ $N(X) = \{\mathbf{0}\}$ $\iff$ $X$ full column rank.

Kalau $\text{rank}(X) = r < p$: ada $(p-r)$-dimensi ruang solusi. Kita perlu constraint tambahan untuk unique solution → regularization (ridge, lasso) atau re-parameterization.

# Ilustrasi: column space dan residuals
n <- 100; p <- 3
X <- cbind(1, matrix(rnorm(n*(p-1)), n, p-1))
beta_true <- c(2, 1, -1)
y <- X %*% beta_true + rnorm(n, sd=0.5)

# OLS
beta_hat <- solve(t(X) %*% X) %*% t(X) %*% y
y_hat <- X %*% beta_hat
e <- y - y_hat

# Residuals orthogonal to columns of X
cat("X^T e (should be ~0):\n")
print(round(t(X) %*% e, 8))

# y_hat in C(X): can write y_hat = X * beta_hat (by construction)
# e in N(X^T): X^T e = 0

# Decomposition of y:
cat("||y||^2:", sum(y^2), "\n")
cat("||y_hat||^2 + ||e||^2:", sum(y_hat^2) + sum(e^2), "\n")
# Pythagorean theorem: ||y||^2 = ||y_hat||^2 + ||e||^2 (approximately)
# (not exact because y_hat and e are orthogonal, Pythagoras applies)

8 8. Span dan Generating Sets

Span dari kumpulan vektor $\{\mathbf{v}_1, \ldots, \mathbf{v}_k\}$: \[\text{span}\{\mathbf{v}_1, \ldots, \mathbf{v}_k\} = \{c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k : c_i \in \mathbb{R}\}\]

Ini adalah subspace terkecil yang mengandung semua $\mathbf{v}_i$.

Column space $C(A) = \text{span}$ dari kolom-kolom $A$. Ini artinya: set semua vektor yang bisa “dicapai” melalui $A$.

Coordinate representation: kalau $\{\mathbf{b}_1, \ldots, \mathbf{b}_k\}$ adalah basis dari $V$, setiap $\mathbf{v} \in V$ punya representasi unik: \[\mathbf{v} = c_1\mathbf{b}_1 + \cdots + c_k\mathbf{b}_k\]

Vektor koordinat $[c_1, \ldots, c_k]$ bergantung pada pilihan basis — inilah kenapa ada “change of basis” dalam PCA.

9 9. Gram-Schmidt Orthogonalization

Proses untuk mengkonversi basis biasa menjadi orthonormal basis. Ini adalah fondasi dari QR decomposition.

Diberikan linearly independent vectors $\{\mathbf{a}_1, \mathbf{a}_2, \mathbf{a}_3, \ldots\}$:

Step 1: $\mathbf{q}_1 = \mathbf{a}_1 / \|\mathbf{a}_1\|$

Step 2: $\tilde{\mathbf{q}}_2 = \mathbf{a}_2 - (\mathbf{a}_2^T\mathbf{q}_1)\mathbf{q}_1$ (subtract projection onto $\mathbf{q}_1$), lalu normalize: $\mathbf{q}_2 = \tilde{\mathbf{q}}_2/\|\tilde{\mathbf{q}}_2\|$

Step 3: $\tilde{\mathbf{q}}_3 = \mathbf{a}_3 - (\mathbf{a}_3^T\mathbf{q}_1)\mathbf{q}_1 - (\mathbf{a}_3^T\mathbf{q}_2)\mathbf{q}_2$ (subtract projections onto $\mathbf{q}_1$ dan $\mathbf{q}_2$), normalize.

Dan seterusnya. Hasilnya: $\{\mathbf{q}_1, \mathbf{q}_2, \mathbf{q}_3, \ldots\}$ adalah orthonormal set yang men-span subspace yang sama.

# Gram-Schmidt di R
gram_schmidt <- function(A) {
  n <- ncol(A)
  Q <- matrix(0, nrow(A), n)
  for (j in 1:n) {
    v <- A[, j]
    if (j > 1) {
      for (k in 1:(j-1)) {
        v <- v - sum(v * Q[, k]) * Q[, k]  # subtract projection
      }
    }
    Q[, j] <- v / sqrt(sum(v^2))  # normalize
  }
  Q
}

A <- matrix(c(1,1,0,1,0,1,0,1,1), nrow=3)
Q <- gram_schmidt(A)

# Verify orthonormality
cat("Q^T Q (should be I):\n")
print(round(t(Q) %*% Q, 10))

10 10. Practice Problems

Practice Problems

Problem 1: Apakah subset berikut merupakan subspace dari $\mathbb{R}^3$?

$W_1 = \{(x_1, x_2, x_3) : x_1 + x_2 = 0\}$
$W_2 = \{(x_1, x_2, x_3) : x_1 + x_2 = 1\}$
$W_3 = \{(x_1, x_2, x_3) : x_1 x_2 = 0\}$

Solusi:

Ya. Check:

$\mathbf{0} \in W_1$: $0 + 0 = 0$ ✓
Closure addition: kalau $x_1+x_2=0$ dan $y_1+y_2=0$ maka $(x_1+y_1)+(x_2+y_2)=0$ ✓
Closure scalar: kalau $x_1+x_2=0$ maka $cx_1+cx_2=c(x_1+x_2)=0$ ✓

Tidak. $\mathbf{0} \notin W_2$ karena $0+0=0 \neq 1$.
Tidak. $\mathbf{u} = (1,0,0) \in W_3$ dan $\mathbf{v} = (0,1,0) \in W_3$, tapi $\mathbf{u} + \mathbf{v} = (1,1,0)$ dan $(1)(1) = 1 \neq 0$, jadi $\mathbf{u}+\mathbf{v} \notin W_3$. Tidak closed under addition.

Problem 2: Temukan basis dan dimensi dari:

\[A = \begin{bmatrix}2 & 4 & 0 \\ 1 & 2 & 1 \\ 3 & 6 & 1\end{bmatrix}\]

Temukan basis untuk $C(A)$ dan $N(A)$. Verifikasi rank-nullity theorem.

Solusi:

Row reduce: \[\begin{bmatrix}2&4&0\\1&2&1\\3&6&1\end{bmatrix} \xrightarrow{\text{RREF}} \begin{bmatrix}1&2&0\\0&0&1\\0&0&0\end{bmatrix}\]

Rank = 2. Pivot columns: 1 dan 3.

Basis $C(A)$: kolom 1 dan 3 dari $A$ original: \[\left\{\begin{bmatrix}2\\1\\3\end{bmatrix}, \begin{bmatrix}0\\1\\1\end{bmatrix}\right\}\]

Free variable: $x_2 = t$. Dari RREF: $x_1 = -2t$, $x_3 = 0$.

Basis $N(A)$: $\left\{\begin{bmatrix}-2\\1\\0\end{bmatrix}\right\}$

Rank-nullity: $2 + 1 = 3 = n$ ✓

Problem 3 (Dummy Variable Trap):

Bayangkan kamu punya variabel kategori dengan 3 level (A, B, C) dan intercept. Tunjukkan bahwa meng-include semua 3 dummy variabel menyebabkan multicollinearity.

Solusi: Definisikan $D_A, D_B, D_C$ sebagai dummy variables dengan $D_k = 1$ jika observasi adalah kategori $k$, 0 otherwise.

Karena setiap observasi tepat masuk satu kategori: $D_A + D_B + D_C = \mathbf{1}$ (vektor dengan semua entri 1).

Kalau $X = [\mathbf{1}, D_A, D_B, D_C]$, maka kolom pertama ($\mathbf{1}$) adalah jumlah kolom 2-4 → linear dependence → $\text{rank}(X) < 4$ → perfect multicollinearity → $X^TX$ singular.

Solusi: drop satu dummy (reference category). $X = [\mathbf{1}, D_A, D_B]$ — $D_C$ adalah baseline, efeknya ter-capture oleh intercept.

Problem 4 (R):

# Eksplorasi column space dan null space secara visual
library(pracma)

# Model dengan dummy variable trap
n <- 50
group <- rep(c("A","B","C"), length.out=n)
DA <- as.numeric(group == "A")
DB <- as.numeric(group == "B")
DC <- as.numeric(group == "C")
const <- rep(1, n)

X_trap <- cbind(const, DA, DB, DC)
cat("Rank with all dummies:", qr(X_trap)$rank, "\n")  # 3, not 4!
cat("det(X^TX):", det(t(X_trap) %*% X_trap), "\n")  # ~0

# Fix: drop DC (reference category)
X_fix <- cbind(const, DA, DB)
cat("Rank after fix:", qr(X_fix)$rank, "\n")  # 3 ✓

# Null space dimension confirms
cat("Null space dimension (trap):", 4 - qr(X_trap)$rank, "\n")  # 1
cat("Null space (trap):\n")
print(round(nullspace(X_trap), 4))
# Null vector should be proportional to (1, -1, -1, -1) or similar

--- title: "Vector Spaces, Basis & Dimension" subtitle: "Struktur Abstrak di Balik Data" format: html: toc: true toc-depth: 3 code-fold: false --- ::: {.callout-note title="Why This Matters for Your Work"} Vector spaces adalah bahasa yang tepat untuk membicarakan hal-hal seperti: - **Column space of $X$**: apakah $\mathbf{y}$ bisa diprediksi sempurna oleh $X$? Jawabannya: ya, jika dan hanya jika $\mathbf{y} \in C(X)$. - **OLS sebagai proyeksi**: fitted values $\hat{\mathbf{y}}$ adalah proyeksi ortogonal $\mathbf{y}$ ke $C(X)$. Residuals $\mathbf{e}$ berada di orthogonal complement dari $C(X)$. - **Identifiability**: model teridentifikasi $\iff$ $X$ full column rank $\iff$ $\dim(C(X)) = p$. - **Degrees of freedom**: $df_{residual} = n - p = \dim(\text{orthogonal complement of } C(X))$. - **Factor models**: latent factors $\mathbf{f}$ span suatu subspace; factor loadings $\Lambda$ menghubungkan subspace laten ke observable space. ::: --- ## 1. Vector Space: Definisi ::: {.callout-important title="Definisi: Vector Space"} Himpunan $V$ dengan operasi **penjumlahan** ($+$) dan **perkalian skalar** ($\cdot$) disebut **vector space** atas $\mathbb{R}$ jika memenuhi 8 aksioma: **Aksioma penjumlahan** (untuk $\mathbf{u}, \mathbf{v}, \mathbf{w} \in V$): 1. **Closure**: $\mathbf{u} + \mathbf{v} \in V$ 2. **Commutativity**: $\mathbf{u} + \mathbf{v} = \mathbf{v} + \mathbf{u}$ 3. **Associativity**: $(\mathbf{u} + \mathbf{v}) + \mathbf{w} = \mathbf{u} + (\mathbf{v} + \mathbf{w})$ 4. **Zero vector**: $\exists \mathbf{0} \in V$ s.t. $\mathbf{v} + \mathbf{0} = \mathbf{v}$ 5. **Additive inverse**: $\exists (-\mathbf{v}) \in V$ s.t. $\mathbf{v} + (-\mathbf{v}) = \mathbf{0}$ **Aksioma perkalian skalar** (untuk $c, d \in \mathbb{R}$, $\mathbf{u}, \mathbf{v} \in V$): 6. **Closure**: $c\mathbf{v} \in V$ 7. **Distributivity (scalar)**: $c(\mathbf{u} + \mathbf{v}) = c\mathbf{u} + c\mathbf{v}$ 8. **Distributivity (vector)**: $(c+d)\mathbf{v} = c\mathbf{v} + d\mathbf{v}$ 9. **Associativity**: $c(d\mathbf{v}) = (cd)\mathbf{v}$ 10. **Identity**: $1 \cdot \mathbf{v} = \mathbf{v}$ ::: Contoh-contoh vector space yang relevan: - $\mathbb{R}^n$: vektor kolom dengan $n$ komponen — yang paling kita pakai - $\mathbb{R}^{m \times n}$: semua matriks $m \times n$ - Ruang fungsi kontinu $C([0,1])$: relevant untuk functional data analysis - Ruang polinomial berderajat ≤ $k$: relevant untuk polynomial regression --- ## 2. Subspaces ::: {.callout-important title="Definisi: Subspace"} Subset $W \subseteq V$ adalah **subspace** jika: 1. $\mathbf{0} \in W$ (berisi zero vector) 2. Closed under addition: $\mathbf{u}, \mathbf{v} \in W \Rightarrow \mathbf{u} + \mathbf{v} \in W$ 3. Closed under scalar multiplication: $\mathbf{v} \in W, c \in \mathbb{R} \Rightarrow c\mathbf{v} \in W$ Ekuivalen: $W$ closed under **semua kombinasi linear** — jika $\mathbf{v}_1, \ldots, \mathbf{v}_k \in W$ maka $c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k \in W$ untuk semua $c_i \in \mathbb{R}$. ::: Contoh subspace di $\mathbb{R}^n$: - $\{\mathbf{0}\}$: trivial subspace - $\mathbb{R}^n$: full space - Line melalui titik asal: $\{t\mathbf{v} : t \in \mathbb{R}\}$ - Plane melalui titik asal: $\{s\mathbf{u} + t\mathbf{v} : s, t \in \mathbb{R}\}$ **Perhatian**: Line yang tidak melalui titik asal bukan subspace (karena tidak mengandung $\mathbf{0}$). Ini artinya hyperplanes dalam econometrics yang tidak pass through origin bukan subspace biasa — mereka **affine subspaces**. --- ## 3. Empat Subspace Fundamental dari Matriks Ini adalah salah satu hasil paling elegan dalam linear algebra, dikembangkan oleh Gilbert Strang. Untuk matriks $A \in \mathbb{R}^{m \times n}$, ada empat subspace fundamental: ::: {.callout-important title="Definisi: Four Fundamental Subspaces"} **1. Column space** $C(A) \subseteq \mathbb{R}^m$: $$C(A) = \{\mathbf{b} : \mathbf{b} = A\mathbf{x} \text{ untuk suatu } \mathbf{x} \in \mathbb{R}^n\}$$ = span dari kolom-kolom $A$. Ini adalah set semua $\mathbf{b}$ yang menyebabkan $A\mathbf{x} = \mathbf{b}$ punya solusi. **2. Null space** $N(A) \subseteq \mathbb{R}^n$: $$N(A) = \{\mathbf{x} : A\mathbf{x} = \mathbf{0}\}$$ = solusi dari sistem homogeneous. Mengukur "redundansi" dalam $A$. **3. Row space** $C(A^T) \subseteq \mathbb{R}^n$: $$C(A^T) = C(A^T) = \text{span of rows of } A$$ = span dari baris-baris $A$. **4. Left null space** $N(A^T) \subseteq \mathbb{R}^m$: $$N(A^T) = \{\mathbf{y} : A^T\mathbf{y} = \mathbf{0}\}$$ **Dimensi** (rank-nullity theorem): - $\dim(C(A)) = \dim(C(A^T)) = \text{rank}(A)$ - $\dim(N(A)) = n - \text{rank}(A)$ - $\dim(N(A^T)) = m - \text{rank}(A)$ **Fundamental orthogonality**: $$C(A) \perp N(A^T) \quad (\text{dalam } \mathbb{R}^m)$$ $$C(A^T) \perp N(A) \quad (\text{dalam } \mathbb{R}^n)$$ ::: Interpretasi untuk OLS: $A = X \in \mathbb{R}^{n \times p}$: - $C(X)$: semua possible fitted values (subspace $p$-dimensi dalam $\mathbb{R}^n$) - $N(X^T) = C(X)^\perp$: residuals harus berada di sini ($\mathbf{e} \perp C(X)$) - $C(X^T)$: row space — "information space" dari features - $N(X)$: null space — directions in feature space that produce zero fitted values --- ## 4. Linear Independence ::: {.callout-important title="Definisi: Linear Independence"} Vektor-vektor $\mathbf{v}_1, \ldots, \mathbf{v}_k$ **linearly independent** jika: $$c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_k\mathbf{v}_k = \mathbf{0} \Rightarrow c_1 = c_2 = \cdots = c_k = 0$$ Artinya: tidak ada vektor yang bisa ditulis sebagai kombinasi linear vektor-vektor lainnya. **Linearly dependent**: ada $c_i \neq 0$ sedemikian sehingga $c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k = \mathbf{0}$. Cara mudah check: buat matriks dengan vektor sebagai kolom → linearly independent $\iff$ rank = k. ::: **Contoh mudah**: - $\mathbf{v}_1 = \begin{bmatrix}1\\0\end{bmatrix}$, $\mathbf{v}_2 = \begin{bmatrix}0\\1\end{bmatrix}$: independent (basis standard $\mathbb{R}^2$) - $\mathbf{v}_1 = \begin{bmatrix}1\\2\end{bmatrix}$, $\mathbf{v}_2 = \begin{bmatrix}2\\4\end{bmatrix}$: dependent ($\mathbf{v}_2 = 2\mathbf{v}_1$) **Di econometrics**: variabel dummy trap! Kalau kamu include dummy untuk semua kategori PLUS intercept, kolom-kolom $X$ linearly dependent. Contoh: $D_1 + D_2 + \cdots + D_k = \mathbf{1}$ (vektor constant) = intercept column. Perfect multicollinearity. --- ## 5. Basis dan Dimensi ::: {.callout-important title="Definisi: Basis dan Dimensi"} **Basis** dari vector space $V$ adalah kumpulan vektor $\{\mathbf{b}_1, \ldots, \mathbf{b}_k\}$ yang: 1. **Linearly independent** 2. **Spans** $V$ (setiap vektor di $V$ bisa ditulis sebagai kombinasi linear) **Dimensi** $\dim(V)$ adalah jumlah vektor dalam basis mana pun. Semua basis dari $V$ punya jumlah vektor yang sama. **Standard basis** dari $\mathbb{R}^n$: $\mathbf{e}_1 = (1,0,\ldots,0)^T$, $\mathbf{e}_2 = (0,1,0,\ldots,0)^T$, ..., $\mathbf{e}_n = (0,\ldots,0,1)^T$. ::: ### Rank-Nullity Theorem ::: {.callout-important title="Definisi: Rank-Nullity Theorem"} Untuk $A \in \mathbb{R}^{m \times n}$: $$\underbrace{\dim(C(A))}_{\text{rank}(A)} + \underbrace{\dim(N(A))}_{\text{nullity}(A)} = n$$ **Interpretasi**: dari $n$ "input dimensions" (kolom-dimensi dari $\mathbb{R}^n$), sebagian "survive" (contribute ke output) dan sebagian "collapse ke nol" (null space). Jumlahnya harus $n$. **Untuk OLS**: $X \in \mathbb{R}^{n \times p}$. - Kalau $\text{rank}(X) = p$ (full column rank): $\dim(N(X)) = 0$ → hanya solusi trivial $\boldsymbol{\beta} = \mathbf{0}$ dalam null space → unique OLS solution. - Kalau $\text{rank}(X) = r < p$ (rank deficient): $\dim(N(X)) = p - r > 0$ → ada $(p-r)$-dimensi worth of $\boldsymbol{\beta}$ values yang give zero prediction → infinite OLS solutions. ::: --- ## 6. Worked Example: Menemukan Basis dan Dimensi ::: {.callout-tip title="Worked Example: Column Space dan Null Space" collapse="true"} Temukan basis dan dimensi dari column space dan null space untuk: $$A = \begin{bmatrix}1 & 2 & 1 & -1 \\ 2 & 4 & 2 & -2 \\ 1 & 3 & 4 & 1\end{bmatrix}$$ ### Row Reduce ke RREF Augmented matrix (hanya $A$, tanpa $\mathbf{b}$): $$\begin{bmatrix}1 & 2 & 1 & -1 \\ 2 & 4 & 2 & -2 \\ 1 & 3 & 4 & 1\end{bmatrix}$$ $R_2 \leftarrow R_2 - 2R_1$: $$\begin{bmatrix}1 & 2 & 1 & -1 \\ 0 & 0 & 0 & 0 \\ 1 & 3 & 4 & 1\end{bmatrix}$$ $R_3 \leftarrow R_3 - R_1$: $$\begin{bmatrix}1 & 2 & 1 & -1 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 3 & 2\end{bmatrix}$$ $R_2 \leftrightarrow R_3$: $$\begin{bmatrix}1 & 2 & 1 & -1 \\ 0 & 1 & 3 & 2 \\ 0 & 0 & 0 & 0\end{bmatrix}$$ $R_1 \leftarrow R_1 - 2R_2$ (RREF): $$\begin{bmatrix}1 & 0 & -5 & -5 \\ 0 & 1 & 3 & 2 \\ 0 & 0 & 0 & 0\end{bmatrix}$$ **Pivot columns**: 1 dan 2. **Free variables**: $x_3$ dan $x_4$. **Rank** = 2 (jumlah pivot). ### Column Space Basis untuk $C(A)$: kolom-kolom pivot dari matriks **asli** $A$ (bukan RREF): $$\text{basis}(C(A)) = \left\{\begin{bmatrix}1 \\ 2 \\ 1\end{bmatrix}, \begin{bmatrix}2 \\ 4 \\ 3\end{bmatrix}\right\}$$ $\dim(C(A)) = 2$. (Note: ini subspace dari $\mathbb{R}^3$.) ### Null Space Dari RREF, express pivot variables dalam free variables ($x_3 = s$, $x_4 = t$): - Baris 2: $x_2 + 3s + 2t = 0 \Rightarrow x_2 = -3s - 2t$ - Baris 1: $x_1 - 5s - 5t = 0 \Rightarrow x_1 = 5s + 5t$ Solusi umum: $$\mathbf{x} = \begin{bmatrix}5s + 5t \\ -3s - 2t \\ s \\ t\end{bmatrix} = s\begin{bmatrix}5 \\ -3 \\ 1 \\ 0\end{bmatrix} + t\begin{bmatrix}5 \\ -2 \\ 0 \\ 1\end{bmatrix}$$ **Basis** untuk $N(A)$: $$\left\{\begin{bmatrix}5 \\ -3 \\ 1 \\ 0\end{bmatrix}, \begin{bmatrix}5 \\ -2 \\ 0 \\ 1\end{bmatrix}\right\}$$ $\dim(N(A)) = 2$. **Verifikasi rank-nullity**: $\dim(C(A)) + \dim(N(A)) = 2 + 2 = 4 = n$ ✓ ```r library(pracma) A <- matrix(c(1,2,1,-1,2,4,2,-2,1,3,4,1), nrow=3, byrow=TRUE) # RREF rref(A) # Rank qr(A)$rank # 2 # Null space basis nullspace(A) # Should give two vectors spanning N(A) # Column space: columns corresponding to pivot positions pivot_cols <- c(1, 2) # from RREF analysis col_space_basis <- A[, pivot_cols] print(col_space_basis) ``` ::: --- ## 7. Koneksi ke OLS: Column Space dan Identifiability ::: {.callout-caution title="Connection: OLS dan Four Fundamental Subspaces"} Dalam OLS, $\mathbf{y} \in \mathbb{R}^n$ dan $X \in \mathbb{R}^{n \times p}$: **Fitted values** $\hat{\mathbf{y}} = X\hat{\boldsymbol{\beta}} \in C(X)$ Ini adalah proyeksi ortogonal $\mathbf{y}$ ke $C(X)$. Karena proyeksi selalu unik, $\hat{\mathbf{y}}$ unik bahkan ketika $\hat{\boldsymbol{\beta}}$ tidak. **Residuals** $\mathbf{e} = \mathbf{y} - \hat{\mathbf{y}} \in N(X^T)$ Karena $C(X) \perp N(X^T)$: $\hat{\mathbf{y}} \perp \mathbf{e}$, dan $X^T\mathbf{e} = \mathbf{0}$ (OLS normal equations). **Degrees of freedom**: - Model df = $\dim(C(X)) = \text{rank}(X)$ - Residual df = $\dim(N(X^T)) = n - \text{rank}(X)$ **Identifiability**: $\hat{\boldsymbol{\beta}}$ unik $\iff$ $N(X) = \{\mathbf{0}\}$ $\iff$ $X$ full column rank. Kalau $\text{rank}(X) = r < p$: ada $(p-r)$-dimensi ruang solusi. Kita perlu constraint tambahan untuk unique solution → regularization (ridge, lasso) atau re-parameterization. ```r # Ilustrasi: column space dan residuals n <- 100; p <- 3 X <- cbind(1, matrix(rnorm(n*(p-1)), n, p-1)) beta_true <- c(2, 1, -1) y <- X %*% beta_true + rnorm(n, sd=0.5) # OLS beta_hat <- solve(t(X) %*% X) %*% t(X) %*% y y_hat <- X %*% beta_hat e <- y - y_hat # Residuals orthogonal to columns of X cat("X^T e (should be ~0):\n") print(round(t(X) %*% e, 8)) # y_hat in C(X): can write y_hat = X * beta_hat (by construction) # e in N(X^T): X^T e = 0 # Decomposition of y: cat("||y||^2:", sum(y^2), "\n") cat("||y_hat||^2 + ||e||^2:", sum(y_hat^2) + sum(e^2), "\n") # Pythagorean theorem: ||y||^2 = ||y_hat||^2 + ||e||^2 (approximately) # (not exact because y_hat and e are orthogonal, Pythagoras applies) ``` ::: --- ## 8. Span dan Generating Sets **Span** dari kumpulan vektor $\{\mathbf{v}_1, \ldots, \mathbf{v}_k\}$: $$\text{span}\{\mathbf{v}_1, \ldots, \mathbf{v}_k\} = \{c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k : c_i \in \mathbb{R}\}$$ Ini adalah subspace terkecil yang mengandung semua $\mathbf{v}_i$. Column space $C(A) = \text{span}$ dari kolom-kolom $A$. Ini artinya: set semua vektor yang bisa "dicapai" melalui $A$. **Coordinate representation**: kalau $\{\mathbf{b}_1, \ldots, \mathbf{b}_k\}$ adalah basis dari $V$, setiap $\mathbf{v} \in V$ punya representasi **unik**: $$\mathbf{v} = c_1\mathbf{b}_1 + \cdots + c_k\mathbf{b}_k$$ Vektor koordinat $[c_1, \ldots, c_k]$ bergantung pada pilihan basis — inilah kenapa ada "change of basis" dalam PCA. --- ## 9. Gram-Schmidt Orthogonalization Proses untuk mengkonversi basis biasa menjadi **orthonormal basis**. Ini adalah fondasi dari QR decomposition. Diberikan linearly independent vectors $\{\mathbf{a}_1, \mathbf{a}_2, \mathbf{a}_3, \ldots\}$: **Step 1**: $\mathbf{q}_1 = \mathbf{a}_1 / \|\mathbf{a}_1\|$ **Step 2**: $\tilde{\mathbf{q}}_2 = \mathbf{a}_2 - (\mathbf{a}_2^T\mathbf{q}_1)\mathbf{q}_1$ (subtract projection onto $\mathbf{q}_1$), lalu normalize: $\mathbf{q}_2 = \tilde{\mathbf{q}}_2/\|\tilde{\mathbf{q}}_2\|$ **Step 3**: $\tilde{\mathbf{q}}_3 = \mathbf{a}_3 - (\mathbf{a}_3^T\mathbf{q}_1)\mathbf{q}_1 - (\mathbf{a}_3^T\mathbf{q}_2)\mathbf{q}_2$ (subtract projections onto $\mathbf{q}_1$ dan $\mathbf{q}_2$), normalize. Dan seterusnya. Hasilnya: $\{\mathbf{q}_1, \mathbf{q}_2, \mathbf{q}_3, \ldots\}$ adalah orthonormal set yang men-span subspace yang sama. ```r # Gram-Schmidt di R gram_schmidt <- function(A) { n <- ncol(A) Q <- matrix(0, nrow(A), n) for (j in 1:n) { v <- A[, j] if (j > 1) { for (k in 1:(j-1)) { v <- v - sum(v * Q[, k]) * Q[, k] # subtract projection } } Q[, j] <- v / sqrt(sum(v^2)) # normalize } Q } A <- matrix(c(1,1,0,1,0,1,0,1,1), nrow=3) Q <- gram_schmidt(A) # Verify orthonormality cat("Q^T Q (should be I):\n") print(round(t(Q) %*% Q, 10)) ``` --- ## 10. Practice Problems ::: {.callout-warning title="Practice Problems" collapse="true"} **Problem 1**: Apakah subset berikut merupakan subspace dari $\mathbb{R}^3$? (a) $W_1 = \{(x_1, x_2, x_3) : x_1 + x_2 = 0\}$ (b) $W_2 = \{(x_1, x_2, x_3) : x_1 + x_2 = 1\}$ (c) $W_3 = \{(x_1, x_2, x_3) : x_1 x_2 = 0\}$ **Solusi**: (a) **Ya**. Check: - $\mathbf{0} \in W_1$: $0 + 0 = 0$ ✓ - Closure addition: kalau $x_1+x_2=0$ dan $y_1+y_2=0$ maka $(x_1+y_1)+(x_2+y_2)=0$ ✓ - Closure scalar: kalau $x_1+x_2=0$ maka $cx_1+cx_2=c(x_1+x_2)=0$ ✓ (b) **Tidak**. $\mathbf{0} \notin W_2$ karena $0+0=0 \neq 1$. (c) **Tidak**. $\mathbf{u} = (1,0,0) \in W_3$ dan $\mathbf{v} = (0,1,0) \in W_3$, tapi $\mathbf{u} + \mathbf{v} = (1,1,0)$ dan $(1)(1) = 1 \neq 0$, jadi $\mathbf{u}+\mathbf{v} \notin W_3$. Tidak closed under addition. --- **Problem 2**: Temukan basis dan dimensi dari: $$A = \begin{bmatrix}2 & 4 & 0 \\ 1 & 2 & 1 \\ 3 & 6 & 1\end{bmatrix}$$ Temukan basis untuk $C(A)$ dan $N(A)$. Verifikasi rank-nullity theorem. **Solusi**: Row reduce: $$\begin{bmatrix}2&4&0\\1&2&1\\3&6&1\end{bmatrix} \xrightarrow{\text{RREF}} \begin{bmatrix}1&2&0\\0&0&1\\0&0&0\end{bmatrix}$$ Rank = 2. Pivot columns: 1 dan 3. Basis $C(A)$: kolom 1 dan 3 dari $A$ original: $$\left\{\begin{bmatrix}2\\1\\3\end{bmatrix}, \begin{bmatrix}0\\1\\1\end{bmatrix}\right\}$$ Free variable: $x_2 = t$. Dari RREF: $x_1 = -2t$, $x_3 = 0$. Basis $N(A)$: $\left\{\begin{bmatrix}-2\\1\\0\end{bmatrix}\right\}$ Rank-nullity: $2 + 1 = 3 = n$ ✓ --- **Problem 3** (Dummy Variable Trap): Bayangkan kamu punya variabel kategori dengan 3 level (A, B, C) dan intercept. Tunjukkan bahwa meng-include semua 3 dummy variabel menyebabkan multicollinearity. **Solusi**: Definisikan $D_A, D_B, D_C$ sebagai dummy variables dengan $D_k = 1$ jika observasi adalah kategori $k$, 0 otherwise. Karena setiap observasi tepat masuk satu kategori: $D_A + D_B + D_C = \mathbf{1}$ (vektor dengan semua entri 1). Kalau $X = [\mathbf{1}, D_A, D_B, D_C]$, maka kolom pertama ($\mathbf{1}$) adalah jumlah kolom 2-4 → linear dependence → $\text{rank}(X) < 4$ → perfect multicollinearity → $X^TX$ singular. **Solusi**: drop satu dummy (reference category). $X = [\mathbf{1}, D_A, D_B]$ — $D_C$ adalah baseline, efeknya ter-capture oleh intercept. --- **Problem 4** (R): ```r # Eksplorasi column space dan null space secara visual library(pracma) # Model dengan dummy variable trap n <- 50 group <- rep(c("A","B","C"), length.out=n) DA <- as.numeric(group == "A") DB <- as.numeric(group == "B") DC <- as.numeric(group == "C") const <- rep(1, n) X_trap <- cbind(const, DA, DB, DC) cat("Rank with all dummies:", qr(X_trap)$rank, "\n") # 3, not 4! cat("det(X^TX):", det(t(X_trap) %*% X_trap), "\n") # ~0 # Fix: drop DC (reference category) X_fix <- cbind(const, DA, DB) cat("Rank after fix:", qr(X_fix)$rank, "\n") # 3 ✓ # Null space dimension confirms cat("Null space dimension (trap):", 4 - qr(X_trap)$rank, "\n") # 1 cat("Null space (trap):\n") print(round(nullspace(X_trap), 4)) # Null vector should be proportional to (1, -1, -1, -1) or similar ``` :::