Let the columns of a p×q matrix M over any ring be partitioned into n blocks, M = [M1,...,Mn]. If no p×p submatrix of M with columns from distinct blocks Mi is invertible, then there is an invertible p×p matrix Q and a positive integer m <= p such that QM = [QM1,...,QMn] is in reduced echelon form and in all but at most m - 1 blocks QMi the last m entries of each column are either all zero or they include a non-zero non-unit.

CEMAT - Center for Computational and Stochastic Mathematics