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