### Proof of $Rig_A(r)\leq (n-r)^2$ for any $n\times n$ matrix $A$

Let $B$ be the bottom-left $r\times r$ submatrix of $A$ of full rank $r$ (up to permutation of rows and columns, there must be one, if $A$ has rank larger than $r$): $A=\begin{pmatrix} B & C \\ D & E \end{pmatrix}$ The $i$-th column of $C$ is a linear combination $Bx$ of the columns of $B$ for some vector $x$. Replace the $i$-th column of $E$ by $Dx$ (using the same vector $x$). This way, every column of the obtained matrix $A'$ is a linear combination of the first $r$ columns. Since we have only changed the entries of $E$, the upper bound $(n-r)^2$ on the rigidity follows.
S. Jukna