Mathematical Conversations

A matrix M is rigid if one needs to change it in many places in order to reduce its rank significantly. While a random matrix M (say over a finite field) is rigid with high probability, coming up with explicit constructions of such matrices is still mostly open (and would have applications in computational complexity). I will survey some of the known results (mostly negative ones), in particular showing that matrices with an abelian symmetry group are non rigid.