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

Istvan Miklos, Cordian Riener

#P-hardness of computing matrix immanants are proved for each member of a broad class of shapes and restricted sets of matrices. The class is characterized in the following way. If a shape of size $n$ in it is in form $(w,\mathbf{1}+\lambda)$ or its conjugate is in that form, where $\mathbf{1}$ is the all-$1$ vector, then $|\lambda|$ is $n^{\varepsilon}$ for some $0<\varepsilon$, $\lambda$ can be tiled with $1\times 2$ dominos and $(3w+3h(\lambda)+1)|\lambda| \le n$, where $h(\lambda)$ is the height of $\lambda$. The problem remains \#P-hard if the immanants are evaluated on $0$-$1$ matrices. We also give hardness proofs of some immanants whose shape $\lambda = (\mathbf{1}+\lambda_d)$ has size $n$ such that $|\lambda_d| = n^{\varepsilon}$ for some $0<\varepsilon<\frac{1}{2}$, and for some $w$, the shape $\lambda_d/(w)$ is tilable with $1\times 2$ dominos. The \#P-hardness result holds when these immanants are evaluated on adjacency matrices of planar, directed graphs, however, in these cases the edges have small positive integer weights.

Knowledge Graph



Sign up or login to leave a comment