M3-T4 — Rank and Linear Independence

Learning objectives

After this lesson, you should be able to:

• Define linear independence and test whether given vectors are independent.
• Compute the rank of a matrix by elimination (the number of pivots) and state that row rank equals column rank.
• Explain why the rank is at most min(m, n).
• Interpret rank as the number of independent constraints, measurements or motion directions in robot problems.

Introduction and motivation

A robot with two sensors that both measure the same combination of its state has not learned two things, it has learned one thing twice. A mobile base whose wheels cannot slide sideways has fewer independent motion directions than coordinates. An arm at a stretched-out pose loses one direction of hand motion. In every case the quantity that counts what is really there is the rank, and a drop in rank is how degeneracy shows up.

The intuition

Some vectors are redundant. If v₂ is just twice v₁, then once you have v₁ the second vector adds nothing: every combination of the two is a combination of one. We call such a set dependent. A set is independent when none of its vectors can be built from the others.

The rank of a matrix is the number of independent columns. Elimination counts it for you: each pivot is one genuinely new direction, and a column without a pivot was a combination of earlier ones.

Geometric and physical interpretation

Geometric view. The columns of a matrix span a subspace (a line, a plane, …) and the rank is its dimension. Three independent vectors in 3D span all of space; three vectors in a plane span at most the plane, whatever they are. Physical view. Rank is the number of independent things a mechanism or sensor suite can do or reveal. A differential-drive base has two wheel speeds, hence at most rank 2 for its velocities, even though a planar body has three degrees of freedom (x, y, heading): it cannot move sideways. A set of range measurements from points that all lie on one line from the robot cannot fix a position across that line.

The mathematics

v₁, …, v_k

vectors of the same length.

rank(A)

the rank of A: the number of independent columns, which equals the number of independent rows.

r

shorthand for rank(A).

Linear independence

c1 v1 + c2 v2 + ... + ck vk = 0   only if   c1 = c2 = ... = ck = 0

What it means. The only way to combine the vectors to get zero is to use zero of each. If some non-trivial combination gives zero, one vector can be solved for in terms of the others, so it is redundant.

Rank

rank(A) = number of pivots after elimination = number of independent columns = number of independent rows
rank(A) ≤ min(m, n)

What it means. Each pivot is a new independent direction. A matrix cannot have more independent columns than columns, nor more independent rows than rows, so the rank is at most the smaller dimension. A matrix with rank equal to this bound is called full rank.

A test for square matrices

n vectors in R^n are independent   ⇔   the matrix with them as columns has det ≠ 0   ⇔   rank = n

What it means. For a square matrix, full rank means invertible. This ties the idea to the previous modules: a zero determinant means a non-trivial combination of columns gives zero.

Rank counts the independent columns (equivalently rows). Full rank means no redundancy; a drop in rank means a dependency has appeared.

Step-by-step derivation: rank from elimination, and row rank = column rank

Elimination preserves the dependencies among columns. The relation c₁a₁ + … + cnan = 0 is the same as A c = 0. Row operations replace A by EA with E invertible, and A c = 0 ⇔ EA c = 0, so the solutions c, the dependencies, are exactly the same before and after elimination. Therefore the columns of A are dependent in exactly the same way as the columns of the echelon form U.

1. In the echelon form U, the pivot columns are independent: each has a leading non-zero entry in a row where the earlier pivot columns have zeros, so no combination of earlier ones can produce it.
2. Every non-pivot column of U is a combination of the pivot columns (it can be written using the entries in the pivot rows).
3. By the first statement, the same holds for the corresponding columns of A. So the number of independent columns of A is the number of pivots: rank = number of pivots.
4. Row rank equals column rank. Row operations keep each row a combination of the original rows (and vice versa, because they are invertible), so the row space of A equals that of U. The non-zero rows of U are independent (they form a staircase), and there are as many of them as pivots. So the number of independent rows is also the number of pivots.

The bound. There is at most one pivot per row and at most one pivot per column, so rank ≤ min(m, n).

Independence test for three vectors in 3D. They are independent exactly when the matrix with them as columns has three pivots, equivalently a non-zero determinant (the triple product of the earlier lessons is non-zero: they span a box of positive volume).

A worked example: spotting dependence and computing ranks

• Two vectors. (1, 2) and (2, 4): the second is twice the first, so 2·(1, 2) − 1·(2, 4) = 0 is a non-trivial combination giving zero. Dependent, rank 1.
• A classic 3 × 3. A = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]. Eliminate: R2 − 4R1 = (0, −3, −6), R3 − 7R1 = (0, −6, −12), then R3 − 2R2 = (0, 0, 0). Two pivots, so rank = 2. Indeed column 3 = 2·column 2 − column 1: 2·(2, 5, 8) − (1, 4, 7) = (3, 6, 9).
• Dependent rows. [[1, 2, 3], [2, 4, 6], [1, 0, 1]]: row 2 is twice row 1, so rank 2 (not 3). Its determinant is 0.
• Full rank. [[1, 0, 2], [0, 1, 3], [1, 1, 5]] has determinant 1·(5 − 3) − 0 + 2·(0 − 1) = 0: not full rank (row 3 = row 1 + row 2), so rank 2. Compare [[1, 0, 2], [0, 1, 3], [1, 1, 6]] with determinant 1·(6 − 3) + 2·(0 − 1) = 1: rank 3.
• Bound. A 5 × 3 matrix has rank at most 3, however it was measured.

Robotics application

Observability of sensor suites. If a measurement model is z = H x, the rank of H counts how many independent combinations of the state the sensors reveal. Fewer than the number of state variables means some combinations cannot be recovered at all, whatever the noise level. The UAV track discusses this in sensor-suite design.

Mobility. A differential-drive robot has a velocity space of rank 2 in a 3D pose space: its constraint matrix has rank 1 (no sideways motion), which is the nonholonomic constraint of the Navigation track (see robot motion models).

Manipulator degeneracy. The Jacobian of a planar two-link arm has rank 2 in general and rank 1 when the arm is fully stretched: the hand loses a direction of motion. Module 8 builds on exactly this.

Calibration data. To determine a calibration matrix from point pairs, the data matrix must have full column rank; calibration poses that are all coplanar, or measurements taken along one line, produce a rank-deficient data matrix and an ambiguous calibration.

Engineering implications and limitations

Practical rules

• Rank in floating point is a tolerance question. Real data are never exactly dependent. Use the SVD and count singular values above a tolerance (Module 6), not exact zero pivots.
• Near-dependence is the dangerous case. Two nearly parallel columns give full rank on paper and a hopelessly ill-conditioned problem in practice. Look at the smallest singular value, not just the rank.
• Design for full rank. Place sensors and choose calibration poses so the data matrix has full column rank with margin. A rank-deficient calibration is a design error you can fix before collecting data.
• Monitor rank at run time. Degeneracy detectors in LiDAR odometry check whether the matrix of surface normals still has enough independent directions (for instance a long featureless corridor loses one).
• Do not confuse rank with size. Many rows (many measurements) do not raise the rank if they repeat the same information.

Limits

Rank is a yes/no count; it does not say how far a matrix is from losing rank. For that you need the singular values and the condition number, introduced in Module 6.

Common misconceptions

Engineering takeaways

1. Vectors are independent if the only combination giving zero is the trivial one; otherwise one of them is redundant.
2. The rank is the number of pivots after elimination, which equals the number of independent columns and of independent rows.
3. Rank ≤ min(m, n); a square matrix is invertible exactly when its rank is n.
4. Rank counts independent measurements, constraints or motion directions, so a drop in rank signals degeneracy.
5. With real data, decide rank with singular values and a tolerance, and check conditioning, not only rank.

References and further reading

Primary papers and authoritative documentation.

• MIT 18.06SC Linear Algebra (OCW): lectures on independence, basis and dimension
• 3Blue1Brown, Essence of Linear Algebra: linear independence, span and basis
• Immersive Linear Algebra: chapter 8, Rank
• Michigan ROB 101: Computational Linear Algebra: rank and independence in a computational course

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Rank tells you how many independent directions there are. Next you will meet the two most important sets of vectors attached to a matrix: everything it can produce (the column space) and everything it destroys (the null space).

Related content

Nothing below is required to finish this lesson.

• Before
  M3-T3: LU Decomposition

  Factor a matrix as L times U, reuse the factors for many right-hand sides, and explain why pivoting matters.

• Lab
  M3-L1: Solve a Robot's Constraints

  A mobile base has wheel and speed constraints: solve for the commands, and handle systems with no solution or many.