1.5: Rank and Homogeneous Systems

Rank and Homogeneous Systems

There is a special type of system which requires additional study. This type of system is called a homogeneous system of equations, which we defined above in Definition 1.2.3. Our focus in this section is to consider what types of solutions are possible for a homogeneous system of equations.

Consider 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 \]

We now present a new definition.

Definition \(\PageIndex{2}\): Linear Combination

Let \(X_1,\cdots ,X_n,V\) be column matrices. Then \(V\) is said to be a linear combination of the columns \(X_1,\cdots , X_n\) if there exist scalars, \(a_{1},\cdots ,a_{n}\) such that \[V = a_1 X_1 + \cdots + a_n X_n\nonumber \]

A remarkable result of this section is that a linear combination of the basic solutions is again a solution to the system. Even more remarkable is that every solution can be written as a linear combination of these solutions. Therefore, if we take a linear combination of the two solutions to Example \(\PageIndex{2}\), this would also be a solution. For example, we could take the following linear combination

\[3 \left[ \begin{array}{r} -4 \\ 1 \\ 0 \end{array} \right] + 2 \left[ \begin{array}{r} -3 \\ 0\\ 1 \end{array} \right] = \left[ \begin{array}{r} -18 \\ 3 \\ 2 \end{array} \right]\nonumber \] You should take a moment to verify that \[\left[ \begin{array}{r} x \\ y \\ z \end{array} \right] = \left[ \begin{array}{r} -18 \\ 3 \\ 2 \end{array} \right]\nonumber \]

is in fact a solution to the system in Example \(\PageIndex{2}\).

Another way in which we can find out more information about the solutions of a homogeneous system is to consider the rank of the associated coefficient matrix. We now define what is meant by the rank of a matrix.

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

Let \(A\) be a matrix and consider any row-echelon form of \(A\). Then, the number \(r\) of leading entries of \(A\) does not depend on the 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 pivot positions (or pivot columns) 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.

Consider our above Example \(\PageIndex{2}\) in the context of this theorem. The system in this example has \(m = 2\) equations in \(n = 3\) variables. First, because \(n>m\), we know that the system has a nontrivial solution, and therefore infinitely many solutions. This tells us that the solution will contain at least one parameter. The rank of the coefficient matrix can tell us even more about the solution! The rank of the coefficient matrix of the system is \(1\), as it has one leading entry in row-echelon form. Theorem \(\PageIndex{1}\) tells us that the solution will have \(n-r = 3-1 = 2\) parameters. You can check that this is true in the solution to Example \(\PageIndex{2}\).

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.

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.