TR07-122 Authors: Zeev Dvir, Amir Shpilka

Publication: 7th December 2007 11:34

Downloads: 1787

Keywords:

In this paper we study the problem of explicitly constructing a

{\em dimension expander} raised by \cite{BISW}: Let $\mathbb{F}^n$

be the $n$ dimensional linear space over the field $\mathbb{F}$.

Find a small (ideally constant) set of linear transformations from

$\F^n$ to itself $\{A_i\}_{i \in I}$ such that for every linear

subspace $V \subset \F^n$ of dimension $\dim(V) < n/2$ we have

$$\dim\left(\sum_{i \in I} A_i(V) \right) \geq (1+\alpha) \cdot

\dim(V),$$ where $\alpha >0$ is some constant. In other words, the

dimension of the subspace spanned by $\{ A_i(V) \}_{i\in I}$

should be at least $(1+\alpha) \cdot \dim(V)$. For fields of

characteristic zero Lubotzky and Zelmanov \cite{LubotzkyZelmanov}

completely solved the problem by exhibiting a set of matrices, of

size independent of $n$, having the dimension expansion property.

In this paper we consider the finite field version of the problem

and obtain the following results:

1) We give a constant number of matrices that expand the dimension of every

subspace of dimension $d < n/2$ by a factor of $(1 + 1/\log n)$.

2) We give a set of $O(\log n)$ matrices with expanding factor

of $(1+\alpha)$, for some constant $\alpha>0$.

Our constructions are algebraic in nature and rely on expanding

Cayley graphs for the group $\mathbb{Z}/\mathbb{Z}n$ and

small-diameter Cayley graphs for the group $\mathrm{SL}_2(p)$.