Complexity of matrix problems
From MaRDI portal
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.
Recommendations
Cites work
- Application of modules over a dyad for the classification of finite \(p\)-groups possessing an Abelian subgroup of index \(p\) and of pairs of mutually annihilating operators
- Canonical matrices for linear matrix problems
- CLASSIFICATION PROBLEMS FOR SYSTEMS OF FORMS AND LINEAR MAPPINGS
- scientific article; zbMATH DE number 3138903 (Why is no real title available?)
- scientific article; zbMATH DE number 3179506 (Why is no real title available?)
- scientific article; zbMATH DE number 3715764 (Why is no real title available?)
- scientific article; zbMATH DE number 3767869 (Why is no real title available?)
- scientific article; zbMATH DE number 42721 (Why is no real title available?)
- scientific article; zbMATH DE number 3460441 (Why is no real title available?)
- scientific article; zbMATH DE number 3475514 (Why is no real title available?)
- scientific article; zbMATH DE number 3218902 (Why is no real title available?)
- scientific article; zbMATH DE number 3278303 (Why is no real title available?)
- Indecomposable representations
- Normal forms in matrix spaces
- On classification of normal matrices in an indefinite scalar product
- PARTIALLY ORDERED SETS OF INFINITE TYPE
- Representation of partially ordered sets
- REPRESENTATIONS OF QUIVERS OF INFINITE TYPE
- Simultaneous similarity of matrices
- Unitary and Euclidean representations of a quiver
- Unzerlegbare Darstellungen. I. (Indecomposable representations. I)
Cited in
(56)- Computational complexity of problems in classification according to a relation matrix
- Complexities of special matrix multiplication problems
- The matrix multidisk problem
- Computation of canonical matrices for chains and cycles of linear mappings.
- Canonical matrices for linear matrix problems
- Wildness for tensors
- Identifying complexity by means of matrices
- Systems of subspaces of a unitary space
- A framework for Coxeter spectral classification of finite posets and their mesh geometries of roots.
- Matrix rank and communication complexity
- Isometric and selfadjoint operators on a vector space with nondegenerate diagonalizable form
- A finite-tame-wild trichotomy theorem for tensor diagrams
- Congruence of matrix spaces, matrix tuples, and multilinear maps
- Pairs of commuting nilpotent operators with one-dimensional intersection of kernels and matrices commuting with a Weyr matrix
- On the structure of loop-free non-negative edge-bipartite graphs
- Operators on positive semidefinite inner product spaces
- Rigid systems of second-order linear differential equations
- Wildness of the problems of classifying two-dimensional spaces of commuting linear operators and certain Lie algebras
- Length realizability for pairs of quasi-commuting matrices
- Wildness of the problem of classifying nilpotent Lie algebras of vector fields in four variables
- Lipschitz property for systems of linear mappings and bilinear forms
- One-peak posets with positive quadratic Tits form, their mesh translation quivers of roots, and programming in Maple and Python
- Combinatorial Hopf algebra of superclass functions of type \(D\).
- Canonical matrices of isometric operators on indefinite inner product spaces
- Normal form of \(m\)-by-\(n\)-by-2 matrices for equivalence
- Problems of classifying associative or Lie algebras and triples of symmetric or skew-symmetric matrices are wild
- On the fraction of matrices with maximal additive complexity
- On equivalence of matrices over commutative rings
- Canonical forms for unitary congruence and *congruence
- Classification problem for graphs and lattices is wild.
- On combinatorial algorithms computing mesh root systems and matrix morsifications for the Dynkin diagram \(\mathbb A_n\)
- Remarks on the classification of a pair of commuting semilinear operators
- Topological classification of chains of linear mappings
- Non-degenerate 2\times k\times (k+1) hypermatrices
- Structure and a Coxeter-Dynkin type classification of corank two non-negative posets.
- On Borel complexity of the isomorphism problems for graph related classes of Lie algebras and finite p-groups
- On the problem of classifying solvable Lie algebras having small codimensional derived algebras
- Specht's criterion for systems of linear mappings
- A canonical form for nonderogatory matrices under unitary similarity
- The problems of classifying pairs of forms and local algebras with zero cube radical are wild.
- On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
- Three-equipped posets and their representations and corepresentations (inseparable case).
- Centers of multilinear forms and applications
- The separating variety for 2 × 2 matrix invariants
- Admissible transformations and Lie symmetries of linear systems of second-order ordinary differential equations
- Steady growth of length function and Malcev algebras
- On decompositions and transitive actions of nilpotent Lie groups
- Tensor decompositions with applications to local unitary and stochastic local operations and classical communication equivalence of multipartite pure states
- On rank one 2-representations of web categories
- Tensor rank and complexity
- Classification of \(\operatorname{G}_2\)-orbits for pairs of octonions
- Auerbach bases, projection constants, and the joint spectral radius of principal submatrices
- Canonical form of m-by-2-by-2 matrices over a field of characteristic other than two
- Complexity measures of sign matrices
- Pairs of mutually annihilating operators
- Integral bilinear forms, Coxeter transformations and Coxeter polynomials of finite posets
This page was built for publication: Complexity of matrix problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1863557)
