0
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ Updated the answer if you have any questions let me know. $\endgroup$
    – Alex D
    Feb 10, 2021 at 22:17
  • $\begingroup$ Hi JAS! Is there any way I can expand my answer to help you better? $\endgroup$
    – Alex D
    Feb 12, 2021 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, 2021 at 6:13

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2021 at 6:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .