Large matrix rank does not exclude row-scale saving

3 October 2026. Written construction and limitation; not a universal lower bound.

The broader problem asks when future computation can be maintained by finite rules with bounded local access and allocation. Here we isolate one composition question: how many stored bits must an exact decoder read after a matrix and a query have been prepared separately? The present result limits a proposed structural explanation of saving in systematic linear storage.

Statement and scope

For independent uniform binary vectors u,v, put $$S(B;u,v)=\sum_{i,j}B_{ij}(2u_iv_j-1),\qquad F(C)=\mathbb E\max_{B\in C}S(B;u,v).$$ Matrix addition and matrix rank are over F2; scores and weights are ordinary integers. The full-row code R_n={y 1^T} has $$F(R_n)=\frac{n^{3/2}}{2\sqrt{2\pi}}+O(\sqrt n).$$ For every n>=16 there is a binary linear code C of dimension n such that $$\min_{0\ne B\in C}\operatorname{rank}(B)\ge\tfrac32\sqrt n, \qquad \left|F(C)-F(R_n)\right|\le6n.$$ In particular, its saving still has the row-code leading coefficient, although every nonzero pattern has growing matrix rank. Moreover C intersects the row-plus-column code $$L_n=\{(x_i+z_j)_{ij}:x,z\in\mathbb F_2^n\}$$ only in zero. Its defect dimension dim((C+L_n)/L_n) is therefore n.

This excludes literal low-rank codewords, or exact rank-one fibers, as a necessary explanation of this saving. It does not exclude an explanation allowing small common repairs: the construction is deliberately within O(n) cell changes of full-row advice. It does not improve the conjectured universal bound F(C)=O(n^(3/2)) for dim C<=n, nor settle its sharp coefficient.

A parameterized construction

Choose integers h<n and k=ceil(n/h)<=h. Let K=F_(2^h), with a fixed binary basis. Select a binary linear injection from F2^n into K^k. For y with coefficient image (a_0,…,a_(k-1)), let D(y) be the h by h binary matrix of the linear map $$f_y(t)=\sum_{j=0}^{k-1}a_jt^{2^j}\quad(t\in K).$$ For nonzero y this is a nonzero ordinary polynomial of degree at most 2^(k-1). It has at most that many roots. Its kernel is a binary vector space, hence has dimension at most k-1. Consequently $$\operatorname{rank}D(y)\ge h-k+1.$$ This also proves injectivity of D. This is the classical linearized-polynomial rank-metric construction; the root-count proof above is all that is imported into our argument.

Pad D(y) into the upper-left h by h corner of an n by n matrix, calling it Dtilde(y), and set $$B(y)=y\mathbf1^{\mathsf T}+\widetilde D(y),\qquad C_{n,h}=\{B(y):y\in\mathbb F_2^n\}.$$ An unchanged column of B(y) equals y, so the code has dimension n. Adding that column to each of the first h columns yields the padded columns of D(y). Their span is contained in the column span of B(y). Thus, without losing one unit of rank, $$\operatorname{rank}B(y)\ge\operatorname{rank}D(y)\ge h-k+1 \quad(y\ne0).$$

To check C_(n,h) intersect L_n, take an unchanged row, which is constant across columns. If B(y)_(ij)=x_i+z_j, this forces z_j to be constant. All columns of B(y) must then agree. Comparison with an unchanged column forces D(y)=0 and hence y=0. This proves the claimed defect dimension.

Saving is stable under the common repair

For each y, B(y) differs from y 1^T only in the same h^2 cells. Each score coefficient is either -1 or 1, so for every u,v,y, $$|S(B(y);u,v)-S(y\mathbf1^{\mathsf T};u,v)|\le h^2.$$ The elementary inequality |max a_y-max b_y|<=max|a_y-b_y| now gives, pointwise and then in expectation, $$|F(C_{n,h})-F(R_n)|\le h^2.$$ There is no exchange of maximum and expectation and no assumption that the maximizing y is fixed before the query.

For n>=16 choose h=ceil(2 sqrt(n)). Then h<n, k<=h, h^2<=6n, and $$h-k+1\ge h-n/h\ge\tfrac32\sqrt n.$$ These establish the statement. More generally the same tradeoff permits sqrt(n)<<h<<n^(3/4): minimum rank is asymptotic to h while the repair cost h^2 is o(n^(3/2)).

For x!=0, the exact fiber Q_x={x v^T:v in F2^n} contains only matrices of rank at most one. Our constructed code therefore has C intersect Q_x={0} for every x, despite F(C)=Theta(n^(3/2)). Exact-fiber counting alone does not recognize these near-row patterns.

Resources and quantifiers

We use exactly the systematic linear-advice contract: raw A entries plus n fixed public linear parities with coefficient patterns B(e_l). Storage has S=n^2+n immutable bits at public fixed addresses. There is no other A-dependent metadata, pointer routing, initialization or control channel. The decoder is deterministic, correct for every A,u,v; all old-bit reads during composition and any deferred work through its one-bit answer are charged. Query-only computation and allocation are free in this read model.

For this code the free-advice optimum is E dist(uv^T,C)=n2/4-F(C). Charging advice reads increases the optimal mean by between zero and n. Both costs for this particular encoding therefore equal $$\frac{n^2}{4}-\frac{n^{3/2}}{2\sqrt{2\pi}}+O(n).$$ This is not an assertion that this encoding is globally optimal. Achieving the distance may use exhaustive query-only search; we claim no efficient query runtime.

Each generator B(e_l) is supported on one full row and at most h^2 corner cells. In the stated h=ceil(2 sqrt(n)) construction, all n parities can therefore be prepared in O(n^2) bit XOR operations; copying raw storage also costs O(n^2). A fixed public coefficient description uses at most n^3 bits and is independent of A. The chosen field, basis and injection are part of this public encoding, not hidden input-dependent advice.

For the compact affine fragments y=Ax and x=v, u^T y=1, boundary width b=2n, coefficient input size N0=Theta(n^2), and the fixed-shape named CNF encoding has N=Theta(n^2 log n), including names, clauses and auxiliary variables. Thus the saving order is Theta(b^(3/2)); the leading read term is Theta(N/log N), not quadratic in the full named input size. No consequence for unrestricted SAT algorithms, arbitrary stored bases, Turing machines or scaffolding automata is asserted.

What remains

A useful inverse principle would have to be stable under small simultaneous changes to all codewords, or identify another quantitative invariant of their joint linear structure. Literal matrix rank is too unstable. The common-repair bound already handles this example, while the fixed-defect contraction theorem does not cover it directly because its defect dimension grows as n.

The open question remains whether every dimension-at-most-n systematic code has F(C)=O(n^(3/2)). This construction neither proves nor refutes that statement. It repairs the structural search criterion.

Provenance and verification

The rank-distance ingredient is classical: E. M. Gabidulin, “Theory of codes with maximum rank distance,” Problems of Information Transmission 21(1), 1985, 1-12; publisher record. We supplied the specific polynomial root-count argument rather than relying on an unexamined theorem number. The row-parity asymptotic and common-repair comparison are established in the linked Lab notes. Their combination here is a written obstruction to a proposed route; historical novelty is not established. This is not a formally verified theorem or an inference from finite experiments.