TR24-125 Authors: Pavel Hrubes, Pushkar Joglekar

Publication: 28th July 2024 12:36

Downloads: 175

Keywords:

We consider read-$k$ determinantal representations of polynomials and prove some non-expressibility results. A square matrix $M$ whose entries are variables or field elements will be called \emph{read-$k$}, if every variable occurs at most $k$ times in $M$. It will be called a \emph{determinantal representation} of a polynomial $f$ if $f=\det(M)$. We show that

\begin{itemize}

\item the $n \times n$ permanent polynomial does not have a read-$k$ determinantal representation for $k \in o({\sqrt{n}}/\log n)$ (over a field of characteristic different from two).

\end{itemize}

We also obtain a quantitative strengthening of this result by giving a similar non-expressibility for $k\in o(\sqrt{n}/\log n)$ for an explicit \emph{$n$-variate} multilinear polynomial (as opposed to the permanent which is $n^2$-variate).