How much to disturb a non-invertible element in $\mathcal{M}_n(\mathbb{R})$ to make it invertible?

Question

For a given singular matrix in $\mathcal{M}_n(\mathbb{R})$, what's the smallest number of entries one has to modify in order to make it invertible?

Answer 1

You will need to change a number of entries equal to the nullity of the matrix, which for a square matrix is the multiplicity of the eigenvalue 0.

If the matrix has rank $r$, then there are $r$ rows that can linearly combine to make the remaining $n-r$ rows. If you change one entry in one of the remaining $n-r$ rows to make it linearly independent, you now have a matrix with rank $r+1$. Repeat this argument until you have a matrix of rank $n$, which is invertible if it is $n\times n$. Thus it will take at least $n-r$ changes, which is the nullity of the matrix.

Answer 2

There are some matrices for which the answer is 1, for example $\mathcal I_n$ where the top-left entry has been changed to a $0$ (or indeed, any of the entries on the diagonal changed to $0$).

But as user1551 said in their comment, the answer for $0_n$ (the $n \times n$ zero matrix) would be $n$.

I think $n$ would be the maximum; you could imagine starting with just the first row of the matrix and then add each row one at a time, and if the new row was linearly dependent, change one element in the new row such that it isn't any more. (Something akin to Cantor's Diagonal Argument for the real numbers being uncountable, if you've come across that.)

Certainly, a very crude upper bound is $\frac{1}{2}n(n+1)$, which is the number of changes it would take to make it upper- or lower-diagonal with nonzero entries on the diagonal.