#P-hardness proofs of matrix immanants evaluated on restricted matrices

Abstract

We establish the $\#P$-hardness of computing a broad class of immanants, even when restricted to specific categories of matrices. Concretely, we prove that computing $\lambda$-immanants of $0$-$1$ matrices is $\#P$-hard whenever the partition~$\lambda$ contains a sufficiently large domino-tileable region, subject to certain technical conditions. We also give hardness proofs for some $\lambda$-immanants of weighted adjacency matrices of planar directed graphs, such that the shape $\lambda =(1+{\lambda }_d)$ has size $n$ such that $|{\lambda }_d|=n^{\epsilon }$ for some $0<\epsilon <\frac{1}{2}$, and such that for some $w$, the shape ${\lambda }_d/(w)$ is tileable with $1\times 2$ dominos.

Accepted for publication at Theoretical Computer Science