SJSU Singular Matrix Database

### Structural rank, theoretical rank and numerical rank

The structural rank of a matrix is the number of entries in the maximum transversal of the bipartite graph of A. It is also known as the maximum assignment and size of a maximum matching in the bipartite graph of A. The Matlab function sprank calculates the structural rank of a matrix. If we use term "theoretical rank" to represent the rank as used in a theoretical mathematics course then:

• with probability one in exact arithmetic, the structural rank of A is equal to the theoretical rank of S, where S has the same nonzero pattern as A, but with random numerical values (S = sprand(A) in Matlab); and
• the structural rank is an upper bound on the numerical rank of the matrix, for any tolerance used to define the numerical rank.

Here is a simple example. For some small value ε > 0 let A be the matrix:

 1 1 1 0 1 1 1 0 1 1 1 + ε 0 0 0 0 0

• the theoretical rank of A is 2, for ε different than zero;
• the structural rank of A is 3, since the structural rank considers the nonzero pattern in A and not the numerical values; and
• the numerical rank of A is 1 as long as the tolerance, tol, used to define the numerical rank satisfies (2 / 3) ε ≤ tol < 3 since for small ε the singular values of A are closely approximated by 3, (2 / 3) ε , 0 and 0.