Matrix rigidity basics

Adapted from a workshop talk by C Ramya at FSTTCS 2020.

The rigidity of a matrix is a notion of how “robustly high degree” it is. Formally, the $r$-rigidity of a matrix $M \in \F^{n \times n}$, denoted $R_r(M)$, is how many entries you need to modify in $M$ in order to lower the rank to $\leq r$.

What’s the most rigid you could be?

Here’s a generic strategy you could use to make $M$ have rank $\leq r$:

leave the first few rows as is until the rank reaches $r$;
for every subsequent row, shoehorn it into it the span of the previous rows.

Intuitively, to make a row fit into a space of dimension $r$, you need to “get rid of $n-r$ of the $n$ degrees of freedom”, so it seems like you should be able to do it by changing $n-r$ coordinates. But an arbitrary set $n-r$ of coordinates won’t always do: for example, no value of $x$ can make this matrix rank $2$:

\[ \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ x & 0 & 1 \end{pmatrix} \]

But you can indeed shoehorn any row $u \in \F^n$ into a space $V$ of dimension $r$ by modifying at most $n-r$ coordinates as long as you get to choose which ones:

identify a subset $S$ of $r$ coordinates on which $V$ has full rank;¹
because $V$ has full rank on $S$, there must be some $v \in V$ that matches $u$ on $S$;
change $u$ to $v$.

Up to a permutation of the columns, this is what happens:

Therefore, we only need to change $n-r$ coordinates per row, and we need to do this only for the $n-r$ last rows in the worst case, so $R_r(M) \leq (n-r)^2$.

Random matrices are rigid

It turns out this $(n-r)^2$ is tight: when the field $\F$ is big enough, a random matrix has rigidity $(n-r)^2$ with high probability.

By a direct probability computation

This is because the shoehorning trick itself is tight. Indeed, for any space $V \sse \F^n$ and any set $S$ of $> \dim(V)$ coordinates, a random vector over $\F^S$ will lie outside of $V_S$ except w.p. $1/|\F|$. This means that a random row $u \in \F^n$ is overwhelmingly likely to increase the dimension of $V$, even if $u$ is later modified adversarially outside of $S$.

Therefore, by a union bound,² unless we’re modifying at least $n-r$ coordinates in a row, the row will be overwhelmingly likely to increase the rank (unless the rank is already $>r$). Therefore, to make sure the rank is $\leq r$, we need to modify at least $n-r$ coordinates in at least $n-r$ of the rows.

By a counting argument

More formally, matrices such that $R_r(M) \leq s$ can be written as the sum of an $s$-sparse matrix and a matrix of rank $\leq r$, so there can only be at most

\[\underbrace{\binom{n^2}{s}|\F|^s}_\text{$s$-sparse matrices} \times \underbrace{\binom{n}{r}^2 |\F|^{n^2-(n-r)^2}}_\text{matrices of rank $\leq r$}\]

of them, while there are exactly $|\F|^{n^2}$ matrices total. So, as long as

\[ \begin{align*} \binom{n^2}{s}|\F|^s \times \binom{n}{r}^2 |\F|^{n^2-(n-r)^2} &\ll |\F|^{n^2}\\ \Leftrightarrow \binom{n^2}{s}|\F|^s &\ll \frac{|\F|^{(n-r)^2}}{\binom{n}{r}^2}, \end{align*} \]

then most matrices have $R_r(M) > s$.

TODO: make note proving that bound on # of rank-k matrices

If $\F$ is big enough to overwhelm the binomials (say, if $|\F| \geq 2^{n^3}$), then we can set $s = (n-r)^2-1$, which shows that most matrices have rigidity at least $(n-r)^2$ as we showed earlier.

But even in the worst case, when $|\F| = 2$, we can still get good bounds. Taking the log and approximating the binomials, the inequality becomes

\[2s\log n + s < (n-r)^2 - 2r \log n,\]

After dropping negligible terms,³ we’re left with $2s \log n < (n-r)^2$, which means most matrices have rigidity at least $\Omega\p{(n-r)^2/\log n}$. This only a log factor away from the upper bound.

Explicit rigid matrices

It would be great to construct explicit matrices whose rigidity matches that of random matrices. In fact, if one could find matrices such that $R_{\delta n}(M) \geq n^{1+\eps}$ for some constants $\delta,\eps>0$, this would already have groundbreaking consequences in algebraic circuit complexity by Valiant’s depth reduction.

Example 1: identity matrix

Consider the identity matrix $I^n$: it has full rank, so that seems like a good start. We can make it rank $r$ by changing $n-r$ of the ones into zeros, so it cannot have rigidity more than $n-r$.

But it turns out it does have rigidity $n-r$. Indeed, if its rigidity was less than $n-r$, then you could decompose it as the sum $I^n = A + B$ such that $A$ has $<n-r$ nonzero elements and $\rank(B) \leq r$. But this is impossible because we’d have

\[\rank(I^n) = \rank(A+B) \leq \rank(A)+\rank(B) < (n-r) + r = n\]

(note that this “subadditivity” of rank is also used to give lower bounds on communication complexity, see Monochromatic rectangles#The rank method).

Example 2: Midrijānis

There is a sense in which $I^n$ is “overkill” when $r$ is small: $I^n$ offers you rank $n$ to start with, which is much more than you actually need. Midrijānis’s idea was that you can do better if you build your matrix from smaller identity matrices $I^{2r}$.

Concretely, let $M_{n,2r}$ be the matrix that is formed by putting together $(n/2r)^2$ identity matrices $I^{2r}$ into a big $n \times n$ matrix. Then $R_r(M_{n,2r}) = n^2/4r$. Indeed, if any of the $(n/2r)^2$ blocks retains rank $>r$, then the whole thing will have rank $>r$, so by the same reasoning as before, if you want to decrease the rank to $r$, you need to change at least $2r-r = r$ elements in each of the blocks, for a total of $(n/2r)^2 \cdot r = n^2/4r$ changes.

However, for $r = \eps n$, which is the regime we’re interested about, the rigidity is still only linear.

Example 3: that construction that gains a log n factor

TODO: haven’t learned this yet

You can find it by Gaussian elimination. ↩
The union bound is over all $\binom{n}{<n-r}$ possible choices of $<n-r$ entries to modify. ↩
assuming $r\le.9n$, say ↩