Rank and Linear Systems

## What the question is really asking `Ax = b` is a compact way of writing m linear equations in n unknowns. `A` is the m-by-n matrix of coefficients, `x` is the vector of unknowns, and `b` is the vector of right-hand sides. Before you compute anything, an interviewer wants to know whether you understand that such a system has exactly three possible fates: no solution, one solution, or an infinite family of solutions. ## The mechanical procedure: elimination on the augmented matrix Write the coefficients and the right-hand side side by side as the augmented matrix `[A | b]`, then use the three row operations - swap two rows, scale a row by a nonzero number, add a multiple of one row to another - to reach row echelon form. None of these operations changes the solution set, which is the whole reason the method works. In echelon form each nonzero row starts with a leading nonzero entry called a **pivot**, and pivots move strictly rightward as you go down. ## Case 1 - no solution (inconsistent) Take ``` x + y + z = 3 x + 2y + 3z = 6 2x + 3y + 4z = 10 ``` Subtracting row 1 from row 2 gives `(0, 1, 2 | 3)`. Subtracting twice row 1 from row 3 gives `(0, 1, 2 | 4)`. Subtracting the new row 2 from the new row 3 gives `(0, 0, 0 | 1)`, which reads `0x + 0y + 0z = 1`. No numbers can satisfy that, so the original system has no solution. Notice the third equation was, on the left, exactly the sum of the first two - but its right-hand side was not the sum of the first two right-hand sides. The equations disagree about a quantity they jointly determine. ## Case 2 - infinitely many solutions Change the last right-hand side from 10 to 9: ``` x + y + z = 3 x + 2y + 3z = 6 2x + 3y + 4z = 9 ``` The same elimination now ends with `(0, 0, 0 | 0)`, a row that says `0 = 0`. That is not a contradiction, just a redundant equation. Two pivots survive, in the columns for `x` and `y`, and the column for `z` has no pivot - `z` is a **free variable**. Setting `z = t` and back-substituting gives `y = 3 - 2t` and `x = t`, so every vector `(t, 3 - 2t, t)` solves the system. Geometrically the three planes meet in a line rather than a point, and the line is the entire solution set. ## Case 3 - exactly one solution If elimination leaves a pivot in every one of the n columns of `A` and produces no contradictory row, back-substitution pins each unknown to a single value. The three planes meet in a single point. ## The compact statement A system is **consistent** exactly when `b` can be written as a combination of the columns of `A`; equivalently, elimination never produces a zero coefficient row with a nonzero right-hand entry. This consistency criterion is also stated as: the coefficient matrix and the augmented matrix must have the same number of pivots. Given consistency, the solution is unique precisely when the columns of `A` are linearly independent, so that every column earns a pivot and no free variable exists. ## Why exactly two solutions is impossible Suppose `x1` and `x2` both solve `Ax = b` and are different. For any number t, the vector `x1 + t(x2 - x1)` satisfies `A(x1 + t(x2 - x1)) = b + t(b - b) = b`. Every point on the line through the two solutions is also a solution, so as soon as you have two you have infinitely many. This is a favourite quick check in interviews and follows purely from linearity. ## Shape intuition, and its limits More equations than unknowns (`m > n`, overdetermined) usually means no exact solution, and fewer equations than unknowns (`m < n`, underdetermined) usually means infinitely many - but *usually* is not *always*. A tall system whose right-hand side happens to be consistent has an exact solution; a wide system can still be inconsistent if two of its rows contradict each other. Never answer from the shape alone; the pivots decide. ## Where this shows up in practice When a fitted model blows up or a solver reports a singular matrix, it is almost always case 1 or case 2 in disguise: duplicated or derived columns leave an unknown free, or noisy measurements make equations that should agree disagree. Recognising which case you are in tells you whether to add information, remove a redundant unknown, or move from exact solving to a best-fit formulation.