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.