`sprank`

Structural rank of a sparse matrix.

Syntax

r = sprank(A)

Returns the structural rank of A, computed from its nonzero pattern alone.

Description

Structural rank ignores the numerical values and asks how many independent entries the pattern could support, a maximum matching in the bipartite graph of rows and columns. The numerical rank can never exceed it, so sprank(A) < min(size(A)) proves the matrix is singular whatever its values, while a full structural rank does not guarantee that it is not.

Input arguments

A: Sparse or full matrix.

Output arguments

r: Integer: the largest number of nonzeros that can be chosen with no two in the same row or column.

Example

Rank of a pattern

sprank(speye(3))
sprank(sparse([1 1; 0 0]))
sprank(sparse([1 0; 1 0]))

Output

ans = 3
ans = 1
ans = 1

sprank