determining rank of matrix


One can determine the rank of even large matrices by using row and column operationsMathworldPlanetmath to put the matrix in a triangular form. The method presented here is a version of row reduction to echelon formMathworldPlanetmath, but some simplifications can be made because we are only interested in finding the rank of the matrix.

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

  1. 1.

    Permuting rows

  2. 2.

    Permuting colums

  3. 3.

    Adding a multipleMathworldPlanetmathPlanetmath of a row to another row

  4. 4.

    Multiplying a row by an invertiblePlanetmathPlanetmathPlanetmath 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, one may want to use this operation to keep the numbers in a reasonable range or, if one has a matrix of integers, one may want to cancel denominators so that one does not have to deal with fractions.

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

  1. 1.

    If there are no rows or all the entries of the matrix are zero, you are done.

  2. 2.

    Permute rows and columns so as to put a non-zero element in the (1,1) position of the matrix.

  3. 3.

    Subtract multiples of the first row so as to put all the entries in the first column except the first one zero.

  4. 4.

    Repeat the process starting at step 1 with the submatrixMathworldPlanetmath gotten by throwing away the first row and the first column.

Let us illustrate this with the following matrix:

0110011000100010000110101

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

1100001100100010000110101

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

11000011000-1001000010-1101

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

110000𝟏𝟏𝟎𝟎0-𝟏𝟎𝟎𝟏0𝟎𝟎𝟎𝟏0-𝟏𝟏𝟎𝟏

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

110000𝟏𝟏𝟎𝟎0𝟎𝟏𝟎𝟏0𝟎𝟎𝟎𝟏0𝟎𝟐𝟎𝟏

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

110000110000𝟏𝟎𝟏00𝟎𝟎𝟏00𝟐𝟎𝟏

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

110000110000𝟏𝟎𝟏00𝟎𝟎𝟏00𝟎𝟎-𝟐

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

110000110000101000𝟎𝟏000𝟎-𝟐

Since the (1,1) entry of this submatrix is zero, we must make a permutationMathworldPlanetmath. We will swap the fourth and the fifth columns:

110000110000110000𝟏𝟎000-𝟐𝟎

We add twice the fourth row to the fifth row:

110000110000110000𝟏𝟎000𝟎𝟎

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

110000110000110000100000𝟎

Since the sole entry of this submatrix is zero, we are done and have a triangular matrixMathworldPlanetmath. Since there are four non-zero rows, the rank is 4.

In the presentationMathworldPlanetmathPlanetmath above, certain entries of the matrix have been shown in boldface. When using the method in practice, it is only necessary to write these entries — the other entries can be ignored and need not be copied from step to step.

Title determining rank of matrix
Canonical name DeterminingRankOfMatrix
Date of creation 2013-03-22 17:19:23
Last modified on 2013-03-22 17:19:23
Owner Algeboy (12884)
Last modified by Algeboy (12884)
Numerical id 9
Author Algeboy (12884)
Entry type Algorithm
Classification msc 15A03
Related topic GaussianElimination
Related topic ReducedRowEchelonForm