Bilinear rank of rectangular matrix multiplication
To multiply an a-by-b matrix by a b-by-c matrix, a bilinear algorithm multiplies linear combinations of entries from the two inputs. What is the fewest such products needed for each shape over the rationals?
Why it matters and what counts as progress
Why it matters: Small rectangular products are building blocks for larger algorithms. A lower rank counts fewer scalar multiplications for that shape.
What counts as progress: An upper bound needs an explicit bilinear scheme and an identity valid for every input. Lower bounds rule out all schemes below a stated rank. The number of additions is a separate measure.
How the problem developed
A. I. Perminov and the Lille catalogue Recorded schemes with 644 and 710 products for the two matrix shapes discussed here.
Arhan Canli and Claude agents Gave a 640-product scheme for the by format and checked the identities in Lean.
Arhan Canli and Claude agents Gave a 708-product scheme for the by format and checked the identities in Lean.
AI contributions 2
Multiplying by matrices with 708 multiplications
Canli gives an exact rank-at-most-708 bilinear scheme for the by matrix product over the rationals. The formal proof also gives a bilinear algorithm over every field of characteristic zero.
Multiplying by matrices with 640 multiplications
Canli gives an exact rank-at-most-640 bilinear scheme for the by matrix product over the rationals. The formal proof also gives a bilinear algorithm over every field of characteristic zero.
Sources
Publication history
Daily emails by default, only when there’s an update.