The border rank of the matrix multiplication operator for n × n matrices is a standard measure of its complexity. Using techniques from algebraic geometry and representation theory, we show the border rank is at least 2n^2 − n. Our bounds are better than the previous lower bound (due to Lickteig in 1985) of 3n^2 /2 + n/2 − 1 for all n ≥ 3. The bounds are obtained by finding new equations that bilinear maps of small border rank must satisfy, i. e., new equations for secant varieties of triple Segre products, that matrix multiplication fails to satisfy.
New lower bounds for the border rank of matrix multiplication / Landsberg, J.M. ; Ottaviani, Giorgio. - In: THEORY OF COMPUTING. - ISSN 1557-2862. - ELETTRONICO. - 11:(2015), pp. 285-298. [10.4086/toc.2015.v011a011]
New lower bounds for the border rank of matrix multiplication
OTTAVIANI, GIORGIO MARIA
2015
Abstract
The border rank of the matrix multiplication operator for n × n matrices is a standard measure of its complexity. Using techniques from algebraic geometry and representation theory, we show the border rank is at least 2n^2 − n. Our bounds are better than the previous lower bound (due to Lickteig in 1985) of 3n^2 /2 + n/2 − 1 for all n ≥ 3. The bounds are obtained by finding new equations that bilinear maps of small border rank must satisfy, i. e., new equations for secant varieties of triple Segre products, that matrix multiplication fails to satisfy.
| File | Dimensione | Formato | |
|---|---|---|---|
|
LOToCfinal.pdf
accesso aperto
Descrizione: Articolo principale
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Creative commons
Dimensione
253.03 kB
Formato
Adobe PDF
|
253.03 kB | Adobe PDF |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
