Let $1\leq r \leq n$ be integers. I'd like to find the smallest integer $m$ such that every matrix $A \in M_n(\mathbb R)$ of rank $r$ can be transformed into a matrix $A'$ of rank $r-1$ by changing at most $m$ coefficients.

The question is rather arbitrary, but here are some examples and remarks, partly to apologise:

  • If $n =r$, you can transform any invertible matrix $A$ into a non-invertible one by modifying a single coefficient (just pick one whose corresponding cofactor doesn't vanish, and set it to the value that cancels the determinant), so $m = 1$.
  • The matrix $(1)_{i,j}$ is of rank $1$, and you obviously have to change all of its coefficients to lower the rank, so $m=n^2$ when $r = 1$.
  • In general, if $\mathop{\mathrm{rk}} A = r$, you can swap some rows and columns so that the $(r-1) \times (r-1)$ northeast submatrix of $A$ is invertible. Then, it's quite easy to show that you can modify the coefficients in the southwest block so that the rank becomes $r-1$. This proves that in general, $m \leq (n+1-r)^2$.

These arguments make me believe (perhaps rather naïvely) that the answer is in fact $m= (n+1-r)^2$, but I haven't got any concrete proof strategy to show it (and the contemplation of small examples quickly gets somehow messy).

Can you find the true value of $m$?


1 Answer 1


Your conjecture is true over any infinite field. More generally, in the set $M_{ab}$ of $a\times b$ matrices, at most $(a-r+1)(b-r+1)$ entries must be changed to reduce the rank of a rank $r$ matrix.

For completeness I first prove the direction you mentioned. As noted, we can reorder the rows and columns of a rank $r$ matrix $A\in M_{ab}$ until it has the form $$ A=\begin{bmatrix}X&Y\\Z&W\end{bmatrix} $$ where $X\in M_{r-1,r-1}$ is nonsingular. By changing the $(a-r+1)(b-r+1)$ entries in $W$, we can change $A$ to $$ \begin{bmatrix}X&Y\\Z&ZX^{-1}Y\end{bmatrix} =\begin{bmatrix}X\\Z\end{bmatrix} \begin{bmatrix}I&X^{-1}Y\end{bmatrix} $$ which has rank $r-1$, as required.

For the converse I will use some algebraic geometry. "Open" and "closed" will refer to the Zariski topology. With $m=(a-r+1)(b-r+1)-1$, we must show there exists a rank $r$ matrix whose rank cannot be reduced by changing $m$ entries. Let $R_r\subseteq M_{ab}$ denote the set of matrices of rank at most $r$. Note that $R_r$ is closed. The entries of a matrix in $M_{ab}$ are indexed by the set $I=\{1,\ldots,a\}\times\{1,\ldots,b\}$. For $J\subseteq I$, consider the subspace of matrices whose $J$-entries are zero: $$ Z_J=\{A\in M_{ab}\mid A_{ij}=0\text{ for all }(i,j)\in J\}. $$ Changing up to $m$ entries is equivalent to adding an element of $Z_J$ for some $J$ with $|J|=ab-m$. Thus we must prove $R_r$ is not contained in $$ \bigcup_{J\subseteq I\atop|J|=ab-m}R_{r-1}+Z_J. $$ In fact I will show the Zariski closure of this set does not contain $R_r$. We assumed the base field $k$ is infinite, so it suffices to prove this over the algebraic closure of $k$. Therefore suppose $k$ is algebraically closed.

Recall that there is a notion of dimension for algebraic varieties, namely Krull dimension, which coincides with linear dimension for a vector space. Moreover a dominant morphism can only reduce dimension. We need a couple of facts about $R_r$: namely it is irreducible and has dimension $r(a+b-r)$. To see this, let $U\subseteq M_{ab}$ be the open set of matrices with a nonsingular top left $r\times r$ submatrix. There is an isomorphism $GL(r)\times M_{a-r,r}\times M_{r,b-r}\to U\cap R_r$ given by $$ (X,Y,Z)\mapsto \begin{bmatrix}X\\Y\end{bmatrix} \begin{bmatrix}I&Z\end{bmatrix}. $$ Thus $U\cap R_r$ is irreducible and has dimension $r^2+(a-r)r+r(b-r)=r(a+b-r)$. The image of the multiplication map $\mu:M_{ar}\times M_{rb}\to M_{ab}$ is $R_r$. Clearly $U'=\mu^{-1}(U)$ is nonempty. Since $M_{ar}\times M_{rb}$ is irreducible, we have $$ R_r=\mu(M_{ar}\times M_{rb})=\mu(\overline{U'})=\overline{\mu(U')}\subseteq\overline{U\cap R_r}. $$ Hence $R_r$ is irreducible with dimension $r(a+b-r)$.

For each $J\subseteq I$, consider the projection $\phi_J:M_{ab}\to M_{ab}/Z_J$. Note that the codomain is a vector space of dimension $|J|$; intuitively $\phi_J$ picks out the $J$-entries of a matrix. Let $$ D_r=\{J\subseteq I\mid\phi_J|_{R_r}\text{ is dominant}\}. $$ Intuitively, $J\in D_r$ means that if someone specifies the $J$ entries of a matrix, you can almost always choose the remaining entries to make a rank $r$ matrix. If $J$ belongs to $D_r$ then so does any subset of $J$. Suppose $J\in D_r\setminus D_{r-1}$ and $R_r\subseteq\overline{R_{r-1}+Z_J}$. Then $$ \phi_J(R_r)\subseteq\phi_J(\overline{R_{r-1}+Z_J})=\overline{\phi_J(R_{r-1}+Z_J)}=\overline{\phi_J(R_{r-1})}\subsetneq M_{ab}/Z_J, $$ contradicting $J\in D_r$. Hence $J\in D_r\setminus D_{r-1}$ implies $\overline{R_{r-1}+Z_J}$ does not contain $R_r$.

Now suppose $|J|=ab-m$. First suppose $J\in D_r$. Recall that the dimension of $R_{r-1}$ is $(r-1)(a+b-r+1)=ab-m-1<|J|$. Thus $J\notin D_{r-1}$, so $R_r\not\subseteq\overline{R_{r-1}+Z_J}$.

On the other hand, suppose $J\notin D_r$. Pick a maximal subset $J'\subseteq J$ with $J'\in D_r$. Pick $j\in J\setminus J'$ and let $J''=J'\cup\{j\}$. Then $Z_{J'}=Z_{J''}+Z_{I\setminus\{j\}}$, so $\phi_{J'}$ factors as $\psi\phi_{J''}$ for some linear map $\psi$. Note that changing a single entry of a matrix cannot increase the rank by more than $1$, so $$ R_{r-1}+Z_{I\setminus\{j\}}\subseteq R_r. $$ Hence $$ \psi^{-1}(\phi_{J'}(R_{r-1}))=\phi_{J''}(R_{r-1}+Z_{I\setminus\{j\}})\subseteq\phi_{J''}(R_r). $$ Now $J''\notin D_r$ by choice of $J'$, so $\phi_{J''}(R_r)$ is not dense. Hence $\phi_{J'}(R_{r-1})$ is not dense, so $J'\in D_r\setminus D_{r-1}$. Hence $R_r\not\subseteq\overline{R_{r-1}+Z_{J'}}$. But $Z_J\subseteq Z_{J'}$, so again $R_r\not\subseteq\overline{R_{r-1}+Z_J}$.

We have shown $R_r\not\subseteq\overline{R_{r-1}+Z_J}$ whenever $|J|=ab-m$. Since $R_r$ is irreducible, it follows that $$ R_r\not\subseteq\bigcup_{J\subseteq I\atop|J|=ab-m}\overline{R_{r-1}+Z_J}, $$ as required.

Finally note that the conjecture is false for a finite field. Indeed a rank $2$ matrix over a field of size $q$ can only have $q+1$ distinct rows up to scalar multiple, so the rank can be reduced by changing at most $\frac{q}{q+1}n^2$ entries. This is less than $(n-1)^2$ for $n$ sufficiently large.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .