Proof. As an example, suppose the reduced row echelon formlink of a matrix looks like follows:

Here, the first and third columns are pivot columns. The reduced row echelon form guarantees that each of these columns is a standard vector, which makes them linearly independent. Therefore, the pivot columns of the reduced row echelon form of a matrix are linearly independent. This completes the proof.

Proof. Suppose the reduced row echelon form of a matrix $\boldsymbol{A}$ is:

By definitionlink of a reduced row echelon form, we know that the pivot columns correspond to standard vectors. As we can see from the above form, the non-pivot columns (the second, fourth and fifth columns of $\mathrm{rref}(\boldsymbol{A})$ in this case) can be expressed as a linear combination of the standard vectors that appear to their left.

By theoremlink, we know that the solutions of the homogeneous system $\boldsymbol{Ax}=\boldsymbol{0}$ and $\mathrm{rref}(\boldsymbol{A}) \boldsymbol{x}=\boldsymbol{0}$ are the same. In other words, the following linear equations have the same solution set:

Where $\boldsymbol{a}_i$ and $\boldsymbol{b}_i$ represent the $i$-th column of $\boldsymbol{A}$ and $\mathrm{rref}(\boldsymbol{A})$ respectively. In the case of \eqref{eq:YPqbuUPalPbDD76jSDV}, $x_1$ and $x_3$ are basic variableslink while $x_2$, $x_4$ and $x_5$ are free variableslink. To show that the second column of $\boldsymbol{A}$ can be written using the columns of $\boldsymbol{A}$ corresponding to the pivot columns of $\mathrm{rref}(\boldsymbol{A})$, let $x_2=1$ and $x_4=x_5=0$. We are free to do so because they are free variables - we can assign any value to them.

Therefore, we have that:

We have managed to express a column in $\boldsymbol{A}$ corresponding to a non-pivot column in $\mathrm{rref}(\boldsymbol{A})$ using the columns in $\boldsymbol{A}$ corresponding to the pivot columns in $\mathrm{rref}(\boldsymbol{A})$. Similarly, we can repeat this process and express the other columns in $\boldsymbol{A}$ corresponding to the pivot columns in $\mathrm{rref}(\boldsymbol{A})$ as a linear combination of the columns in $\boldsymbol{A}$ corresponding to the pivot columns in $\mathrm{rref}(\boldsymbol{A})$. This completes the proof.

Proof. Suppose the reduced row echelon form of matrix $\boldsymbol{A}$ is:

Now, consider the homogenous system $\boldsymbol{Ax}=\boldsymbol{0}$. Since $x_2$ and $x_4$ are free variableslink, we can assign any value to them - say $x_2=x_4=0$. If we denote the pivot columns of \eqref{eq:YY8D78LuHFJ5DEnOhKc} as $\boldsymbol{p}_1$ and $\boldsymbol{p}_3$, the linear system can be expressed as:

Since $\boldsymbol{p}_1$ and $\boldsymbol{p}_3$ are linearly independent by theoremlink, we know that $x_1=x_3=0$ by definitionlink of linear independence.

Now, if we denote the columns of $\boldsymbol{A}$ as $\boldsymbol{a}_1$, $\boldsymbol{a}_2$, $\boldsymbol{a}_3$ and $\boldsymbol{a}_4$, the linear system $\boldsymbol{Ax}=\boldsymbol{0}$ can be written as:

Recall from theoremlink that if $\mathrm{rref}(\boldsymbol{A})$ is the reduced row echelon form of matrix $\boldsymbol{A}$, then the solutions to the homogeneous linear system $\boldsymbol{Ax}=\boldsymbol{0}$ and $\mathrm{rref}(\boldsymbol{A})\boldsymbol{x}=\boldsymbol{0}$ are the same. Because $x_2$ and $x_4$ are free variables, let's eliminate them by setting $x_2=x_4=0$ in \eqref{eq:M58BPqGPa49wqmfl1pu} to get:

We know that \eqref{eq:gFM9eVdtjDP6B3Gb7HG} and \eqref{eq:i0ju1BhVl3xskDbSKCy} share the same solution set. Since \eqref{eq:gFM9eVdtjDP6B3Gb7HG} holds only if $x_1=x_3=0$, we have that \eqref{eq:i0ju1BhVl3xskDbSKCy} also holds only if $x_1=x_3=0$. By definitionlink then, $\boldsymbol{a}_1$ and $\boldsymbol{a}_3$ must be linearly independent. This completes the proof.

Proof. From theoremlink, we know that the pivot columns of the reduced row echelon form $\mathrm{rref}(\boldsymbol{A})$ of a matrix $\boldsymbol{A}$ are linearly independent. From theoremlink, we know that columns in $\boldsymbol{A}$ corresponding to the linearly independent columns in $\mathrm{rref}(\boldsymbol{A})$ are also linearly independent. This means that the columns in $\boldsymbol{A}$ corresponding to the pivot columns in $\mathrm{rref}(\boldsymbol{A})$ are also linearly independent (since the pivot columns are linearly independent). This completes the proof.

Proof. By definitionlink, basic variables correspond to pivot columns. We know from theoremlink that the columns corresponding to pivot columns are linearly independent. This means that the columns that correspond to basic variables are linearly independent. This completes the proof.