Systems of Linear Equations

For Ax = b with A an m×n matrix and augmented matrix [A|b]: (1) If rank(A) ≠ rank([A|b]) → INCONSISTENT, no solution. (2) If rank(A) = rank([A|b]) = n (number of unknowns) → UNIQUE solution. (3) If rank(A) = rank([A|b]) = r < n → INFINITELY many solutions with (n − r) free parameters. Memory aid: 'Ranks differ = none; Ranks equal & = unknowns = one; Ranks equal & < unknowns = infinite.' For homogeneous systems Ax = 0, rank([A|0]) always equals rank(A), so they are always consistent (trivial solution exists); they have non-trivial solutions iff rank(A) < n.

When you stare at a 3×3 system on the GATE paper, you have two clean weapons in your toolkit: Cramer's Rule, which is beautiful but expensive, and Gaussian Elimination, which is what computers actually run. Picking the right one — and knowing the time-complexity facts the examiner loves — is what this lesson is about.

Definition: Cramer's Rule solves a square linear system Ax = b (with det(A) ≠ 0) by the formula x_i = det(A_i) / det(A), where A_i is A with its i-th column replaced by the right-hand side vector b.

Definition: Gaussian Elimination reduces the augmented matrix [A | b] to row echelon form through a sequence of elementary row operations, and then recovers the solution by back-substitution from the last equation upward.

Definition: LU decomposition factorises A = L · U into a lower-triangular L and an upper-triangular U so that one expensive O(n³) factor-once step makes every subsequent solve for a new right-hand side cheap (O(n²)).

Cramer's Rule — when it shines, when it doesn't

Cramer's Rule is the algebraic ideal. For a 2×2 system its formula reads off in seconds; for a 3×3 it is still tractable on paper. It is the right tool when:

• The system is small (n = 2 or 3).
• You need a symbolic answer (parameters in the matrix, not just numbers).
• The question explicitly tests conceptual understanding of determinants.

But Cramer's Rule is computationally awful at scale. Computing det(A) by naive cofactor expansion costs O(n!) operations; even with the recursion arranged carefully you end up at O(n! · n). For an n×n system you must compute n+1 determinants — det(A), det(A_1), …, det(A_n). For a 10×10 system that is already > 30 million operations. For a 100×100 system, more than the number of atoms in your laptop. This is why no production linear-algebra library uses Cramer's Rule.

Crucially, Cramer's Rule fails the moment det(A) = 0. That happens when the rows (or columns) of A are linearly dependent — meaning either the system has no solution (inconsistent) or infinitely many solutions (dependent). Cramer's Rule cannot distinguish these two cases; it just refuses to apply. Gaussian elimination handles both gracefully.

Gaussian Elimination — the workhorse

Gaussian elimination is the algorithm every numerical solver descends from. Its three elementary row operations — swap two rows, scale a row by a non-zero constant, add a multiple of one row to another — preserve the solution set. Apply them systematically to put zeros below the diagonal one column at a time, producing an upper-triangular matrix. Then back-substitute from the bottom.

The arithmetic cost is O(n³) — specifically about (2/3) n³ floating-point operations for the elimination plus n² for the back-substitution. That cubic scaling is the single most important number to memorise from this lesson; GATE has tested it in close to every recent year. Compare 10^3 = 1000 operations for n=10 vs Cramer's 30 million — three orders of magnitude faster, and the gap widens as n grows.

Gaussian elimination also tells you, as a side effect, the rank of A, the dimension of its null space, and whether the system is consistent. It is, in that sense, a diagnostic instrument as much as a solver.

Partial pivoting — the numerical-stability fix

Pure Gaussian elimination has a hidden weakness: if a pivot (the diagonal entry you're using to clear the column) is very small relative to the entries below it, dividing by it amplifies floating-point round-off error catastrophically. The standard fix is partial pivoting: before each elimination step, swap rows so that the largest absolute value in the current column sits on the diagonal. This keeps the multipliers ≤ 1 in magnitude and bounds error growth. GATE often phrases it as: "Gaussian elimination with partial pivoting is numerically stable" — that exact sentence has appeared in past papers.

There is also complete pivoting (search both rows and columns), which gives slightly better stability but doubles the bookkeeping cost and is rarely worth it in practice.

LU decomposition — pay once, solve many

Often a system of the form Ax = b must be solved repeatedly with the same A but different b — for example, in finite-element method simulations or in iterative refinement schemes. Gaussian elimination from scratch would cost O(n³) each time. LU does better.

Factor A = LU once (O(n³)). Then for every new b:

1. Solve Ly = b by forward substitution — O(n²).
2. Solve Ux = y by back substitution — O(n²).

So k right-hand sides cost O(n³ + kn²) instead of O(kn³). For k = 100 and n = 1000, that's a 100× speed-up. This is why LU is the standard interface in BLAS / LAPACK, in MATLAB's backslash operator, and inside SciPy's linalg.solve.

The "what does det(A) tell you" decision table

This is the GATE-favourite synthesis question.

• det(A) ≠ 0 → unique solution exists. Cramer's, Gaussian, LU all work. Matrix is invertible.
• det(A) = 0 and the augmented system is consistent → infinitely many solutions (the null space of A is non-trivial). Cramer's Rule fails.
• det(A) = 0 and the augmented system is inconsistent → no solution. Cramer's Rule fails.

To separate the two zero-det cases, compare rank(A) with rank([A | b]) using row-reduction. If they are equal, solutions exist; if not, the system is inconsistent. (Rouché–Capelli theorem.)

Why it matters: Linear systems are the bedrock of every quantitative GATE topic — from circuit analysis (Kirchhoff's equations) to PageRank (eigenvector iteration) to neural network training (least-squares solves). Knowing which solver fits which situation is part of the GATE CSE problem-solving toolkit, and the time-complexity facts are direct one-mark questions.

Real-world example: A real-time route optimisation engine for Indian Railways must solve large sparse linear systems whenever it recomputes travel times after a track event. The engineers don't run Cramer — they pre-compute an LU factorisation of the sparse Laplacian once a day, then service every incoming query in O(n²) time. That choice is literally the difference between "answer in 80 ms" and "answer in 8 minutes."

Common misconception: "Cramer's Rule is faster because the formula looks short." The formula is short; the evaluation of n+1 determinants is what kills it. Symbolic compactness has nothing to do with algorithmic cost.

Common misconception: "If det(A) = 0, the system has no solution." Half-true at best. det(A) = 0 means not unique — the system may have either no solution or infinitely many. You need the augmented-rank check to decide.

Common misconception: "Gaussian elimination without pivoting is fine in practice." For matrices whose diagonal entries are small, naive elimination can produce wildly wrong answers in floating-point even when det(A) is well away from zero. Always pivot.

Question: For an n×n linear system Ax = b with det(A) ≠ 0, what is the asymptotic worst-case running time of Gaussian elimination with partial pivoting?

Solution:
Step 1: Forward elimination dominates. For column k (1 to n−1), it costs O((n−k)²) work to clear the column below the pivot. Sum from k=1 to n−1 gives Θ(n³).
Step 2: Partial pivoting adds an O(n−k) search per column for the max element — negligible compared to the elimination cost.
Step 3: Back substitution is Θ(n²).
Conclusion: Total cost is Θ(n³) — the textbook answer GATE expects, often phrased as "O(n³)."

"Find the value of the parameter k for which the system has no solution." This single phrase has appeared in GATE CSE Engineering Mathematics nearly every alternate year. The procedure is mechanical once you understand what the determinant is really telling you about the geometry of the three planes.

Definition: A system of linear equations Ax = b has a unique solution if and only if the coefficient matrix A is non-singular, i.e., det(A) ≠ 0.

Definition: When det(A) = 0, the system is either inconsistent (no solution) or has infinitely many solutions, depending on the right-hand side b.

The problem

We are given:

x + y + z = 6
x + 2y + 3z = 10
x + 2y + kz = μ

The question is: for what value(s) of k does this system fail to have a unique solution? And once we know that k, the supplementary question is: for what μ is the system inconsistent versus underdetermined?

Step 1 — Set up the coefficient matrix

The coefficient matrix is

A = [[1, 1, 1], [1, 2, 3], [1, 2, k]]

A unique solution to Ax = b exists if and only if det(A) ≠ 0 (Cramer's Rule, or equivalently A is invertible). So we compute det(A) as a function of k and find where it vanishes.

Step 2 — Evaluate the determinant by row reduction

Direct cofactor expansion works but invites sign errors. A cleaner route: subtract row 1 from rows 2 and 3, which does not change the determinant.

Row 2 ← Row 2 − Row 1: [1−1, 2−1, 3−1] = [0, 1, 2]
Row 3 ← Row 3 − Row 1: [1−1, 2−1, k−1] = [0, 1, k−1]

The matrix becomes upper-triangular-ish:

[[1, 1, 1], [0, 1, 2], [0, 1, k − 1]]

Expanding along column 1 (only one non-zero entry, the leading 1):

det(A) = 1 × det([[1, 2], [1, k − 1]]) = 1 × (1 × (k − 1) − 2 × 1) = k − 3

Step 3 — Locate the critical value

A unique solution exists iff det(A) ≠ 0, i.e., k ≠ 3. So the answer to "for what k is there no unique solution?" is k = 3.

But this is not the full story. At k = 3 the system can be either inconsistent (no solution at all) or consistent and underdetermined (infinitely many solutions). Which one occurs depends on μ.

Step 4 — At k = 3, decide between no solution and infinitely many

Substitute k = 3 and look at the row-reduced augmented matrix [A | b]:

[[1, 1, 1 | 6], [0, 1, 2 | 4], [0, 1, 2 | μ − 6]]

Row 3 minus Row 2 gives [0, 0, 0 | μ − 6 − 4] = [0, 0, 0 | μ − 10].

• If μ − 10 ≠ 0, i.e., μ ≠ 10, the last equation reads 0 = (μ − 10), a contradiction — the system has no solution.
• If μ = 10, the last equation reads 0 = 0, which is a tautology — the system reduces to two independent equations in three unknowns and has infinitely many solutions.

So the complete answer:

• k ≠ 3: unique solution (for every μ)
• k = 3 and μ ≠ 10: no solution
• k = 3 and μ = 10: infinitely many solutions

Geometric intuition

Each linear equation in three variables represents a plane in ℝ³. Three planes can intersect in three qualitatively different ways:

• Unique solution: the three planes meet at a single point. This requires the three normal vectors to be linearly independent — equivalent to det(A) ≠ 0.
• No solution: the three planes form a triangular prism, or two are parallel with the third cutting across. No common point exists.
• Infinitely many solutions: the three planes share a common line (or a common plane), giving a one- or two-parameter family of solutions.

At k = 3, the third plane becomes parallel to a linear combination of the first two. The position of the third plane — controlled by μ — then determines whether it shares the same line as the others (giving infinitely many solutions) or sits offset (no solution).

Why it matters: GATE problems are not asking you to solve the system. They are asking you to recognise the geometry. Once you internalise that det(A) = 0 means "the three planes don't pin down a point", every variant of this question becomes one-line work — compute the determinant, set it to zero.

The general GATE pattern

The template for any "find k such that..." problem is:

1. Identify the coefficient matrix A (it does not include the right-hand side b).
2. Compute det(A) as a polynomial in k. Use row operations to keep the algebra clean.
3. Solve det(A) = 0 for the critical k.
4. At each critical k, examine the rank of A versus the rank of the augmented matrix [A | b]:
   • rank(A) = rank([A | b]) = n ⇒ unique solution
   • rank(A) = rank([A | b]) < n ⇒ infinitely many solutions
   • rank(A) < rank([A | b]) ⇒ no solution (inconsistent)

This is the Rouché–Capelli theorem, and it is the master rule of linear systems.

Worked example variant

Question: For what value of k does the system x + 2y + z = 3, 2x + 3y + 2z = 4, 3x + 5y + 3z = k have infinitely many solutions?

Solution:
Step 1: Coefficient matrix A = [[1, 2, 1], [2, 3, 2], [3, 5, 3]]. Notice row 3 = row 1 + row 2 in the coefficient part.
Step 2: det(A) = 0 automatically (linearly dependent rows). So unique solution never exists.
Step 3: For infinitely many solutions, the augmented matrix must also satisfy row 3 = row 1 + row 2, i.e., k = 3 + 4 = 7.
Conclusion: At k = 7, infinitely many solutions; for any other k, no solution.

Real-world example

Real-world example: In civil-engineering network analysis — load distribution across a truss with redundant members — engineers solve linear systems where some equations are dependent. If the loads are consistent with the dependency, infinitely many internal-force distributions are possible (the structure is statically indeterminate). If the loads violate the dependency, the equations are inconsistent and the assumed structure cannot exist as drawn. The same mathematics — Rouché–Capelli — that picks the right k in a GATE problem decides whether a real bridge is solvable.

Common misconception

Common misconception: Many students compute det([A | b]) (a non-square augmented matrix has no determinant — this alone betrays the error) or think that det(A) = 0 always means "no solution". Neither is right. The determinant is computed for the coefficient matrix only, and det(A) = 0 means "no unique solution" — it leaves open whether there are zero or infinitely many solutions. The distinction is made by comparing ranks.

Cover the answer, recall, then check. 11 cards on solvability and rank — a GATE favourite.

Q1. State the Rouché–Capelli consistency condition for Ax = b.
A1. The system is consistent ⇔ rank(A) = rank([A|b]) (coefficient rank equals augmented rank).

Q2. When does a consistent system have a unique solution vs infinitely many?
A2. With n unknowns: unique ⇔ rank = n; infinitely many ⇔ rank < n (then n − rank free parameters).

Q3. When is Ax = b inconsistent (no solution)?
A3. When rank(A) < rank([A|b]) — a zero row of A pairs with a nonzero entry in b.

Q4. For a homogeneous system Ax = 0, is there always a solution?
A4. Yes — x = 0 always works, so it is never inconsistent. It has a non-trivial solution ⇔ rank(A) < n ⇔ det(A) = 0 (square case).

Q5. How many independent solutions does Ax = 0 have?
A5. Dimension of null space = n − rank(A) (the nullity). This is the number of free variables.

Q6. State Cramer's rule and its limitation.
A6. xᵢ = det(Aᵢ)/det(A), where Aᵢ replaces column i with b. Works only when det(A) ≠ 0 (square, unique-solution systems).

Q7. What does Gaussian elimination reduce the matrix to, and why?
A7. Row-echelon form, from which rank is read off and back-substitution solves the system. It is the general, efficient method.

Q8. A homogeneous square system has only the trivial solution under what condition?
A8. det(A) ≠ 0 (equivalently full rank n).

Q9. For a 3-variable non-homogeneous system with rank(A) = 2 = rank([A|b]), describe the solution set.
A9. Consistent with infinitely many solutions and 3 − 2 = 1 free parameter (a line of solutions).

Q10. Rank–nullity theorem for A (m×n)?
A10. rank(A) + nullity(A) = n (number of columns).

Q11. How do you find the value of a parameter that makes a system have infinitely many / no solutions?
A11. Reduce to echelon form; set the determinant/leading pivot to force rank(A) < n, then compare rank([A|b]) — equal ⇒ infinitely many, unequal ⇒ none.

Solvability of Ax = b is a perennial GATE CSE question, usually phrased as "for what value of the parameter does the system have no / unique / infinitely many solutions?" It is a 1–2 mark near-guaranteed topic, and the same rank logic underlies vector-space and matrix questions.

The controlling idea: rank

Everything reduces to comparing three numbers — rank(A), rank of the augmented matrix [A|b], and n (the number of unknowns).

Situation	Condition
Inconsistent (no solution)	rank(A) < rank([A|b])
Unique solution	rank(A) = rank([A|b]) = n
Infinitely many	rank(A) = rank([A|b]) < n
Free parameters	n − rank(A)

For a homogeneous system Ax = 0, rank([A|b]) always equals rank(A), so it is never inconsistent: x = 0 is guaranteed, and non-trivial solutions exist exactly when rank(A) < n (square: det(A) = 0).

Methods

Gaussian elimination to row-echelon form is the workhorse — read rank, then back-substitute. Cramer's rule (xᵢ = det(Aᵢ)/det(A)) is fine only when det(A) ≠ 0. The rank–nullity theorem, rank + nullity = n, ties solution-space dimension to rank.

Exam Tricks & Tips

• 🎯 Always compare rank(A) with rank([A|b]) first — it decides consistency before any solving.
• 🎯 Non-trivial solution of Ax = 0 ⇔ det(A) = 0 for a square system; set the determinant to zero to find the special parameter value.
• 🎯 Count free variables = n − rank to describe an infinite solution set (line, plane, …).
• 🎯 Parameter problems: reduce to echelon, then split into the case det = 0 vs det ≠ 0.
• 🎯 Cramer only for square, det ≠ 0 — don't apply it to under/over-determined systems.
• ❌ Common mistake: concluding "no solution" whenever det(A) = 0. det = 0 could still be consistent with infinitely many solutions — you must check the augmented rank.

Expected exam pattern

A parameter (k, λ) appears in the matrix or b; you determine which values give unique / infinite / no solution. Or a homogeneous system asks for the condition of a non-trivial solution. NAT variants ask for the number of free parameters.

Quick recap

Consistent ⇔ rank(A)=rank([A|b]). Unique ⇔ that common rank = n. Infinite ⇔ rank < n, with n−rank free variables. Homogeneous never inconsistent; non-trivial ⇔ det(A)=0. Use Gaussian elimination; Cramer only when det ≠ 0.