A Lower Bound on Determinantal Complexity

Paper

• Kumar, Volk - A Lower Bound on Determinantal Complexity

Results

• Determinantal Complexity of $f$: Smallest dimension of a matrix $M$ filled with affine linear forms such that $\det(M)$ computes $f$.
• Determinantal Complexity of $\sum_{i=1}^n x_i^n$ is $1.5n -3$.
• Permanent has determinantal complexity $(n-1)^2 +1$ (over reals). This is the same as the number of variables in Perm.

Proof Overview

• Let $M$ be a $m\times m$ matrix that computes $f=\sum_{i=1}^n x_i^n$.
• Converting the matrix into normal form.
  • The constnat part of the matrix (i.e., $M_0 = M(0)$) can be assumed to be diagonal matrix of rank $m-1$.
• Determinantal Complexity of high degree polynomials.
  • If $M$ has entries being polynomials of degree $n-1$ and $M$ is in normal form and $det(M)=f$, then $m\geq n/2$.
  • The same holds for any polynomial $(\sum_{i=1}^n x_i^n)(1+Q)$ with $Q(0)=0$.
• Trading Dimension of the Matrix as Degree
  • If there is an $m\times m$ matrix with affine functions and $det(M)=f$, then there is a matrix $N$ of dimension $(m-n+2)\times (m-n+2)$ whose entries are polynomials of degree at most $n-1$.
  • Normal form keeps intact.
• Now the lowerbound from $1$ implies that $m\geq n/2$, hence that $m'-n -2 \geq n/2$ with degree $n-1$. Hence $m'\geq 3n/2 -3$.

Needed Lemmas

• Lemma 3.1: Let $P_1,\dots, P_t, Q_1,\dots, Q_t$ be polynomials that have a common root and $R$ be polynomials such that $\deg(R) <d$ and $\sum_{i=1}^n x_i^d = R+ \sum_{j=1}^t P_j Q_j$. Then $t>n/2$.
• Lemma 3.8: Let $\begin{pmatrix} A& B\ C& D\end{pmatrix}$. Then $\det(M)=\det(A-BD^{-1}C)\det(D)$.
  • Proof:
  • $\begin{pmatrix} A& B\ C& D\end{pmatrix} = \begin{pmatrix} A-BD^{-1}C& BD^{-1}\ 0& I_{m-t}\end{pmatrix} = \begin{pmatrix} I_t & 0\ C& D\end{pmatrix}$.

Second Part

• Lemma 3.9: If $\deg(M)\leq d-1$, additionally $M$ at $(1,1)$ is zero and one on the diagonal and the constant part is diagonal and $\det(M)= f \cdot (\beta + Q)$ where $\beta\neq 0$ and $Q$ constant free.
• Then $m\geq n-1$.
• Proof:
• Using the Laplace expansion gives us $\det(M)= \sum_{j=1}^m (-1)^{j+1} M_{1.j} \det(N_{1,j})$ where $N_{i,j}$ is the submatrix of deleting the $i$th row and $j$th column.
• Claim: $\det(N_{1,j})$ is a constant free polynomial for $j>1$.
  • $N_{1,j}$ has at most $m-2$ non-zero entries
    • $M_0$ has at most $m-1$ non-zero entries by assumption.
• $N_{1,1}(0)$ is the identity matrix.
• Hence, $\det(N_{1,1})=1 + P(X)$ with $P(X)$ being constant free.
• We can write $f (beta + Q) = \det(M) = \sum_{j=1}^m (-1)^{j+1} M_{1,j} \det(N_{1,j}) = M_{1,1}\cdot (1+P) + \sum_{j=2}^m (-1)^{j+1} M_{1,j} \det(N_{1,j})$.
• Hence, $f (beta + Q) = M_{1,1} + M_{1,1} \cdot P + \sum_{j=2}^m (-1)^{j+1} M_{1,j} \det(N_{1,j})$.
• Now $\sum_{i=1}^n x_i^n = 1/\beta (- Q(\sum_{i=1}^n x_i^n)+ M_{1,1} + M_{1,1}P + \sum_{j=2}^m (-1)^{j+1} M_{1,j}\det(N_{1,j}))$.
• Since $\deg(M_{1,1})<d$ (per entry) and all other polynomials are constant free (have the common root 0), we can apply Lemma 3.1.
  • Notice that our requirement says that the constant part of $M$ at $(1,1)$ needs to be zero (which is a requirement) and as the constant part of $M$ is a diagonal matrix, all $M_{1,j}$ are zero.
  • The requirement coming from the proof is much less than required, as we only need to find a laplace decomposition where $M_{i,j}$ and $N_{i,j}$ are zero.

Third Part

• Let $M$ be a $m\times m$ matrix.
• Let $D_t$ be the principal minor of $M$ which is obtained by deleting the first $m-t$ rows and columns.
• $D_t$ is invertible for all $t\leq m-1.
  • $\det(D_t)$ is non-zero as $D_t(0)$ is the identity matrix (by constant requirement). This is then implied by $\det(D_t(0))\neq 0$.
  • As every entry in $M$ has degree one and $\det(M)$ has degree $n$, $m\geq n$.
• Hence, $D_{n-2}$ is invertible.
• Let $M=\begin{pmatrix} A& B\ C& D\end{pmatrix}$.
• By Lemma 3.8 $\det(M) = \det(A-BD^{-1}C) \det(D)$.
• Since $D^{-1} = adj(D)/\det(D)$ where $adj(D)$ is the adjugate of $D$.
  • The adjugate is given by: the entry of $\adj(A)_{i,j}$ is the $j,i$th minor of $A$ times $(-1)^{i+j}$.
• Now the entries of $D^{-1}$ can be written a a ratio of two polynomials where the denominator has degree at most $n-2$ and the numerator has degree at most $n-3$.
  • As the minor removes at least one row/column and hence one linear form.
• Now the entries of $A-BD^{-1}C$ are given by polynomials with the following maximum degree (in order) $1,1, n-3/n-2, 1$.
• This gives us that the entries have degree $1+n-3+1$ in the numerator and $n-2$ in the denominator.
• This also implies that $A-BD^{-1}C$ is a $(m-n+2) \times (m-n+2)$ matrix.
  • The reason is that $\det(M)$ is a degree $m$ polynomial and $\det(D)$ is a degree $n-1$ polynomial.
  • Hence, $\det(A-BD^{-1}C$ has to produce a degree $m-n+2$ polynomial.
  • As $A,B,C$ have only linear forms, this means the matrix size has to be at least $(m-n+2) \times (m-n+2)$.
• The denominator now gets cleared by the additional multiplication of $\det(D)$.
• Hence, we can have a matrix $N$ that is givey by $(A-BD^{-1}C) \det(D)$ that has entries of degree at most $n-1$.
• Let $\det(D)=1+Q$.
• Then we can write $\det(M) (1+Q)^{m-n+2} = \det(N) (1+Q)$ where $N$ is the matrix $A-BD^{-1}C$ multiplied every entry with $1+Q$.
  • This follows from the dimension of $A-BD^{-1}C$.
• Simplifying further gives us $(\sum_{i=1}^n x_i^n)(1+Q)^{m-n+1} = \det(N)$.
  • Using the fact that $\det(M)=f$.
• This gives us the bound, provided we show that the constant part of $N$ at position $0,0$ is zero and one on the diagonal.
• I am skipping this part.