Séminaire Lotharingien de Combinatoire, B52f (2004), 11 pp.

Marc Fortin and Christophe Reutenauer

Commutative/Noncommutative Rank of Linear Matrices and Subspaces of Matrices of Low Rank

Abstract. A space of matrix of low rank is a vector space of rectangular matrices whose maximum rank is stricly smaller than the number of rows and the numbers of columns. Among these are the compression spaces, where the rank condition is garanteed by a rectangular hole of 0's of appropriate size. Spaces of matrices are naturally encoded by linear matrices. The latter have a double existence: over the rational function field, and over the free field (noncommutative). We show that a linear matrix corresponds to a compression space if and only if its rank over both fields is equal. We give a simple linear-algebraic algorithm in order to decide if a given space of matrices is a compression space. We give inequalities relating the commutative rank and the noncommutative rank of a linear matrix.

Received: May 21, 2004. Accepted: November 8, 2004. Final Version: November 16, 2004.

The following versions are available: