We characterize the complexity of some natural and important
problems in linear algebra. In particular, we identify natural
complexity classes for which the problems of (a) determining if a
system of linear equations is feasible and (b) computing the rank of
an integer matrix, ... more >>>

The rank of a matrix has been used a number of times to prove lower
bounds on various types of complexity. In particular it has been used
for the size of monotone formulas and monotone span programs. In most
cases that this approach was used, there is not a single ... more >>>