Lower bounds established for tensor rank in specific matrix multiplication

New lower bounds on tensor rank of $(2,n,m)$ matrix multiplication with GPT-6

Computational Complexity

Summary

Matrix multiplication is a basic math operation used in many computer algorithms, and understanding its complexity helps improve computing efficiency. The authors studied how complicated multiplying a 2-by-n matrix with an n-by-m matrix can get, measured by a concept called tensor rank. They found new minimum complexity levels for this multiplication kind, providing stronger limits than before, applicable for any field of numbers. This helps clarify how hard the problem really is in general.

What this means in practice

  • For algorithm designers: Rule out certain computational shortcuts for matrix multiplications involving 2-by-n and n-by-m dimensions based on new complexity limits.
  • For hardware architects: Inform hardware design decisions by understanding inherent lower bounds on matrix multiplication complexity for specific input sizes.

A theory result. No direct application yet.

Authors

Jason Yang

Abstract

The tensor rank of $2\times n$-with-$n\times m$ matrix multiplication is at least $(n+2)m$ if $n\ge 4$ and at least $\left\lceil \frac{24}{5}m \right\rceil$ if $n=3$. Both lower bounds apply over arbitrary fields.
View PDFOpen arXiv