### Rank Bounds for Design Matrices and Applications

```Rank Bounds for Design Matrices
and Applications
Shubhangi Saraf
Rutgers University
Based on joint works with
Albert Ai, Zeev Dvir, Avi Wigderson
Sylvester-Gallai Theorem (1893)
v
v
v
v
Suppose that
every line
through two
points passes
through a
third
Sylvester Gallai Theorem
v
v
v
v
Suppose that
every line
through two
points passes
through a
third
Proof of Sylvester-Gallai:
• By contradiction. If possible, for every pair of points, the line
through them contains a third.
• Consider the point-line pair with the smallest distance.
P
m
Q
ℓ
dist(Q, m) < dist(P, ℓ)
• Several extensions and variations studied
– Complexes, other fields, colorful, quantitative, high-dimensional
• Several recent connections to complexity theory
– Structure of arithmetic circuits
– Locally Correctable Codes
• BDWY:
–
–
–
–
Connections of Incidence theorems to rank bounds for design matrices
Lower bounds on the rank of design matrices
Strong quantitative bounds for incidence theorems
2-query LCCs over the Reals do not exist
• This work: builds upon their approach
– Improved and optimal rank bounds
– Improved and often optimal incidence results
– Stable incidence thms
• stable LCCs over R do not exist
The Plan
• Extensions of the SG Theorem
• Improved rank bounds for design matrices
• From rank bounds to incidence theorems
• Proof of rank bound
• Stable Sylvester-Gallai Theorems
– Applications to LCCs
Points in Complex space
Kelly’s Theorem:
Hesse Configuration
For every pair of points in   ,
the line through them contains
a third, then all points
contained in a complex plane
[Elkies, Pretorius, Swanpoel 2006]:
First elementary proof
This work:
New proof using basic
linear algebra

Quantitative SG
For every point there are at
least  points s.t there is a
third point on the line
1
BDWY: dimension ≤ ( 2 )
This work:
dimension ≤

vi
Stable Sylvester-Gallai Theorem
v
v
v
v
Suppose that
for every two
points there
is a third that
is  -collinear
with them
Stable Sylvester Gallai Theorem
v
v
v
v
Suppose that
for every two
points there
is a third that
is  -collinear
with them
Other extensions
• High dimensional Sylvester-Gallai Theorem
• Colorful Sylvester-Gallai Theorem
• Average Sylvester-Gallai Theorem
• Generalization of Freiman’s Lemma
The Plan
• Extensions of the SG Theorem
• Improved rank bounds for design matrices
• From rank bounds to incidence theorems
• Proof of rank bound
• Stable Sylvester-Gallai Theorems
– Applications to LCCs
Design Matrices
An m x n matrix is a
(q,k,t)-design matrix if:
1. Each row has at most q
non-zeros
2. Each column has at
least k non-zeros
3. The supports of every
two columns intersect
in at most t rows
n
·q
¸k
m
·t
An example
(q,k,t)-design matrix
q=3
k=5
t=2
Main Theorem: Rank Bound
Thm: Let A be an m x n complex
(q,k,t)-design matrix then:

≥  −

Holds for any field of char=0 (or very large positive char)
Not true over fields of small characteristic!
Earlier Bounds (BDWY):  ≥  −
2
2
Rank Bound: no dependence on q
Thm: Let A be an m x n complex
(q,k,t)-design matrix then:

≥  −

Square Matrices
Thm: Let A be an n x n complex
≈ , ≈ , ≈  -design matrix then:
≥ ()
• Any matrix over the Reals/complex numbers with same zero-nonzero
pattern as incidence matrix of the projective plane has high rank
– Not true over small fields!
• Rigidity?
The Plan
• Extensions of the SG Theorem
• Improved rank bounds for design matrices
• From rank bounds to incidence theorems
• Proof of rank bound
• Stable Sylvester-Gallai Theorems
– Applications to LCCs
Rank Bounds to Incidence Theorems
• Given 1 , 2 , … ,  ∈
• For every collinear triple  ,  ,  , ∃  ,  ,  so that   +
+   = 0
• Construct  ×  matrix V s.t  ℎ row is
• Construct  ×  matrix  s.t for each collinear triple  ,  ,
there is a row with  ,  ,  in positions , ,  resp.
• ⋅=
Rank Bounds to Incidence Theorems
• ⋅ =0
• Want: Upper bound on rank of V
• How?: Lower bound on rank of A
The Plan
• Extensions of the SG Theorem
• Improved rank bounds for design matrices
• From rank bounds to incidence theorems
• Proof of rank bound
• Stable Sylvester-Gallai Theorems
– Applications to LCCs
Proof
Easy case: All entries are either zero or one
m
n
n
n
=n
At
A
Off-diagonals
·t
m
Diagonal entries ¸ k
“diagonal-dominant matrix”
General Case: Matrix scaling
Idea (BDWY) : reduce to easy case using matrixscaling:
c c …
c
1
Replace Aij with ri¢cj¢Aij
ri, cj positive reals
Same rank, support.
Has ‘balanced’ coefficients:
r1
r2
.
.
.
.
.
.
rm
2
n
Matrix scaling theorem
Sinkhorn (1964) / Rothblum and Schneider (1989)
Thm: Let A be a real m x n matrix with nonnegative entries. Suppose every zero minor of A
of size a x b satisfies
a
b
+ · 1
m n
Then for every ² there exists a scaling of A with
row sums 1 ± ² and column sums (m/n) ± ²
Can be applied also to squares of entries!
Scaling + design →
perturbed identity matrix
• Let A be an  ×  scaled (, , )design matrix.

(Column norms = , row norms = 1)

• Let  = ∗
•
=

•  ?
• BDWY:
• This work:
Mij ≤
≠
2

≤  1 −
1

Bounding the rank of perturbed
identity matrices
M Hermitian matrix,  ≥
≥

2 +
2
≠
2

The Plan
• Extensions of the SG Theorem
• Improved rank bounds for design matrices
• From rank bounds to incidence theorems
• Proof of rank bound
• Stable Sylvester-Gallai Theorems
– Applications to LCCs
Stable Sylvester-Gallai Theorem
v
v
v
v
Suppose that
for every two
points there
is a third that
is  -collinear
with them
Stable Sylvester Gallai Theorem
v
v
v
v
Suppose that
for every two
points there
is a third that
is  -collinear
with them
Not true in general ..
∃ points in ≈  dimensional space s.t for
every two points there exists a third point that
is
-collinear with them
Bounded Distances
• Set of points is B-balanced if all distances are
between 1 and B
• triple  ,  ,  is -collinear
∃  ,  ,  so that
+   +   ≤
and
1
4B
≤ 1 , 2 , 3 ≤ 1
Theorem
Let 1 , 2 , … ,  be a set of B-balanced points
in   so that
for each  ,  there is a point  such that
the triple is - collinear.
Then
′ (1 , 2 , … ,  ) ≤  6
Incidence theorems to design matrices
• Given B-balanced 1 , 2 , … ,  ∈
• For every almost collinear triple  ,  ,  , ∃  ,  ,  >
|  +   +   | ≤
1
4
so that
• Construct  ×  matrix V s.t  ℎ row is
• Construct  ×  matrix  s.t for each almost collinear triple
,  ,  there is a row with  ,  ,  in positions , ,  resp.
•  ⋅  =  (Each row has small norm)
proof
• ⋅=
• Want to show rows of V are close to low dim space
• Suffices to show columns are close to low dim space
• Columns are close to the span of singular vectors of A
with small singular value
• Structure of A implies A has few small singular values
(Hoffman-Wielandt Inequality)
The Plan
• Extensions of the SG Theorem
• Improved rank bounds for design matrices
• From rank bounds to incidence theorems
• Proof of rank bound
• Stable Sylvester-Gallai Theorems
– Applications to LCCs
Correcting from Errors
Message
Encoding
Correction
≤ fraction
Corrupted Encoding
Local Correction & Decoding
Message
Encoding
Local
Correction
≤ fraction
Corrupted Encoding
Stable Codes over the Reals
• Linear Codes
:  →
• Corruptions:
– arbitrarily corrupt  locations
– small ℓ∞ perturbations on rest of the coordinates
• Recover message up to small perturbations
• Widely studied in the compressed sensing
literature
Our Results
Constant query stable LCCs over the Reals do not exist.
(Was not known for 2-query LCCs)
There are no constant query LCCs over the Reals
with decoding using bounded coefficients
Thanks!
```