Lecture Notes
Semester 1
Vector and Matrix Theory
Lecture 10: The Complete Solution

Lecture 10: The Complete Solution to Ax=bAx = b

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

  1. Complete solution dari Ax=bAx = b adalah x=particular solution+nullspace solutionx = \text{particular solution} + \text{nullspace solution}
  2. Eliminasi dari [A b][A \ b] mengantarkan ke [R d][R \ d]. Ax=bAx = b senilai dengan Rx=dRx = d.
  3. Ax=bAx = b dan Rx=dRx = d memiliki solusi jika seluruh baris nol di RR juga nol di dd (0=0)(0 = 0).
  4. AA punya full column rank r=nr = n jika nullspace N(A)=0N(A) = 0 - no free variables.
  5. AA punya full row rank r=mr = m jika column space C(A)=RmC(A) = \mathbb{R}^m: Ax=bAx = b selalu punya solusi.
  6. Ketika Rx=dRx=d punya solusi, salah satu particular solution xpx_p memiliki seluruh free variable bernilai nol.
  7. Empat kasus utama:
    • r=n=mr = n = m: AA punya solusi unik dan invertible.
    • r=n<mr = n < m: Ax=bAx = b memiliki 1 atau 0 solusi.
    • r=m<nr = m < n: setiap Ax=bAx = b memiliki solusi.
    • r<m,r<nr < m, r < n: Ax=bAx = b 0 atau ∞\infty solusi.

Particular Solution Axp=bAx_p = b

Gilbert's personal favorite: jadikan free variables bernilai nol dan pivot variables bernilai dd.

xp menyelesaikan Axp=bxn(n−r) menyelesaikan Axn=0\begin{align*} x_{p} &\text{ menyelesaikan } &Ax_p &= b \\ x_{n} & (n - r) \text{ menyelesaikan } &Ax_n &= 0 \end{align*}

Sehingga solusi dari Ax=bAx = b adalah

x=xp+xn\fbox{$x = x_p + x_n$}

Contoh

Terdapat Ax=bAx = b:

[129311610132][x1x2x3x4]=[725]\begin{bmatrix} 1 & 2 & 9 & 3 \\ 1 & 1 & 6 & 1 \\ 0 & 1 & 3 & 2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \begin{bmatrix} 7 \\ 2 \\ 5 \end{bmatrix}

Setelah dieliminasi ke bentuk R→Rx=dR \rightarrow Rx = d:

[103−101320000][x1x2x3x4]=[−350]\begin{bmatrix} 1 & 0 & 3 & -1 \\ 0 & 1 & 3 & 2 \\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \begin{bmatrix} -3 \\ 5 \\ 0 \end{bmatrix}

Maka particular solutionnya adalah

[−3500]{pivot1=d1=−3pivot2=d2=5free3=0free4=0\begin{bmatrix} -3 \\ 5 \\ 0 \\ 0 \end{bmatrix} \begin{cases} \text{pivot}_1 = d_1 = -3 \\ \text{pivot}_2 = d_2 = 5 \\ \text{free}_3 = 0 \\ \text{free}_4 = 0 \end{cases}

nullspace solutionnya adalah

s1→x3[−3−310],s2→x4[1−201]s_1\rightarrow x_3\begin{bmatrix} -3 \\ -3 \\ 1 \\ 0 \end{bmatrix}, s_2\rightarrow x_4\begin{bmatrix} 1 \\ -2 \\ 0 \\ 1 \end{bmatrix}

Sehingga solusi lengkap dari Ax=bAx = b adalah

x=xp+xnx=[−3500]⏟xp+x3[−3−310]+x4[1−201]⏟xn\begin{align*} x &= x_p + x_n \\ x&= \underbrace{\begin{bmatrix} -3 \\ 5 \\ 0 \\ 0 \end{bmatrix}}_{x_p} + \underbrace{x_3\begin{bmatrix} -3 \\ -3 \\ 1 \\ 0 \end{bmatrix} + x_4\begin{bmatrix} 1 \\ -2 \\ 0 \\ 1 \end{bmatrix}}_{x_n} \end{align*}

Setiap matriks AA dengan full column rank r=nr = n memiliki properti:

  1. Setiap kolom dari AA memiliki pivot.
  2. Tidak ada free variable sehingga tidak ada special solution.
  3. Nullspace N(A)N(A) hanya memiliki satu vektor nol.
  4. Jika Ax=bAx = b memiliki solusi, maka hanya itulah solusinya.
  5. Matriks persegi AA dapat diinvers jika dan hanya jika AA memiliki full column rank r=nr = n.

Setiap matriks AA dengan full row rank r=mr = m memiliki properti:

  1. Setiap baris dari AA memiliki pivot. RR tidak memiliki baris nol.
  2. Setiap Ax=bAx = b memiliki solusi untuk setiap bb.
  3. Column space C(A)C(A) adalah Rm\mathbb{R}^m.
  4. Ada n−r=n−mn - r = n - m special solution dalam nullspace N(A)N(A).
  5. Nullspace dari ATA^T adalah vektor nol.

Possibilites for Linear Equations

Parameter 1Parameter 2TypeSolution
r=mr = mr=nr = nPersegi, dapat diinversMemiliki 1 solusi
r=mr = mr<nr < nPendek, lebarMemiliki ∞\infty solusi
r<mr < mr=nr = nTinggi, tipisMemiliki 0 atau 1 solusi
r<mr < mr<nr < nTidak full rankMemiliki 0 atau ∞\infty solusi

Review of the Key Ideas

  1. Rank rr adalah jumlah pivot di RR. Matriks RR memiliki m−rm-r baris nol.
  2. Ax=bAx = b dapat diselesaikan jika dan hanya jika m−rm - r baris terakhir menghasilkan 0=00 = 0.
  3. Particulas solution xpx_p memiliki seluruh free variable bernilai nol.
  4. Pivot variable ditentukan setelah memilih free variable.
  5. Full column rank r=nr = n berarti tidak ada variabel bebas: 1 atau tidak ada solusi.
  6. Full row rank r=mr = m berarti 1 solusi jika m=nm = n dan ∞\infty solusi jika m<nm < n.

Worked Examples

Misalkan 3×43 \times 4 matriks AA memiliki vektor s=[2310]Ts = \begin{bmatrix} 2 & 3 & 1 & 0 \end{bmatrix}^T sebagai satu-satunya special solution untuk Ax=0Ax = 0.

  1. Apakah rank dari AA dan solusi lengkap Ax=0Ax = 0?
  2. Bagaimana bentuk rref(A)\text{rref}(A)?
  3. Apakah Ax=bAx = b memiliki solusi untuk setiap bb?

Jawab:

  1. n−r=3  ⟹  4−r=1  ⟹  r=3n - r = 3 \implies 4 - r = 1 \implies r = 3. AA memiliki full row rank.

  2. Perhatikan vektor ss: lihat pembahasan

    [2310]A13=−2A23=−3letak free variableA33=0\begin{bmatrix} 2 \\ 3 \\ 1 \\ 0 \end{bmatrix} \begin{matrix} \text{A}_{13} = -2 \\ \text{A}_{23} = -3 \\ \text{letak free variable} \\ \text{A}_{33} = 0 \end{matrix}

    Maka rref(A)\text{rref}(A) adalah

    [10−2001−300001]\begin{bmatrix} 1 & 0 & -2 & 0 \\ 0 & 1 & -3 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}

  3. Ax=bAx = b memiliki solusi untuk setiap bb karena AA memiliki full row rank dan m<nm < n.

Jika Ax=bAx = b dan Cx=bCx = b memiliki solusi lengkap yang sama, apakah berarti A=CA = C?

Jawab:

Jika Ax=bAx = b dan Cx=bCx = b memiliki solusi yang sama, maka AA dan CC memiliki bentuk yang sama dan nullspace yang sama. Jika kolom 1 dari AA, x=[1 0… 0]x = [1 \ 0 \dots \ 0] menyelesaikan Ax=bAx = b lalu menyelesaikan Cx=bCx = b pula, maka AA dan CC memiliki kolom 1 yang sama. Begitu pula kolom lainnya. A=CA = C.

Lecture 9: The Nullspace of ALecture 11: Independence, Basis, and Dimension