determining rank of matrix

One can determine the rank of even large matrices by using row andcolumn operations to put the matrix in a triangular form. The methodpresented here is a version of row reduction to echelon form,but some simplifications can be made because we are only interestedin finding the rank of the matrix.

The foundation of this method is that the rank of a matrix is leftinvariant by the following operations:

1.
Permuting rows
2.
Permuting colums
3.
Adding a multiple of a row to another row
4.
Multiplying a row by an invertible scalar

The last operation is really not needed, but it can be convenient.For instance, if some of the numbers in the matrix are huge, onemay want to use this operation to keep the numbers in a reasonablerange or, if one has a matrix of integers, one may want to canceldenominators so that one does not have to deal with fractions.

These operations can be used to put the matrix in a triangularform; once this is done, all one has to do to determine the rankis count how many non-zero rows there are. A systematic way ofgoing about this is as follows:

1.
If there are no rows or all the entries of the matrix arezero, you are done.
2.
Permute rows and columns so as to put a non-zero element inthe $(1,1)$ position of the matrix.
3.
Subtract multiples of the first row so as to put all theentries in the first column except the first one zero.
4.
Repeat the process starting at step 1 with the submatrixgotten by throwing away the first row and the first column.

Let us illustrate this with the following matrix:

\\begin{matrix}0&1&1&0&0\\\\1&1&0&0&0\\\\1&0&0&0&1\\\\0&0&0&0&1\\\\1&0&1&0&1\\end{matrix}

We interchange the first two rows to put a $1$ in the $(1,1)$ position:

\\begin{matrix}1&1&0&0&0\\\\0&1&1&0&0\\\\1&0&0&0&1\\\\0&0&0&0&1\\\\1&0&1&0&1\\end{matrix}

We subtract the first row from the third and the fifth rows:

\\begin{matrix}1&1&0&0&0\\\\0&1&1&0&0\\\\0&-1&0&0&1\\\\0&0&0&0&1\\\\0&-1&1&0&1\\end{matrix}

We now concentrate on the submatrix gotten by ignoring thefirst column and the first row:

\\begin{matrix}1&1&0&0&0\\\\0&\\mathbf{1}&\\mathbf{1}&\\mathbf{0}&\\mathbf{0}\\\\0&\\mathbf{-1}&\\mathbf{0}&\\mathbf{0}&\\mathbf{1}\\\\0&\\mathbf{0}&\\mathbf{0}&\\mathbf{0}&\\mathbf{1}\\\\0&\\mathbf{-1}&\\mathbf{1}&\\mathbf{0}&\\mathbf{1}\\end{matrix}

Since the $(1,1)$ position of this submatrix is not zero,we do not need to do any permuting. Instead, we go to thenext step and add the second column to the third and fifthcolumns:

\\begin{matrix}1&1&0&0&0\\\\0&\\mathbf{1}&\\mathbf{1}&\\mathbf{0}&\\mathbf{0}\\\\0&\\mathbf{0}&\\mathbf{1}&\\mathbf{0}&\\mathbf{1}\\\\0&\\mathbf{0}&\\mathbf{0}&\\mathbf{0}&\\mathbf{1}\\\\0&\\mathbf{0}&\\mathbf{2}&\\mathbf{0}&\\mathbf{1}\\end{matrix}

We now narrow our focus to the submatrix gotten by throwingout the first and second rows and columns:

\\begin{matrix}1&1&0&0&0\\\\0&1&1&0&0\\\\0&0&\\mathbf{1}&\\mathbf{0}&\\mathbf{1}\\\\0&0&\\mathbf{0}&\\mathbf{0}&\\mathbf{1}\\\\0&0&\\mathbf{2}&\\mathbf{0}&\\mathbf{1}\\end{matrix}

Since the $(1,1)$ entry of this submatrix is again not zero,we do not need to do any permuting. Thus, we move to thenext step and subtract twice the third row from the fifth row:

\\begin{matrix}1&1&0&0&0\\\\0&1&1&0&0\\\\0&0&\\mathbf{1}&\\mathbf{0}&\\mathbf{1}\\\\0&0&\\mathbf{0}&\\mathbf{0}&\\mathbf{1}\\\\0&0&\\mathbf{0}&\\mathbf{0}&\\mathbf{-2}\\end{matrix}

We now narrow our focus to the submatrix gotten by throwingout the first, second, and third rows and columns:

\\begin{matrix}1&1&0&0&0\\\\0&1&1&0&0\\\\0&0&1&0&1\\\\0&0&0&\\mathbf{0}&\\mathbf{1}\\\\0&0&0&\\mathbf{0}&\\mathbf{-2}\\end{matrix}

Since the $(1,1)$ entry of this submatrix is zero, we must makea permutation. We will swap the fourth and the fifth columns:

\\begin{matrix}1&1&0&0&0\\\\0&1&1&0&0\\\\0&0&1&1&0\\\\0&0&0&\\mathbf{1}&\\mathbf{0}\\\\0&0&0&\\mathbf{-2}&\\mathbf{0}\\end{matrix}

We add twice the fourth row to the fifth row:

\\begin{matrix}1&1&0&0&0\\\\0&1&1&0&0\\\\0&0&1&1&0\\\\0&0&0&\\mathbf{1}&\\mathbf{0}\\\\0&0&0&\\mathbf{0}&\\mathbf{0}\\end{matrix}

We narrow our focus to the submatrix gotten by ignoringall but the fifth row and column:

\\begin{matrix}1&1&0&0&0\\\\0&1&1&0&0\\\\0&0&1&1&0\\\\0&0&0&1&0\\\\0&0&0&0&\\mathbf{0}\\end{matrix}

Since the sole entry of this submatrix is zero, we are doneand have a triangular matrix. Since there are fournon-zero rows, the rank is $4$ .

In the presentation above, certain entries of the matrix have beenshown in boldface. When using the method in practice, it is onlynecessary to write these entries — the other entries can beignored and need not be copied from step to step.