Rank of a matrix and echelon form
Rank of a matrix, row/column operations, echelon forms (REF/RREF), minors, pivot positions, Rouché–Capelli consistency, and algorithms to compute rank.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Engineers express many real-world problems as systems of linear equations: circuit analysis, statics, control systems, signal processing, and data fitting. The rank of a matrix tells you if a system is solvable, how many independent equations or variables there are, and whether a solution is unique. Echelon forms give a reliable, step-by-step method to compute rank and solve systems.
Key ideas
- Row (column) space: The set of all linear combinations of the rows (columns) of a matrix, considered as vectors in ℝ^n (ℝ^m). It is a subspace.
- Linear independence: A set of vectors is linearly independent if no nontrivial linear combination of them is zero; that is, c₁v₁+⋯+c_kv_k = 0 implies all c_i = 0.
- Rank of a matrix: The rank of A, denoted rank(A), is the maximum number of linearly independent rows (or columns) of A. Equivalent definition: Rank is the dimension of the row space (which equals the dimension of the column space). Also equivalently, for finite matrices, rank is the largest order r of any non-zero minor (determinant of an r×r submatrix) of A.
- Elementary row operations (EROs): (1) Swap two rows, (2) Multiply a row by a non-zero scalar, (3) Add a multiple of one row to another. These operations are reversible and do not change the row space dimension; hence they do not change rank.
- Row echelon form (REF): A matrix is in REF if (i) all non-zero rows are above any all-zero rows, (ii) the leading non-zero entry (pivot) of each non-zero row is to the right of the leading entry of the row above, and (iii) all entries below a pivot are zero. REF is not unique.
- Reduced row echelon form (RREF): An REF that further satisfies: (iv) each pivot is 1, (v) each pivot is the only non-zero entry in its column (zeros above and below). RREF is unique for each matrix.
- Pivot: In REF/RREF, the first non-zero entry in a non-zero row (in RREF, it is 1). The number of pivots equals rank(A).
- Full rank: A has full row rank if rank(A) = m and full column rank if rank(A) = n.
- Basis facts: The non-zero rows of RREF(A) form a basis for the row space; the pivot columns of the original matrix A form a basis for the column space.
- Nullity: The dimension of the solution space of A x = 0 (the null space). For A ∈ ℝ^{m×n}, rank-nullity theorem states: rank(A) + nullity(A) = n.
- Consistency of linear system: For A x = b, the system is consistent (has at least one solution) if and only if rank(A) = rank([A|b]) (Rouché–Capelli theorem). If consistent and rank(A) = n, the solution is unique; if consistent and rank(A) < n, there are infinitely many solutions with n − rank(A) free variables.
Exact statements commonly required in exams:
Theorem (Row rank equals column rank): For any matrix A ∈ ℝ^{m×n}, the maximum number of linearly independent rows equals the maximum number of linearly independent columns. This common value is rank(A). Assumptions: Finite matrix over a field (ℝ for engineering). Sketch proof idea: Using EROs, reduce A to REF; EROs do not change row rank. In REF, the non-zero rows are linearly independent; their count is the row rank. The pivot columns (in the original matrix) are linearly independent; their count equals the column rank. Hence equal.
Theorem (Invariance of rank under elementary operations): Elementary row operations do not change rank; elementary column operations do not change rank either. Assumptions: Operations over a field with non-zero scalars allowed. Reason: Each ERO corresponds to multiplication by an invertible elementary matrix on the left (or right for column operations). Invertible multiplication does not change the dimension of row/column spaces.
Definition via minors: The rank of A is the largest integer r such that there exists an r×r submatrix with non-zero determinant, and every (r+1)×(r+1) minor has determinant zero. Assumptions: Determinant defined (square submatrices). This definition is equivalent to the linear-independence definition.
Rouché–Capelli theorem: The system A x = b is consistent if and only if rank(A) = rank([A|b]). If consistent, number of free variables is n − rank(A). If rank(A) = n, the solution is unique. Assumptions: A over a field; rank defined via REF or minors.
Rank bounds and product properties: For A ∈ ℝ^{m×n}, 0 ≤ rank(A) ≤ min(m, n). For products, rank(A B) ≤ min(rank(A), rank(B)). If P and Q are invertible (square, appropriate sizes), rank(P A Q) = rank(A).
How to compute rank in practice (algorithmic steps):
- Gaussian elimination to REF:
- Choose left-most non-zero column.
- Swap a non-zero row to the top if necessary.
- Use row replacements to make zeros below the pivot.
- Move to the next row and the next column to the right; repeat until done.
- Count non-zero rows (or pivots). That count is rank(A).
- Gauss–Jordan elimination to RREF adds:
- Scale pivot rows to make pivot 1.
- Zero out entries above each pivot.
- By minors (small matrices): Check any 1×1 minors (non-zero entries) → rank ≥ 1; then check 2×2 minors, etc., stopping when you find the largest order non-zero minor.
What to draw if asked for a diagram: Draw a rectangular grid of boxes representing a matrix. Shade or circle the pivot positions in REF to visually show that all entries below each pivot are zero and that pivot columns step to the right as you move down. Label rows R1, R2, … and indicate EROs (e.g., R2 ← R2 − k·R1) with arrows.
Derivation universities commonly ask: “Show that the number of non-zero rows in REF equals the rank.”
- Start with A and apply EROs to reach an REF U; since EROs are invertible, rank(U) = rank(A).
- In U, each non-zero row has its leading non-zero entry (pivot) in a later column than the row above, and zeros below each pivot.
- Suppose c₁u₁ + ⋯ + c_r u_r = 0 is a linear combination of the r non-zero rows u_i of U. Look at the last pivot column (in row r). Only u_r has a non-zero entry there; hence c_r = 0. Proceed upward by induction to force all c_i = 0. Therefore, the non-zero rows are linearly independent, so row space dimension of U is r. Hence rank(A) = r, the number of pivots (non-zero rows).
Formulas
rank(A) = number of pivots in REF of A
- A: matrix (no units). Applies after any sequence of elementary row operations to reach REF.
rank(A) = dimension of row space of A = dimension of column space of A
- A: matrix (no units). Applies to finite matrices over a field; states equality of row and column rank.
rank(A) = max order r such that there exists an r×r minor of A with non-zero determinant
- A: matrix (no units). Use for small matrices or proofs by minors.
rank(A) + nullity(A) = n
- A ∈ ℝ^{m×n} (no units), n: number of columns (no units). Applies to homogeneous system A x = 0.
System A x = b is consistent ⇔ rank(A) = rank([A|b])
- A: coefficient matrix, b: right-hand side vector (no units), [A|b]: augmented matrix. Applies to linear systems over a field.
If consistent and rank(A) = n then solution is unique; if rank(A) < n then infinitely many solutions
- A ∈ ℝ^{m×n} (no units), n: number of variables. Applies to linear systems A x = b.
0 ≤ rank(A) ≤ min(m, n)
- A ∈ ℝ^{m×n} (no units). Always true.
A ∈ ℝ^{n×n} is invertible ⇔ rank(A) = n ⇔ det(A) ≠ 0
- Square matrices (no units). Links rank, determinant, and invertibility.
rank(A B) ≤ min(rank(A), rank(B))
- A, B: matrices with compatible sizes (no units). Applies to products.
rank(P A Q) = rank(A)
- P, Q: invertible matrices of compatible sizes (no units). Applies to similarity-like transformations with invertible factors.
rank(A^T) = rank(A)
- A: any matrix over a field (no units). Equivalently, row rank equals column rank.
Worked examples
Example 1: Compute rank by REF (Gaussian elimination) Given A = [ [2, 4, 6], [1, 3, 2], [0, 1, -1] ]. Determine rank(A).
Step 1: Write the matrix and start elimination. A = Row1: (2, 4, 6) Row2: (1, 3, 2) Row3: (0, 1, -1)
Step 2: Create a pivot in column 1 at Row1. Swap Row1 and Row2 to reduce fractions. After swap R1 ↔ R2: R1: (1, 3, 2) R2: (2, 4, 6) R3: (0, 1, -1)
Step 3: Zero below pivot in column 1 using R2 ← R2 − 2·R1. R2: (2, 4, 6) − 2·(1, 3, 2) = (0, −2, 2) Matrix now: R1: (1, 3, 2) R2: (0, −2, 2) R3: (0, 1, −1)
Step 4: Next pivot in column 2 at Row2. Make it 1 for clarity: R2 ← (−1/2)·R2 ⇒ R2: (0, 1, −1). Step 5: Zero below pivot in column 2: R3 ← R3 − R2 ⇒ (0, 1, −1) − (0, 1, −1) = (0, 0, 0). Step 6: Zero above pivot (optional for REF, needed for RREF): R1 ← R1 − 3·R2 ⇒ (1, 3, 2) − 3·(0, 1, −1) = (1, 0, 5). REF (also near-RREF) obtained: R1: (1, 0, 5) R2: (0, 1, −1) R3: (0, 0, 0)
Count non-zero rows (pivots): 2. Therefore, by rank(A) = number of pivots in REF of A, the answer is:
Final: rank(A) = 2.
Example 2: Rank and consistency using Rouché–Capelli Given the system of equations: 2x + y − z = 1 x + 3y + 2z = 4 3x + 4y + z = 2 Determine if the system is consistent. If yes, find the solution and rank of the coefficient matrix.
Step 1: Form A and augmented [A|b]. A = [ [2, 1, −1], [1, 3, 2], [3, 4, 1] ], b = [1, 4, 2]^T. [A|b] = (2, 1, −1 | 1) (1, 3, 2 | 4) (3, 4, 1 | 2)
Step 2: Perform EROs to reach REF on [A|b]. Swap R1 ↔ R2 for a leading 1: (1, 3, 2 | 4) (2, 1, −1 | 1) (3, 4, 1 | 2)
Zero below pivot in col 1: R2 ← R2 − 2·R1 ⇒ (0, −5, −5 | −7) R3 ← R3 − 3·R1 ⇒ (0, −5, −5 | −10)
Pivot in col 2 at R2. Make it 1: R2 ← (−1/5)·R2 ⇒ (0, 1, 1 | 7/5) Zero below pivot in col 2: R3 ← R3 − (−5)·R2 = R3 + 5·R2 ⇒ (0, 0, 0 | −10 + 5·(7/5)) = (0, 0, 0 | −10 + 7) = (0, 0, 0 | −3)
Step 3: Interpret the row (0, 0, 0 | −3). This represents 0 = −3, a contradiction. Therefore, rank([A|b]) > rank(A). The system is inconsistent.
Conclusion:
- The system has no solution (inconsistent) because rank(A) ≠ rank([A|b]).
- To find rank(A) alone, ignore the last column and continue REF for A only. The first two rows are not multiples; we already have two pivots (col 1 and col 2), while the third row becomes dependent, so rank(A) = 2.
Example 3: Rank by minors (small matrix) Given B = [ [1, 2, 3], [2, 4, 6], [1, 0, 1] ]. Find rank(B) using minors.
Step 1: Check if det(B) ≠ 0. Compute determinant (expand along row 1): |B| = 1·|4 6; 0 1| − 2·|2 6; 1 1| + 3·|2 4; 1 0| = 1·(4·1 − 6·0) − 2·(2·1 − 6·1) + 3·(2·0 − 4·1) = 4 − 2·(2 − 6) + 3·(0 − 4) = 4 − 2·(−4) − 12 = 4 + 8 − 12 = 0. So det(B) = 0 ⇒ rank(B) < 3.
Step 2: Check 2×2 minors. Consider minor from rows (1,3) and cols (1,3): |1 3; 1 1| = 1·1 − 3·1 = −2 ≠ 0. Therefore, there exists a non-zero 2×2 minor. Thus, rank(B) = 2 (largest order non-zero minor is 2, and 3×3 minors are zero).
Common mistakes
- Stopping elimination too early and miscounting pivots. Only count a row as non-zero if it has at least one non-zero entry after elimination.
- Thinking any non-zero entry is a pivot even if there is a non-zero above it. In REF, a pivot must be the first non-zero entry of its row and have zeros below.
- Assuming REF is unique. Only RREF is unique; REF can differ depending on steps, but rank (pivot count) is invariant.
- Mixing up “rank(A) = number of variables” with “rank(A) = number of equations.” Rank is the number of independent rows/columns, not necessarily equal to m or n.
- Using column operations when solving A x = b without understanding that column operations change the meaning of variables. For solving systems, prefer row operations. Column operations do preserve rank but alter variable relationships.
- In Rouché–Capelli, checking only rank(A) and forgetting to compare with rank([A|b]). You must compare both for consistency.
- In minors method, finding one zero 2×2 minor and concluding rank < 2. You must show all 2×2 minors are zero to conclude rank ≤ 1; a single zero minor is not enough.
For your exam
- Derivations/proofs: Show that the number of non-zero rows in REF equals rank; show EROs do not change rank; prove rank(A B) ≤ min(rank(A), rank(B)). Provide clear steps and reasons for each ERO and each inequality.
- Numericals: Compute the rank of a given matrix by Gaussian elimination; determine consistency and solve A x = b; find rank using minors for 2×2 or 3×3 matrices. Show all steps, indicate each row operation, and box or bold the final rank.
- Algorithmic trace: Perform Gauss–Jordan elimination to RREF and identify pivot columns and free variables. Clearly mark pivots and express the solution vector using parameters for free variables.
- Diagram: If asked, draw a matrix with pivot positions circled in REF, arrows indicating EROs, and labels for rows and columns.
- What full marks answers include: Correct and precise definitions, cleanly written EROs, accurate arithmetic, a final statement tying pivot count to rank, and for systems, a line applying Rouché–Capelli explicitly (e.g., “rank(A) = 2, rank([A|b]) = 3 ⇒ inconsistent”).
Quick check
- Define rank of a matrix and give two equivalent ways to compute it.
- For A ∈ ℝ^{3×4}, what are the possible values of rank(A)? If rank(A) = 2, how many free variables are there in A x = 0?
- The augmented matrix reduces to REF with rows: (1, 0, 2 | 3), (0, 1, −1 | 4), (0, 0, 0 | 0). Is the system consistent? What is rank(A) and how many solutions does A x = b have?
Answers: 1) Rank is the maximum number of linearly independent rows/columns; compute by counting pivots in REF/RREF or by the order of the largest non-zero minor. 2) Possible ranks: 0, 1, 2, 3; nullity = 4 − 2 = 2 free variables. 3) Consistent (no contradictory row); rank(A) = 2; infinitely many solutions (since rank < number of variables = 3).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?