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

# Guide on Pivot Positions and Columns in Linear Algebra

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!
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 form 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 matrix:

$$\boldsymbol{A}= \begin{pmatrix} 3&2&4&4\\ 1&2&4&4\\ 1&1&2&2\\ \end{pmatrix}$$

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}$:

\begin{align*} \begin{pmatrix} 3&2&4&4\\ 1&2&4&4\\ 1&1&2&2\\ \end{pmatrix}\sim \begin{pmatrix} 3&2&4&4\\ 0&-4&-8&-8\\ 0&-1&-2&-2\\ \end{pmatrix}\sim \begin{pmatrix} 3&2&4&4\\ 0&1&2&2\\ 0&1&2&2\\ \end{pmatrix}\sim \begin{pmatrix} 3&0&0&0\\ 0&1&2&2\\ 0&0&0&0\\ \end{pmatrix}\sim \begin{pmatrix} 1&0&0&0\\ 0&1&2&2\\ 0&0&0&0\\ \end{pmatrix} \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:

$$\begin{pmatrix} \color{blue}1&0&0&0\\ 0&\color{blue}1&2&2\\ 0&0&0&0\\ \end{pmatrix}$$

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

$$\begin{pmatrix} \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{pmatrix}$$
Example.

## Identifying pivot columns of a reduced row echelon form

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

$$\begin{pmatrix} 1&2&0&3&\color{blue}0\\ 0&0&1&2&\color{blue}0\\ 0&0&0&0&\color{blue}0\\ 0&0&0&0&\color{blue}0\\ \end{pmatrix}$$

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:

$$\begin{pmatrix} 1&0&3&\color{purple}2\\ 0&1&2&\color{purple}2\\ 0&0&0&\color{purple}0\\ \end{pmatrix}$$

What are the basic and free variables? Note that the rightmost column is colored to emphasize that it does not represent the coefficients of the system.

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

$$\begin{equation}\label{eq:ycogAn6MLpKSJSH2QLA} \begin{pmatrix} \color{red}1&\color{blue}0&3&\color{purple}2\\ \color{red}0&\color{blue}1&2&\color{purple}2\\ \color{red}0&\color{blue}0&0&\color{purple}0\\ \end{pmatrix} \end{equation}$$

Writing this out explicitly as a system of linear equations:

$$\begin{cases} x_1+3x_3&=\color{purple}2\\ x_2+2x_3&=\color{purple}2\\ 0&=\color{purple}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:

$$\begin{pmatrix} 1&2&0&3&\color{blue}0\\ 0&0&1&2&\color{blue}0\\ 0&0&0&0&\color{blue}0\\ 0&0&0&0&\color{blue}0\\ \end{pmatrix}$$

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:

$$\boldsymbol{A}=\begin{pmatrix} 2&2&4&\color{purple}4\\ 1&2&1&\color{purple}2\\ \end{pmatrix}$$

What are the free and basic variables?

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

\begin{align*} \begin{pmatrix} 2&2&4&\color{purple}4\\ 1&2&1&\color{purple}2\\ \end{pmatrix}\sim \begin{pmatrix} 1&1&2&\color{purple}2\\ 1&2&1&\color{purple}2\\ \end{pmatrix} \sim \begin{pmatrix} 1&1&2&\color{purple}2\\ 0&-1&1&\color{purple}0\\ \end{pmatrix} \sim \begin{pmatrix} 1&0&3&\color{purple}2\\ 0&-1&1&\color{purple}0\\ \end{pmatrix} \sim \begin{pmatrix} 1&0&3&\color{purple}2\\ 0&1&-1&\color{purple}0\\ \end{pmatrix} \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}$ would look like:

$$\boldsymbol{A}=\begin{pmatrix} 1&*&*&\color{purple}0\\ 0&1&*&\color{purple}0\\ \end{pmatrix}$$

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.

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 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.

If the row echelon form has no rows with all zeros except the rightmost column, then the system has at least one solution. More specifically, if the row echelon form has a row of zeros, then there exist infinitely many solutions.

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:

$$\begin{pmatrix} 2&-3&3&\color{blue}3\\ 0&-3&2&\color{blue}4\\ 0&0&0&\color{blue}2 \end{pmatrix}$$

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=2$. This means that a solution does not exist.

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

$$\begin{pmatrix} 2&-3&3&\color{blue}3\\ 0&-3&2&\color{blue}4\\ 0&0&0&\color{blue}0 \end{pmatrix}$$

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.

Theorem.

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

If the row echelon form of the coefficient matrix contains no rows that are filled with zeros, then the corresponding system of linear equations is consistent, that is, the system 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:

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

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 a 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 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.

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!