Asking for a proof for the number of free variables in a consistent linear system

Given any system of linear equations, we can represent it by an augmented matrix and turn the matrix into (reduced) row echelon form.

Let $$p$$ denote the number of pivots in the (reduced) row echelon form and $$n$$ denote the number of unknowns in the system. If the system is consistent, then there are $$n-p$$ unknowns whose value can be assigned arbitrarily, and in particular, we can always be sure that if column $$i$$ of the (reduced) row echelon matrix does not contain a pivot, then we can choose to assign arbitrary value to the unknown $$x_i$$.

It's quite obvious to "see" that the above statement is true whenever we have an example of (reduced) row echelon matrix representing a consistent linear system. But may I ask how to prove the above statement in a rigorous manner?

• Updated the answer if you have any questions let me know. Feb 10 '21 at 22:17
• Hi JAS! Is there any way I can expand my answer to help you better? Feb 12 '21 at 4:46
• @AlexD Hi Alex, thank you for your reply, sorry I was on something else and just saw your answer. I'll read it now and come back to you if I have any question related. Thanks again :) Feb 12 '21 at 6:13

Suppose you have the $$n$$ by $$n$$ matrix $$A$$, and that you were trying to find a vector $$x$$ such that $$Ax=b,$$ for some vector $$b$$ in $$\mathbb{R}^{n}$$.

Also suppose you were able to find a solution, call it $$x_{p}$$, by putting the augmented matrix $$A|b$$ in reduced row echelon form. This is only one solution. The complete solution $$\hat x$$ is given by $$\hat{x}=x_{p}+x_{n},\tag{\star}$$ where $$x_{n}$$ is ANY vector in the null space of $$A$$.

Remember that the null space is the set of all vectors $$x$$ such that $$Ax=0$$. Then $$\hat{x}$$ is indeed the complete solution since we have \begin{alignat*}{2} A\hat{x}&=A(x_{p}+x_{n})\\ &=Ax_{p}+Ax_{n}\\ &=(b)+(0)\\ &=b. \end{alignat*}

To answer your question: Having $$p$$ column pivots means you have $$p$$ linearly independent column vectors, so the dimension of the column space of the matrix is $$p$$.

The dimension of the null space must then be $$(n-p)$$, so a list of $$(n-p)$$ independent vectors span the null space.

Suppose $$x_{1},x_{2},...,x_{n-p}$$ is such a list of $$(n-p)$$ independent vectors spanning the null space of A. Since the null space is a vector space, it is closed under addition and scalar multiplication. This means that any linear combination of $$x_{1},x_{2},...,x_{n-p}$$ will be in the null space of A. That is to say, the vector $$x_{n}=a_{1}x_{1}+a_{2}x_{2}+...+a_{n-p}x_{n-p}$$ is in the null space, for arbitrary coefficients $$a_{i}$$.

Then the complete solution from $$(\star)$$ becomes \begin{alignat*}{2} \hat{x}&=x_{p}+x_{n}\\ &=x_{p}+(a_{1}x_{1}+a_{2}x_{2}+...+a_{n-p}x_{n-p}), \end{alignat*} where we can pick arbitrary values for $$a_{1},...,a_{n-p}$$. These are the $$(n-p)$$ arbitrary unknowns you mention in your question.

• Thanks Alex, the answer is good by far I can see. The only thing is that I guess I need to recap some linear algebra to see why every solution is included in the form $\hat{x}=x_{p}+x_{n}$ and why the dimension of null space is related to the dimension of the column space by $n-p$. If you could include some hints for them that would be great :) Also, may I ask if similar argument could be used for generalisation to arbitrary field (other than $\mathbb{R}$)? Feb 12 '21 at 6:47