# For a matrix in a row-echelon form, what's a good algorithm to find the free variables?

Suppose I have a reduced row echelon form of a matrix for linear equations. The pivots from the corresponding Gaussian elimination are available. For example, in $$\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{pmatrix} \cdot \begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix} = \begin{pmatrix} a \\ 0 \\ 0 \end{pmatrix}$$ I'd remove $$y_2$$ and $$y_3$$, together with the last 2 rows and columns, to obtain $$y_1 = a$$. This is required for arbitrary such matrices in the row-echelon form.

Q: If the matrix is underdetermined, how to programmatically find the free variables?

(Alternatively, I could seek the dependent variables, like $$y_1$$ in the example.) I could get this information by attempting to solve the equations system. As the solutions are not needed, could another way be more efficient?

• Could you give a precise mathematical definition of what you mean by "free variables"? I would think that you could consider $y_2$ to be free and $y_1,y_3$ to be determined by it; or you could consider $y_3$ to be free and $y_1,y_2$ to be determined by it.
– D.W.
Commented Aug 25 at 17:19
• @D.W. Sorry for the confusion. By "free" I mean variables that can't be uniquely determined, i.e., can have infininitely many values, unlike the unique $y_1 = a$. Does this make sense? Is there a more precise term? Commented Aug 25 at 18:20
• Please edit your question to state that in the question. We prefer that you revise a question so all information needed is contained in the question (so people don't have to read the comments) and so that it reads well for someone who encounters it for the first time.
– D.W.
Commented Aug 26 at 3:22