Intuition The big pictureA linear system A x = b A\mathbf{x}=\mathbf{b} A x = b single point (or set of points) where all constraints meet. Gaussian elimination is just organized substitution : we peel off variables one at a time by adding scaled copies of equations to each other until the system becomes trivially readable.
WHY it matters for ML: every time you fit least-squares regression, solve normal equations, invert a covariance matrix, or run a Newton step, a linear solve is happening underneath. It is the workhorse of numerical linear algebra.
A collection of m m m n n n a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n = b 1 a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1 a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n = b 1 A x = b A\mathbf{x}=\mathbf{b} A x = b A A A coefficient matrix (m × n m\times n m × n x \mathbf{x} x b \mathbf{b} b
Definition Augmented matrixWe glue b \mathbf{b} b A A A [ A ∣ b ] [\,A\mid \mathbf{b}\,] [ A ∣ b ]
The three elementary row operations (each is reversible, so they never change the solution set):
Swap two rows. (R i ↔ R j R_i \leftrightarrow R_j R i ↔ R j Scale a row by a nonzero constant. (R i → c R i R_i \to cR_i R i → c R i Add a multiple of one row to another. (R i → R i + c R j R_i \to R_i + cR_j R i → R i + c R j
Intuition WHY these preserve solutionsEach operation corresponds to a legal algebraic manipulation of equations : reordering equations, multiplying an equation by a nonzero number, or adding one true equation to another. A number x \mathbf{x} x new solutions appear either. The solution set is invariant.
Gaussian elimination has two phases.
Phase 1 — Forward elimination → row echelon form (REF).
Goal: make everything below each leading entry (pivot) zero, working left to right.
Pick the pivot in column j j j
For every row i i i a i j a j j \dfrac{a_{ij}}{a_{jj}} a j j a ij forces a i j → 0 a_{ij}\to 0 a ij → 0
Phase 2 — Back substitution.
The last equation now has one unknown → solve it. Substitute upward into the previous equation, and repeat.
(Optionally continue elimination upward and scale pivots to 1 → reduced row echelon form (RREF) , the identity-like form where you can read solutions off directly. This is Gauss–Jordan .)
Solve
x + y + z = 6 2 x + 3 y + 7 z = 30 x − y + 2 z = 5 \begin{aligned} x + y + z &= 6\\ 2x + 3y + 7z &= 30\\ x - y + 2z &= 5 \end{aligned} x + y + z 2 x + 3 y + 7 z x − y + 2 z = 6 = 30 = 5
Augmented: [ 1 1 1 6 2 3 7 30 1 − 1 2 5 ] \left[\begin{array}{ccc|c}1&1&1&6\\2&3&7&30\\1&-1&2&5\end{array}\right] 1 2 1 1 3 − 1 1 7 2 6 30 5
Step 1: R 2 → R 2 − 2 R 1 R_2 \to R_2 - 2R_1 R 2 → R 2 − 2 R 1 Why? Multiplier = − 2 / 1 = − 2 =-2/1=-2 = − 2/1 = − 2 2 2 2 1 1 1 → [ 0 , 1 , 5 ∣ 18 ] \to [0,\,1,\,5\mid 18] → [ 0 , 1 , 5 ∣ 18 ]
Step 2: R 3 → R 3 − 1 R 1 R_3 \to R_3 - 1R_1 R 3 → R 3 − 1 R 1 Why? Kills the 1 1 1 → [ 0 , − 2 , 1 ∣ − 1 ] \to [0,\,-2,\,1\mid -1] → [ 0 , − 2 , 1 ∣ − 1 ]
Now: [ 1 1 1 6 0 1 5 18 0 − 2 1 − 1 ] \left[\begin{array}{ccc|c}1&1&1&6\\0&1&5&18\\0&-2&1&-1\end{array}\right] 1 0 0 1 1 − 2 1 5 1 6 18 − 1
Step 3: R 3 → R 3 + 2 R 2 R_3 \to R_3 + 2R_2 R 3 → R 3 + 2 R 2 Why? Pivot in column 2 is now 1 1 1 = − ( − 2 ) / 1 = + 2 =-(-2)/1=+2 = − ( − 2 ) /1 = + 2 − 2 -2 − 2 → [ 0 , 0 , 11 ∣ 35 ] \to [0,\,0,\,11\mid 35] → [ 0 , 0 , 11 ∣ 35 ]
REF: [ 1 1 1 6 0 1 5 18 0 0 11 35 ] \left[\begin{array}{ccc|c}1&1&1&6\\0&1&5&18\\0&0&11&35\end{array}\right] 1 0 0 1 1 0 1 5 11 6 18 35
Back-substitute. Why bottom-up? The last row has only z z z
11 z = 35 ⇒ z = 35 / 11 11z = 35 \Rightarrow z = 35/11 11 z = 35 ⇒ z = 35/11 y + 5 z = 18 ⇒ y = 18 − 175 / 11 = 23 / 11 y + 5z = 18 \Rightarrow y = 18 - 175/11 = 23/11 y + 5 z = 18 ⇒ y = 18 − 175/11 = 23/11 x + y + z = 6 ⇒ x = 6 − 23 / 11 − 35 / 11 = 8 / 11 x + y + z = 6 \Rightarrow x = 6 - 23/11 - 35/11 = 8/11 x + y + z = 6 ⇒ x = 6 − 23/11 − 35/11 = 8/11
Solution: ( 8 11 , 23 11 , 35 11 ) \left(\tfrac{8}{11}, \tfrac{23}{11}, \tfrac{35}{11}\right) ( 11 8 , 11 23 , 11 35 )
x + 2 y + z = 4 2 x + 4 y + 3 z = 9 \begin{aligned} x + 2y + z &= 4\\ 2x + 4y + 3z &= 9 \end{aligned} x + 2 y + z 2 x + 4 y + 3 z = 4 = 9
[ 1 2 1 4 2 4 3 9 ] \left[\begin{array}{ccc|c}1&2&1&4\\2&4&3&9\end{array}\right] [ 1 2 2 4 1 3 4 9 ]
Step 1: R 2 → R 2 − 2 R 1 ⇒ [ 0 , 0 , 1 ∣ 1 ] R_2 \to R_2 - 2R_1 \Rightarrow [0,0,1\mid 1] R 2 → R 2 − 2 R 1 ⇒ [ 0 , 0 , 1 ∣ 1 ] Why? Clears the 2 2 2
REF: [ 1 2 1 4 0 0 1 1 ] \left[\begin{array}{ccc|c}1&2&1&4\\0&0&1&1\end{array}\right] [ 1 0 2 0 1 1 4 1 ]
Column 2 has no pivot → y y y free variable . Set y = t y=t y = t
Row 2: z = 1 z=1 z = 1
Row 1: x = 4 − 2 t − z = 3 − 2 t x = 4 - 2t - z = 3 - 2t x = 4 − 2 t − z = 3 − 2 t
Solution: ( x , y , z ) = ( 3 − 2 t , t , 1 ) (x,y,z) = (3-2t,\ t,\ 1) ( x , y , z ) = ( 3 − 2 t , t , 1 ) t t t WHY infinite? Fewer pivots than unknowns → a direction of freedom.
x + y = 2 x + y = 5 \begin{aligned} x + y &= 2\\ x + y &= 5 \end{aligned} x + y x + y = 2 = 5
R 2 → R 2 − R 1 ⇒ [ 0 , 0 ∣ 3 ] R_2 \to R_2 - R_1 \Rightarrow [0,0\mid 3] R 2 → R 2 − R 1 ⇒ [ 0 , 0 ∣ 3 ] 0 = 3 0 = 3 0 = 3 Contradiction → the system is inconsistent . Two parallel lines never meet.
Recall Reading the outcome from REF
A pivot in every column (of A A A unique solution.
A free column (no pivot) but no contradiction → infinitely many .
A row [ 0 … 0 ∣ c ] [\,0\ \dots\ 0 \mid c\,] [ 0 … 0 ∣ c ] c ≠ 0 c\neq0 c = 0 no solution .
Common mistake Dividing by a zero (or tiny) pivotWhy it feels right: "Just use the top entry of the column as pivot." Why it breaks: if that entry is 0 0 0 − a i j / 0 -a_{ij}/0 − a ij /0 Fix: partial pivoting — swap in the row whose column entry has the largest magnitude before eliminating.
Common mistake Forgetting the RHS when doing row opsWhy it feels right: the "interesting" math is in A A A Why it breaks: the operation is on the equation ; both sides must change. Fix: always operate on the full augmented row [ A ∣ b ] [\,A\mid b\,] [ A ∣ b ]
Common mistake Declaring "no solution" when you only got0 = 0 0=0 0 = 0 Why it feels right: a zero row looks empty/broken. Why it breaks: 0 = 0 0=0 0 = 0 always true (it just means a redundant equation → free variable), whereas 0 = c ≠ 0 0=c\neq0 0 = c = 0 Fix: check the RHS of the zero row.
Recall Feynman: explain to a 12-year-oldImagine 3 friends who each know one clue about a secret number trio. Alone the clues are messy. So you combine clues — "take twice my clue away from yours" — to knock out one unknown at a time. Keep doing this until one clue mentions only one number: solve it. Then walk backwards plugging it in. Gaussian elimination is exactly this "cancel one, then work backwards" trick, done neatly in a grid.
Mnemonic Remember the flow"Pick, Peel, Pop, Push."
Pick a pivot → Peel (clear below it) → Pop to REF (triangular) → Push back up (back-substitute). For safety: Pivot the Biggest (partial pivoting).
Intuition Why we care about∼ 2 3 n 3 \sim\frac{2}{3}n^3 ∼ 3 2 n 3 n × n n\times n n × n 2 3 n 3 \frac{2}{3}n^3 3 2 n 3 b \mathbf{b} b
What are the three elementary row operations? Swap two rows; scale a row by a nonzero constant; add a multiple of one row to another.
Why do elementary row operations not change the solution set? Each corresponds to a reversible legal algebra move on the equations, so no solutions are added or lost.
What is the multiplier used to zero entry a_ij using pivot a_jj? c = -a_ij / a_jj, applied as R_i -> R_i + c·R_j.
In REF, what does a pivot in every column of A mean? The system has a unique solution.
In REF, what does a free column (no pivot, no contradiction) mean? Infinitely many solutions (that variable is free).
A reduced row reads [0 0 ... 0 | c] with c ≠ 0. What does it mean? The system is inconsistent — no solution.
What is partial pivoting and why use it? Swap in the row with the largest-magnitude entry in the pivot column; avoids dividing by zero/tiny pivots and controls numerical error.
Difference between REF and RREF? REF is upper-triangular with zeros below pivots; RREF additionally has pivots equal to 1 and zeros above them (identity-like).
What is the approximate op count of Gaussian elimination on an n×n system? About (2/3)n^3 floating-point operations.
Why do back-substitution from the bottom row? The bottom row of REF has only one unknown, so you can solve it directly and substitute upward.
uses multiplier c = -a_ij/a_jj
Augmented matrix A given b
Elementary row operations
Pivot cancels entries below
ML solves least-squares normal equations
Intuition Hinglish mein samjhoDekho, linear system A x = b A\mathbf{x}=\mathbf{b} A x = b
Ek zaroori cheez: hamesha augmented matrix [ A ∣ b ] [A\mid b] [ A ∣ b ] − a i j / a j j -a_{ij}/a_{jj} − a ij / a j j
Answer teen tarah ka ho sakta hai: agar har column me pivot hai to unique solution; agar koi column bina pivot ke hai (free variable) to infinite solutions; aur agar koi row 0 = c 0 = c 0 = c 0 = 0 0=0 0 = 0
ML me yeh cheez har jagah chhupi hoti hai — least squares regression, covariance matrix invert karna, Newton step — sab ke andar ek linear solve chal raha hota hai. Aur bade systems me tiny pivot se numerical error bhadak jaata hai, isliye "partial pivoting" (sabse bada element ko pivot banao) use karte hain. Mantra: Pick, Peel, Pop, Push.
