Calculating matrix rank

You've already discussed the definition of the matrix rank, row and column ranks, full rank, and rank-deficient matrices. You've also learned the connection between rank and the number of solutions to a linear equation system. But you still don't know how to find the rank of a matrix. So, let's study methods for finding the rank of a matrix now!

Row-echelon form

To find the rank of a matrix, you need to determine the number of linearly independent rows it contains. You can reduce the matrix to echelon form through elementary transformations. After the reduction, you need to count the number of non-zero rows.

Let's examine the process by using a small example:

$$A = \begin{pmatrix} 4 &10& 1\\ 2 &4 &3\\ 7 &17 &3 \end{pmatrix}$$

First, subtract the third row multiplied by two from the second row:$$A = \begin{pmatrix} 4 &10& 1\\ \textcolor{blue}{ 2 -2\cdot7} & \textcolor{blue}{4-2\cdot17} & \textcolor{blue}{3 - 2\cdot3}\\ 7 &17 &3 \end{pmatrix} =\begin{pmatrix} 4 &10& 1\\ \textcolor{blue}{-12} &\textcolor{blue}{-30} &\textcolor{blue}{-3}\\ 7 &17 &3 \end{pmatrix}$$ Now, add the first row multiplied by three to the second row. After this operation, the second row consists of zeros, so there are only two non-zero rows left:

$$A = \begin{pmatrix} 4 &10& 1\\ \textcolor{blue}{-12+3\cdot4} &\textcolor{blue}{-30+3\cdot10} &\textcolor{blue}{-3+3\cdot1}\\ 7 &17 &3 \end{pmatrix} = \begin{pmatrix} 4 &10& 1\\ \textcolor{blue}0 & \textcolor{blue}0 & \textcolor{blue}0\\ 7&17&3 \end{pmatrix}$$After that, swap the second and the third row to obtain a row echelon form:

$$\begin{pmatrix} 4 &10& 1\\ 7&17&3 \\ \textcolor{blue}0 & \textcolor{blue}0 & \textcolor{blue}0 \end{pmatrix}$$

The first and second rows are linearly independent since you can't express them via each other. There is no need to continue with the reduction because you now know that the rank of the matrix $A$ is equal to $2$. The same thing happens if you calculate the column rank of this matrix. If you don't believe it, do it yourself!

And now, you're ready to understand why the row and column ranks are equal. When you were reducing the matrix to echelon form by applying the elementary transformations to its rows, you didn't change the row and column ranks of the original matrix $A$. This statement is often proven in linear algebra, but it's far too complex for now, and we won't discuss this proof. The same happens if you apply the elementary operations to the columns of the matrix.

If you've obtained a reduced row echelon form of a matrix, you can also apply elementary column operations to it, and you'll finally get an identity matrix. It's a square matrix in which all the main diagonal elements are equal to one, and all other elements are equal to zero. So, since these operations don't change the row and the column ranks of the original matrix $A$, these ranks are equal to the rank of $A$ and to each other because you've obtained a square matrix.

The basics of bounding minors method

You can also find the rank of a matrix with the bounding minors method. You do this by using another definition of the rank that we haven't discussed yet. The rank of the matrix is equal to the order of the largest minor, which is not equal to $0$. Using this method results in the same value for the rank as looking for the number of linearly independent rows (or columns). You have already studied minors — as a reminder, to find a minor of a matrix $A$ you should remove a row and a column from this matrix and calculate a determinant of this new matrix with fewer rows and columns.

And what are bounding minors? Suppose that you have a matrix $A$ and its size is $n \times n$. As in the picture below, you can represent this matrix as a table. Imagine that you've found a blue minor $M$ and its size is $k\times k$. If you increase its size to $(k+1)\times(k+1)$ by adding a row and a column of elements from the original matrix $A$ colored in pink, you'll get a new minor $M'$ of $(k+1)^{th}$ order. This minor $M'$ bounds the minor $M$.

The core of the bounding minors method is to find minors starting from minors of the lowest order and moving to minors of higher orders. If a minor of the $n^{th}$ order is not $0$, and all minors of the $(n+1)^{th}$ order bounding it are equal to $0$, then the rank of the matrix is $n$.

So, let's summarize this method as an algorithm:

1. Find a non-zero element of a matrix. If all elements are zeros, the rank of the matrix is equal to $0$ and you can stop. Otherwise, you have to continue with the minors of the $2^{nd}$ order.
2. Calculate binding minors of the $2^{nd}$ order for this element. If all of them are equal to $0$, the rank of the matrix is equal to $1$ and you can stop. Otherwise, you have to continue with the minors of the $3^{rd}$ order.
3. Calculate bounding minors of the $3^{rd}$ order for a non-zero minor of the $2^{nd}$ order. If all of them are equal to $0$, the rank of the matrix is equal to $2$ and you can stop. Otherwise, you have to continue with the minors of the $4^{th}$ order.
4. Continue calculating the bounding minor of the higher orders until you find minors, which are all equal to $0$. If all the biggest possible minors are not equal to $0$, you have a full rank matrix.

Example of bounding minors method

Looking at an example should make this method clearer. Suppose that you have a matrix

$$A = \begin{pmatrix} 1 &2& -1 &-2\\ 2 &4 &3&0\\ -1&-2&6&6 \end{pmatrix}$$First, look at the minor of the first order $M_{1}$. It can be any non-zero element of this matrix. Let's choose element $A_{11}$ for simplicity: $$A = \begin{pmatrix} \textcolor{blue} {1} &2& -1 &-2\\ 2 &4 &3&0\\ -1&-2&6&6 \end{pmatrix}$$

This element isn't equal to zero, so the rank of this matrix is at least $1$. So, continue with the minors of the second order. Here, you can add not only elements of the second row and column of the matrix $A$, but also elements from its third and fourth columns and from the third row. Since you don't know which minors are equal to $0$ and which are not, let's start with the second row and the second column:$$A = \begin{pmatrix} \textcolor{blue} {1} & \textcolor{red}2& -1 &-2\\ \textcolor{red} 2 & \textcolor{red} 4 &3&0\\ -1&-2&6&6 \end{pmatrix}$$

You'll get a $M_2=\begin{vmatrix} 1 & 2 \\ 2 & 4 \end{vmatrix} =0$. Should you stop now and decide that the rank of the matrix is equal to $1$? No, you can't since you haven't checked whether all minors of the second order are equal to $0$. So, let's check another minor: $$A = \begin{pmatrix} \textcolor{blue} {1} &2& \textcolor{red}{-1} &-2\\ \textcolor{red}2 &4 &\textcolor{red}{3}&0\\ -1&-2&6&6 \end{pmatrix}$$You'll get a $M_2=\begin{vmatrix} 1 & -1 \\ 2 & 3 \end{vmatrix} =5$. As this bounding minor is not equal to $0$, you know that the rank of the matrix is at least $2$.

Next, check minors that bound this new minor. There are only two of them.

• You can obtain the first one if you add elements of the second column and the third row of the matrix $A$ to the minor $M_2$: $$A = \begin{pmatrix} \textcolor{blue} {1} &\textcolor{red}2& \textcolor{blue}{-1} &-2\\ \textcolor{blue}2 &\textcolor{red}4 &\textcolor{blue}{3}&0\\ \textcolor{red}{-1}&\textcolor{red}{-2}&\textcolor{red}6&6 \end{pmatrix}$$

$$M_3=\begin{vmatrix} 1 & 2 & -1\\ 2 & 4 & 3\\ -1 & -2 & 6 \end{vmatrix} =0$$

• You can obtain the second one if you add elements of the fourth column and the third row of the matrix $A$ to the minor $M_2$:$$A = \begin{pmatrix} \textcolor{blue} {1} &2& \textcolor{blue}{-1} &\textcolor{red}{-2}\\ \textcolor{blue}2 &4 &\textcolor{blue}{3}&\textcolor{red}0\\ \textcolor{red}{-1}&{-2}&\textcolor{red}6&\textcolor{red}6 \end{pmatrix}$$

$$M_3=\begin{vmatrix} 1 & -1 & -2\\ 2 & 3 & 0\\ -1 & 6 & 6 \end{vmatrix} =0$$As you can see, both these minors are equal to $0$. So, as all bounding minors are equal to $0$, we can conclude that the rank of the matrix is $2$.

So, now you know two different methods for finding the rank of a matrix. How to choose which one to apply? In general, if a matrix is not that big, it'll be faster and more efficient to reduce it to echelon form and calculate the amount of non-zero rows. If a matrix is big, it'll be faster and more convenient to calculate its rank using the bounding minors method. There may be small and large matrices for which everything will be opposite. You'll learn to choose the most efficient way while solving problems.

Conclusion

Let's sum up all the most important things you've learned today:

• You can find the rank of a matrix by reducing it to echelon form via elementary transformations to calculate the amount of linearly independent rows of the matrix.

• There's another definition for the rank of a matrix as the order of the largest minor, which is not equal to $0$.

• According to this new definition, you can find the rank of a matrix using the bounding minors method.