Structural rank of a matrix

The structural rank of a matrix is the maximum rank of all numerical matrices with the same nonzero pattern. We illustrate this on a very simple example and give an implementation in Scilab using the Metanet toolbox.

Example

Consider the matrix \[ M=\begin{pmatrix} m_{11} & m_{12}& 0\\ m_{21} & 0 & 0\\ 0 & m_{32} & 0 \end{pmatrix} \] taken from [3, p. 74]. The matrix can be associated with a bipartite graph:

The graph has three maximum matching of the maximum cardinality 2:

Therefore, the structural rank of the matrix is $r=2$. We show a Scilab implementation below.

References

  1. Reinschke, K. J.: Multivariable Control - A Graph-theoretic Approach. Lecture Notes in Control and Information Science 108. Springer-Verlag, 1988.
  2. Murota, K.: Systems Analysis by Graphs and Matroids - Structural Solvability and Controllability Springer-Verlag, 1987.
  3. Röbenack, K.: Beitrag zur Analyse von Deskriptorsystemen. Shaker-Verlag, 1999 (ISBN: 978-3-8265-6795-7) [mehr]

Scilab implementation

First, we have to install the Metanet toolbox by

atomsInstall('metanet')

and restart Scilab.

function [r]=srank (A),
// Calculates the structural rank of a matrix using bipartite matching
A=clean(A);
[n,m]=size(A);
tail=[];
head=[];
for j=1:n,
 for i=1:m,
  if A(j,i)<>0 then
   tail=[tail j];
   head=[head i+n];
  end;
 end;
end;
g=make_graph('srank', 0, n+m, tail, head);
[card,match]=best_match (g);
r=card;
endfunction;