A Note on Matrix Rigidity

Joel Friedman^{∗} Department of Computer Science Princeton University Princeton, NJ 08544

June 25, 1990 Revised October 25, 1991

Abstract

In this paper we give an explicit construction of n × n matrices over finite fields which are somewhat rigid, in that if we change at most k entries in each row, its rank remains at least Cn(log_{q} k)/k, where q is the size of the field and C is an absolute constant. Our matrices satify a somewhat stronger property, we which explain and call “strong rigidity.” We introduce and briefly discuss strong rigidity, because it is in a sense a simpler property and may be easier to use in giving explicit constructions.

Recently there has been interest in giving explicit constructions of n × n matrices which are “rigid,” in the sense that their rank is high and remains high when a few of their coefficients are changed (see [Val77], [Gri76], [Raz], and [PSR]^{1}). It is easy to construct n × n matrices over infinite fields, F, such that when no more that k of the entries of each row are altered, the rank remains at least n/k; one can take a van der Monde matrix, for example. In this note we give an explicit construction of a matrix which is slightly more rigid than such a construction, for finite fields, F, and k larger than some constant (depending on the size of the field). These matrices are actually “strongly rigid,” in a sense that we will discuss later.

∗This paper was written while on leave from Princeton, at the Hebrew University. The author wishes to acknowledge the National Science Foundation for supporting this research in part under PYI grant CCR–8858788, and a grant from the program of Medium and Long Term Research at Foreign Centers of Excellence.

1Pudlak and Savitzky have shown that over the real numbers, a Hadamard matrix of dimension n remains of rank r if no more than n^{2}/(r^{4} log^{2} r) of its entries are changed. Razborov has improved this to n^{2}/(r^{3} log r).

Theorem 1 For any constant C_{1} > 0 there is a constant C_{2} > 0 such that the following holds. Let F be a finite field of q elements. Let A be an n × n matrix such that the first n/2 rows are the basis of a linear error-correcting code in F^{n} of minimum distance ≥ C_{1}n. If B is any n × n matrix over F with at most k non-zero entries in each row, where k ≤ n/C_{2}, then we have

rank(A + B) ≥ \frac{n}{C_{2}k} (log_{q} k + log_{q}(q − 1)).

In the above theorem it is the “log_{q} k” as opposed to the “log_{q}(q − 1)” which is of interest. We have included the “log_{q}(q − 1)” to remark that when q → ∞ with fixed n and k, the construction does not completely degenerate.

The above matrices satisfy a stronger property, which we call “strong rigidity.” After proving this theorem we define and discuss strong rigidity, because it is somewhat easier to work with and may be a useful point of view in constructing other explicit examples.

We recall that there are many types of explicitly specified codes, which for any value of q give a sequence of n’s and a code for each such n of dimension n/2 and minimum distance C_{1}n with C_{1} independent of q and n (one can take Justesen codes or Goppa codes, see respectively [vL82] and [vdGvL88]). Thus the above theorem, for any value of q and many of n, gives matrices rigid in the above sense.

Proof The first n/2 rows of A represent vectors v_{1}, …, v_{n/2} which are a basis of linear code (subspace) C ⊂ F^{n} of minimum distance ≥ C_{1}n. Let b_{1}, ⋯, b_{n/2} be the first n/2 rows of B. If the rank of the matrix consisting of the first n/2 rows of A + B is t, then this is just to say that

E ≡ {w = (w_{1}, …, w_{n/2}) ∈ F^{n/2} | ∑_{i=1}^{n/2} w_{i}(v_{i} + b_{i}) = 0}

(here 0 is the origin in F^{n}) satisfies

dim E = \frac{n}{2} − t.

Since E is an (n/2) − t dimensional subspace of F^{n/2}, we can find a non-zero element w ∈ E of weight r for any r satisfying

|Hamming ball of radius r/2 in F^{n/2}| ≥ q^{t},

or more crudely,

\binom{n/2}{r/2}(q − 1)^{r/2} ≥ q^{t}.  (1)

But for such a w we have

∑_{i=1}^{n/2} w_{i}b_{i} ∈ C − {0},

and so such an r must satisfy rk ≥ C_{1}n. So taking r_{0} = ⌈C_{1}n/k⌉ − 1, equation 1 cannot hold for r = r_{0}, that is to say that t is bounded below by

t ≥ log_{q} [\binom{n/2}{r_{0}/2}(q − 1)^{r_{0}/2}] ≥ log_{q} \binom{n/2}{r_{0}/2} + \frac{r_{0}}{2} log_{q}(q−1) ≥ \frac{n}{C_{2}k} (log_{q} k+log_{q}(q−1)),

for large enough C_{2}, also assuming k ≤ n/C_{2}, where we have estimated

log_{q} \binom{n/2}{r_{0}/2} ≥ log_{q}[(\frac{n}{2} − \frac{r_{0}}{2} )^{r_{0}/2} / (r_{0}/2)^{r_{0}/2}] ≥ \frac{n}{C_{2}k} log_{q} k .

□

Definition 2 C ⊂ F^{n} is (k, t)-strongly rigid if every subspace B spanned by c = dim C vectors b_{1}, …, b_{c}, each of weight ≤ k, has

dim(B ∩ C) ≤ dim C − t.  (2)

Glancing at the proof of theorem 1 shows that matrix A is actually (k, t)-strongly rigid with t = n log_{q} k/(C_{2}k). Strong rigidity is a simpler property to check, in the sense that we do not care about the precise relations between a basis for C and of one for B. Therefore, as in theorem 1, we hope that it may be easier to work with strong rigidity to give explicit constructions.

To compare strong rigidity to the usual notion of rigidity, we’ll say that an n × n matrix A is (k, t)-rigid if whenever no more than k entries in each row of A are altered, then A’s rank remains at least t. It is easy to see (and well-known) that if A is a “random” n × n matrix in an infinite or sufficiently large field, F, then with high probability^{2} A will be (k, t)-rigid with any t ≤ n − (nk)^{1/2}.

While we cannot assert so large a value of t for the existence of strongly rigid matrices, we can obtain existence for a value of t which is interesting for some of the intended applications of rigid matrices.

Theorem 3 Let k, n be integers with k ≤ n/2 and (for simplicity) n even. Then over any finite field, F, there exists a (k, t)-strongly rigid code C ⊂ F^{n} of dimension n/2, for any t with

t ≤ \frac{n}{8} − \frac{1}{2}k log_{q} \frac{n}{k} − \frac{k}{4} − \frac{log_{q} n}{4},

where q is the size of F. The same holds for any infinite field, where in the above equation we substitute 0 for the two occurrences of log_{q}( ), and where we require strict inequality. If we substitute “n/10” for the “n/8” in the above equation for t, then any n × n matrix over F is (k, t)-strongly rigid with “high probability.”

2If F is infinite, the entries of A should be chosen from a distribution which has each field element weighted sufficiently small.

Proof This is, as usual, an easy counting argument (in the case of infinite fields one counts dimensions). For any subspaces B, C of F^{n} with

dim B = dim C,  dim(B ∩ C) ≥ dim C − t,  (3)

it is easy to see that there exist v_{1}, …, v_{t} ∈ F^{n} and ℓ_{1}, …, ℓ_{t} ∈ (F^{n})^{∗} (i.e. the dual of F^{n} as an F-vector space) such that

C = {v ∈ sp ⟨B, v_{1}, …, v_{t}⟩ | ℓ_{i}(v) = 0 ∀i} ,  (4)

where sp ⟨ ⟩ denotes the linear span. To see this, notice that equation 3 also implies

dim(B + C) ≤ dim C + t = dim B + t ;

hence we can choose v_{i} so that

B + C = sp ⟨B, v_{1}, …, v_{t}⟩

and then choose ℓ_{i} so that equation 4 holds.

Equation 4 shows that to every code C of dimension n/2 which is not (k, t)-strongly rigid there corresponds (at least one collection of) a B generated by n/2 vectors of weight ≤ k and vectors v_{i} and (dual) vectors ℓ_{i} as above. In the case of F finite, the number of vectors of weight ≤ k is

≤ n(q − 1)^{k}\binom{n}{k}

(assuming k ≤ n/2), and so the total number of collections (B, {v_{i}}, {ℓ_{i}}) is bounded by

≤ [n(q − 1)^{k}\binom{n}{k}]^{n/2} q^{2nt}.  (5)

On the other hand, the total number of subspaces of F^{n} of dimension n/2 is

\frac{(q^{n} − 1)(q^{n} − q) ⋯ (q^{n} − q^{(n/2)+1})}{(q^{n/2} − 1)(q^{n/2} − q) ⋯ (q^{n/2} − q^{(n/2)−1})} ≥ (\frac{q^{n} − 1}{q^{n/2} − 1})^{n/2} > (q^{n/2})^{n/2} .

It follows that a (k, t)-strongly rigid C of dimension n/2 exists provided that

q^{n^{2}/4} ≥ [n(q − 1)^{k}\binom{n}{k}]^{n/2} q^{2nt},

in particular, using \binom{n}{k} ≤ (n − k)^{k}/k^{k},

t ≤ \frac{n}{8} − \frac{1}{2}k log_{q} \frac{n}{k} − \frac{k}{4} − \frac{log_{q} n}{4}.

Also, if we replace the n/8 in the above by n/10, then a randomly chosen C of dimension n/2 has probability ≤ n^{−n/40} of not being (k, t)-rigid.

If the field is infinite, then the dimension of the set of tuples (B, {v_{i}}, {ℓ_{i}}) as an F variety^{3} is

\frac{kn}{2} + 2nt.

This, of course, is the q → ∞ limit of log_{q} of the expression in equation 5. The same goes through for the set of all C, i.e. subspaces of dimension n/2 in F^{n}, meaning that one counts its dimension as an F variety (and gets the q → ∞ limit of log q of the previously derived expression for finite fields). Therefore we get the aforementioned results, except that we need strict inequality in the inequality for t, and that when we use n/10 instead of n/8, “high probability” means occurs as a subvariety of codimension ≥ ⌊n/40⌋.

□

J. Håstad has pointed out to me that the construction given in theorem 1 will, in general, be no better that (k, t)-rigid for t proportional to n log_{q} k/k; that is, by starting with n/2 random vectors {b_{i}} of small weights, choosing a random subspace of F^{n} of dimension t, and choosing n/2 random vectors in this subspace, {u_{i}}, one gets (many) matrices A as in the theorem which are not (k, t)-rigid for appropriate t of order n log_{q} k/k (i.e. where A’s first n/2 rows are {b_{i} + u_{i}}).

The author wishes to thank A. Wigderson, J. Håstad, and A. Razborov for helpful discussions and comments.

References

[Gri76] D.Y. Grigorjev. Notes of the Leningrad Branch of the Steklov Mathematical Institute of the Academy of Science of the USSR, 60:38–48, 1976.

[PSR] Pudlak, Savitzky, and A. Razborov. Observations on rigidity of Hadamard matrices. Personal Communication.

[Raz] A. Razborov. On rigid matrices. Problems of Pure and Applied Mathematics (Literal Translation from Russian). to appear.

[Val77] L.G. Valiant. Graph-theoretic arguments in low-level complexity. Technical Report, University of Edinburgh, 1977. Computer Science Report 13-77. Also in Proc. 6th Symp. on Mathematical Foundations of Computer Science, Tratranska Lomnica, Czechoslovakia 1978.

3Throughout this paragraph we will, by a slight abuse of terminology, use “F variety” to mean “algebraic set over F.” We do not require these sets to be irreducible.

[vdGvL88] G. van der Geer and J. van Lint. Introduction to Coding Theory and Algebraic Geometry. Birkhäuser Verlag, Boston, 1988.

[vL82] J. van Lint. Introduction to Coding Theory. Springer-Verlag, New York, 1982.