Systems of Linear Equations

Gaussian Elimination, Row Echelon Form, dan Existence of Solutions

Why This Matters for Your Work

Di balik setiap OLS regression tersembunyi sebuah system of linear equations: $X^TX\boldsymbol{\beta} = X^T\mathbf{y}$. Ketika kamu punya perfect multicollinearity, system ini punya infinite solutions — $\hat{\boldsymbol{\beta}}$ tidak unik, identifikasi gagal.

Pemahaman tentang kapan sistem linear punya solusi unik, tak ada solusi, atau tak terhingga solusi adalah fondasi untuk memahami: - Multicollinearity dan identifiability dalam econometrics - Overdetermined systems (lebih banyak persamaan dari unknown — inilah regression!) - Underdetermined systems (lebih banyak unknown — inilah regularization needed) - Ridge regression sebagai cara “membuat” system selalu punya solusi unik

1 1. Formulasi Sistem Linear

1.1 Dari Persamaan ke Matriks

Sistem $m$ persamaan linear dengan $n$ unknowns: \[\begin{aligned} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n &= b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n &= b_2 \\ &\vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n &= b_m \end{aligned}\]

bisa ditulis sebagai: \[A\mathbf{x} = \mathbf{b}\]

di mana $A \in \mathbb{R}^{m \times n}$, $\mathbf{x} \in \mathbb{R}^n$, $\mathbf{b} \in \mathbb{R}^m$.

1.2 Augmented Matrix

Untuk memecahkan sistem, kita gunakan augmented matrix $[A|\mathbf{b}]$:

\[[A|\mathbf{b}] = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} & \vline & b_1 \\ a_{21} & a_{22} & \cdots & a_{2n} & \vline & b_2 \\ \vdots & \vdots & \ddots & \vdots & \vline & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} & \vline & b_m \end{bmatrix}\]

Ini menyimpan semua informasi yang dibutuhkan untuk menyelesaikan sistem.

1.3 Tiga Kemungkinan Solusi

Untuk sistem $A\mathbf{x} = \mathbf{b}$, hanya ada tiga kemungkinan:

Unique solution (solusi tunggal): tepat satu $\mathbf{x}$ yang memenuhi semua persamaan
No solution (inconsistent): tidak ada $\mathbf{x}$ yang memenuhi semua persamaan
Infinite solutions: ada tak terhingga $\mathbf{x}$ yang memenuhi semua persamaan

Tidak ada kemungkinan keempat. Ini adalah teorema fundamental aljabar linear.

2 2. Gaussian Elimination

2.1 Elementary Row Operations

Kita dapat memanipulasi sistem tanpa mengubah solusi menggunakan tiga elementary row operations:

Row swap: tukar baris $i$ dan baris $j$: $R_i \leftrightarrow R_j$
Row scaling: kalikan baris $i$ dengan skalar $c \neq 0$: $R_i \leftarrow cR_i$
Row addition: tambahkan kelipatan baris $j$ ke baris $i$: $R_i \leftarrow R_i + cR_j$

Operasi-operasi ini menghasilkan sistem yang ekuivalen (punya solusi yang sama).

2.2 Row Echelon Form (REF)

Row Echelon Form adalah bentuk matriks di mana: 1. Semua baris nol (jika ada) berada di bawah 2. Leading entry (pivot) setiap baris nonzero lebih ke kanan dari pivot baris sebelumnya 3. Semua entri di bawah pivot adalah nol

Contoh REF: \[\begin{bmatrix} \mathbf{2} & 3 & -1 & 5 \\ 0 & \mathbf{4} & 2 & -1 \\ 0 & 0 & \mathbf{3} & 7 \\ 0 & 0 & 0 & 0 \end{bmatrix}\]

(Bold = pivot positions)

2.3 Reduced Row Echelon Form (RREF)

Reduced Row Echelon Form tambah mempersyaratkan: 4. Setiap pivot adalah 1 5. Semua entri di atas pivot juga nol

RREF unik untuk setiap matriks. Contoh RREF: \[\begin{bmatrix} \mathbf{1} & 0 & 0 & 2 \\ 0 & \mathbf{1} & 0 & -3 \\ 0 & 0 & \mathbf{1} & 1 \end{bmatrix}\]

2.4 Algoritma Gaussian Elimination

Forward elimination (ke REF): 1. Cari kolom paling kiri yang punya nonzero entry 2. Jika perlu, swap rows agar nonzero entry ada di baris atas (ini partial pivoting untuk numerical stability) 3. Gunakan row operations untuk zero out semua entry di bawah pivot 4. Repeat untuk sub-matriks yang tersisa

Back substitution: setelah REF, solve dari baris bawah ke atas.

3 3. Rank dan Solusi

Definisi: Rank

Rank dari matriks $A$ ($\text{rank}(A)$) adalah jumlah pivot positions dalam REF dari $A$.

Secara ekuivalen: dimensi dari column space $C(A)$ = dimensi dari row space $C(A^T)$.

Properti: - $\text{rank}(A) \leq \min(m, n)$ - $\text{rank}(A) = \text{rank}(A^T)$ - $\text{rank}(AB) \leq \min(\text{rank}(A), \text{rank}(B))$ - Full column rank: $\text{rank}(A) = n$ — kolom-kolom A linearly independent - Full row rank: $\text{rank}(A) = m$ — baris-baris A linearly independent

3.1 Teorema Existence dan Uniqueness

Untuk sistem $A\mathbf{x} = \mathbf{b}$ dengan $A \in \mathbb{R}^{m \times n}$:

Kondisi	Jenis Solusi
$\text{rank}(A) < \text{rank}([A\\|\mathbf{b}])$	No solution (inconsistent)
$\text{rank}(A) = \text{rank}([A\\|\mathbf{b}]) = n$	Unique solution
$\text{rank}(A) = \text{rank}([A\\|\mathbf{b}]) < n$	Infinite solutions

Intuisi: $\mathbf{b}$ harus berada di column space $C(A)$ untuk solusi ada. Jika ada, solusi unik $\iff$ tidak ada “free variables” $\iff$ rank = $n$.

3.2 Rank-Nullity Theorem

Definisi: Rank-Nullity Theorem

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

di mana $\text{nullity}(A) = \dim(N(A))$ = dimensi dari null space = jumlah free variables.

Implikasi untuk OLS: kalau $X \in \mathbb{R}^{n \times p}$ punya $\text{rank}(X) = p$ (full column rank), maka $\text{nullity}(X) = 0$ → tidak ada free variables → $(X^TX)\boldsymbol{\beta} = X^T\mathbf{y}$ punya solusi unik.

4 4. Worked Example: Gaussian Elimination

Worked Example: Solve 3x3 System Step by Step

Selesaikan sistem: \[\begin{aligned} 2x_1 + x_2 - x_3 &= 8 \\ 3x_1 + 2x_2 + x_3 &= 11 \\ x_1 - x_2 + 2x_3 &= 3 \end{aligned}\]

Augmented matrix awal: \[[A|\mathbf{b}] = \begin{bmatrix} 2 & 1 & -1 & \vline & 8 \\ 3 & 2 & 1 & \vline & 11 \\ 1 & -1 & 2 & \vline & 3 \end{bmatrix}\]

Step 1: Buat zero di kolom 1, bawah pivot (baris 1).

$R_2 \leftarrow R_2 - \frac{3}{2}R_1$: \[\begin{bmatrix} 2 & 1 & -1 & \vline & 8 \\ 0 & \frac{1}{2} & \frac{5}{2} & \vline & -1 \\ 1 & -1 & 2 & \vline & 3 \end{bmatrix}\]

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

Step 2: Buat zero di kolom 2, bawah pivot (baris 2).

$R_3 \leftarrow R_3 + 3R_2$: \[\begin{bmatrix} 2 & 1 & -1 & \vline & 8 \\ 0 & \frac{1}{2} & \frac{5}{2} & \vline & -1 \\ 0 & 0 & 10 & \vline & -4 \end{bmatrix}\]

Ini adalah REF. Sekarang back substitution:

Dari baris 3: $10x_3 = -4 \Rightarrow x_3 = -0.4$

Dari baris 2: $\frac{1}{2}x_2 + \frac{5}{2}(-0.4) = -1 \Rightarrow \frac{1}{2}x_2 = -1 + 1 = 0 \Rightarrow x_2 = 0$

Dari baris 1: $2x_1 + 0 - (-0.4) = 8 \Rightarrow 2x_1 = 7.6 \Rightarrow x_1 = 3.8$

Solusi: $\mathbf{x} = \begin{bmatrix}3.8 \\ 0 \\ -0.4\end{bmatrix}$

Verifikasi di R:

A <- matrix(c(2,1,-1,3,2,1,1,-1,2), nrow=3, byrow=TRUE)
b <- c(8, 11, 3)

# Solve the system
x <- solve(A, b)
cat("Solution:", x, "\n")
# [1]  3.8  0.0 -0.4

# Verify: Ax should equal b
cat("A %*% x:", A %*% x, "\n")
# [1]  8 11  3 ✓

# Check rank
cat("Rank of A:", qr(A)$rank, "\n")
# [1] 3  (full rank → unique solution)

5 5. Contoh: Infinite Solutions (Multicollinearity)

Worked Example: Sistem dengan Infinite Solutions

Bayangkan data regression di mana satu variabel adalah perfect linear combination dari yang lain. Misalnya $x_3 = 2x_1 + x_2$. Ini menyebabkan kolom-kolom $X$ linearly dependent.

Pertimbangkan sistem sederhana: \[\begin{bmatrix}1 & 2 & 1 \\ 0 & 1 & -1 \\ 1 & 3 & 0\end{bmatrix} \begin{bmatrix}\beta_1 \\ \beta_2 \\ \beta_3\end{bmatrix} = \begin{bmatrix}5 \\ 1 \\ 6\end{bmatrix}\]

Augmented matrix: \[\begin{bmatrix}1 & 2 & 1 & \vline & 5 \\ 0 & 1 & -1 & \vline & 1 \\ 1 & 3 & 0 & \vline & 6\end{bmatrix}\]

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

$R_3 \leftarrow R_3 - R_2$: \[\begin{bmatrix}1 & 2 & 1 & \vline & 5 \\ 0 & 1 & -1 & \vline & 1 \\ 0 & 0 & 0 & \vline & 0\end{bmatrix}\]

Baris terakhir: $0 = 0$ — bukan kontradiksi, tapi juga tidak memberikan info baru.

Rank $= 2 < n = 3$, dan $\text{rank}(A) = \text{rank}([A|\mathbf{b}]) = 2$ → infinite solutions.

Free variable: $\beta_3 = t$ (arbitrary).

Back substitution: - $\beta_2 = 1 + t$ - $\beta_1 = 5 - 2(1+t) - t = 3 - 3t$

Solusi umum: $\boldsymbol{\beta} = \begin{bmatrix}3 \\ 1 \\ 0\end{bmatrix} + t\begin{bmatrix}-3 \\ 1 \\ 1\end{bmatrix}$ untuk sembarang $t \in \mathbb{R}$.

Artinya: ada tak terhingga kombinasi $(\beta_1, \beta_2, \beta_3)$ yang fit data sama baiknya → coefficients tidak teridentifikasi.

A <- matrix(c(1,2,1,0,1,-1,1,3,0), nrow=3, byrow=TRUE)
b <- c(5, 1, 6)

cat("Rank of A:", qr(A)$rank, "\n")  # 2 < 3
# solve(A, b) akan error karena A singular
tryCatch(solve(A, b), error=function(e) cat("Error:", e$message, "\n"))

6 6. Koneksi ke Econometrics: Multicollinearity

Connection: Perfect Multicollinearity dan OLS

Dalam regresi OLS, kita solve sistem normal equations: \[X^TX\hat{\boldsymbol{\beta}} = X^T\mathbf{y}\]

Ini adalah sistem $p$ persamaan dengan $p$ unknowns ($\hat{\boldsymbol{\beta}} \in \mathbb{R}^p$).

Kapan solusi unik? Ketika $X^TX$ invertible, yaitu $\text{rank}(X^TX) = p$.

Kunci: $\text{rank}(X^TX) = \text{rank}(X)$.

Jadi OLS punya unique solution $\iff$ $X$ full column rank ($\text{rank}(X) = p$).

Perfect multicollinearity: misalnya ada $j \neq k$ di mana $\mathbf{x}_j = c\mathbf{x}_k$ untuk suatu $c$. Maka kolom-kolom $X$ linearly dependent, $\text{rank}(X) < p$, $X^TX$ singular → OLS gagal memberikan unique solution.

Near multicollinearity: kolom-kolom $X$ “hampir” linearly dependent. $X^TX$ masih invertible tapi kondisi buruk (condition number besar). Ini menyebabkan: - Standard errors yang sangat besar - Estimat $\hat{\boldsymbol{\beta}}$ yang tidak stabil (sensitif terhadap perubahan kecil data) - Sulit interpretasi koefisien individual

Solusi: 1. Drop salah satu variabel yang collinear 2. Ridge regression: solve $(X^TX + \lambda I)\hat{\boldsymbol{\beta}} = X^T\mathbf{y}$ — menambah $\lambda I$ memastikan matriks selalu invertible 3. PCA: transformasi ke orthogonal predictors terlebih dahulu

# Demonstrasi multicollinearity
set.seed(42)
n <- 100
x1 <- rnorm(n)
x2 <- 2*x1 + rnorm(n, sd=0.01)  # hampir perfect collinearity
y <- x1 + x2 + rnorm(n)

X <- cbind(1, x1, x2)
cat("Rank of X:", qr(X)$rank, "\n")  # 3, tapi hampir 2

# Condition number (rasio eigenvalue terbesar ke terkecil)
ev <- eigen(t(X) %*% X)$values
cat("Condition number:", max(ev)/min(ev), "\n")  # sangat besar!

# Lihat di lm()
summary(lm(y ~ x1 + x2))
# Standard errors sangat besar meskipun R-squared tinggi

7 7. Solving Linear Systems di R

# === Setup ===
A <- matrix(c(2,1,-1,3,2,1,1,-1,2), nrow=3, byrow=TRUE)
b <- c(8, 11, 3)

# === solve() untuk Ax = b ===
x <- solve(A, b)
print(x)

# === Cek rank ===
qr(A)$rank

# Lebih detail: QR decomposition
qr_result <- qr(A)
cat("Rank:", qr_result$rank, "\n")
cat("Pivot columns:", qr_result$pivot, "\n")

# === RREF (butuh package pracma) ===
# install.packages("pracma")
library(pracma)
rref(A)           # RREF dari A
rref(cbind(A, b)) # RREF dari augmented matrix [A|b]

# === Null space (solusi homogeneous Ax = 0) ===
# Untuk A yang tidak full rank:
A_singular <- matrix(c(1,2,1,0,1,-1,1,3,0), nrow=3, byrow=TRUE)
null_space <- pracma::nullspace(A_singular)
cat("Null space:\n"); print(null_space)
cat("Verify A*null = 0:\n"); print(A_singular %*% null_space)

# === Condition number ===
kappa(A)          # condition number (rasio singular values)
# Interpretasi: kalau > 1e10, matriks "practically singular"

# === Least squares (overdetermined systems) ===
# Ketika m > n, Ax = b tidak punya exact solution
# OLS minimize ||Ax - b||^2
A_tall <- matrix(rnorm(15), 5, 3)  # 5x3: overdetermined
b_tall <- rnorm(5)
x_ls <- qr.solve(A_tall, b_tall)  # least squares solution

8 8. Practice Problems

Practice Problems

Problem 1: Gaussian Elimination

Selesaikan sistem berikut dan tentukan jenis solusinya: \[\begin{aligned} x + 2y - z &= 3 \\ 2x + 3y + z &= 10 \\ 3x + 5y &= 13 \end{aligned}\]

Solusi: Augmented matrix: \[\begin{bmatrix}1 & 2 & -1 & \vline & 3 \\ 2 & 3 & 1 & \vline & 10 \\ 3 & 5 & 0 & \vline & 13\end{bmatrix}\]

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

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

Rank = 2 < n = 3 → infinite solutions. Free variable $z = t$.

$y = -4 - 3t$, $x = 3 - 2(-4-3t) + t = 11 + 7t$.

General solution: $(x,y,z) = (11,-4,0) + t(7,-3,1)$.

Problem 2: Tentukan apakah sistem berikut punya solusi, dan jika ya, temukan solusinya: \[\begin{bmatrix}1 & 0 & 2 \\ 0 & 1 & -1 \\ 2 & 1 & 3\end{bmatrix}\mathbf{x} = \begin{bmatrix}3 \\ 2 \\ 9\end{bmatrix}\]

Solusi: $R_3 \leftarrow R_3 - 2R_1$, kemudian $R_3 \leftarrow R_3 - R_2$: \[\begin{bmatrix}1 & 0 & 2 & \vline & 3 \\ 0 & 1 & -1 & \vline & 2 \\ 0 & 0 & 0 & \vline & 2\end{bmatrix}\]

Baris terakhir: $0 = 2$ — kontradiksi! → No solution (inconsistent).

Makna geometris: $\mathbf{b} = (3,2,9)^T$ tidak berada di column space dari $A$.

Problem 3 (Konseptual): Jelaskan mengapa Ridge Regression selalu punya unique solution.

Solusi: Ridge regression solve $(X^TX + \lambda I)\hat{\boldsymbol{\beta}} = X^T\mathbf{y}$.

Kita perlu $X^TX + \lambda I$ invertible. Untuk $\lambda > 0$, matriks ini selalu positive definite: \[\mathbf{v}^T(X^TX + \lambda I)\mathbf{v} = \mathbf{v}^TX^TX\mathbf{v} + \lambda\mathbf{v}^T\mathbf{v} = \|X\mathbf{v}\|^2 + \lambda\|\mathbf{v}\|^2 > 0\]

untuk $\mathbf{v} \neq \mathbf{0}$ (karena $\lambda > 0$ dan $\|\mathbf{v}\| > 0$). Positive definite → invertible → unique solution.

Secara intuitif: Ridge “regularizes” $X^TX$ dengan menambahkan identitas, memastikan semua eigenvalues > 0, menghilangkan masalah near-singularity.

--- title: "Systems of Linear Equations" subtitle: "Gaussian Elimination, Row Echelon Form, dan Existence of Solutions" format: html: toc: true toc-depth: 3 code-fold: false --- ::: {.callout-note title="Why This Matters for Your Work"} Di balik setiap OLS regression tersembunyi sebuah system of linear equations: $X^TX\boldsymbol{\beta} = X^T\mathbf{y}$. Ketika kamu punya perfect multicollinearity, system ini punya **infinite solutions** — $\hat{\boldsymbol{\beta}}$ tidak unik, identifikasi gagal. Pemahaman tentang kapan sistem linear punya solusi unik, tak ada solusi, atau tak terhingga solusi adalah fondasi untuk memahami: - **Multicollinearity** dan **identifiability** dalam econometrics - **Overdetermined systems** (lebih banyak persamaan dari unknown — inilah regression!) - **Underdetermined systems** (lebih banyak unknown — inilah regularization needed) - **Ridge regression** sebagai cara "membuat" system selalu punya solusi unik ::: --- ## 1. Formulasi Sistem Linear ### Dari Persamaan ke Matriks Sistem $m$ persamaan linear dengan $n$ unknowns: $$\begin{aligned} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n &= b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n &= b_2 \\ &\vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n &= b_m \end{aligned}$$ bisa ditulis sebagai: $$A\mathbf{x} = \mathbf{b}$$ di mana $A \in \mathbb{R}^{m \times n}$, $\mathbf{x} \in \mathbb{R}^n$, $\mathbf{b} \in \mathbb{R}^m$. ### Augmented Matrix Untuk memecahkan sistem, kita gunakan **augmented matrix** $[A|\mathbf{b}]$: $$[A|\mathbf{b}] = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} & \vline & b_1 \\ a_{21} & a_{22} & \cdots & a_{2n} & \vline & b_2 \\ \vdots & \vdots & \ddots & \vdots & \vline & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} & \vline & b_m \end{bmatrix}$$ Ini menyimpan semua informasi yang dibutuhkan untuk menyelesaikan sistem. ### Tiga Kemungkinan Solusi Untuk sistem $A\mathbf{x} = \mathbf{b}$, hanya ada tiga kemungkinan: 1. **Unique solution (solusi tunggal)**: tepat satu $\mathbf{x}$ yang memenuhi semua persamaan 2. **No solution (inconsistent)**: tidak ada $\mathbf{x}$ yang memenuhi semua persamaan 3. **Infinite solutions**: ada tak terhingga $\mathbf{x}$ yang memenuhi semua persamaan Tidak ada kemungkinan keempat. Ini adalah teorema fundamental aljabar linear. --- ## 2. Gaussian Elimination ### Elementary Row Operations Kita dapat memanipulasi sistem tanpa mengubah solusi menggunakan tiga **elementary row operations**: 1. **Row swap**: tukar baris $i$ dan baris $j$: $R_i \leftrightarrow R_j$ 2. **Row scaling**: kalikan baris $i$ dengan skalar $c \neq 0$: $R_i \leftarrow cR_i$ 3. **Row addition**: tambahkan kelipatan baris $j$ ke baris $i$: $R_i \leftarrow R_i + cR_j$ Operasi-operasi ini menghasilkan **sistem yang ekuivalen** (punya solusi yang sama). ### Row Echelon Form (REF) **Row Echelon Form** adalah bentuk matriks di mana: 1. Semua baris nol (jika ada) berada di bawah 2. Leading entry (pivot) setiap baris nonzero lebih ke kanan dari pivot baris sebelumnya 3. Semua entri di bawah pivot adalah nol Contoh REF: $$\begin{bmatrix} \mathbf{2} & 3 & -1 & 5 \\ 0 & \mathbf{4} & 2 & -1 \\ 0 & 0 & \mathbf{3} & 7 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$ (Bold = pivot positions) ### Reduced Row Echelon Form (RREF) **Reduced Row Echelon Form** tambah mempersyaratkan: 4. Setiap pivot adalah 1 5. Semua entri di **atas** pivot juga nol RREF unik untuk setiap matriks. Contoh RREF: $$\begin{bmatrix} \mathbf{1} & 0 & 0 & 2 \\ 0 & \mathbf{1} & 0 & -3 \\ 0 & 0 & \mathbf{1} & 1 \end{bmatrix}$$ ### Algoritma Gaussian Elimination **Forward elimination** (ke REF): 1. Cari kolom paling kiri yang punya nonzero entry 2. Jika perlu, swap rows agar nonzero entry ada di baris atas (ini **partial pivoting** untuk numerical stability) 3. Gunakan row operations untuk zero out semua entry di bawah pivot 4. Repeat untuk sub-matriks yang tersisa **Back substitution**: setelah REF, solve dari baris bawah ke atas. --- ## 3. Rank dan Solusi ::: {.callout-important title="Definisi: Rank"} **Rank** dari matriks $A$ ($\text{rank}(A)$) adalah jumlah pivot positions dalam REF dari $A$. Secara ekuivalen: dimensi dari column space $C(A)$ = dimensi dari row space $C(A^T)$. Properti: - $\text{rank}(A) \leq \min(m, n)$ - $\text{rank}(A) = \text{rank}(A^T)$ - $\text{rank}(AB) \leq \min(\text{rank}(A), \text{rank}(B))$ - **Full column rank**: $\text{rank}(A) = n$ — kolom-kolom A linearly independent - **Full row rank**: $\text{rank}(A) = m$ — baris-baris A linearly independent ::: ### Teorema Existence dan Uniqueness Untuk sistem $A\mathbf{x} = \mathbf{b}$ dengan $A \in \mathbb{R}^{m \times n}$: | Kondisi | Jenis Solusi | |---------|-------------| | $\text{rank}(A) < \text{rank}([A\|\mathbf{b}])$ | **No solution** (inconsistent) | | $\text{rank}(A) = \text{rank}([A\|\mathbf{b}]) = n$ | **Unique solution** | | $\text{rank}(A) = \text{rank}([A\|\mathbf{b}]) < n$ | **Infinite solutions** | **Intuisi**: $\mathbf{b}$ harus berada di column space $C(A)$ untuk solusi ada. Jika ada, solusi unik $\iff$ tidak ada "free variables" $\iff$ rank = $n$. ### Rank-Nullity Theorem ::: {.callout-important title="Definisi: Rank-Nullity Theorem"} Untuk $A \in \mathbb{R}^{m \times n}$: $$\text{rank}(A) + \text{nullity}(A) = n$$ di mana $\text{nullity}(A) = \dim(N(A))$ = dimensi dari null space = jumlah free variables. **Implikasi untuk OLS**: kalau $X \in \mathbb{R}^{n \times p}$ punya $\text{rank}(X) = p$ (full column rank), maka $\text{nullity}(X) = 0$ → tidak ada free variables → $(X^TX)\boldsymbol{\beta} = X^T\mathbf{y}$ punya solusi unik. ::: --- ## 4. Worked Example: Gaussian Elimination ::: {.callout-tip title="Worked Example: Solve 3x3 System Step by Step" collapse="true"} Selesaikan sistem: $$\begin{aligned} 2x_1 + x_2 - x_3 &= 8 \\ 3x_1 + 2x_2 + x_3 &= 11 \\ x_1 - x_2 + 2x_3 &= 3 \end{aligned}$$ **Augmented matrix awal**: $$[A|\mathbf{b}] = \begin{bmatrix} 2 & 1 & -1 & \vline & 8 \\ 3 & 2 & 1 & \vline & 11 \\ 1 & -1 & 2 & \vline & 3 \end{bmatrix}$$ **Step 1**: Buat zero di kolom 1, bawah pivot (baris 1). $R_2 \leftarrow R_2 - \frac{3}{2}R_1$: $$\begin{bmatrix} 2 & 1 & -1 & \vline & 8 \\ 0 & \frac{1}{2} & \frac{5}{2} & \vline & -1 \\ 1 & -1 & 2 & \vline & 3 \end{bmatrix}$$ $R_3 \leftarrow R_3 - \frac{1}{2}R_1$: $$\begin{bmatrix} 2 & 1 & -1 & \vline & 8 \\ 0 & \frac{1}{2} & \frac{5}{2} & \vline & -1 \\ 0 & -\frac{3}{2} & \frac{5}{2} & \vline & -1 \end{bmatrix}$$ **Step 2**: Buat zero di kolom 2, bawah pivot (baris 2). $R_3 \leftarrow R_3 + 3R_2$: $$\begin{bmatrix} 2 & 1 & -1 & \vline & 8 \\ 0 & \frac{1}{2} & \frac{5}{2} & \vline & -1 \\ 0 & 0 & 10 & \vline & -4 \end{bmatrix}$$ Ini adalah **REF**. Sekarang back substitution: **Dari baris 3**: $10x_3 = -4 \Rightarrow x_3 = -0.4$ **Dari baris 2**: $\frac{1}{2}x_2 + \frac{5}{2}(-0.4) = -1 \Rightarrow \frac{1}{2}x_2 = -1 + 1 = 0 \Rightarrow x_2 = 0$ **Dari baris 1**: $2x_1 + 0 - (-0.4) = 8 \Rightarrow 2x_1 = 7.6 \Rightarrow x_1 = 3.8$ Solusi: $\mathbf{x} = \begin{bmatrix}3.8 \\ 0 \\ -0.4\end{bmatrix}$ **Verifikasi di R**: ```r A <- matrix(c(2,1,-1,3,2,1,1,-1,2), nrow=3, byrow=TRUE) b <- c(8, 11, 3) # Solve the system x <- solve(A, b) cat("Solution:", x, "\n") # [1] 3.8 0.0 -0.4 # Verify: Ax should equal b cat("A %*% x:", A %*% x, "\n") # [1] 8 11 3 ✓ # Check rank cat("Rank of A:", qr(A)$rank, "\n") # [1] 3 (full rank → unique solution) ``` ::: --- ## 5. Contoh: Infinite Solutions (Multicollinearity) ::: {.callout-tip title="Worked Example: Sistem dengan Infinite Solutions" collapse="true"} Bayangkan data regression di mana satu variabel adalah perfect linear combination dari yang lain. Misalnya $x_3 = 2x_1 + x_2$. Ini menyebabkan kolom-kolom $X$ linearly dependent. Pertimbangkan sistem sederhana: $$\begin{bmatrix}1 & 2 & 1 \\ 0 & 1 & -1 \\ 1 & 3 & 0\end{bmatrix} \begin{bmatrix}\beta_1 \\ \beta_2 \\ \beta_3\end{bmatrix} = \begin{bmatrix}5 \\ 1 \\ 6\end{bmatrix}$$ Augmented matrix: $$\begin{bmatrix}1 & 2 & 1 & \vline & 5 \\ 0 & 1 & -1 & \vline & 1 \\ 1 & 3 & 0 & \vline & 6\end{bmatrix}$$ $R_3 \leftarrow R_3 - R_1$: $$\begin{bmatrix}1 & 2 & 1 & \vline & 5 \\ 0 & 1 & -1 & \vline & 1 \\ 0 & 1 & -1 & \vline & 1\end{bmatrix}$$ $R_3 \leftarrow R_3 - R_2$: $$\begin{bmatrix}1 & 2 & 1 & \vline & 5 \\ 0 & 1 & -1 & \vline & 1 \\ 0 & 0 & 0 & \vline & 0\end{bmatrix}$$ Baris terakhir: $0 = 0$ — bukan kontradiksi, tapi juga tidak memberikan info baru. Rank $= 2 < n = 3$, dan $\text{rank}(A) = \text{rank}([A|\mathbf{b}]) = 2$ → **infinite solutions**. Free variable: $\beta_3 = t$ (arbitrary). Back substitution: - $\beta_2 = 1 + t$ - $\beta_1 = 5 - 2(1+t) - t = 3 - 3t$ Solusi umum: $\boldsymbol{\beta} = \begin{bmatrix}3 \\ 1 \\ 0\end{bmatrix} + t\begin{bmatrix}-3 \\ 1 \\ 1\end{bmatrix}$ untuk sembarang $t \in \mathbb{R}$. **Artinya**: ada tak terhingga kombinasi $(\beta_1, \beta_2, \beta_3)$ yang fit data sama baiknya → coefficients tidak teridentifikasi. ```r A <- matrix(c(1,2,1,0,1,-1,1,3,0), nrow=3, byrow=TRUE) b <- c(5, 1, 6) cat("Rank of A:", qr(A)$rank, "\n") # 2 < 3 # solve(A, b) akan error karena A singular tryCatch(solve(A, b), error=function(e) cat("Error:", e$message, "\n")) ``` ::: --- ## 6. Koneksi ke Econometrics: Multicollinearity ::: {.callout-caution title="Connection: Perfect Multicollinearity dan OLS"} Dalam regresi OLS, kita solve sistem **normal equations**: $$X^TX\hat{\boldsymbol{\beta}} = X^T\mathbf{y}$$ Ini adalah sistem $p$ persamaan dengan $p$ unknowns ($\hat{\boldsymbol{\beta}} \in \mathbb{R}^p$). **Kapan solusi unik?** Ketika $X^TX$ invertible, yaitu $\text{rank}(X^TX) = p$. Kunci: $\text{rank}(X^TX) = \text{rank}(X)$. Jadi OLS punya unique solution $\iff$ $X$ **full column rank** ($\text{rank}(X) = p$). **Perfect multicollinearity**: misalnya ada $j \neq k$ di mana $\mathbf{x}_j = c\mathbf{x}_k$ untuk suatu $c$. Maka kolom-kolom $X$ linearly dependent, $\text{rank}(X) < p$, $X^TX$ singular → OLS gagal memberikan unique solution. **Near multicollinearity**: kolom-kolom $X$ "hampir" linearly dependent. $X^TX$ masih invertible tapi **kondisi buruk** (condition number besar). Ini menyebabkan: - Standard errors yang sangat besar - Estimat $\hat{\boldsymbol{\beta}}$ yang tidak stabil (sensitif terhadap perubahan kecil data) - Sulit interpretasi koefisien individual **Solusi**: 1. Drop salah satu variabel yang collinear 2. Ridge regression: solve $(X^TX + \lambda I)\hat{\boldsymbol{\beta}} = X^T\mathbf{y}$ — menambah $\lambda I$ memastikan matriks selalu invertible 3. PCA: transformasi ke orthogonal predictors terlebih dahulu ```r # Demonstrasi multicollinearity set.seed(42) n <- 100 x1 <- rnorm(n) x2 <- 2*x1 + rnorm(n, sd=0.01) # hampir perfect collinearity y <- x1 + x2 + rnorm(n) X <- cbind(1, x1, x2) cat("Rank of X:", qr(X)$rank, "\n") # 3, tapi hampir 2 # Condition number (rasio eigenvalue terbesar ke terkecil) ev <- eigen(t(X) %*% X)$values cat("Condition number:", max(ev)/min(ev), "\n") # sangat besar! # Lihat di lm() summary(lm(y ~ x1 + x2)) # Standard errors sangat besar meskipun R-squared tinggi ``` ::: --- ## 7. Solving Linear Systems di R ```r # === Setup === A <- matrix(c(2,1,-1,3,2,1,1,-1,2), nrow=3, byrow=TRUE) b <- c(8, 11, 3) # === solve() untuk Ax = b === x <- solve(A, b) print(x) # === Cek rank === qr(A)$rank # Lebih detail: QR decomposition qr_result <- qr(A) cat("Rank:", qr_result$rank, "\n") cat("Pivot columns:", qr_result$pivot, "\n") # === RREF (butuh package pracma) === # install.packages("pracma") library(pracma) rref(A) # RREF dari A rref(cbind(A, b)) # RREF dari augmented matrix [A|b] # === Null space (solusi homogeneous Ax = 0) === # Untuk A yang tidak full rank: A_singular <- matrix(c(1,2,1,0,1,-1,1,3,0), nrow=3, byrow=TRUE) null_space <- pracma::nullspace(A_singular) cat("Null space:\n"); print(null_space) cat("Verify A*null = 0:\n"); print(A_singular %*% null_space) # === Condition number === kappa(A) # condition number (rasio singular values) # Interpretasi: kalau > 1e10, matriks "practically singular" # === Least squares (overdetermined systems) === # Ketika m > n, Ax = b tidak punya exact solution # OLS minimize ||Ax - b||^2 A_tall <- matrix(rnorm(15), 5, 3) # 5x3: overdetermined b_tall <- rnorm(5) x_ls <- qr.solve(A_tall, b_tall) # least squares solution ``` --- ## 8. Practice Problems ::: {.callout-warning title="Practice Problems" collapse="true"} **Problem 1**: Gaussian Elimination Selesaikan sistem berikut dan tentukan jenis solusinya: $$\begin{aligned} x + 2y - z &= 3 \\ 2x + 3y + z &= 10 \\ 3x + 5y &= 13 \end{aligned}$$ **Solusi**: Augmented matrix: $$\begin{bmatrix}1 & 2 & -1 & \vline & 3 \\ 2 & 3 & 1 & \vline & 10 \\ 3 & 5 & 0 & \vline & 13\end{bmatrix}$$ $R_2 \leftarrow R_2 - 2R_1$, $R_3 \leftarrow R_3 - 3R_1$: $$\begin{bmatrix}1 & 2 & -1 & \vline & 3 \\ 0 & -1 & 3 & \vline & 4 \\ 0 & -1 & 3 & \vline & 4\end{bmatrix}$$ $R_3 \leftarrow R_3 - R_2$: $$\begin{bmatrix}1 & 2 & -1 & \vline & 3 \\ 0 & -1 & 3 & \vline & 4 \\ 0 & 0 & 0 & \vline & 0\end{bmatrix}$$ Rank = 2 < n = 3 → **infinite solutions**. Free variable $z = t$. $y = -4 - 3t$, $x = 3 - 2(-4-3t) + t = 11 + 7t$. General solution: $(x,y,z) = (11,-4,0) + t(7,-3,1)$. --- **Problem 2**: Tentukan apakah sistem berikut punya solusi, dan jika ya, temukan solusinya: $$\begin{bmatrix}1 & 0 & 2 \\ 0 & 1 & -1 \\ 2 & 1 & 3\end{bmatrix}\mathbf{x} = \begin{bmatrix}3 \\ 2 \\ 9\end{bmatrix}$$ **Solusi**: $R_3 \leftarrow R_3 - 2R_1$, kemudian $R_3 \leftarrow R_3 - R_2$: $$\begin{bmatrix}1 & 0 & 2 & \vline & 3 \\ 0 & 1 & -1 & \vline & 2 \\ 0 & 0 & 0 & \vline & 2\end{bmatrix}$$ Baris terakhir: $0 = 2$ — kontradiksi! → **No solution** (inconsistent). Makna geometris: $\mathbf{b} = (3,2,9)^T$ tidak berada di column space dari $A$. --- **Problem 3** (Konseptual): Jelaskan mengapa Ridge Regression selalu punya unique solution. **Solusi**: Ridge regression solve $(X^TX + \lambda I)\hat{\boldsymbol{\beta}} = X^T\mathbf{y}$. Kita perlu $X^TX + \lambda I$ invertible. Untuk $\lambda > 0$, matriks ini selalu positive definite: $$\mathbf{v}^T(X^TX + \lambda I)\mathbf{v} = \mathbf{v}^TX^TX\mathbf{v} + \lambda\mathbf{v}^T\mathbf{v} = \|X\mathbf{v}\|^2 + \lambda\|\mathbf{v}\|^2 > 0$$ untuk $\mathbf{v} \neq \mathbf{0}$ (karena $\lambda > 0$ dan $\|\mathbf{v}\| > 0$). Positive definite → invertible → unique solution. Secara intuitif: Ridge "regularizes" $X^TX$ dengan menambahkan identitas, memastikan semua eigenvalues > 0, menghilangkan masalah near-singularity. :::