Lecture Notes
Semester 1
Vector and Matrix Theory
Reduced Row Echelon Form

Prerequisites: Reduced Row Echelon Form Interpretation

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

Reduced Row Echelon Form

Solving EA=UEA = U

Suatu matriks AA dapat dieliminasi barisnya menjadi matriks upper triangular UU dengan matriks eliminasi EE.

EA=UEA = U

Contoh:

Terdapat matriks AA berikut:

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

Kita dapat mengeliminasi baris pertama dengan mengalikan AA dengan matriks eliminasi E1E_1 berikut:

E1=[100−210−301]E_1 = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ -3 & 0 & 1 \end{bmatrix}

Sehingga:

E1A=[12027001−4−6002−4−8]E_1A = \begin{bmatrix} 1 & 2 & 0 & 2 & 7 \\ 0 & 0 & 1 & -4 & -6 \\ 0 & 0 & 2 & -4 & -8 \end{bmatrix}

Kita dapat mengeliminasi baris kedua dengan mengalikan E1AE_1A dengan matriks eliminasi E2E_2 berikut:

E2=[1000100−21]E_2 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -2 & 1 \end{bmatrix}

Sehingga:

E2E1A=U=[12027001−4−600044]E_2E_1A = U = \begin{bmatrix} 1 & 2 & 0 & 2 & 7 \\ 0 & 0 & 1 & -4 & -6 \\ 0 & 0 & 0 & 4 & 4 \end{bmatrix}

Bentuk matriks E2E1AE_2E_1A di atas sudah merupakan bentuk upper triangular.

Solving FU=RFU = R

Suatu matriks upper triangular UU dapat dieliminasi kolomnya menjadi matriks reduced row echelon RR dengan matriks eliminasi FF.

Melanjutkan contoh sebelumnya, kita dapat membuat baris ketiga menjadi baris pivot dengan membaginya dengan nilai pivot seperti ditunjukkan oleh matriks eliminasi F3F_3 berikut:

F3=[1000100014]F_3 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & \frac{1}{4} \end{bmatrix}

Sehingga:

F3U=[12027001−4−600011]F_3U = \begin{bmatrix} 1 & 2 & 0 & 2 & 7 \\ 0 & 0 & 1 & -4 & -6 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix}

Lalu pada baris kedua, kita dapat membuat nilai yang berada tepat diatas pivot baris ketiga menjadi nol dengan mengalikan F3UF_3U dengan matriks eliminasi F2F_2 berikut:

F2=[100014001]F_2 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 4 \\ 0 & 0 & 1 \end{bmatrix}

Sehingga:

F2F3U=[120270010−200011]F_2F_3U = \begin{bmatrix} 1 & 2 & 0 & 2 & 7 \\ 0 & 0 & 1 & 0 & -2 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix}

Lalu pada baris pertama, kita dapat membuat nilai yang berada tepat diatas pivot baris ketiga menjadi nol dengan mengalikan F2F3UF_2F_3U dengan matriks eliminasi F1F_1 berikut:

F1=[10−2010001]F_1 = \begin{bmatrix} 1 & 0 & -2 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}

Sehingga:

F1F2F3U=R=[120050010−200011]F_1F_2F_3U = R = \begin{bmatrix} 1 & 2 & 0 & 0 & 5 \\ 0 & 0 & 1 & 0 & -2 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix}

Bentuk matriks F1F2F3UF_1F_2F_3U di atas sudah merupakan bentuk reduced row echelon.

RREF Interpretation

Kita sudah mendapatkan dua jenis matriks dari AA yaitu UU dan RR.

A=[1202724108362213]A = \begin{bmatrix} 1 & 2 & 0 & 2 & 7 \\ 2 & 4 & 1 & 0 & 8 \\ 3 & 6 & 2 & 2 & 13 \end{bmatrix} U=[12027001−4−600044]U = \begin{bmatrix} 1 & 2 & 0 & 2 & 7 \\ 0 & 0 & 1 & -4 & -6 \\ 0 & 0 & 0 & 4 & 4 \end{bmatrix} R=[120050010−200011]R = \begin{bmatrix} 1 & 2 & 0 & 0 & 5 \\ 0 & 0 & 1 & 0 & -2 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix}

Matriks RR merupakan bentuk "identitas" penyusun matriks AA. Pivot kolom (dalam contoh: kolom 1, 3, dan 4) pada matriks RR menunjukkan kolom utama penyusun matriks AA.

Kolom non pivot dapat diinterpretasikan sebagai kombinasi linear dari kolom pivot. Misalnya, kolom 2 pada matriks AA dapat diinterpretasikan sebagai kombinasi linear dari pivot-kolom matriks AA:

[246]=2[123]+0[012]+0[202]\begin{bmatrix} 2 \\ 4 \\ 6 \end{bmatrix} = 2 \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} + 0 \begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix} + 0 \begin{bmatrix} 2 \\ 0 \\ 2 \end{bmatrix}

dimana koefisien 22, 00, dan 00 merupakan nilai kolom non pivot pada matriks RR.

Sehingga seluruh kolom pada matriks AA dapat di-breakdown menjadi kombinasi linear dari pivot-kolom matriks AA dengan koefisien yang sesuai dengan nilai kolom non pivot pada matriks RR:

[123]=1[123]+0[012]+0[202]\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} = 1 \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} + 0 \begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix} + 0 \begin{bmatrix} 2 \\ 0 \\ 2 \end{bmatrix} [246]=2[123]+0[012]+0[202]\begin{bmatrix} 2 \\ 4 \\ 6 \end{bmatrix} = 2 \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} + 0 \begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix} + 0 \begin{bmatrix} 2 \\ 0 \\ 2 \end{bmatrix} [012]=0[123]+1[012]+0[202]\begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix} = 0 \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} + 1 \begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix} + 0 \begin{bmatrix} 2 \\ 0 \\ 2 \end{bmatrix} [202]=0[123]+0[012]+1[202]\begin{bmatrix} 2 \\ 0 \\ 2 \end{bmatrix} = 0 \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} + 0 \begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix} + 1 \begin{bmatrix} 2 \\ 0 \\ 2 \end{bmatrix} [7813]=5[123]−2[012]+1[202]\begin{bmatrix} 7 \\ 8 \\ 13 \end{bmatrix} = 5 \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} - 2 \begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix} + 1 \begin{bmatrix} 2 \\ 0 \\ 2 \end{bmatrix}
Lecture 13: Finite-State MachineLecture 8: Vector Spaces and Subspaces