search
Search
Unlock 100+ guides
search toc
close
account_circle
Profile
exit_to_app
Sign out
search
keyboard_voice
close
Searching Tips
Search for a recipe:
"Creating a table in MySQL"
Search for an API documentation: "@append"
Search for code: "!dataframe"
Apply a tag filter: "#python"
Useful Shortcuts
/ to open search panel
Esc to close search panel
to navigate between search results
d to clear all current filters
Enter to expand content preview Doc Search Code Search Beta SORRY NOTHING FOUND!
mic
Start speaking... Voice search is only supported in Safari and Chrome.
Shrink
Navigate to

# Relationship Between Pivots and Linear Dependence

schedule Aug 12, 2023
Last updated
local_offer
Linear Algebra
Tags
mode_heat
Master the mathematics behind data science with 100+ top-tier guides
Start your free 7-days trial now!
Theorem.

# Pivot columns are linearly independent

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

$$\begin{pmatrix} 1&*&0&*&*\\ 0&0&1&*&*\\ 0&0&0&0&0\\ 0&0&0&0&0\\ \end{pmatrix}$$

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.

Theorem.

# Non-pivot columns can be expressed as a linear combination of pivot columns

The columns of a matrix $\boldsymbol{A}$ corresponding to the non-pivot columns can be expressed as a linear combination of the columns of $\boldsymbol{A}$ corresponding to the pivot columns.

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

$$\begin{equation}\label{eq:YPqbuUPalPbDD76jSDV} \mathrm{rref}(\boldsymbol{A})=\begin{pmatrix} 1&*&0&*&*\\ 0&0&1&*&*\\ 0&0&0&0&0\\ 0&0&0&0&0\\ \end{pmatrix} \end{equation}$$

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:

\begin{align*} x_1\boldsymbol{a}_1+x_2\boldsymbol{a}_2+x_3\boldsymbol{a}_3 +x_4\boldsymbol{a}_4+x_5\boldsymbol{a}_5&=0\\ x_1\boldsymbol{b}_1+x_2\boldsymbol{b}_2+x_3\boldsymbol{b}_3 +x_4\boldsymbol{b}_4+x_5\boldsymbol{b}_5&=0 \end{align*}

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:

\begin{align*} \boldsymbol{a}_1x_1+\boldsymbol{a}_2+\boldsymbol{a}_3x_3 &=\boldsymbol{0}\\ \boldsymbol{a}_2 &=-\boldsymbol{a}_1x_1-\boldsymbol{a}_3x_3\\ \end{align*}

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.

Theorem.

# Columns corresponding to linearly independent columns in reduced row echelon are also linearly independent

Columns in matrix $\boldsymbol{A}$ that correspond to the linearly independent columns in the reduced row echelon form of $\boldsymbol{A}$ are also linearly independent.

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

$$\begin{equation}\label{eq:YY8D78LuHFJ5DEnOhKc} \begin{pmatrix} 1&*&0&*\\ 0&0&1&*\\ 0&0&0&0\\ 0&0&0&0\\ \end{pmatrix} \end{equation}$$

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:

$$\begin{equation}\label{eq:gFM9eVdtjDP6B3Gb7HG} x_1\boldsymbol{p}_1+x_3\boldsymbol{p}_3=\boldsymbol{0} \end{equation}$$

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:

$$\begin{equation}\label{eq:M58BPqGPa49wqmfl1pu} x_1\boldsymbol{a}_1+ x_2\boldsymbol{a}_2+ x_3\boldsymbol{a}_3+ x_4\boldsymbol{a}_4 =\boldsymbol{0} \end{equation}$$

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:

$$\begin{equation}\label{eq:i0ju1BhVl3xskDbSKCy} x_1\boldsymbol{a}_1+x_3\boldsymbol{a}_3=\boldsymbol{0} \end{equation}$$

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.

Theorem.

# Columns corresponding to pivot columns are linearly independent

Let matrix $\mathrm{rref}(\boldsymbol{A})$ be the reduced row echelon form of matrix $\boldsymbol{A}$. The columns in $\boldsymbol{A}$ corresponding to the pivot columns in $\mathrm{rref}(\boldsymbol{A})$ are linearly independent.

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.

Theorem.

# Columns that correspond to basic variables are linearly independent

The columns that correspond to basic variableslink are linearly independent.

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.

thumb_up
thumb_down
Comment
Citation
Ask a question or leave a feedback...
thumb_up
0
thumb_down
0
chat_bubble_outline
0
settings
Enjoy our search
Hit / to insta-search docs and recipes!