Matrix Rank, Systems of Equations & LU Decomposition
“Echelon forms, Rouché-Capelli theorem, unique vs infinite solutions, and Doolittle LU factorization.”
1.Matrix Rank, Echelon Forms, and Fundamental Subspaces
§ 1.1.For an m x n matrix A over the real field R:
Row Echelon Form (REF): A matrix is in REF if: (1) all zero rows are at the bottom, (2) the leading entry of each non-zero row is strictly to the right of the leading entry of the row above it.
Rank: The rank of A, denoted rho(A) or Rank(A), is the maximum number of linearly independent row vectors (or column vectors). Rank(A) <= min(m, n).
Rank-Nullity Theorem: For an m x n matrix representing linear transformation T: R^n -> R^m, dim(Col(A)) + dim(Null(A)) = n, i.e., Rank(A) + Nullity(A) = n.
System of Linear Equations AX = B:
- Augmented matrix: [A | B] of dimension m x (n + 1).
- Rouché-Capelli Theorem:
1. Rank(A) < Rank([A | B]): System is INCONSISTENT (0 solutions, hyperplanes never intersect).
2. Rank(A) = Rank([A | B]) = n: System is CONSISTENT with UNIQUE solution.
3. Rank(A) = Rank([A | B]) = r < n: System is CONSISTENT with INFINITELY MANY solutions parameterized by (n - r) free variables.
LU Decomposition: A matrix A can be factored as A = L * U, where L is a unit lower triangular matrix (diagonal elements = 1) and U is an upper triangular matrix.
To solve AX = B using LU: first solve LY = B via forward substitution (O(n^2)), then solve UX = Y via backward substitution (O(n^2)).
A square matrix A admits an LU decomposition without row permutations (Gaussian elimination without partial pivoting) if and only if all of its leading principal submatrices A_k (for k = 1, 2, ..., n-1) are non-singular (Det(A_k) != 0).
2. Worked Problem: Parametric Consistency of Linear Systems
Students frequently confuse the condition for no solution with infinite solutions. For infinite solutions, the entire row in the augmented matrix including RHS must reduce to 0 = 0.
Problem [Original Practice Problem · Modeled on GATE Pattern]:
Consider the linear system:
x + 2y + 3z = 5
x + 3y + 5z = 8
2x + 5y + a*z = b
Determine the values of a and b such that the system has (i) a unique solution, (ii) infinitely many solutions, and (iii) no solution.
Step 1: Write Augmented Matrix [A | B]:
[ 1 2 3 | 5 ]
[ 1 3 5 | 8 ]
[ 2 5 a | b ]
Step 2: Eliminate x from Row 2 and Row 3 (R2 -> R2 - R1, R3 -> R3 - 2*R1):
R2: [ 0 (3-2) (5-3) | (8-5) ] = [ 0 1 2 | 3 ]
R3: [ 0 (5-4) (a-6) | (b-10) ] = [ 0 1 a-6 | b-10 ]
Step 3: Eliminate y from Row 3 (R3 -> R3 - R2):
R3: [ 0 (1-1) (a-6-2) | (b-10-3) ] = [ 0 0 a-8 | b-13 ]
Resulting Upper Triangular Augmented Matrix:
[ 1 2 3 | 5 ]
[ 0 1 2 | 3 ]
[ 0 0 a-8 | b-13 ]
Step 4: Analyze cases based on Rouché-Capelli Theorem:
- Case 1 (Unique Solution): Rank(A) = 3 = n. This requires a - 8 != 0 => a != 8. (b can be any real number).
- Case 2 (Infinitely Many Solutions): Rank(A) = Rank([A|B]) < 3. Both third row entries must vanish: a - 8 = 0 and b - 13 = 0 => a = 8 and b = 13. (Free variable = 3 - 2 = 1).
- Case 3 (No Solution / Inconsistent): Rank(A) = 2 while Rank([A|B]) = 3. This requires a - 8 = 0 and b - 13 != 0 => a = 8 and b != 13 (giving 0*z = non-zero, impossible).
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
Efficient GATE maths coverage with high-yield topic prioritization.
Building geometric intuition for linear algebra before solving problems.