publication . Article . Other literature type . Preprint . 2017

Tensor rank is not multiplicative under the tensor product

Matthias Christandl; Asger Kjaerulff Jensen; Jeroen Zuiddam;
Open Access English
  • Published: 25 May 2017
  • Country: Netherlands
Abstract
Abstract The tensor rank of a tensor t is the smallest number r such that t can be decomposed as a sum of r simple tensors. Let s be a k -tensor and let t be an l -tensor. The tensor product of s and t is a ( k + l ) -tensor. Tensor rank is sub-multiplicative under the tensor product. We revisit the connection between restrictions and degenerations. A result of our study is that tensor rank is not in general multiplicative under the tensor product. This answers a question of Draisma and Saptharishi. Specifically, if a tensor t has border rank strictly smaller than its rank, then the tensor rank of t is not multiplicative under taking a sufficiently hight tensor ...
Persistent Identifiers
Subjects
free text keywords: Algebraic complexity theory, Border rank, Degeneration, Quantum information theory, Tensor rank, Young flattening, Mathematics - Commutative Algebra, Computer Science - Computational Complexity, Quantum Physics, 15A69, Geometry and Topology, Algebra and Number Theory, Numerical Analysis, Discrete Mathematics and Combinatorics, Tensor contraction, Tensor (intrinsic definition), Cartesian tensor, Tensor product of algebras, Tensor product, Tensor product of Hilbert spaces, Symmetric tensor, Mathematics, Tensor density, Combinatorics
Funded by
NWO| Quantum Position-Based Cryptography
Project
  • Funder: Netherlands Organisation for Scientific Research (NWO) (NWO)
  • Project Code: 2300171798
,
EC| QMULT
Project
QMULT
Multipartite Quantum Information Theory
  • Funder: European Commission (EC)
  • Project Code: 337603
  • Funding stream: FP7 | SP2 | ERC

Alexander Alder. Grenzrang und Grenzkomplexität aus algebraischer und topologischer Sicht. PhD thesis, Zürich University, 1984.

[Sch81] [Str69] [Str83] [Str87] [Str88] [Str91] [Win71] Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity 3.0.2, 2016. Online survey, https://github.com/dasarpmar/lowerbounds-survey.

SIAM J. Comput., 10(3):434-455, 1981.

Math., 13(4):354-356, 1969.

Volker Strassen. Rank and optimal computation of generic tensors. Linear Algebra Appl., 52/53:645-685, 1983. [OpenAIRE]

Volker Strassen. Relative bilinear complexity and matrix multiplication. J. Reine Angew. Math., 375/376:406-443, 1987.

Volker Strassen. The asymptotic spectrum of tensors. J. Reine Angew. Math., 384:102-152, 1988.

Volker Strassen. Degeneration and complexity of bilinear maps: some asymptotic spectra. J. Reine Angew. Math., 413:127-180, 1991.

Shmuel Winograd. On multiplication of 2 2 matrices. Linear Algebra Appl., 4(4):381-388, 1971. [OpenAIRE]

[YCGD10] Nengkun Yu, Eric Chitambar, Cheng Guo, and Runyao Duan.

Tensor rank of the tripartite state W tensor n. Phys. Rev. A, 81(1):014301, 2010.

[Zui17] Jeroen Zuiddam. A note on the gap between rank and border rank. Linear Algebra Appl., 525:33-44, 2017. [OpenAIRE]

Abstract
Abstract The tensor rank of a tensor t is the smallest number r such that t can be decomposed as a sum of r simple tensors. Let s be a k -tensor and let t be an l -tensor. The tensor product of s and t is a ( k + l ) -tensor. Tensor rank is sub-multiplicative under the tensor product. We revisit the connection between restrictions and degenerations. A result of our study is that tensor rank is not in general multiplicative under the tensor product. This answers a question of Draisma and Saptharishi. Specifically, if a tensor t has border rank strictly smaller than its rank, then the tensor rank of t is not multiplicative under taking a sufficiently hight tensor ...
Persistent Identifiers
Subjects
free text keywords: Algebraic complexity theory, Border rank, Degeneration, Quantum information theory, Tensor rank, Young flattening, Mathematics - Commutative Algebra, Computer Science - Computational Complexity, Quantum Physics, 15A69, Geometry and Topology, Algebra and Number Theory, Numerical Analysis, Discrete Mathematics and Combinatorics, Tensor contraction, Tensor (intrinsic definition), Cartesian tensor, Tensor product of algebras, Tensor product, Tensor product of Hilbert spaces, Symmetric tensor, Mathematics, Tensor density, Combinatorics
Funded by
NWO| Quantum Position-Based Cryptography
Project
  • Funder: Netherlands Organisation for Scientific Research (NWO) (NWO)
  • Project Code: 2300171798
,
EC| QMULT
Project
QMULT
Multipartite Quantum Information Theory
  • Funder: European Commission (EC)
  • Project Code: 337603
  • Funding stream: FP7 | SP2 | ERC

Alexander Alder. Grenzrang und Grenzkomplexität aus algebraischer und topologischer Sicht. PhD thesis, Zürich University, 1984.

[Sch81] [Str69] [Str83] [Str87] [Str88] [Str91] [Win71] Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity 3.0.2, 2016. Online survey, https://github.com/dasarpmar/lowerbounds-survey.

SIAM J. Comput., 10(3):434-455, 1981.

Math., 13(4):354-356, 1969.

Volker Strassen. Rank and optimal computation of generic tensors. Linear Algebra Appl., 52/53:645-685, 1983. [OpenAIRE]

Volker Strassen. Relative bilinear complexity and matrix multiplication. J. Reine Angew. Math., 375/376:406-443, 1987.

Volker Strassen. The asymptotic spectrum of tensors. J. Reine Angew. Math., 384:102-152, 1988.

Volker Strassen. Degeneration and complexity of bilinear maps: some asymptotic spectra. J. Reine Angew. Math., 413:127-180, 1991.

Shmuel Winograd. On multiplication of 2 2 matrices. Linear Algebra Appl., 4(4):381-388, 1971. [OpenAIRE]

[YCGD10] Nengkun Yu, Eric Chitambar, Cheng Guo, and Runyao Duan.

Tensor rank of the tripartite state W tensor n. Phys. Rev. A, 81(1):014301, 2010.

[Zui17] Jeroen Zuiddam. A note on the gap between rank and border rank. Linear Algebra Appl., 525:33-44, 2017. [OpenAIRE]

Any information missing or wrong?Report an Issue