Computational complexity of immanents and representations of the full linear group
type: Item
instance of: scholarly article
title: Computational complexity of immanents and representations of the full linear group
zbMATH Open document ID: 0706.15007
DOI: 10.1007/BF01077707
publication date: 1990-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 4158839
zbMATH Keywords: character
zbMATH Keywords: complex irreducible representation
zbMATH Keywords: symmetric group
zbMATH Keywords: immanent
zbMATH Keywords: algorithm
zbMATH Keywords: complexity
author: Alexander Barvinok
MaRDI profile type: Publication
cites work: On the complexity of immanants
cites work: Q3952291
Recommended article: The Computational Complexity to Evaluate Representations of General Linear Groups
Recommended article: Q4888936
Recommended article: Complexity and computation in matrix groups.
Recommended article: Q4012094
Recommended article: On the complexity of computation in finite Abelian, nilpotent and soluble groups
Recommended article: Computing Irreducible Representations of Finite Groups
Recommended article: Q4005480
Recommended article: On the computational complexity of the theory of Abelian groups
Recommended article: Q4517198
Recommended article: Q4011250
published in: Functional Analysis and Its Applications
description: scientific article; zbMATH DE number 4158839