Consider the linear system $Ax=b$ where $$ A = \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \end{bmatrix} . $$
Let us assume that $b$ is in the column space of $A$. By elimination we obtain the $A$ matrix in "echelon" form $$ \text{ef}(A)= \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 0 \end{bmatrix} $$ This tells us that $x_4$ is a free variable. However if we let $x=(x_1, x_3, x_4, x_2)^\top$ and rearrange the columns of $A$ accordingly, now $$ A_2 = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{bmatrix} $$ doing elimination $$ \text{ef}(A_2)= \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} $$ and now $x_2$ is the free variable.
Does that mean that the free variables can be chosen freely? In this case it looks like they can be, but does that always work in general?