search
Search
Unlock 100+ guides
search toc
close
account_circle
Profile
exit_to_app
Sign out
What does this mean?
Why is this true?
Give me some examples!
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
near_me
Linear Algebra
54 guides
keyboard_arrow_down
check_circle
Mark as learned
thumb_up
0
thumb_down
0
chat_bubble_outline
0
Comment
auto_stories Bi-column layout
settings

Guide on Pivot Positions and Columns in Linear Algebra

schedule Jan 6, 2024
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!
Definition.

Pivot position and pivot column

A pivot position in a matrix $\boldsymbol{A}$ is the location in the matrix with row-leading $1$ in the reduced row echelon formlink of $\boldsymbol{A}$. A pivot column is a column in $\boldsymbol{A}$ that contains the pivot position.

Example.

Determining the pivot positions and columns of a matrix

Consider the following augmented matrix:

$$\boldsymbol{A}= \left(\begin{array}{ccc|c} 3&2&4&4\\ 1&2&4&4\\ 1&1&2&2\\ \end{array}\right)$$

Determine the pivot positions as well as the pivot columns of $\boldsymbol{A}$.

Solution. The first step is to obtain the reduced row echelon form of $\boldsymbol{A}$ like so:

\begin{align*} \left(\begin{array}{ccc|c} 3&2&4&4\\ 1&2&4&4\\ 1&1&2&2\\ \end{array}\right) \sim \left(\begin{array}{ccc|c} 3&2&4&4\\ 0&-4&-8&-8\\ 0&-1&-2&-2\\ \end{array}\right)\sim \left(\begin{array}{ccc|c} 3&2&4&4\\ 0&1&2&2\\ 0&1&2&2\\ \end{array}\right)\sim \left(\begin{array}{ccc|c} 3&0&0&0\\ 0&1&2&2\\ 0&0&0&0\\ \end{array}\right)\sim \left(\begin{array}{ccc|c} 1&0&0&0\\ 0&1&2&2\\ 0&0&0&0\\ \end{array}\right) \end{align*}

The pivot positions are locations with row-leading ones in reduced row echelon form. In this case, the following blue entries are the pivot positions:

$$\left(\begin{array}{ccc|c} \color{blue}1&0&0&0\\ 0&\color{blue}1&2&2\\ 0&0&0&0\\ \end{array}\right)$$

Pivot columns are columns that include the pivot positions. This means that the following red and green columns are the pivot columns:

$$\left(\begin{array}{ccc|c} \color{red}1&\color{green}0&0&0\\ \color{red}0&\color{green}1&2&2\\ \color{red}0&\color{green}0&0&0\\ \end{array}\right)$$
Example.

Identifying pivot columns of a reduced row echelon form

Consider the following reduced row echelon form of an augmented matrix:

$$\left( \begin{array}{cccc|c} 1&2&0&3&0\\ 0&0&1&2&0\\ 0&0&0&0&0\\ 0&0&0&0&0\\ \end{array}\right)$$

Identify the pivot columns.

Solution. The first and third columns of the reduced row echelon form correspond to the pivot columns as they have pivot positions (row-leading ones).

Definition.

Basic and free variables

In the context of linear systems, basic variables are variables that correspond to pivot columns. All other variables are called free variables.

In some textbooks, basic variables are called leading variables.

Example.

Finding basic and free variables (1)

Suppose the row echelon form of some system of linear equations is:

$$\left( \begin{array}{ccc|c} 1&0&3&2\\ 0&1&2&2\\ 0&0&0&0\\ \end{array} \right)$$

What are the basic and free variables?

Solution. Here, the two pivot columns are as follows:

$$$$\label{eq:ycogAn6MLpKSJSH2QLA} \left( \begin{array}{ccc|c} \color{red}1&\color{blue}0&3&2\\ \color{red}0&\color{blue}1&2&2\\ \color{red}0&\color{blue}0&0&0\\ \end{array}\right)$$$$

Writing this out explicitly as a system of linear equations:

$$\begin{cases} x_1+3x_3&=2\\ x_2+2x_3&=2\\ 0&=0 \end{cases}$$

The first and second columns in \eqref{eq:ycogAn6MLpKSJSH2QLA} hold the coefficients of variables $x_1$ and $x_2$ respectively. This means that the basic variables are $x_1$ and $x_2$ because they correspond to the pivot columns.

The other variable $x_3$ is called a free variable. Free variables are described as "free" because we can assign any value to them. Once we do so, the values of the basic variables are automatically determined. For instance, let's say we assign $x_3=1$ in this case. Substituting this into the first linear equation yields:

\begin{align*} x_1+3(1)&=2\\ x_1&=-1 \end{align*}

Similarly, $x_2$ can be computed easily by substituting our free variable $x_3=1$ into the second linear equation:

\begin{align*} x_2+2(1)&=2\\ x_2&=0 \end{align*}

Therefore, one solution to the system is:

\begin{align*} x_1&=-1\\ x_2&=0\\ x_3&=1 \end{align*}

Note that the value for the basic variables will depend on the value we assign to the free variable. For instance, if we had assigned $x_3=2$ instead, we would end up with $x_1=-4$ and $x_2=-2$. This means that if we have free variables, then the solutions to this system will not be unique - there will be infinitely many solutions.

Generally, we let free variables take on some value $t\in\mathbb{R}$ so that we can express basic variables as some function of $t$. In this case, we let $x_3=t$. Substituting this into the second equation gives:

$$x_2+2t=2\;\;\;\;\implies\;\;\;\; x_2=2-2t$$

Similarly, substituting $t$ into the first equation gives:

$$x_1+3t=2\;\;\;\;\implies\;\;\;\; x_1=2-3t$$

Therefore, the solution to the linear system is:

$$\begin{pmatrix} x_1\\x_2\\x_3 \end{pmatrix}= \begin{pmatrix} 2-2t\\2-3t\\t \end{pmatrix}= \begin{pmatrix} -2\\-3\\1 \end{pmatrix}t+ \begin{pmatrix} 2\\2\\0 \end{pmatrix}$$

Plugging in any scalar value for $t$ will give us a particular solution to the system!

Example.

Finding a general solution given an reduced row echelon form

Consider the following reduced row echelon form of an augmented matrix:

$$\left( \begin{array}{cccc|c} 1&2&0&3&0\\ 0&0&1&2&0\\ 0&0&0&0&0\\ 0&0&0&0&0 \end{array} \right)$$

Identify the basic and free variables. Also, find the general solution to the system.

Solution. The first and third columns of the reduced row echelon form correspond to the pivot columns. This means that that $x_1$ and $x_3$ are basic variables while $x_2$ and $x_4$ are free variables.

Let's set $x_2=r$ and $x_4=t$. From the second row, we have that:

$$x_3+2t=0 \;\;\;\implies\;\;\; x_3=-2t$$

From the first row, we have that:

$$x_1+2r+3t=0 \;\;\;\implies\;\;\; x_1=-2r-3t$$

The solution is therefore:

$$\begin{pmatrix}x_1\\x_2\\x_3\\x_4 \end{pmatrix}= \begin{pmatrix} -2r-3t\\r\\-2t\\t \end{pmatrix}= r\begin{pmatrix} -2\\1\\0\\0 \end{pmatrix}- t\begin{pmatrix} -3\\0\\-2\\1 \end{pmatrix}$$
Example.

Finding free and basic variables of a wide augmented matrix

Consider the following augmented matrix:

$$\left(\begin{array}{ccc|c} 2&2&4&4\\ 1&2&1&2\\ \end{array}\right)$$

What are the free and basic variables?

Solution. We first need to convert $\boldsymbol{A}$ into reduced row echelon form:

\begin{align*} \left(\begin{array}{ccc|c} 2&2&4&4\\ 1&2&1&2\\ \end{array}\right)\sim \left(\begin{array}{ccc|c} 1&1&2&2\\ 1&2&1&2\\ \end{array}\right) \sim \left(\begin{array}{ccc|c} 1&1&2&2\\ 0&-1&1&0\\ \end{array}\right) \sim \left(\begin{array}{ccc|c} 1&0&3&2\\ 0&-1&1&0\\ \end{array}\right) \sim \left(\begin{array}{ccc|c} 1&0&3&2\\ 0&1&-1&0\\ \end{array}\right) \end{align*}

Basic variables are variables that correspond to pivot columns. In this case, the first two columns are the pivot columns, which means variables $x_1$ and $x_2$ are basic variables. The remaining variable $x_3$ is a free variable.

Once again, let's make sense of what this means. The corresponding system of linear equations is:

$$\begin{cases} x_1+3x_3&=2\\ x_2-x_3&=0\\ \end{cases}$$

To obtain the general solution to the system, we let our free variable $x_3=t$. Plugging this into the first and second equations gives:

\begin{align*} x_1&=2-3t\\ x_2&=t\\ \end{align*}

Therefore, the general solution is:

$$\begin{pmatrix} x_1\\x_2\\x_3 \end{pmatrix}= \begin{pmatrix} 2-3t\\t\\t \end{pmatrix}= \begin{pmatrix} -3\\1\\1 \end{pmatrix}t+ \begin{pmatrix} 2\\0\\0 \end{pmatrix}$$

Since $t$ can be any scalar, the system has infinitely many solutions.

We will now prove a useful theorem stating that a homogeneous linear system with more unknowns than equations has infinitely many solutions.

Theorem.

A homogeneous linear system with more unknowns than equations has infinitely many solutions

If $\boldsymbol{A}$ is an $m\times{n}$ matrix where $m\lt{n}$, that is, if $\boldsymbol{A}$ has more columns than rows, then the homogeneous linear system $\boldsymbol{Ax}=\boldsymbol{0}$ has infinitely many solutions.

In terms of systems of linear equations, if the system has more variables (or unknowns) than equations, then there exist infinitely many solutions.

Proof. To start, we will consider a $2\times3$ matrix $\boldsymbol{A}$ for simplicity. The row echelon form of $\boldsymbol{A}$ may look like:

$$\boldsymbol{A}= \left(\begin{array}{ccc|c} 1&*&*&0\\ 0&1&*&0\\ \end{array}\right)$$

Where the $*$ represents any number. Since we have two pivot columns, we have $2$ basic variables. The remaining third variable is a free variable. As the examples above have demonstrated, free variables can take on any value, which means that there are infinitely many solutions.

What if we have the following case with $1$ basic variable and $2$ free variables:

$$\boldsymbol{A}= \left(\begin{array}{ccc|c} 1&*&*&0\\ 0&0&0&0\\ \end{array}\right)$$

Again, the existence of at least one free variable guarantees that the system has infinitely many solutions.

To generalize, as long as there are more columns than rows, the system will always have free variables. Whenever there are free variables, the system will have infinitely many solutions. This completes the proof.

Theorem.

Checking for the existence and uniqueness of solutions using row echelon form

If the row echelon form of an augmented matrix has a row with all zeros except the rightmost column, then the system is inconsistent, that is, it has no solutions. In other words, if there is a pivot position in the rightmost column of the augmented matrix, then the system is inconsistent. Here's an example of such a case:

$$\left(\begin{array}{ccc|c} 1&5&2&3\\ 0&1&2&5\\ 0&0&0&5\\ \end{array}\right)$$

If the row echelon form has a row of zeros, then the system is consistent with infinitely many solutions. Here's an example:

$$\left(\begin{array}{ccc|c} 1&5&2&3\\ 0&1&2&5\\ 0&0&0&0\\ \end{array}\right)$$

In all the other cases when the row echelon form, the system is consistent with one unique solution. Here's an example:

$$\left(\begin{array}{ccc|c} 1&5&2&3\\ 0&1&2&5\\ 0&0&1&4\\ \end{array}\right)$$

Discussion and proof. We know that to obtain the solutions of a system of linear equations, we can reformulate the system as $\boldsymbol{Ax}=\boldsymbol{b}$ and then reduce the augmented matrix into the reduced row echelon form.

However, if all we care about is the nature of the solution instead of the actual values of the solution, then reducing the augmented matrix to the row echelon form (instead of the reduced row echelon form) is sufficient.

For instance, consider the following row echelon form:

$$\left(\begin{array}{ccc|c} 1&5&2&3\\ 0&1&2&5\\ 0&0&0&5\\ \end{array}\right)$$

This row echelon form tells us that the corresponding system of linear equations is inconsistent since we have a row corresponding to the equation $0=5$. This means that a solution does not exist.

Let's now consider an echelon form with a row of all zeros:

$$\left(\begin{array}{ccc|c} 1&5&2&3\\ 0&1&2&5\\ 0&0&0&0\\ \end{array}\right)$$

We see that the basic variables are $x_1$ and $x_2$ while the free variable is $x_3$. This means that we have infinitely many solutions due to the presence of the free variable. Again, this echelon form does not allow us to compute the solutions to the system directly but it does give us useful information about the existence as well as the uniqueness of the solutions.

Finally, consider the following case:

$$\left(\begin{array}{ccc|c} 1&5&2&3\\ 0&1&2&5\\ 0&0&1&4\\ \end{array}\right)$$

Here, we have $3$ basic variables and no free variable. This means that no variable is allowed to freely vary and thus giving us an unique solution.

This completes the proof.

Even though we can check for the presence of an unique solution using the row echelon form of the augmented matrix, we can actually look at that of the coefficient matrix instead.

Theorem.

Checking for unique solutions using the echelon form of the coefficient matrix

If the row echelon form of the coefficient matrix does not contains a row filled with zeros, then the corresponding system of linear equations is consistent and has exactly one solution.

Equivalently, if every column of the coefficient matrix contains a pivot position, then the system has an unique solution.

Proof. Consider the following row echelon form of some augmented matrix:

$$\left(\begin{array}{ccc|c} 1&*&*&\color{blue}*\\ 0&1&*&\color{blue}*\\ 0&0&1&\color{blue}* \end{array}\right)$$

The last row corresponds to the linear equation $x_3=\color{blue}*$. Consider the case when this $\color{blue}*$ equals some scalar value, say $5$. Since $x_3=5$, we can substitute this into the second row to get $x_2$. Finally, substituting $x_3$ and $x_2$ into the first row will give us $x_1$. Since we can solve for $x_1$, $x_2$ and $x_3$, we end up with an unique solution.

Note that even if the right-most column of the augmented matrix is all zeros, the system would still have an unique solution, namely $x_1=x_2=x_3=0$. Therefore, regardless of what values the right-most column of the augmented matrix take, we will always get an unique solution. This means that we can just refer to the row echelon form of the coefficient matrix in order to know whether or not the system has an unique solution.

This completes the proof.

Example.

Checking if a system has solutions

Consider the following system of linear equations:

$$\begin{cases} 3x_1+5x_2&=7\\ x_1+3x_2&=4\\ \end{cases}$$

Does this system have a solution?

Solution. To check whether or not a solution exists, we can refer to the echelon form of the coefficient matrix:

$$\begin{pmatrix} 3&5\\1&3\\ \end{pmatrix}\sim \begin{pmatrix} 3&5\\0&-4\\ \end{pmatrix}\sim \begin{pmatrix} 3&5\\0&1\\ \end{pmatrix}$$

Because the echelon form of the coefficient matrix does not contain a row with all zeros, we conclude that the system has an unique solution.

Practice problems

Consider the following system of linear equations:

$$\begin{cases} 2x+4y&=2\\ x+2y&=1\\ \end{cases}$$

Find the following:

• pivot positions.

• pivot columns.

• basic variable.

• free variable.

• a general solution to the system.

• a particular solution to the system.

Show solution

We first write the system of linear equations as an augmented matrix:

$$\left(\begin{array}{cc|c} 2&4&2\\ 1&2&1 \end{array}\right)$$

We then obtain the row-echelon form:

$$\left(\begin{array}{cc|c} 2&4&2\\ 1&2&1 \end{array}\right)\sim \left(\begin{array}{cc|c} 2&4&2\\ 0&0&0 \end{array}\right)$$

The pivot positions are the positions of the row-leading non-zeros indicated below:

$$\left(\begin{array}{cc|c} \color{blue}2&4&2\\ 0&0&0 \end{array}\right)$$

Here, the second row are all zeros and therefore has no pivot positions.

A pivot column is a column that contains a pivot position. In this case, only the first column is a pivot column:

$$\left(\begin{array}{cc|c} \color{green}2&4&2\\ \color{green}0&0&0 \end{array}\right)$$

A basic variable corresponds to a pivot column, which means that $x$ is a basic variable.

All variables that are not a basic variable are called free variables. In this case then, $y$ is a free variable.

To find the general solution to the system, focus on the first row:

$$2x+4y=2$$

Let $y=t$ where $t$ is any scalar value. We now solve for $x$ like so:

\begin{align*} 2x+4t&=2\\ 2x&=2-4t\\ x&=1-2t\\ \end{align*}

Therefore, the general solution to the system is:

\begin{align*} x&=1-2t\\ y&=t \end{align*}

Plugging in any value for $t$ gives us any particular solution. For example, setting $t=1$ gives us the following solution:

\begin{align*} x&=-1\\ y&=1 \end{align*}

Consider the following augmented matrix:

$$\left(\begin{array}{ccc|c} 1&3&5&4\\ 4&2&2&4\\ 2&3&7&3\\ \end{array}\right)$$

Identify the pivot positions and pivot columns.

Show solution

To identify the pivot positions and pivot columns, we must obtain the row-echelon form:

$$\left(\begin{array}{ccc|c} 1&1&1&4\\ 3&1&2&4\\ 2&3&2&3\\ \end{array}\right)\implies \left(\begin{array}{ccc|c} 1&1&1&4\\ 0&2&1&8\\ 0&-1&0&5\\ \end{array}\right)\implies \left(\begin{array}{ccc|c} 1&1&1&4\\ 0&2&1&8\\ 0&0&1&18\\ \end{array}\right)$$

The pivot positions are the positions of the row-leading non-zeros indicated below:

$$\left(\begin{array}{ccc|c} \color{blue}1&1&1&4\\ 0&\color{blue}2&1&8\\ 0&0&\color{blue}1&18\\ \end{array}\right)$$

A pivot column is a column that contains a pivot position. In this case, all three columns are the pivot columns:

$$\left(\begin{array}{ccc|c} \color{green}1&\color{red}1&\color{purple}1&4\\ \color{green}0&\color{red}2&\color{purple}1&8\\ \color{green}0&\color{red}0&\color{purple}1&18\\ \end{array}\right)$$

Consider the following augmented matrix of a homogeneous system of linear equations:

$$\left(\begin{array}{cccc|c} 3&2&3&7&0\\ 1&5&1&2&0\\ 2&1&2&3&0\\ \end{array}\right)$$

Which of the following is true?

The system is inconsistent with no solutions.

The system is consistent with an unique solution.

The system is consistent with infinitely many solutions.

Since there are more columns than rows, the system must be consistent with infinitely many solutions by theorem.

Consider the following augmented matrix:

$$\left(\begin{array}{cccc|c} 3&2&2&3&4\\ 0&1&2&5&8\\ 0&0&0&2&2\\ 0&0&0&0&3\\ \end{array}\right)$$

Which of the following is true?

The system is inconsistent with no solutions.

The system is consistent with an unique solution.

The system is consistent with infinitely many solutions.

Since the last row contains all zeros except the last entry ($0=3$), the system must be inconsistent with no solutions.

Consider the following augmented matrix:

$$\left(\begin{array}{cccc|c} 4&5&3&0&2\\ 0&1&0&5&7\\ 0&0&2&3&2\\ 0&0&0&0&0\\ \end{array}\right)$$

Which of the following is true?

The system is inconsistent with no solutions.

The system is consistent with an unique solution.

The system is consistent with infinitely many solutions.

Since the last row contains all zeros, we have a free variable. By theoremlink, we have that the system is consistent with infinitely many solutions.

Consider the following coefficient matrix of a system of linear equations:

$$\begin{pmatrix} 2&4&1\\ 0&4&5\\ 0&0&3 \end{pmatrix}$$

Which of the following is true?

The system is inconsistent with no solutions.

The system is consistent with an unique solution.

The system is consistent with infinitely many solutions.

By theoremlink, since there are no rows with all zeros in the coefficient matrix, the system is consistent with an unique solution.

Edited by 0 others
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!