Gaussian elimination — forward elimination, back substitution: Exercises

4.5.9 · D4 · Maths › Linear Algebra (Full) › Gaussian elimination — forward elimination, back substitutio

Vocabulary ka quick reminder jo hum use karte hain (sab parent se):

Augmented matrix $[A ∣ b]$ — coefficients aur right-hand side ek saath side by side, bar se separated.
Pivot — woh nonzero entry jo hum har column mein use karte hain uske neeche ki entries clear karne ke liye.
Multiplier $m_{ik} = a_{ik} / a_{k k}$ — pivot row ka exactly itna amount jo hum subtract karte hain entry $a_{ik}$ ko zero out karne ke liye.
Upper-triangular $U$ — diagonal ke neeche sab zeros; woh "staircase" jo bottom-up solve karne deta hai.

L1 — Recognition

Exercise 1.1

Inme se kaun sa matrix upper-triangular form mein hai (back substitution ke liye ready)? $A = [2013], B = [1402], C = 100530217$

Recall Solution

KYA check karte hain: upper-triangular matlab diagonal ke strictly neeche har entry zero honi chahiye. Sirf diagonal line ke neeche dekho.

$A$ : below-diagonal entry position $(2, 1)$ par $0$ hai. ✓ Upper-triangular.
$B$ : position $(2, 1)$ par $4 \neq = 0$ hai. ✗ Upper-triangular nahi.
$C$ : diagonal ke neeche positions $(2, 1), (3, 1), (3, 2)$ hain, sab $0$ . ✓ Upper-triangular.

Answer: $A$ aur $C$ upper-triangular hain; $B$ nahi hai.

Exercise 1.2

Neeche diye augmented matrix mein, column 1 ka pivot aur uske neeche wali entry jo eliminate karni hai, dono identify karo. $[46 - 2 1 69]$

Recall Solution

Pivot = column 1 mein diagonal entry = $a_{11} = 4$ . Eliminate karne wali entry = column 1 mein uske neeche wali = $a_{21} = 6$ . Multiplier hoga $m_{21} = a_{21} / a_{11} = 6/4 = \frac{3}{2}$ , aur hum $R_{2} \to R_{2} - \frac{3}{2} R_{1}$ karenge. (Yahan tum se run karne ko nahi kaha gaya — bas players identify karo.)

L2 — Application

Exercise 2.1

Forward elimination + back substitution se solve karo: $x + 2 y 3 x + 4 y = 5 = 11$

Recall Solution

Augmented matrix: $[1324511]$ Forward elimination. Pivot $a_{11} = 1$ . Multiplier $m_{21} = 3/1 = 3$ , toh $R_{2} \to R_{2} - 3 R_{1}$ . KYU: row 1 ki $3$ copies subtract karne se position $(2, 1)$ mein $3$ turn ho jaata hai $3 - 3 (1) = 0$ mein. Row 2 ban jaati hai: $(3 - 3, 4 - 6 ∣ 11 - 15) = (0, - 2 ∣ - 4)$ . $[10 2 - 2 5 - 4]$ Back substitution.

Row 2: $- 2 y = - 4 \Rightarrow y = 2$ .
Row 1: $x + 2 (2) = 5 \Rightarrow x = 1$ .

Answer: $x = 1, y = 2$ . Original row 2 check karo: $3 (1) + 4 (2) = 11$ ✓.

Exercise 2.2

$3 \times 3$ system solve karo: $x + y + z 2 x + 3 y + z x - y + 2 z = 6 = 11 = 5$

Recall Solution

Augmented matrix: $121 13 - 1 1126115$ Column 1, pivot $a_{11} = 1$ .

$m_{21} = 2/1 = 2$ : $R_{2} \to R_{2} - 2 R_{1} = (0, 1, - 1 ∣ - 1)$ .
$m_{31} = 1/1 = 1$ : $R_{3} \to R_{3} - 1 R_{1} = (0, - 2, 1 ∣ - 1)$ . $100 11 - 2 1 - 1 1 6 - 1 - 1$ Column 2, pivot $a_{22} = 1$ .
$m_{32} = - 2/1 = - 2$ : $R_{3} \to R_{3} - (- 2) R_{2} = R_{3} + 2 R_{2} = (0, 0, - 1 ∣ - 3)$ . $100110 1 - 1 - 1 6 - 1 - 3$ Back substitution.
Row 3: $- z = - 3 \Rightarrow z = 3$ .
Row 2: $y - z = - 1 \Rightarrow y - 3 = - 1 \Rightarrow y = 2$ .
Row 1: $x + y + z = 6 \Rightarrow x + 2 + 3 = 6 \Rightarrow x = 1$ .

Answer: $x = 1, y = 2, z = 3$ . Original row 3 check karo: $1 - 2 + 6 = 5$ ✓.

L3 — Analysis

Exercise 3.1

Elimination karo aur system classify karo (unique / none / infinite): $x + 2 y - z 2 x + 4 y - 2 z 3 x + 6 y - z = 1 = 2 = 5$

Recall Solution

Augmented matrix: $123246 - 1 - 2 - 1 125$ Column 1, pivot $1$ .

$m_{21} = 2$ : $R_{2} \to R_{2} - 2 R_{1} = (0, 0, 0 ∣ 0)$ .
$m_{31} = 3$ : $R_{3} \to R_{3} - 3 R_{1} = (0, 0, 2 ∣ 2)$ . $100200 - 1 02 102$ Row 2 poori zeros hai — column 2 mein koi pivot available nahi. Swap $R_{2} \leftrightarrow R_{3}$ karo taaki nonzero entry upar aaye (yeh rows reorder karta hai bina solution set badhe): $100200 - 1 20 120$ Structure padho:
Row 3 $0 = 0$ hai — hamesha true, koi information nahi deta → ek free variable exist karta hai.
Pivots columns 1 aur 3 mein hain. Column 2 mein koi pivot nahi, toh $y$ free hai.

Classification: infinitely many solutions. Maano $y = t$ .

Row 2: $2 z = 2 \Rightarrow z = 1$ .
Row 1: $x + 2 t - 1 = 1 \Rightarrow x = 2 - 2 t$ .

Answer: $(x, y, z) = (2 - 2 t, t, 1)$ kisi bhi real $t$ ke liye → infinitely many solutions.

Exercise 3.2

Bina poora solve kiye determine karo ki system consistent hai ya nahi: $x - y + 2 z 2 x - 2 y + 4 z = 4 = 7$

Recall Solution

Column 1, pivot $1$ . $m_{21} = 2$ : $R_{2} \to R_{2} - 2 R_{1}$ . Row 2: $(2 - 2, - 2 + 2, 4 - 4 ∣ 7 - 8) = (0, 0, 0 ∣ - 1)$ . $[10 - 1 0 20 4 - 1]$ Row 2 padhta hai $0 = - 1$ — impossible. Answer: system inconsistent hai (koi solution nahi). KYU elimination ne reveal kiya: dono equations parallel-but-shifted planes describe karte hain; ek ko twice-the-other se subtract karne par sare variables cancel ho jaate hain aur ek false numeric statement bacha rehta hai.

L4 — Synthesis

Exercise 4.1

Neeche diye system mein pehli pivot position par zero hai. Partial pivoting use karo (us row ko swap karo jisme absolute value mein pehle column ki sabse badi entry ho), phir solve karo. $021 11 - 1 1 - 1 2 415$

Recall Solution

Pivot problem. Position $(1, 1)$ $0$ hai — hum isse divide nahi kar sakte. Column-1 entries dekho: $∣0∣, ∣2∣, ∣1∣$ . Sabse bada hai $∣2∣$ row 2 mein. Swap $R_{1} \leftrightarrow R_{2}$ : $201 11 - 1 - 1 12 145$ Column 1, pivot $2$ .

$m_{21} = 0/2 = 0$ : row 2 pehle se clear hai, kuch nahi karna.
$m_{31} = 1/2$ : $R_{3} \to R_{3} - \frac{1}{2} R_{1} = (0, - \frac{3}{2}, \frac{5}{2} ∣ \frac{9}{2})$ . $200 11 - \frac{3}{2} - 1 1 \frac{5}{2} 14 \frac{9}{2}$ Column 2, pivot $1$ .
$m_{32} = - \frac{3}{2} /1 = - \frac{3}{2}$ : $R_{3} \to R_{3} + \frac{3}{2} R_{2} = (0, 0, 4 ∣ \frac{21}{2})$ . $200110 - 1 14 14 \frac{21}{2}$ Back substitution.
Row 3: $4 z = \frac{21}{2} \Rightarrow z = \frac{21}{8}$ .
Row 2: $y + z = 4 \Rightarrow y = 4 - \frac{21}{8} = \frac{11}{8}$ .
Row 1: $2 x + y - z = 1 \Rightarrow 2 x = 1 - \frac{11}{8} + \frac{21}{8} = 1 + \frac{10}{8} = \frac{18}{8} = \frac{9}{4} \Rightarrow x = \frac{9}{8}$ .

Answer: $x = \frac{9}{8}, y = \frac{11}{8}, z = \frac{21}{8}$ . Original row 1 check karo ( $0 x + y + z = 4$ ): $\frac{11}{8} + \frac{21}{8} = \frac{32}{8} = 4$ ✓.

Exercise 4.2

$k$ ki woh value(s) dhundho jiske liye system ka koi solution nahi ho: $x + 2 y 2 x + k y = 3 = 7$

Recall Solution

Augmented matrix: $[12 2 k 37]$ Eliminate karo. $m_{21} = 2/1 = 2$ : $R_{2} \to R_{2} - 2 R_{1}$ . Row 2: $(0, k - 4 ∣ 7 - 6) = (0, k - 4 ∣ 1)$ . $[10 2 k - 4 31]$ Last row analyse karo $(0) (x) + (k - 4) y = 1$ .

Agar $k - 4 \neq = 0$ (yaani $k \neq = 4$ ): $y = \frac{1}{k - 4}$ solve kar sakte hain → unique solution.
Agar $k - 4 = 0$ (yaani $k = 4$ ): row padhta hai $0 = 1$ → contradiction → koi solution nahi.

Answer: system ka koi solution nahi exactly jab $k = 4$ .

L5 — Mastery

Exercise 5.1

Elimination ke dauran tum use kiye gaye multipliers record karte ho. Matrix ke liye $A = [2643],$ $U$ paane ke liye forward elimination run karo, multiplier ko matrix $L$ mein collect karo, aur verify karo $A = LU$ (LU Decomposition idea).

Recall Solution

Forward elimination. Column 1, pivot $2$ . $m_{21} = 6/2 = 3$ : $R_{2} \to R_{2} - 3 R_{1}$ . Row 2: $(6 - 6, 3 - 12) = (0, - 9)$ . $U = [20 4 - 9] .$ $L$ build karo. $L$ lower-triangular hai jisme diagonal par $1$ s hain aur multiplier $m_{21} = 3$ position $(2, 1)$ par placed hai (exactly woh spot jo humne clear kiya): $L = [1301] .$ $LU = A$ verify karo. $LU = [1301] [20 4 - 9] = [1 \cdot 2 + 0 \cdot 0 3 \cdot 2 + 1 \cdot 0 1 \cdot 4 + 0 \cdot (- 9) 3 \cdot 4 + 1 \cdot (- 9)] = [2643] = A . ✓$ KYU yeh kaam karta hai: har elimination step " $R_{2} \to R_{2} - 3 R_{1}$ " undo hoti hai " $R_{2} \to R_{2} + 3 R_{1}$ " se, jo exactly wahi hai jo $L$ se multiply karna karta hai. Multiplier $3$ store karna hi $U$ se $A$ rebuild karne ki recipe record karna hai.

Exercise 5.2

Forward elimination use karke $A = 1232583814$ ka Determinant compute karo. (Fact jo tum use kar sakte ho: upper-triangular matrix ka determinant diagonal ka product hota hai, aur replacement operation $R_{i} \to R_{i} - m R_{j}$ determinant nahi badalta.)

Recall Solution

Column 1, pivot $1$ .

$m_{21} = 2$ : $R_{2} \to R_{2} - 2 R_{1} = (0, 1, 2)$ .
$m_{31} = 3$ : $R_{3} \to R_{3} - 3 R_{1} = (0, 2, 5)$ . $100212325$ Column 2, pivot $1$ .
$m_{32} = 2$ : $R_{3} \to R_{3} - 2 R_{2} = (0, 0, 1)$ . $U = 100210321$ Determinant. Koi row swaps use nahi kiye gaye (har step ek replacement tha, jo $det$ unchanged rakhta hai), toh $det A = det U = 1 \cdot 1 \cdot 1 = 1.$ Answer: $det A = 1$ . Sign ke baare mein note: agar hum ROWS swap karte, toh har swap determinant ka sign flip karta — toh rule hai $det A = (- 1)^{# swaps} \times (product of pivots)$ .

Exercise 5.3

Ek student claim karta hai: "Kisi bhi $3 \times 3$ system par forward elimination ko exactly 3 multipliers chahiye hote hain." Ek aisa system do jisme kam ki zarurat ho, aur explain karo kyun.

Recall Solution

Counterexample. Ek aisi matrix lo jo pehle se zeros wahan rakhe jahan hum eliminate karte: $A = 100240356 .$ Yeh pehle se upper-triangular hai. Har pivot ke neeche entries already $0$ hain, toh har multiplier $m_{ik} = 0/ a_{k k} = 0$ hoga — matlab koi actual elimination nahi hoti. Zero multipliers ki zarurat hai. General principle: nonzero eliminations ki count is baat par depend karti hai ki kitni below-pivot entries pehle se zero hain. "3" ek full $3 \times 3$ ke liye maximum hai (positions $(2, 1), (3, 1), (3, 2)$ ), guarantee nahi. Pivot ke neeche koi bhi pre-existing zero ek step bacha leta hai. Answer: upar wali diagonal/triangular system ko 0 multipliers chahiye; "hamesha 3" ka claim galat hai.

Connections

LU Decomposition — Exercise 5.1 seed hai: stored multipliers $L$ ban jaate hain.
Row Echelon Form / Reduced Row Echelon Form — woh staircase jiske toward yeh exercises build karte hain.
Pivoting and Numerical Stability — Exercise 4.1 ka swap rule, rigorously.
Rank of a Matrix — Exercise 3.1 mein pivots count karo (two pivots → rank 2).
Determinant — Exercise 5.2 ka product-of-pivots trick.
Solving Linear Systems — Consistency — L3 ke unique/none/infinite verdicts.