Underdetermined Linear System General Solution

Specific Domains Numerics
2

So you have Ax=b where A\in \mathbb{R}^{m\times n} with m<n? Then let x_1 be one particular solution, say, found by x1 = A\b. Then, any other value x_1 + x_0 is also a solution if x_0 solves Ax_0=0. All possible vectors x_0 solving Ax_0=0 are linear combinations of basis vectors in the nullspace of A, i.e., x_0 \in {\cal N}(A).
Example:

julia> using LinearAlgebra

julia> A = rand(-9:9,2,3)
2×3 Array{Int64,2}:
 -7  -9  -7
 -8  -8  -1

julia> rank(A)
2

julia> b = [1,2]
2-element Array{Int64,1}:
 1
 2

julia> x1 = A\b
3-element Array{Float64,1}:
 -0.1637895602137279
 -0.10583641594739004
  0.1570078092889437

julia> N = nullspace(A)
3×1 Array{Float64,2}:
 -0.673770210645276
  0.7024412834386926
 -0.22936858234732868

julia> x0 = 0.5*N[:]
3-element Array{Float64,1}:
 -0.336885105322638
  0.3512206417193463
 -0.11468429117366434

julia> A*(x1+x0)
2-element Array{Float64,1}:
 0.9999999999999996
 1.9999999999999971

julia> b
2-element Array{Int64,1}:
 1
 2

So… by doing N = nullspace(A), you find a matrix N containing basis vectors for the nullspace (kernel) of A. Then, with x1 = A\b, x1 is one solution to Ax=b, but x1+N*z is also a solution to Ax+b for any vector z.

6 Likes