Computational complexity of immanents and representations of the full linear group (Q919059)

Let \(A=(a_{ij})\) be a complex \(n\times n\) matrix, \(\chi\)- a character of a complex irreducible representation of the symmetric group \(S_ n\). The number \[ d_{\chi}(A)=\sum_{\sigma \in S_ n}\chi (\sigma)\prod^{n}_{i=1}a_{i,\sigma (i)} \] is called the immanent of A corresponding to \(\chi\). There exists an algorithm for calculating \(d_{\chi}(A)\) such that its complexity is not greater than \(Cn^ 3\dim^ 4\pi_{\chi}\), where the constant C is absolute.