The rigidity of a matrix A for target rank r is the minimum number of entriesof A that must be changed to ensure that the rank of the altered matrix is atmost r. Since its introduction by Valiant (1977), rigidity and similarrank-robustness functions of matrices have found numerous applications incircuit complexity, communication complexity, and learning complexity. Almostall nxn matrices over an infinite field have a rigidity of (n-r)^2. It is along-standing open question to construct infinite families of explicit matriceseven with superlinear rigidity when r=Omega(n).In this paper, we construct an infinite family of complex matrices with thelargest possible, i.e., (n-r)^2, rigidity. The entries of an nxn matrix in thisfamily are distinct primitive roots of unity of orders roughly exp(n^4 log n).To the best of our knowledge, this is the first family of concrete (but notentirely explicit) matrices having maximal rigidity and a succinct algebraicdescription.Our construction is based on elimination theory of polynomial ideals. Inparticular, we use results on the existence of polynomials in eliminationideals with effective degree upper bounds (effective Nullstellensatz). Usingelementary algebraic geometry, we prove that the dimension of the affinevariety of matrices of rigidity at most k is exactly n^2-(n-r)^2+k$. Finally,we use elimination theory to examine whether the rigidity function issemi-continuous.