1.3: Rank and Homogenous Systems

Learning Objectives

• Recognize a homogeneous system of linear equations and identify the trivial solution.
• Determine conditions under which a homogeneous system has nontrivial solutions.
• Understand the concept of the rank of a matrix and how it relates to pivot columns.
• Use the rank of a matrix to analyze the number and type of solutions in a homogeneous system.
• Relate the number of equations and variables to the existence of nontrivial solutions.

Up to this point, we have studied general systems of linear equations and seen how pivots determine whether a system has a unique solution, infinitely many solutions, or no solution. In this section, we will focus on a special type of linear system and explore a crucial characteristic of matrices: how their rank, closely related to the positions of pivots, governs the solutions of the system.

Homogeneous Systems

There is a special type of system which requires additional study. This type of system is called a homogeneous system of equations.

Definition: Homogenous System of Linear Equations

A system of equations is called homogeneous if each equation in the system is equal to \(0\). A homogeneous system has the form \[\begin{array}{c} a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}= 0 \\ a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}= 0 \\ \vdots \\ a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}= 0 \end{array}\nonumber \] where \(a_{ij}\) are scalars and \(x_{i}\) are variables.

It is easy to see that this system is consistent, with the origin as a solution. This solution has a special name, which we introduce in the following definition.

Definition \(\PageIndex{1}\): Trivial Solution

Consider the homogeneous system of equations given by \[\begin{array}{c} a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}= 0 \\ a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}= 0 \\ \vdots \\ a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}= 0 \end{array}\nonumber \] Then, \(x_{1} = 0, x_{2} = 0, \cdots, x_{n} =0\) is always a solution to this system. We call this the trivial solution .

If the system has a solution in which not all of the \(x_1, \cdots, x_n\) are equal to zero, then we call this solution nontrivial . The trivial solution does not tell us much about the system, as it says that \(0=0\)! Therefore, when working with homogeneous systems of equations, we want to know when the system has a nontrivial solution.

Suppose we have a homogeneous system of \(m\) equations, using \(n\) variables, and suppose that \(n > m\). In other words, there are more variables than equations. Then, it turns out that this system always has a nontrivial solution. Not only will the system have a nontrivial solution, but it also will have infinitely many solutions. It is also possible, but not required, to have a nontrivial solution if \(n=m\) and \(n<m\).

Consider the following example.

Example \(\PageIndex{1}\): Solutions to a Homogeneous System of Equations

Find the nontrivial solutions to the following homogeneous system of equations \[\begin{array}{c} 2x + y - z = 0 \\ x + 2y - 2z = 0 \end{array}\nonumber \]

Solution

Notice that this system has \(m = 2\) equations and \(n = 3\) variables, so \(n>m\). Therefore by our previous discussion, we expect this system to have infinitely many solutions.

The process we use to find the solutions for a homogeneous system of equations is the same process we used in the previous section. First, we construct the augmented matrix, given by \[\left[ \begin{array}{rrr|r} 2 & 1 & -1 & 0 \\ 1 & 2 & -2 & 0 \end{array} \right]\nonumber \] Then, we carry this matrix to its reduced row-echelon form, given below. \[\left[ \begin{array}{rrr|r} 1 & 0 & 0 & 0 \\ 0 & 1 & -1 & 0 \end{array} \right]\nonumber \] The corresponding system of equations is \[\begin{array}{c} x = 0 \\ y - z =0 \\ \end{array}\nonumber \] Since \(z\) is not restrained by any equation, we know that this variable will become our parameter. Let \(z=t\) where \(t\) is any number. Therefore, our solution has the form \[\begin{array}{c} x = 0 \\ y = z = t \\ z = t \end{array}\nonumber \] Hence this system has infinitely many solutions, with one parameter \(t\).

Suppose we were to write the solution to the previous example in another form. Specifically, \[\begin{array}{c} x = 0 \\ y = 0 + t \\ z = 0 + t \end{array}\nonumber \] can be written as \[\left[ \begin{array}{r} x\\ y\\ z \end{array} \right] = \left[ \begin{array}{r} 0\\ 0\\ 0 \end{array} \right] + t \left[ \begin{array}{r} 0\\ 1\\ 1 \end{array} \right]\nonumber \] Notice that we have constructed a column from the constants in the solution (all equal to \(0\)), as well as a column corresponding to the coefficients on \(t\) in each equation. While we will discuss this form of solution more in further chapters, for now consider the column of coefficients of the parameter \(t\). In this case, this is the column \(\left[ \begin{array}{r} 0\\ 1\\ 1 \end{array} \right]\).

There is a special name for this column, which is basic solution. The basic solutions of a system are columns constructed from the coefficients on parameters in the solution. We often denote basic solutions by \(X_1, X_2\) etc., depending on how many solutions occur. Therefore, Example \(\PageIndex{1}\) has the basic solution \(X_1 = \left[ \begin{array}{r} 0\\ 1\\ 1 \end{array} \right]\).

We explore this further in the following example.

Example \(\PageIndex{2}\): Basic Solutions of a Homogeneous System

Consider the following homogeneous system of equations. \[\begin{array}{c} x + 4y + 3z = 0 \\ 3x + 12y + 9z = 0 \end{array}\nonumber \] Find the basic solutions to this system.

Solution

The augmented matrix of this system and the resulting reduced row-echelon form are \[\left[ \begin{array}{rrr|r} 1 & 4 & 3 & 0 \\ 3 & 12 & 9 & 0 \end{array} \right] \rightarrow \cdots \rightarrow \left[ \begin{array}{rrr|r} 1 & 4 & 3 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right]\nonumber \] When written in equations, this system is given by \[x + 4y +3z=0\nonumber \] Notice that only \(x\) corresponds to a pivot column. In this case, we will have two parameters, one for \(y\) and one for \(z\). Let \(y = s\) and \(z=t\) for any numbers \(s\) and \(t\). Then, our solution becomes \[\begin{array}{c} x = -4s - 3t \\ y = s \\ z = t \end{array}\nonumber \] which can be written as \[\left[ \begin{array}{r} x\\ y\\ z \end{array} \right] = \left[ \begin{array}{r} 0\\ 0\\ 0 \end{array} \right] + s \left[ \begin{array}{r} -4 \\ 1 \\ 0 \end{array} \right] + t \left[ \begin{array}{r} -3 \\ 0 \\ 1 \end{array} \right]\nonumber \] You can see here that we have two columns of coefficients corresponding to parameters, specifically one for \(s\) and one for \(t\). Therefore, this system has two basic solutions! These are \[X_1= \left[ \begin{array}{r} -4 \\ 1 \\ 0 \end{array} \right], X_2 = \left[ \begin{array}{r} -3 \\ 0 \\ 1 \end{array} \right]\nonumber \]

Rank

Another way to gain insight into the solutions of a homogeneous system is to examine the number of pivots in its associated coefficient matrix. This leads us to the concept of rank, which we now define as a measure of the number of linearly independent rows (or columns) in a matrix.

Definition \(\PageIndex{3}\): Rank of a Matrix

Let \(A\) be a matrix and consider any reduced row-echelon form of \(A\). Then, the number \(r\) of pivot columns of \(A\) does not depend on the reduced row-echelon form you choose, and is called the rank of \(A\). We denote it by Rank(\(A\)).

Similarly, we could count the number of leading entries in the row echelon form of \(A\) to determine the rank of \(A\).

Example \(\PageIndex{3}\): Finding the Rank of a Matrix

Consider the matrix \[\left[ \begin{array}{rrr} 1 & 2 & 3 \\ 1 & 5 & 9 \\ 2 & 4 & 6 \end{array} \right]\nonumber \] What is its rank?

Solution

First, we need to find the reduced row-echelon form of \(A\). Through the usual algorithm, we find that this is \[\left[ \begin{array}{rrr} \fbox{1} & 0 & -1 \\ 0 & \fbox{1} & 2 \\ 0 & 0 & 0 \end{array} \right]\nonumber \] Here we have two leading entries, or two pivot positions, shown above in boxes.The rank of \(A\) is \(r = 2.\)

Notice that we would have achieved the same answer if we had found the row-echelon form of \(A\) instead of the reduced row-echelon form.

Suppose we have a homogeneous system of \(m\) equations in \(n\) variables, and suppose that \(n > m\). From our above discussion, we know that this system will have infinitely many solutions. If we consider the rank of the coefficient matrix of this system, we can find out even more about the solution. Note that we are looking at just the coefficient matrix, not the entire augmented matrix.

Theorem \(\PageIndex{1}\): Rank and Solutions to a Homogeneous System

Let \(A\) be the \(m \times n\) coefficient matrix corresponding to a homogeneous system of equations, and suppose \(A\) has rank \(r\). Then, the solution to the corresponding system has \(n-r\) parameters.

Notice that if \(n=m\) or \(n<m\), it is possible to have either a unique solution (which will be the trivial solution) or infinitely many solutions.

Example \(\PageIndex{4}\): Finding the Rank of a Matrix

Consider the matrix \[\left[ \begin{array}{rrr} 1 & 2 & 3 \\ 1 & 5 & 9 \\ 2 & 4 & 6 \end{array} \right]\nonumber \] What is its rank?

Solution

First, we need to find the reduced row-echelon form of \(A\). Through the usual algorithm, we find that this is \[\left[ \begin{array}{rrr} \fbox{1} & 0 & -1 \\ 0 & \fbox{1} & 2 \\ 0 & 0 & 0 \end{array} \right]\nonumber \] Here we have two leading entries, or two pivot positions, shown above in boxes.The rank of \(A\) is \(r = 2.\)

Notice that we would have achieved the same answer if we had found the row-echelon form of \(A\) instead of the reduced row-echelon form.

We are not limited to homogeneous systems of equations here. The rank of a matrix can be used to learn about the solutions of any system of linear equations. In the previous section, we discussed that a system of equations can have no solution, a unique solution, or infinitely many solutions. Suppose the system is consistent, whether it is homogeneous or not. The following theorem tells us how we can use the rank to learn about the type of solution we have.

Theorem \(\PageIndex{2}\): Rank and Solutions to a Consistent System of Equations

Let \(A\) be the \(m \times \left( n+1 \right)\) augmented matrix corresponding to a consistent system of equations in \(n\) variables, and suppose \(A\) has rank \(r\). Then

1. the system has a unique solution if \(r = n\)
2. the system has infinitely many solutions if \(r < n\)

We will not present a formal proof of this, but consider the following discussions.

1. No Solution The above theorem assumes that the system is consistent, that is, that it has a solution. It turns out that it is possible for the augmented matrix of a system with no solution to have any rank \(r\) as long as \(r>1\). Therefore, we must know that the system is consistent in order to use this theorem!
2. Unique Solution Suppose \(r=n\). Then, there is a pivot position in every column of the coefficient matrix of \(A\). Hence, there is a unique solution.
3. Infinitely Many Solutions Suppose \(r<n\). Then there are infinitely many solutions. There are less pivot positions (and hence less leading entries) than columns, meaning that not every column is a pivot column. The columns which are \(not\) pivot columns correspond to parameters. In fact, in this case we have \(n-r\) parameters.

Exercises

Exercise 1

Find the rank of the following matrix. \[\left[ \begin{array}{rrrr} 4 & -16 & -1 & -5 \\ 1 & -4 & 0 & -1 \\ 1 & -4 & -1 & -2 \end{array} \right]\nonumber\]

Answer

Rank = \(2\)

Exercise 2

Find the rank of the following matrix. \[\left[ \begin{array}{rrrr} 3 & 6 & 5 & 12 \\ 1 & 2 & 2 & 5 \\ 1 & 2 & 1 & 2 \end{array} \right]\nonumber\]

Exercise 3

Find the rank of the following matrix. \[\left[ \begin{array}{rrrrr} 0 & 0 & -1 & 0 & 3 \\ 1 & 4 & 1 & 0 & -8 \\ 1 & 4 & 0 & 1 & 2 \\ -1 & -4 & 0 & -1 & -2 \end{array} \right]\nonumber\]

Answer

Rank = \(3\)

Exercise 4

Find the rank of the following matrix. \[\left[ \begin{array}{rrrr} 4 & -4 & 3 & -9 \\ 1 & -1 & 1 & -2 \\ 1 & -1 & 0 & -3 \end{array} \right]\nonumber\]

Exercise 5

Find the rank of the following matrix. \[\left[ \begin{array}{rrrrr} 2 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 7 \\ 1 & 0 & 0 & 1 & 7 \end{array} \right]\nonumber\]

Answer

Rank = \(3\)

Exercise 6

Find the rank of the following matrix. \[\left[ \begin{array}{rrr} 4 & 15 & 29 \\ 1 & 4 & 8 \\ 1 & 3 & 5 \\ 3 & 9 & 15 \end{array} \right]\nonumber\]

Exercise 7

Find the rank of the following matrix. \[\left[ \begin{array}{rrrrr} 0 & 0 & -1 & 0 & 1 \\ 1 & 2 & 3 & -2 & -18 \\ 1 & 2 & 2 & -1 & -11 \\ -1 & -2 & -2 & 1 & 11 \end{array} \right]\nonumber\]

Answer

Rank = \(3\)

Exercise 8

Find the rank of the following matrix. \[\left[ \begin{array}{rrrrr} 1 & -2 & 0 & 3 & 11 \\ 1 & -2 & 0 & 4 & 15 \\ 1 & -2 & 0 & 3 & 11 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right]\nonumber\]

Exercise 9

Find the rank of the following matrix. \[\left[ \begin{array}{rrr} -2 & -3 & -2 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \\ -3 & 0 & -3 \end{array} \right]\nonumber \]

Answer

Rank = \(2\)

Exercise 10

Find the rank of the following matrix. \[\left[ \begin{array}{rrrrr} 4 & 4 & 20 & -1 & 17 \\ 1 & 1 & 5 & 0 & 5 \\ 1 & 1 & 5 & -1 & 2 \\ 3 & 3 & 15 & -3 & 6 \end{array} \right]\nonumber\]

Exercise 11

Find the rank of the following matrix. \[\left[ \begin{array}{rrrrr} -1 & 3 & 4 & -3 & 8 \\ 1 & -3 & -4 & 2 & -5 \\ 1 & -3 & -4 & 1 & -2 \\ -2 & 6 & 8 & -2 & 4 \end{array} \right]\nonumber\]

Exercise 12

Suppose \(A\) is an \(m\times n\) matrix. Explain why the rank of \(A\) is always no larger than \(\min \left( m,n\right) .\)

Answer

It is because you cannot have more than \(\min \left( m,n\right)\) nonzero rows in the reduced row-echelon form. Recall that the number of pivot columns is the same as the number of nonzero rows from the description of this reduced row-echelon form.

Exercise 13

State whether each of the following sets of data are possible for the matrix equation \(AX=B\). If possible, describe the solution set. That is, tell whether there exists a unique solution, no solution or infinitely many solutions. Here, \(\left[ A |B \right]\) denotes the augmented matrix.

1. \(A\) is a \(5\times 6\) matrix, \(rank\left( A\right) =4\) and \(rank\left[ A|B \right] =4.\)
2. \(A\) is a \(3\times 4\) matrix, \(rank\left( A\right) =3\) and \(rank\left[ A|B\right] =2.\)
3. \(A\) is a \(4\times 2\) matrix, \(rank\left( A\right) =4\) and \(rank\left[ A|B \right] =4.\)
4. \(A\) is a \(5\times 5\) matrix, \(rank\left( A\right) =4\) and \(rank\left[ A|B \right] =5.\)
5. \(A\) is a \(4\times 2\) matrix, \(rank\left( A\right) =2\) and \(rank\left[ A|B \right] =2\).

Answer

1. This says that both \(A\) and \(A|B\) have exactly one row of zeros at the bottom. This means a solution exists. Since \(A\) has \(5\) columns but only \(4\) pivots, the system will have at least one free variable, leading to an infinite solution set.
2. This surely can’t happen. The rank cannot get smaller after augmenting another column since we can't lose a pivot position in doing this.
3. This is impossible, since \(A\) with only \(2\) columns cannot possibly have \(4\) pivots.
4. Since \(A|B\) has one more pivot than \(A\), in the reduced row echelon form, \(A|B\)'s last row must be \(\left[ \begin{array}{r} 0 & 0 & 0 & 0 & 0 & 1 \end{array} \right]\). In this case, there is no solution to the system of equations represented by the augmented matrix.
5. In this case, there is a unique solution since the columns of \(A\) are independent. In the reduced row echoelon form of both \(A\) and \(A|B\), the last two rows are rows of \(0\)s.

Exercise 14

Consider the system \(-5x+2y-z=0\) and \(-5x-2y-z=0.\) Both equations equal zero and so \(-5x+2y-z=-5x-2y-z\) which is equivalent to \(y=0.\) Does it follow that \(x\) and \(z\) can equal anything? Notice that when \(x=1\), \(z=-4,\) and \(y=0\) are plugged in to the equations, the equations do not equal \(0\). Why?

Answer

These are not legitimate row operations. They do not preserve the solution set of the system.