Solving equations with more unknowns than equations

Question

I am trying to find the unknowns of several equations but there are more unknowns than the number of equations. The code is something like this:

syms x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 

eqn1 = 0.04*x1 + 0.04*x2 + 0.2*x3 + 0.2*x4 + 2*x5 + 0.2*x6 + 0.2*x7 + 0.04*x8 + 0.04*x9 == 111;
eqn2 = 0.04*x2 + 0.04*x3 + 0.2*x4 + 0.2*x5 + 2*x6 + 0.2*x7 + 0.2*x8 + 0.04*x9 + 0.04*x10 == 73;
eqn3 = 0.04*x3 + 0.04*x4 + 0.2*x5 + 0.2*x6 + 2*x7 + 0.2*x8 + 0.2*x9 + 0.04*x10 + 0.04*x11 == 40;  
eqn4 = 0.04*x4 + 0.04*x5 + 0.2*x6 + 0.2*x7 + 2*x8 + 0.2*x9 + 0.2*x10 + 0.04*x11 + 0.04*x12 == 14;
eqn5 = 0.04*x5 + 0.04*x6 + 0.2*x7 + 0.2*x8 + 2*x9 + 0.2*x10 + 0.2*x11 + 0.04*x12 + 0.04*x13 == 0;
eqn6 = 0.04*x6 + 0.04*x7 + 0.2*x8 + 0.2*x9 + 2*x10 + 0.2*11 + 0.2*x12 + 0.04*x13 + 0.04*x14 == 191;
eqn7 = 0.04*x7 + 0.04*x8 + 0.2*x9 + 0.2*x10 + 2*x11 + 0.2*x12 + 0.2*x13 + 0.04*x14 + 0.04*x15 == 153;
eqn8 = 0.04*x8 + 0.04*x9 + 0.2*x10 + 0.2*x11 + 2*x12 + 0.2*x13 + 0.2*x14 + 0.04*x15 + 0.04*x16 == 362;
eqn9 = 0.04*x9 + 0.04*x10 + 0.2*x11 + 0.2*x12 + 2*x13 + 0.2*x14 + 0.2*x15 + 0.04*x16 + 0.04*x17 == 471;

[A,B] = equationsToMatrix([eqn1, eqn2, eqn3, eqn4, 5, eqn6, eqn7, eqn8, eqn9], [x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17])

X = linsolve(A,B)

However, I get the error messages:

Warning: The system is inconsistent. Solution does not exist. 
In symengine (line 57)
In sym/privBinaryOp (line 903)
In sym/linsolve (line 63)
In solveLinEqn (line 15)
X =

 Inf
 Inf
 .
 .
 .
 Inf

Does it mean that there are infinite number of solutions to the unknowns? And are there any other method to help solve this? Thanks!

Answer 1

If you take a peek at the A matrix right before you call linSolve(A,B) you will notice that it has a row of zeros:

[    0, 1/25, 1/25,  1/5,  1/5,    2,  1/5,  1/5, 1/25, 1/25,    0,    0,    0,    0,    0,    0,    0]
[    0,    0, 1/25, 1/25,  1/5,  1/5,    2,  1/5,  1/5, 1/25, 1/25,    0,    0,    0,    0,    0,    0]
[    0,    0,    0, 1/25, 1/25,  1/5,  1/5,    2,  1/5,  1/5, 1/25, 1/25,    0,    0,    0,    0,    0]
[    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0]
[    0,    0,    0,    0,    0, 1/25, 1/25,  1/5,  1/5,    2,    0,  1/5, 1/25, 1/25,    0,    0,    0]
[    0,    0,    0,    0,    0,    0, 1/25, 1/25,  1/5,  1/5,    2,  1/5,  1/5, 1/25, 1/25,    0,    0]
[    0,    0,    0,    0,    0,    0,    0, 1/25, 1/25,  1/5,  1/5,    2,  1/5,  1/5, 1/25, 1/25,    0]
[    0,    0,    0,    0,    0,    0,    0,    0, 1/25, 1/25,  1/5,  1/5,    2,  1/5,  1/5, 1/25, 1/25]

So what does that mean?
Before we delve into under-determined systems let's go over what solving a set of linear equations entails. The exact solution to a linear system Ax = b requires the A matrix to be square i.e. same number of rows and columns, and invertible. Solving such a system requires x = A-1 * b which is something that any numerical software can crunch with ease.

Given your system is under-determined i.e. more unknowns that equations it produces a matrix where the number of columns in A is bigger than the number of rows thus we can only approximate the solution to such system. An under-determined system has an infinite number of solutions so let x' be a solution to the system Ax' = b now it follows that x' = ATw for some vector w. Then we can express the solution of the system as

AATw = b => w = (AAT)-1b
x' = ATw

AAT is known as the Gramm matrix and as it can be seen above it must be invertible in order for the system to have a solution. Since your A matrix has a row of zeros it follows that the Gramm matrix AAT will also have a row of zeros and therefore it's singular (non invertible):

[ 2604/625,  562/625,  109/125,   32/125, 0,    4/125,   11/625,    2/625,    1/625]
[  562/625, 2604/625,  562/625,  109/125, 0,   27/125,    4/125,   11/625,    2/625]
[  109/125,  562/625, 2604/625,  562/625, 0,   31/125,   27/125,    4/125,   11/625]
[   32/125,  109/125,  562/625, 2604/625, 0,  108/125,   32/125,   27/125,    4/125]
[        0,        0,        0,        0, 0,        0,        0,        0,        0]
[    4/125,   27/125,   31/125,  108/125, 0, 2579/625,  312/625,  104/125,   27/125]
[   11/625,    4/125,   27/125,   32/125, 0,  312/625, 2604/625,  562/625,  109/125]
[    2/625,   11/625,    4/125,   27/125, 0,  104/125,  562/625, 2604/625,  562/625]
[    1/625,    2/625,   11/625,    4/125, 0,   27/125,  109/125,  562/625, 2604/625]

TL;DR; Your Gramm Matrix is not invertible thus the system has no solution (aka as an inconsistent system) and that's why you get the inconsistent system error message.
References:
http://www.math.usm.edu/lambers/mat419/

Answer 2

Any system with more unknowns than equations produces an under-determined system with a (# unknowns - # equation) free variables.

As an example 1 equation and 2 unknowns means there is 1 free variable

y = 5x - 2