2
$\begingroup$

I'm in a situation where a system of equations specifies restrictions for the values of variables, but anything not specified is up to me to decide. Basically, anything unspecified is an axis of freedom.

I'm trying to find a method for understanding what variables are unspecified aka are axes of freedom for me to decide / tweak to my liking. Does anyone know how you would do that?

As an example, say I have a system of equations that have fewer equations than unknowns, like this:

$ A=3\\ 0.5*B+0.5*C=2\\ D=5 $

I'm guessing this might have something to do with viewing the equations in matrix form, so doing that with those equations looks like this:

$ \begin{bmatrix} 1 & 0 & 0 & 0 & 3 \\ 0 & 0.5 & 0.5 & 0 & 2 \\ 0 & 0 & 0 & 1 & 5 \end{bmatrix} $

Logically I can deduce that either $B$ or $C$ is up to me, but that if I decide the value of one of them, the other one becomes fully specified.

It gets more complex when there are more equations or more variables though:

$ A+B=5\\ B+C=4\\ C+D=8 $

In matrix form it looks like this:

$ \begin{bmatrix} 1 & 1 & 0 & 0 & 5\\ 0 & 1 & 1 & 0 & 4\\ 0 & 0 & 1 & 1 & 8\\ \end{bmatrix} $

My intuition says that $A$ and $D$ are axes of freedom but I'm not positive that I couldn't choose other variables instead.

Is there some formal way to describe the axes of freedom in an underspecified set of equations like these?

Thanks!

$\endgroup$
1
  • $\begingroup$ Apparently this has something to do with finding the kernel of the matrix, which can also be seen as having to do with eigenvectors and eigenvalues. $\endgroup$
    – Alan Wolfe
    Apr 6, 2017 at 16:07

1 Answer 1

1
$\begingroup$

The kernel (nullspace) will indeed clarify which variables are underspecified.

I will use your examples to demonstrate.

You can represent a linear system of equations as the matrix equation A x = b, where x is the vector of variables, A is the linear coefficient matrix, and b is the vector of constant offsets.

For your first example:

A1 = $\left[\begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 0.5 & 0.5 & 0\\ 0 & 0 & 0 & 1 \end{array}\right]$

x1 = [A, B, C, D]

b1 = [3, 2, 5]

For your second example:

A2 = $\left[\begin{array}{cccc} 1 & 1 & 0 & 0\\ 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 1 \end{array}\right]$

x2 = [A, B, C, D]

b2 = [5, 4, 8]

For underdetermined systems the nullspace of the coefficient matrix will be non-trivial (i.e., not the zero matrix). Any linear algebra library or software package should be able to calculate the nullspace of a matrix, including numpy, MATLAB and Julia.

So calculating the nullspace matrix for the first coefficient matrix:

nullspace(A1) = [0, 0.707107, -0.707107, 0]

Variables whose nullspace coefficients are non-zero are underdetermined, while those with zero coefficients are determined. In this case B and C are underdetermined, as expected.

Repeat for the second coefficient matrix:

nullspace(A2) = [-0.5, 0.5, -0.5, 0.5]

Hopefully you can now see that all variables are underdetermined in this case.

Once you have any solution for x, all other solutions can be created using the nullspace vector N via x + c N for any arbitrary constant c. You could solve for x using least squares (see link below). Otherwise if you have N linearly independent equations containing M underdefined variables then you can arbitrarily assign values to M - N variables and solve for the rest using any of the usual linear algebra solvers.

  • A related StackOverflow answer gives an intuitive explanation of nullspace along with the suggestion of using least squares to obtain an initial solution.
  • For an alternative explanation and an example in MATLAB, see this.
  • For more on the kernel (nullspace), see Wikipedia.
$\endgroup$
1
  • $\begingroup$ I likely made mistakes in this post, but I am out of time. Will return later. $\endgroup$ Apr 6, 2017 at 22:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .