Find which variables are free in underdetermined linear system

user_2047587 0
Viewed 862

I have an underdetermined system of linear equations. This can for example be solved by SimPy, where the solution is then a function of some free variables. What I am looking for is, which are those free variables. This set of variables is not unique but one option is enough. For example

[1  0  1] [x1] = [1]
[0  1  0] [x2] = [1]
          [x3]

Here, x2 is determined by the second equation, and either x1or x3 could be used as a free variable. So for example the set {x1} is a valid solution to my problem

One way of finding this is using SymPy and parsing the solutions to find which variables are used in there. This is rather cumbersome. Is there a nicer way to do this? Preferably without any symbolic computations (returning the index of the free variables).

Here the same question is asked, but not answered, as it turned out the asker wanted to ask something else: How to determine which one is free variable in the result of sympy.linsolve

He just wanted a single solution to the system. I want to know the free variables, and don't even need to know a solution.

sympy scipy linear-algebra numpy python
2 Answers

This is similar to How can I find a basis for the column space of a rectangular matrix? except that you are asking for free variables, which correspond to the columns that remain after we picked a basis for the column space. So, the set difference reduces one problem to the other. Here is an example with a slightly more complicated matrix:

import numpy as np
from scipy.linalg import lu
M = np.array([[1, 1, 0, 1], [0, 0, 1, 0], [0, 0, 7, 0]])
U = lu(M)[2]
basis_columns = {np.flatnonzero(U[i, :])[0] for i in range(U.shape[0])}
free_variables = set(range(U.shape[1])) - basis_columns

Answer: {1, 3}.

Caveat: all this is sensitive to floating point errors, so SymPy could still be preferred if you have exact rational numbers in the input and want to preserve them as such.

Admin1

Not sure this is precise, but I think the free variable is any variable has non-zero coefficient for non-pivotal element in echelon form, and a variable it describes.

user_17583630
Related