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?

Thanks in advance!

  • $\begingroup$ Updated the answer if you have any questions let me know. $\endgroup$
    – Alex D
    Feb 10 '21 at 22:17
  • $\begingroup$ Hi JAS! Is there any way I can expand my answer to help you better? $\endgroup$
    – Alex D
    Feb 12 '21 at 4:46
  • $\begingroup$ @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 :) $\endgroup$
    – J-A-S
    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.

  • $\begingroup$ 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}$)? $\endgroup$
    – J-A-S
    Feb 12 '21 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.