2015, SFoCM. We use algebraic geometry to study matrix rigidity and, more generally, the complexity of computing a matrixvector product, continuing a study initiated in Kumar et al. (2009), Landsberg et al. (preprint). In particular, we (1) exhibit many non-obvious equations testing for (border) rigidity, (2) compute degrees of varieties associated with rigidity, (3) describe algebraic varieties associated with families of matrices that are expected to have super-linear rigidity, and (4) prove results about the ideals and degrees of cones that are of interest in their own right.
