Matrix rigidity measures how many entries of a matrix you must change before its rank drops to some target $r$. Finding an explicit matrix that stays high-rank after many changes would prove circuit lower bounds that complexity theory has sought since 1977. A different line of work, on design matrices, shows that a purely combinatorial property of a matrix's nonzero pattern forces high rank no matter what the nonzero values are. The property is that columns have many nonzeros, rows have few, and any two columns overlap in few rows. This looks like a natural route to rigidity, because changing entries only edits the support pattern. The route breaks for a simple reason. The known theorem uses worst-case parameters, so an adversary can wreck it cheaply. A handful of changes concentrated in one row, or creating extra overlaps between many column pairs, destroys the bound even though almost the whole matrix is still a good design.
This note proposes to prove a rank bound for non-uniform design matrices, where each row, each column, and each pair of columns carries its own parameter and the bound depends on averaged quantities instead of maxima. The bound is then used to lower-bound the rigidity of explicit incidence matrices of hypergraphs with mixed edge sizes. A hypergraph is a set system in which an "edge" can contain any number of vertices. Non-uniformity enters in two ways. A sparse perturbation of a uniform design is always a non-uniform design, so any rigidity argument along these lines has to handle non-uniformity. And mixed-block-size designs are natural explicit candidate matrices in their own right. The concrete deliverable is a theorem of the form "every perturbation of at most $s$ entries leaves rank above $r$" for explicit families, together with a computational study that checks whether the new bound beats the strongest pruning-based use of the old one.
Core Claim
The rigidity of a matrix $M$ at rank $r$ is
$$\mathcal{R}_M(r) = \min \{ \|S\|_0 : \operatorname{rank}(M - S) \le r \},$$
where $\|S\|_0$ counts the nonzero entries of the change matrix $S$. Rank bounds for design matrices defines an $m \times n$ matrix as a $(q,k,t)$-design if every row has at most $q$ nonzeros, every column at least $k$, and any two column supports meet in at most $t$ rows. Using matrix scaling and diagonal dominance, that paper proves $\operatorname{rank}(A) \ge n - qtn^2/(2k^2)$ over characteristic zero, and it explicitly names design matrices as rigidity candidates. This paper supplies the method; our proposal replaces its three global parameters with local ones.
The basis of the new bound is the elementary inequality $\operatorname{rank}(G) \ge (\operatorname{tr} G)^2 / \|G\|_F^2$. Here $G$ is the Gram matrix (the matrix of inner products between columns) of a suitably rescaled copy of $A$, and $\|G\|_F$ is its Frobenius norm. If the scaling makes the diagonal of $G$ equal to one, then
$$\operatorname{rank}(A) \ge \frac{n^2}{n + \sum_{j \ne j'} |G_{jj'}|^2},$$
and each off-diagonal entry $G_{jj'}$ is a sum over the rows shared by columns $j$ and $j'$. The size of each term is set by the local row and column sizes, so the sum depends only on those sizes.
The claim is that this denominator can be bounded by a sum of local overlap terms, one per column pair. Such a sum changes by an amount proportional to $s$ under any $s$-entry perturbation, whereas a worst-case parameter can change by an arbitrary factor. Plugging $M - S$ into the bound would then give rigidity lower bounds for explicit non-uniform incidence matrices directly.
One honest constraint shapes the target. A matrix with few nonzeros is trivially non-rigid, since $\mathcal{R}_M(0) \le \operatorname{nnz}(M)$. The goal is therefore to show that changing a constant fraction of $\operatorname{nnz}(M)$ is necessary at rank as large as possible. This matters for Valiant's program only when columns have polynomially many nonzeros, for example point–line incidences in projective planes, or mixed-size block designs with blocks of size roughly $N^{\delta}$.
Research Program
The first technical step is a scaling theorem with non-uniform marginals. The uniform proof scales $A$ to have prescribed equal row and column norms. Here we need scalings whose targets are matched to the local sizes $q_i$ and $k_j$. Such scalings exist under Hall-type support conditions, and part of the work is showing those conditions survive sparse perturbation, or can be restored by deleting few rows and columns.
The second step bounds each $|G_{jj'}|$ by a sum over the shared rows $C_j \cap C_{j'}$, weighted by the scaled entries. The total is then charged to the hypergraph's intersection profile. This is the "intersection explosion" that the hypergraph literature identifies as the hard part beyond pairwise structure.
The third step is a perturbation lemma. It accounts separately for three kinds of change: deletions shrink $k_j$, insertions grow $q_i$, and insertions that land in the same row in two columns create new pairwise overlaps. The third kind is the dangerous one, because a row receiving $a$ insertions creates on the order of $a^2$ new overlapping pairs.
The candidate explicit families come from the non-uniform side. One is pairwise balanced designs and group divisible designs with mixed block sizes, the objects Chee and Ling use to resolve Turán-type problems about repeated 2-intersections. Their constructions control pairwise intersections exactly, which is what the denominator needs. Another is incidences between points and subspaces of several dimensions in a projective geometry.
We do not try to extend tensor spectral theory. Hou, Chang and Zhang show that even Motzkin–Straus-type bounds for restricted non-uniform classes need special machinery. The incidence-matrix view avoids this, because the ordinary rank of the vertex–edge matrix is defined for any mix of edge sizes.
Several papers constrain which families we may use. Structured matrices with algebraic symmetry tend to be non-rigid. The Walsh–Hadamard transform is not rigid (Alman and Williams). Fourier, circulant and Toeplitz matrices are quasipolynomially non-rigid (Dvir and Liu). The polynomial method breaks further structured families (Dvir and Edelman). Kronecker structure makes rigidity collapse (Alman). We therefore exclude Kronecker-product families. We will also try the known decomposition attacks on every candidate before investing in proofs for it.
The work also has a ceiling. Alman and Liang show that spectral methods hit a wall between rank $\log N$ and $\log^{1+\epsilon} N$ for Hadamard-type matrices. We make no claim of crossing Valiant's barrier. The realistic win is a combinatorial rigidity bound for sparse explicit matrices, in a regime where neither the spectral method nor uniform design bounds apply.
Baselines
The naive reference point is the classical untouched-minor counting argument. It finds a full-rank minor that the perturbation misses, applies to any matrix whose small minors are nonsingular, and gives bounds of order $(N^2/r)\log(N/r)$. For sparse incidence matrices it is often worse than this, because many minors are singular. We will compute it exactly for every candidate family at each rank.
The first strong baseline is the uniform design bound of Barak, Dvir, Wigderson and Yehudayoff applied after pruning. Given a perturbation budget $s$, we delete every row whose support has grown beyond a threshold, every column whose support has shrunk below one, and enough columns to restore a global overlap bound. We then apply the uniform theorem to what remains, with the thresholds optimized per instance. This is the strongest competitor because it uses the same proof engine and only differs in bookkeeping. Beating it means certifying a higher rank at the same $s$, or a larger $s$ at the same rank, for at least one explicit family over a nontrivial range of parameters. No reported result found on Lacuna for rigidity bounds derived from design matrices, so this baseline will be computed by us.
The strongest existing explicit rigidity results sit in other regimes and serve as reference points rather than direct competitors. Alman and Liang report $\mathcal{R}_{H_n}(c\log N) \ge N^2(1/2 - N^{-\gamma})$ for the dense Walsh–Hadamard matrix. Bhangale, Harsha, Paradise and Tal obtain $(\delta N^2, 2^{\log N/\Omega(\log\log N)})$-rigid matrices from an FNP machine, meaning the construction is not explicit in polynomial time. We will state where our bounds sit relative to these in the rank-versus-sparsity plane. For sparse polynomial-time matrices we expect no overlap with either.
The ablation that isolates our key ingredient keeps the averaged Gram-matrix bound but uses the uniform scaling. A second ablation keeps the non-uniform scaling but replaces the per-pair overlap sum with its maximum. If the gain survives only in the first ablation, the scaling is doing the work. If it survives only in the second, the averaging of overlaps is doing the work.
All bounds are evaluated on identical matrices and identical perturbation budgets. Each is given the same per-instance parameter optimization.
Why not just…?
Why not just prune bad rows and columns and use the uniform theorem? This is the real threat. For row growth and column shrinkage, pruning loses only about $s/q$ rows or $s/k$ columns, and it may match any averaged bound. Pruning does poorly on overlap creation. An adversary who spreads insertions so that many rows each gain a few entries raises the overlap of many column pairs. Restoring a global overlap bound then requires deleting a constant fraction of the columns, whereas an averaged sum only grows by the number of new overlapping pairs. The pruned-baseline comparison above settles this empirically. If pruning matches us on every family, we will report the averaged bound as a cleaner proof rather than a stronger result.
Why not just use spectral or Booleanization methods? The method of Alman and Liang analyzes dense matrices with $\pm 1$-like entries and is tight only near rank $\log N$. Sparse 0/1 incidence matrices have no such spectral flatness, and their rigidity is capped by their number of nonzeros. The two approaches cover different matrices. We will still compute the spectral bound on our families as a check that it is weaker there.
Why not just compute rigidity numerically? Heuristic low-rank-plus-sparse solvers only give upper bounds. Tanner, Thompson and Vary show that over the reals the low-rank-plus-sparse set is not closed, so methods such as AltProj and GoDec can diverge while their residual vanishes. The exact fixed-parameter algorithms of Fomin et al. scale only to small rank and sparsity. Numerical computation therefore cannot certify anything. We use it the other way round, to try to falsify candidates and to measure how far our lower bounds sit from achievable upper bounds.
Proposed Experiments
The test bed has four groups. The first is mixed-block-size pairwise balanced and group divisible designs built following Chee and Ling. The second is point–subspace incidences of small projective geometries. The third is random non-uniform hypergraphs with matched size and overlap profiles, as a control. The fourth is the Walsh–Hadamard matrix, as a known non-rigid control. Sizes run from tens of columns, where exact rigidity at tiny rank and sparsity is computable with the Fomin et al. algorithms, up to around $10^4$ columns, where only bounds and heuristics run.
For each matrix and rank we report four quantities: the certified lower bound from the untouched-minor argument, from pruned uniform design bounds, and from the averaged bound with both ablations; and the best upper bound found by heuristic low-rank-plus-sparse search with norm constraints, which avoids the divergence trap. The main metric is certified rigidity as a fraction of $\operatorname{nnz}(M)$, together with the gap to the heuristic upper bound.
The decisive checks are three. First, the averaged bound must strictly beat pruned uniform bounds on some explicit family. Second, it must be exact or nearly exact against the exact solver on small instances. Third, no candidate family may be broken by the heuristic search or by low-probabilistic-rank constructions of the Alman–Williams type. If a family is broken this way, that is a non-rigidity finding in its own right. As a sanity check, the Hadamard control should show heuristic upper bounds well below the trivial maximum.
References
- Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes
- On Extremal k-Graphs Without Repeated Copies of 2-Intersecting Edges
- A homogeneous polynomial associated with general hypergraphs and its applications
- Probabilistic rank and matrix rigidity
- Fourier and Circulant Matrices Are Not Rigid
- Matrix Rigidity and the Croot-Lev-Pach Lemma
- Kronecker products, low-depth circuits, and matrix rigidity
- Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
- Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs
- Matrix Rigidity and the Ill-Posedness of Robust PCA and Matrix Completion
- Matrix Rigidity from the Viewpoint of Parameterized Complexity