Solving linear systems (Gaussian elimination)

1.1.12 · AI-ML › Linear Algebra Essentials

WHAT hai ek linear system?

Teen elementary row operations (har ek reversible hai, isliye yeh solution set ko kabhi change nahi karte):

Swap do rows. ( $R_{i} \leftrightarrow R_{j}$ )
Scale ek row ko ek nonzero constant se. ( $R_{i} \to c R_{i}$ )
Add ek row ka multiple doosri row mein. ( $R_{i} \to R_{i} + c R_{j}$ )

HOW: algorithm (Scratch se Derivation)

Gaussian elimination ke do phases hain.

Phase 1 — Forward elimination → row echelon form (REF). Goal: har leading entry (pivot) ke neeche sab kuch zero banana, left se right kaam karte hue.

Column $j$ mein pivot choose karo (ek nonzero entry).
Uske neeche har row $i$ ke liye, pivot row ka $\frac{a _{ij}}{a _{j j}}$ times subtract karo. Yeh $a_{ij} \to 0$ force karta hai.

Phase 2 — Back substitution. Last equation ab ek unknown ke saath hai → use solve karo. Upar waali equation mein upward substitute karo, aur repeat karo.

(Optionally elimination upar continue karo aur pivots ko 1 tak scale karo → reduced row echelon form (RREF), woh identity-jaisi form jahan se tum solutions directly padh sakte ho. Yeh Gauss–Jordan hai.)

Figure — Solving linear systems (Gaussian elimination)

Worked Example 1 — ek clean $3 \times 3$

Solve karo $x + y + z 2 x + 3 y + 7 z x - y + 2 z = 6 = 30 = 5$

Augmented: $121 13 - 1 1726305$

Step 1: $R_{2} \to R_{2} - 2 R_{1}$ . Kyun? Multiplier $= - 2/1 = - 2$ pivot $1$ ke neeche ke $2$ ko kill karta hai. $\to [0, 1, 5 ∣ 18]$

Step 2: $R_{3} \to R_{3} - 1 R_{1}$ . Kyun? Row 3 ke column 1 mein $1$ ko kill karta hai. $\to [0, - 2, 1 ∣ - 1]$

Ab: $100 11 - 2 151 618 - 1$

Step 3: $R_{3} \to R_{3} + 2 R_{2}$ . Kyun? Column 2 mein pivot ab $1$ hai; multiplier $= - (- 2) /1 = + 2$ hai jo $- 2$ ko clear karta hai. $\to [0, 0, 11 ∣ 35]$

REF: $100110151161835$

Back-substitute karo. Kyun bottom-up? Last row mein sirf $z$ hai.

$11 z = 35 \Rightarrow z = 35/11$ .
$y + 5 z = 18 \Rightarrow y = 18 - 175/11 = 23/11$ .
$x + y + z = 6 \Rightarrow x = 6 - 23/11 - 35/11 = 8/11$ .

Solution: $(\frac{8}{11}, \frac{23}{11}, \frac{35}{11})$ . (§VERIFY mein verified.)

Worked Example 2 — infinitely many solutions

$x + 2 y + z 2 x + 4 y + 3 z = 4 = 9$

$[12241349]$

Step 1: $R_{2} \to R_{2} - 2 R_{1} \Rightarrow [0, 0, 1 ∣ 1]$ . Kyun? $2$ ko clear karta hai.

REF: $[10201141]$

Column 2 mein koi pivot nahi → $y$ ek free variable hai. $y = t$ set karo.

Row 2: $z = 1$ .
Row 1: $x = 4 - 2 t - z = 3 - 2 t$ .

Solution: $(x, y, z) = (3 - 2 t, t, 1)$ , har $t$ ke liye ek solution. WHY infinite? Pivots unknowns se kam hain → freedom ki ek direction.

Worked Example 3 — no solution

$x + y x + y = 2 = 5$

$R_{2} \to R_{2} - R_{1} \Rightarrow [0, 0 ∣ 3]$ , yaani $0 = 3$ . Contradiction → system inconsistent hai. Do parallel lines kabhi nahi milti.

Common Mistakes (Steel-manned)

Recall Feynman: 12-saal ke bacche ko samjhao

3 doston ko imagine karo jo ek secret number trio ke baare mein ek ek clue jaante hain. Akele clues messy hain. Toh tum combine karte ho clues — "mere clue ka double apne clue se le lo" — taaki ek ek unknown ko knock out karo. Tab tak karo jab tak ek clue sirf ek number mention na kare: use solve karo. Phir backwards chalo ise plug in karte hue. Gaussian elimination exactly yeh "ek cancel karo, phir backwards kaam karo" trick hai, ek grid mein neat tarike se ki gayi.

Cost & ML relevance

Flashcards

Teen elementary row operations kya hain?

Do rows swap karo; ek row ko nonzero constant se scale karo; ek row ka multiple doosri row mein add karo.

Elementary row operations solution set kyun nahi change karte?

Har ek equations par ek reversible legal algebra move se correspond karta hai, isliye koi solutions add ya lost nahi hote.

Entry a_ij ko pivot a_jj se zero karne ke liye kaun sa multiplier use hota hai?

c = -a_ij / a_jj, apply hota hai R_i -> R_i + c·R_j ke roop mein.

REF mein, A ke har column mein pivot ka kya matlab hai?

System ka ek unique solution hai.

REF mein, free column (koi pivot nahi, koi contradiction nahi) ka kya matlab hai?

Infinitely many solutions (woh variable free hai).

Ek reduced row reads [0 0 ... 0 | c] jahan c ≠ 0. Iska kya matlab hai?

System inconsistent hai — koi solution nahi.

Partial pivoting kya hai aur ise kyun use karte hain?

Pivot column mein sabse bade magnitude wali entry ke saath row swap in karo; zero/tiny pivots se divide hone se bachta hai aur numerical error control karta hai.

REF aur RREF mein difference?

REF upper-triangular hai jisme pivots ke neeche zeros hain; RREF mein additionally pivots 1 ke barabar hain aur unke upar bhi zeros hain (identity-jaisa).

Gaussian elimination ka ek n×n system par approximate op count kya hai?

Lagbhag (2/3)n^3 floating-point operations.

Back-substitution bottom row se kyun karte hain?

REF ki bottom row mein sirf ek unknown hota hai, toh tum ise directly solve kar sakte ho aur upward substitute kar sakte ho.

Connections

Matrices and matrix operations — row ops elementary matrices se left-multiplication hain.
LU decomposition — multipliers record karta hai elimination reuse karne ke liye.
Matrix inverse — $[A ∣ I]$ par Gauss–Jordan $A^{- 1}$ deta hai.
Rank and null space — pivots ki sankhya = rank; free columns null space span karte hain.
Determinants — pivots ka product (swaps se sign ke saath) $det A$ deta hai.
Least squares regression — normal equations $A^{⊤} A x = A^{⊤} b$ is tarah solve hoti hain.