Complexity of matrix problems

Abstract

In representation theory, the problem of classifying pairs of matrices up to simultaneous similarity is used as a measure of complexity; classification problems containing it are called wild problems. We show in an explicit form that this problem contains all classification matrix problems given by quivers or posets. Then we prove that it does not contain (but is contained in) the problem of classifying three-valent tensors. Hence, all wild classification problems given by quivers or posets have the same complexity; moreover, a solution of any one of these problems implies a solution of each of the others. The problem of classifying three-valent tensors is more complicated.

24 pages

References in corpus (3)

• Canonical matrices for linear matrix problems
• Classification problems for system of forms and linear mappings
• Unitary and Euclidean representations of a quiver

Cited by in corpus (27)

• Systems of subspaces of a unitary space
• Computation of the canonical form for the matrices of chains and cycles of linear mappings
• Problems of classifying associative or Lie algebras and triples of symmetric or skew-symmetric matrices are wild
• Canonical Forms for Unitary Congruence and *Congruence
• Canonical matrices of isometric operators on indefinite inner product spaces
• Wildness for tensors
• The problems of classifying pairs of forms and local algebras with zero cube radical are wild
• Pairs of mutually annihilating operators
• Representations of quivers and mixed graphs
• Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions
• Specht's criterion for systems of linear mappings
• A canonical form for nonderogatory matrices under unitary similarity
• Classification of the Entangled states L\times N\times N
• Remarks on the classification of a pair of commuting semilinear operators
• Wildness of the problems of classifying two-dimensional spaces of commuting linear operators and certain Lie algebras
• Congruence of matrix spaces, matrix tuples, and multilinear maps
• Admissible transformations and Lie symmetries of linear systems of second-order ordinary differential equations
• Topological classification of chains of linear mappings
• Isometric and selfadjoint operators on a vector space with nondegenerate diagonalizable form
• Canonical form of m-by-2-by-2 matrices over a field of characteristic other than two
• Pairs of commuting nilpotent operators with one-dimensional intersection of kernels and matrices commuting with a Weyr matrix
• Operators on positive semidefinite inner product spaces
• Rigid systems of second-order linear differential equations
• Lipschitz property for systems of linear mappings and bilinear forms
• Classification of G_2-orbits for pairs of octonions
• On rank one 2-representations of web categories
• Tensor decompositions with applications to LU and SLOCC equivalence of multipartite pure states