Skip to the lesson
FixTheRobot Explore Robotics / Linear Algebra / M3 Linear Systems and Vector Spaces / M3-T8

Linear Algebra · Theory · M3

M3-T8 — Solvability and Underdetermined Systems

The complete answer to A x = b: when a solution exists, how many there are, and what all of them look like.

  • Lesson 8 of 8
  • Module 3: Linear Systems and Vector Spaces
  • Linear systems
  • About 9 minutes to read

This lesson ties the module together. Using rank, the column space and the null space, you can say for any linear system whether it can be solved, whether the answer is unique, and, when it is not, exactly how large the family of answers is and how to choose one sensibly. Redundant robots live in that last case.

Learning objectives

After this lesson, you should be able to:

  • Decide solvability from b ∈ C(A), or from comparing rank(A) with rank([A | b]).
  • Describe the complete solution set as a particular solution plus the null space.
  • Classify systems by rank, m and n: unique, none, or infinitely many, and name an over- and an underdetermined case.
  • Pick the minimum-norm solution of an underdetermined system and explain why it is a sensible default.

Introduction and motivation

A redundant arm can reach the same hand position with many joint configurations; a UAV with more rotors than degrees of freedom can produce the same thrust and torque in many ways; a calibration with too little data cannot decide between many parameter sets. Each time, the question is the same: is the demand achievable, is the answer unique, and if not, which of the many answers should I use? The tools of the module answer it completely.

The intuition

Three things can happen to A x = b. If b is not something the columns can build, there is no solution. If it is, then either exactly one input produces it (no input is hidden from the matrix), or there are infinitely many: one solution plus any amount of anything the matrix ignores.

Interactive figure. One equation in two unknowns is a line of solutions. A point slides along the line. The point closest to the origin, the minimum-norm solution, is marked and the direction of the line is the null space of the equation. This figure needs JavaScript to be interactive.

One equation, two unknowns: the whole line is a family of solutions. Slide along it; the equation never changes because you are moving along the null space. The point closest to the origin is the minimum-norm solution.
The cases of A x = bA table of the cases by rank. When the rank equals the number of unknowns the solution is unique if it exists. When the rank is less than the number of unknowns there are infinitely many solutions if it exists. When b is outside the column space there is no solution.rank rb in column space?solutions of A x = brobot example r = nyesexactly onedetermined pose r = nno (m > n)none: use least squaresnoisy extra sensors r < nyesinfinitely many (a family)redundant arm r < mnononeinfeasible demand general solution = one particular solution + any vector of the null space
The cases of A x = b by rank and by whether b is in the column space.

Geometric and physical interpretation

Geometric view. Solutions of A x = b form a flat set (a point, a line, a plane, …) parallel to the null space and displaced from it by any one solution: slide the null space until it passes through a solution, and you have every solution. Physical view. Each null-space direction is a way of changing the inputs without changing the output: an elbow swing that leaves the hand where it is, two rotors increasing thrust together while cancelling each other's torque. Moving along the family costs nothing in the task and everything in other criteria (energy, joint limits, obstacle clearance).

The mathematics

xp
a particular solution: any one solution of A x = b.
xn
any vector of the null space N(A).
[A | b]
the augmented matrix.

Existence

A x = b is solvable   ⇔   b in C(A)   ⇔   rank [A | b] = rank A

What it means. Appending b to the columns must not increase the rank: if it does, b brings a new independent direction the columns cannot build.

The complete solution

all solutions:   x = xp + xn,    xn in N(A)          unique   ⇔   N(A) = {0}   ⇔   rank = n

What it means. Any solution can be written as one particular solution plus an element of the null space, and every such sum is a solution. The solution is unique exactly when the null space is trivial.

Minimum norm

xmin = Aᵀ (A Aᵀ)⁻¹ b          (rank A = m < n)          = the solution with no null-space component

What it means. Among all solutions, the shortest is the one lying entirely in the row space; it is perpendicular to the null space, so any added null-space part only makes it longer.

Solvable ⇔ b ∈ C(A). Solutions = one particular solution + the null space. Unique ⇔ rank = n. The shortest solution has no null-space part.

Step-by-step derivation: the general solution and the minimum-norm solution

All solutions are a particular solution plus the null space. Suppose x_p solves A x = b.

  1. Adding a null vector keeps it a solution. If x_n ∈ N(A) then A(x_p + x_n) = Ax_p + Ax_n = b + 0 = b.
  2. Every solution is of that form. If x is any solution then A(x − x_p) = b − b = 0, so x − x_p ∈ N(A); define x_n = x − x_p to write x = x_p + x_n.
  3. Therefore the solution set is exactly { x_p + x_n : x_n ∈ N(A) }. Unique means this set has one element, so N(A) = {0}, which by rank-nullity is rank = n.

The minimum-norm solution. Split any solution as x = x_row + x_null with x_row ∈ C(Aᵀ) and x_null ∈ N(A) (the previous lesson). Because the two parts are perpendicular, ‖x‖² = ‖x_row‖² + ‖x_null‖² (Pythagoras). Since A x = A x_row, x_row is itself a solution, independent of which solution we started from. The shortest solution therefore has x_null = 0: it is the unique solution in the row space.

A formula. A row-space vector has the form x = Aᵀ z. Requiring A x = b gives A Aᵀ z = b. When A has full row rank, A Aᵀ is invertible (it is square and positive definite), so z = (A Aᵀ)⁻¹b and x_min = Aᵀ(A Aᵀ)⁻¹b. (For rank-deficient problems the pseudoinverse of Module 6 plays this role.)

A worked example: a three-unknown system with a free direction

Solve x + y + z = 3 and x − y = 1 (two equations, three unknowns; A = [[1, 1, 1], [1, −1, 0]], b = (3, 1)).

  1. Rank. The rows are independent, so r = 2 = m < n = 3; the column space is all of R², so a solution exists for every b, and the null space has dimension n − r = 1.
  2. Solve with a free variable. The second equation gives x = y + 1. The first becomes (y + 1) + y + z = 3, so z = 2 − 2y. With y = t: (x, y, z) = (1 + t, t, 2 − 2t) = (1, 0, 2) + t(1, 1, −2).
  3. Particular solution and null space. x_p = (1, 0, 2) and the null space is spanned by (1, 1, −2): check A(1, 1, −2) = (1 + 1 − 2, 1 − 1) = (0, 0).
  4. Shortest solution. ‖x‖² = (1 + t)² + t² + (2 − 2t)² = 6t² − 6t + 5, smallest at t = 0.5: x_min = (1.5, 0.5, 1) with ‖x_min‖² = 3.5. It is perpendicular to the null space: (1.5, 0.5, 1)·(1, 1, −2) = 1.5 + 0.5 − 2 = 0. ✓
  5. A contradiction case. x + y = 1 and x + y = 2: rank [A] = 1 but rank [A | b] = 2, so there is no solution.

Robotics application

Redundant manipulators. For a 7-joint arm positioning a hand in 3D, the joint velocities solving J q̇ = ẋ form a four-dimensional family. Picking the minimum-norm one is the pseudoinverse solution of Module 8; adding a null-space term achieves a secondary goal (joint-limit avoidance, obstacle clearance).

Over-actuated vehicles. A hexarotor commanded to produce a given thrust and torques has infinitely many rotor-thrust combinations. Control allocation picks the minimum-norm (least-effort) solution, subject to the constraint that no rotor goes negative: the minimum-norm solution of this lesson is the unconstrained version of that problem.

Under-determined calibration. If a calibration data set does not exercise all directions, the unknown parameters have a null space: any change along it explains the data equally well. The minimum-norm answer is a defensible default, but the true fix is to collect data that makes the system determined.

Estimation with too few measurements. A single range measurement to one landmark fixes a robot to a circle, not a point: an underdetermined localisation. The SLAM track discusses how additional measurements remove the freedom, in landmark-based mapping.

Engineering implications and limitations

Practical rules

  • Classify before solving. Compute rank(A), rank([A | b]), m and n (via the SVD in practice) and decide: unique, none or many. The solver should not discover this by failing.
  • For many solutions, state your selection rule. Minimum norm, closest to a preferred posture, or smoothest over time are all valid; “whatever the solver returned” is not.
  • Use the SVD or pseudoinverse for rank-deficient problems. Do not form Aᵀ(AAᵀ)⁻¹ if AAᵀ is nearly singular; the pseudoinverse (Module 6) handles it gracefully.
  • Inconsistent means least squares. When measurements make the system inconsistent, switch to least squares (Module 5) rather than reporting failure.
  • Watch for slow drift along the null space. In a loop that picks a solution each cycle, null-space components can accumulate; add a small restoring term toward a preferred posture.

Limits

A real actuator has limits (saturation, joint ranges). The “infinitely many solutions” of the linear model shrink to a bounded region once limits are added, and the minimum-norm point may violate them. Constrained optimisation takes over from here, but its core is the linear structure of this lesson.

Common misconceptions

“Fewer equations than unknowns means no solution.”

It usually means infinitely many solutions (if consistent). It is the case of more equations than unknowns that tends to produce none.

“The solver returns the solution.”

When there are infinitely many, a solver returns one of them, chosen by its method. Different methods can return different, equally valid, answers.

“The minimum-norm solution is the true solution.”

It is only the shortest. It is the right choice if “least effort” is what you want, and a bad one if some other criterion matters (for instance reaching a physical limit).

“If A x = b has a solution once, it always will.”

Solvability depends on b being in the column space. A different b (a different demand) can be infeasible for the same A.

Engineering takeaways

  1. A x = b is solvable exactly when b is in the column space, equivalently when rank [A | b] = rank A.
  2. All solutions are one particular solution plus any vector of the null space; the solution is unique exactly when the null space is {0}, i.e. rank = n.
  3. More equations than unknowns tends to give no solution; fewer tends to give infinitely many.
  4. The minimum-norm solution has no null-space component: it lies in the row space and equals Aᵀ(AAᵀ)⁻¹b for full row rank.
  5. Redundant arms, over-actuated vehicles and under-determined calibrations all live in the infinitely-many case.

References and further reading

Primary papers and authoritative documentation.

Knowledge check

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

Question 1

For A = [[1, 2], [2, 4]] and b = (3, 6), then b = (3, 7): decide solvability each time and describe the solutions when they exist.

Explanation

The rows are proportional so rank A = 1. For b = (3, 6): rank [A | b] = 1 as well (the second row is twice the first including b), so it is solvable, with infinitely many solutions: x + 2y = 3, i.e. (3, 0) + t(−2, 1). For b = (3, 7): the augmented matrix has rank 2 (the second equation says 2x + 4y = 7 while twice the first gives 6), so there is no solution.

Question 2

A hexarotor has a 4 × 6 allocation matrix A of rank 4 mapping six rotor thrusts to total thrust and three torques. How many free parameters does the set of thrust patterns producing a given demand have, and which pattern is the minimum-norm one?

Explanation

rank 4, n = 6, so the null space has dimension 6 − 4 = 2: two free parameters (two independent ways of changing the thrusts without changing the demand). The minimum-norm pattern is x = Aᵀ(AAᵀ)⁻¹b, the member of the family with no null-space component; it uses the least total thrust squared.

Question 3

Why is the minimum-norm solution perpendicular to the null space, and what does it mean for any other solution?

Explanation

The minimum-norm solution lies entirely in the row space, which is perpendicular to the null space. Any other solution equals it plus a null-space vector n, and by Pythagoras its squared length is ‖xmin‖² + ‖n‖², strictly greater when n ≠ 0. So every other solution is longer; adding null-space motion costs length without changing the output.

What’s next

Module 3 is complete: you can set up, solve and fully describe any linear system. Module 4 adds the geometry of right angles, which is what makes the best approximate answer, when no exact answer exists, so natural.

Practice this lesson

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.

Next lesson

M4-T1 — Orthogonal Vectors

Test orthogonality with the dot product, split a vector into orthogonal parts, and use right angles in robot geometry.

Nothing below is required to finish this lesson.