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 (6)

• 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 matrices of isometric operators on indefinite inner product spaces
• The problems of classifying pairs of forms and local algebras with zero cube radical are wild
• Canonical form of m-by-2-by-2 matrices over a field of characteristic other than two
• Rigid systems of second-order linear differential equations