On Read-$k$ Projections of the Determinant

The lemma is proved in two steps. In the first step, we transform $M$ to a matrix $M^{\ast }$ with the same determinant such that every row and column of $M^{\ast }$ contains at most one variable. In the second step, we reduce the dimension of $M^{\ast }$.

Assume that $M$ is an $m\times m$ matrix. For the first step, suppose that $M$ contains a variable $x$ in the $(i,j)$-th position. Let $M^{\prime }$ be the $(m+2)\times (m+2)$ matrix

where $M_0$ is obtained by setting the $(i,j)$-th entry to zero in $M$, $e_i$ is the $i$-th unit column vector, $e_j^t$ is the $j$-th unit row vector, and the unspecified entries are zero. Using cofactor expansion on the last column, we obtain $\det (M)=\det (M^{\prime })$. The number of occurrences of variables has not changed while the displayed variable does not share a row or column with another variable. Repeating this construction $s$ times for each variable in $M$, we indeed obtain an $(m+2s)\times (m+2s)$ matrix $M^{\ast }$ with $f=\det (M^{\ast })$ whose rows and columns contain at most one variable each.

We now proceed with the second step. Permuting rows and columns of $M^{\ast }$, we can write $\det (M)=\pm \det (N)$ with

where $A,B,C,D$ are of dimensions $s\times s$, $s\times (s+m)$, $(s+m)\times s$, $(s+m)\times (s+m)$, respectively, and variables appear on the main diagonal of $A$ only.

Since $B$ has $s$ rows, it has rank at most $s$. We can also assume that every column of $B$ is a linear combination of its first $s$ columns. Applying suitable column operations to the last $m+s$ columns of $N$, we can further convert $N$ to the form

with $B_1$ being an $s\times s$ matrix. $D_2$ is of dimension $(m+s)\times m$ and hence has rank at most $m$. Assuming that every row of $D_2$ is a linear combination of its last $m$ rows, we can apply row-operations to write

where $D_2^{\prime }$ is an $m\times m$ scalar matrix. The matrix is a $2s\times 2s$ matrix consisting of scalars except for the $s$ variables on the diagonal of $A$. Since the last column of $H$ contains field elements only, the factor $\pm \det (D_2^{\prime })$ can be moved inside $H$ by multiplying the last column. $◀$

This leads to the following non-constructive lower bound on variable size of determinantal representations.

Let $s_n$ be the smallest $s\ge 1$ such that every multilinear polynomial $f\in 𝔽[x_1,\mathrm{\dots },x_n]$ has a determinantal representation of variable size $s$. Lemma 1 implies that every such $f$ can be expressed as $f=\det (C+x_1{D}_1+\mathrm{\cdots }+x_n{D}_n)$ where $C$ is a scalar matrix and $D_1,\mathrm{\dots },D_n$ are diagonal matrices in ${𝔽}^{2s_n\times 2s_n}$. Viewing entries of $C$ and diagonal entries of $D_1,\mathrm{\dots },D_n$ as parameters, every coefficient of $f$ is a polynomial function of these parameters. Since $f$ has $2^n$ coefficients and there are $k={(2s_n)}^2+2s_{n}n$ parameters, this gives a polynomial map $G:{𝔽}^k\to {𝔽}^{2^n}$ whose image contains all of ${𝔽}^{2^n}$. This implies $k\ge 2^n$.

To see this, assume first that $𝔽$ is finite of size $q$. Then we must have $q^k\ge q^{2^n}$ and hence $k\ge 2^n$. If $𝔽$ is infinite and , the components $G_1,\mathrm{\dots },G_{2^n}$ of $G$ are algebraically dependent over $𝔽$. Then there exists a non-trivial polynomial $g$ with $g(G_1,\mathrm{\dots },G_{2^n})=0$ and $g$ therefore vanishes on all of ${𝔽}^{2^n}$. But this is impossible: given a finite subset $S$ of $𝔽$ of size exceeding the degree of $g$, Schwartz-Zippel lemma implies that $g$ does not vanish already on $S^{2^n}$.

Finally, $k\ge 2^n$ gives $s_n\ge (1-ϵ)2^{n/2-1}$ for every $ϵ>0$ and $n$ sufficiently large. $◀$

If $f$ is a multilinear polynomial with $n>0$ variables, we can write it as

where $f_1,f_0$ are multilinear polynomials in $n-1$ variables. Given formulas for $f_0,f_1$ of size at most $s$, we obtain a formula for $f$ of size $\le 2s+2$. By induction, this gives a formula of size $O(2^n)$. $◀$ Now we are ready to prove Theorem 3.

Let $X$ be the set of variables $\{x_1,\mathrm{\dots },x_n\}$. Let $f\in 𝔽[X]$ be a multilinear polynomial

Introduce new variables $Y=\{y_1,\mathrm{\dots },y_n\}$. Let $\widehat{f}$ be the polynomial

This guarantees that for any boolean substitution $y_1,\mathrm{\dots },y_n\in \{0,1\}$, $\widehat{f}(y_1,\mathrm{\dots },y_n)=a_S$ where $S=\{i|y_i=1\}$. We can therefore write

Note that in this expression, each $x_i$ appears exactly once. Let $g$ be the polynomial $\widehat{f}(y_1,\mathrm{\dots },y_n){\prod }_{i=1}^n(x_i{y}_i+(1-y_i))$. As $\widehat{f}$ is multilinear, it has a formula of size $O(2^n)$ by Lemma 6. It follows that $g$ has a formula of size $O(2^n)$ in which each variable from $X$ appears exactly once. Lemma 4 gives an $m^{\prime }\times m^{\prime }$ matrix $M^{\prime }$ with $m^{\prime }\le O(2^n)$ with entries from $𝔽\cup X\cup Y$ such that $g={\mathrm{perm}}_{m^{\prime }}(M^{\prime })$, each variable from $X$ appears exactly once in $M^{\prime }$ and every row or column of $M^{\prime }$ contains at most one variable. Since $f={\sum }_{y_1,y_2,\mathrm{\dots },y_n\in \{0,1\}}g(X,Y)$ we can apply Lemma 5 to obtain the desired matrix $M$. $◀$

Let $X$ be the set of variables $\{x_{i,j}|1\le i,j\le n\}$ and let $\overline{X}$ be the $n\times n$ matrix with $x_{i,j}$ in $(i,j)$-th entry. Assume that ${\mathrm{perm}}_n(\overline{X})=\det (M)$ where $M$ is a matrix with entries from $𝔽\cup X$.

Let $Z\subseteq X$ be a set of $k$ variables $x_{i_1,j_1},\mathrm{\dots },x_{i_k,j_k}$ where $i_1,\mathrm{\dots },i_k$ are distinct and $j_1,\mathrm{\dots },j_k$ are also distinct. If $k=\lfloor {\log }_{2}n-c\rfloor$, where $c$ is a suitable absolute constant, Theorem 3 implies³³3Note that ${\mathrm{perm}}_n$ is invariant under permutations of rows and columns. the following:

for every multilinear polynomial $f\in 𝔽[Z]$, there exists a matrix ${\overline{X}}_f$ obtained by setting variables outside of $Z$ to constants in $\overline{X}$ such that $f={\mathrm{perm}}_n({\overline{X}}_f)$.

Since ${\mathrm{perm}}_n(\overline{X})=\det (M)$, this means that also $f=\det (M_f)$ where $M_f$ is obtained by setting variables outside of $Z$ to constants in $M$. On the other hand, Theorem 2 shows that there exists a multilinear polynomial in $𝔽[Z]$ which requires determinantal representation of variable size $\mathrm{\Omega }(2^{k/2})$. Hence $M$ must contain $\mathrm{\Omega }(2^{k/2})$ entries from $Z$. Inside $X$, we can find $t=n\lfloor \frac{n}{k}\rfloor$ such disjoint sets $Z_1,\mathrm{\dots },Z_t$. For every $Z_i$, $M$ contains $\mathrm{\Omega }(2^{k/2})$ entries from $Z_i$. Since the sets are disjoint, $M$ contains $\mathrm{\Omega }(t{2}^{k/2})$ entries from $X$ altogether. This gives an $\mathrm{\Omega }(n^{5/2}/\log n)$ lower bound on variable size of $M$. $◀$

If ${\mathrm{perm}}_n$ has a read-$k$ determinantal representation $M$ then $M$ has variable size at most $n^{2}k$. This implies:

${\mathrm{U}}_n$ is defined to have the following property: given $i\in [\mathrm{\ell }]$ and a multilinear polynomial $f\in 𝔽[x_{i,1},\mathrm{\dots },x_{i,r}]$ of the form ${\sum }_{S\subseteq [r]}{a}_S{\prod }_{j\in S}{x}_{i,j}$, we can set $x_{i^{\prime },j}$ to zero for every $i^{\prime }\ne i$ and $y_S$ to $a_S$ for every $S$ to obtain the polynomial $f$ from ${\mathrm{U}}_n$. This is precisely the property we used in the proof of Theorem 7, except that ${\mathrm{U}}_n$ has fewer variables. The same argument as in Theorem 7 gives that every determinantal representation of ${\mathrm{U}}_n$ contains $\mathrm{\Omega }(\mathrm{\ell }{2}^{r/2})$ variables which yields the bound $\mathrm{\Omega }(n^{1.5}/\log n)$. $◀$

Let us make some comments:

1. (i)

   Every read-$k$ determinantal representation of ${\mathrm{U}}_n$ requires $k\ge \mathrm{\Omega }(\sqrt{n}/\log n)$.

2. (ii)

   On the other hand, $U_n$ has a read-$O(n)$ determinantal representation of variable size $O(n^2)$.

(i) is an immediate consequence of Theorem 9. (ii) follows by, first, observing that ${\mathrm{U}}_n$ has an arithmetic formula in which every variable appears $O(n)$ times and, second, that Lemma 4 holds also when ${\mathrm{perm}}_{2m+2}$ is replaced with ${\det }_{2m+2}$.