Open MathsAll courses

Tensors, rank and the exponent

Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).

The exponent of matrix multiplication \(\omega\) is the infimum of the real numbers \(\tau\) such that, for every \(\varepsilon>0\), two \(n\times n\) complex matrices can be multiplied with \(O(n^{\tau+\varepsilon})\) arithmetic operations. The schoolbook method gives \(\omega\le3\). Strassen multiplied \(2\times2\) matrices with seven multiplications; applied recursively, this gives \(\omega\le\log_27<2.81\). Approximate algorithms, Schönhage's asymptotic sum inequality and Strassen's laser method lowered the bound further; Bläser's survey [Bl] explains these tools. Refinements of the laser method reached \(\omega<2.371177\) in August 2026 [DEK+]. OpenAI proved \(\omega\le9/4\) [OpenAI-MM] by a different route: Strassen's characters of tensors are bounded on matrix multiplication through two inequalities for polynomial multiplication. This course gives a complete proof (Theorem A below). OpenAI's companion papers on the bound \(\omega<2.258\) in characteristic zero and on bounds over every field [OpenAI-MM2] are not treated.

The theorem

An arithmetic operation is an addition, a subtraction or a multiplication of two complex numbers; multiplication by a fixed constant counts as one operation.

Theorem A. For every \(\varepsilon>0\) there is a constant \(C_\varepsilon\) such that, for every \(n\ge1\), two \(n\times n\) complex matrices can be multiplied with at most \(C_\varepsilon n^{9/4+\varepsilon}\) arithmetic operations. Thus \(\omega\le9/4\).

The proof goes through the rank of tensors. Section 3 defines the exponent \(\nu\) of the rank of matrix multiplication, and Proposition 1.10 turns every bound \(\nu\le\tau\) into algorithms with \(O(n^{\tau+\varepsilon})\) operations. The course proves \(\nu\le9/4\) (Theorem 7.4).

The field. Throughout the course, \(F\) is the subfield of \(\mathbf C\) generated by all roots of unity. It is the union of the increasing sequence of fields \(\mathbf Q(e^{2\pi i/n!})\), each a finite-dimensional vector space over \(\mathbf Q\), so \(F\) is countable. Lessons 1 to 5 use only that \(F\) has characteristic zero and contains a primitive \(L\)-th root of unity for every \(L\ge1\). Countability enters in Lesson 6, where it makes a space of functions on tensors metrizable. A rank decomposition with coefficients in \(F\) is in particular one with complex coefficients, so working over \(F\) gives the stronger statement.

1. Tensors and restriction

Definition 1.1. A tensor is a trilinear form \[ A=\sum_{i\in I}\sum_{j\in J}\sum_{k\in K}c_{ijk}\,x_iy_jz_k \] with finite index sets \(I,J,K\) and coefficients \(c_{ijk}\in F\). The variables \(x_i\), \(y_j\), \(z_k\) form the three legs of \(A\): the \(X\)-leg, the \(Y\)-leg and the \(Z\)-leg. Let \(A'\) be a second tensor, in variables \(x'_{i'}\), \(y'_{j'}\), \(z'_{k'}\). Then \(A'\) is a restriction of \(A\), written \(A\ge A'\) or \(A'\le A\), if there are linear forms \(\varphi_i\) in the variables \(x'\), \(\psi_j\) in the variables \(y'\) and \(\chi_k\) in the variables \(z'\) such that the substitution \(x_i=\varphi_i\), \(y_j=\psi_j\), \(z_k=\chi_k\) turns \(A\) into \(A'\).

Two substitutions in succession form a substitution, so \(\ge\) is reflexive and transitive. Renaming variables produces an isomorphic tensor, \(A\cong A'\); isomorphic tensors are restrictions of each other. Adding variables that occur in no term, or removing them, produces a tensor that is a restriction of the original and has it as a restriction. A tensor all of whose coefficients vanish is written \(0\); it is a restriction of every tensor. The unit tensor is \(1=xyz\), with one variable on each leg.

The direct sum \(A\oplus A'\) is the sum of the two forms, with disjoint variables on each leg. The tensor product \(A\otimes A'\), also written \(AA'\), has variables \(x_{(i,i')}\), \(y_{(j,j')}\), \(z_{(k,k')}\): \[ A\otimes A'=\sum c_{ijk}\,c'_{i'j'k'}\,x_{(i,i')}\,y_{(j,j')}\,z_{(k,k')}, \] summed over all six indices, where \(c'\) are the coefficients of \(A'\). For an integer \(m\ge0\), the letter \(m\) also denotes the direct sum of \(m\) unit tensors, \(m=\sum_{l=1}^mx_ly_lz_l\).

Lemma 1.2. (a) Up to isomorphism, \(\oplus\) and \(\otimes\) are commutative and associative, \(\otimes\) distributes over \(\oplus\), \(A\oplus0\cong A\), \(A\otimes1\cong A\) and \(A\otimes0=0\). In particular \(m\otimes A\) is isomorphic to the direct sum of \(m\) copies of \(A\).

(b) If \(A\ge A'\) and \(U\ge U'\), then \(A\oplus U\ge A'\oplus U'\) and \(A\otimes U\ge A'\otimes U'\).

(c) \(A\oplus U\ge A\).

(d) Every nonzero tensor \(A\) satisfies \(A\ge1\).

Proof. (a) In each case the terms of the two sides correspond after renaming variables; for the commutativity of \(\otimes\), rename \(x_{(i,i')}\) as \(x_{(i',i)}\), and similarly on the other legs.

(b) For the direct sum, apply the two substitutions to the two sets of variables. For the tensor product, suppose \(x_i=\sum_a\varphi_{ia}x'_a\) is part of the substitution for \(A\) and \(x_{i'}=\sum_{a'}\varphi'_{i'a'}x'_{a'}\) part of the one for \(U\). Substitute \[ x_{(i,i')}=\sum_{a,a'}\varphi_{ia}\varphi'_{i'a'}\,x'_{(a,a')}, \] and similarly on the other legs. By multilinearity the result is \(A'\otimes U'\).

(c) Substitute \(0\) for the variables of \(U\).

(d) Choose \(c_{ijk}\ne0\). Substitute \(x_i=c_{ijk}^{-1}x\), \(y_j=y\), \(z_k=z\), and \(0\) for all other variables. \(\square\)

The semiring \(S\). Call \(A\) and \(A'\) equivalent if \(A\ge A'\) and \(A'\ge A\). By Lemma 1.2(b), direct sum and tensor product pass to equivalence classes. Write \(S\) for the set of classes, \(A+U\) and \(AU\) for the induced operations, and use the same letter for a tensor and its class. With the classes of \(0\) and \(1\), \(S\) is a commutative semiring by Lemma 1.2(a); \(\ge\) is a partial order on \(S\), and \(A\ge A'\) implies \(A+U\ge A'+U\) and \(AU\ge A'U\). The class of the tensor \(m\) is \(m\cdot1\), and \(mA=A+\dots+A\) with \(m\) summands.

Tensors of bilinear maps. Let \(\beta:U\times V\to W\) be a bilinear map of finite-dimensional vector spaces over \(F\), and choose bases \((e_i)_{i\in I}\), \((f_j)_{j\in J}\), \((g_k)_{k\in K}\). Write \(\beta(e_i,f_j)=\sum_kc_{ijk}g_k\). The tensor \(\sum c_{ijk}x_iy_jz_k\) is the tensor of \(\beta\) in these bases: \(x\) and \(y\) are the coordinates of the two inputs, and \(z_k\) is paired with the \(k\)-th coordinate of the output.

Lemma 1.3. (a) The tensors of \(\beta\) in two choices of bases are equivalent.

(b) If \(A\) and \(A'\) are the tensors of \(\beta\) and \(\beta'\) in some bases, then \(A\otimes A'\) is the tensor of the bilinear map \(\beta\otimes\beta'\) from \((U\otimes U')\times(V\otimes V')\) to \(W\otimes W'\), determined by \((u\otimes u',v\otimes v')\mapsto\beta(u,v)\otimes\beta'(u',v')\), in the product bases.

Proof. (a) Change the bases of \(V\) and \(W\); a change of the basis of \(U\) is handled like that of \(V\). Let \(f'_{j'}=\sum_jQ_{jj'}f_j\) and \(g'_{k'}=\sum_kP_{kk'}g_k\) with invertible matrices \(Q\) and \(P\). Write \(w_k(x,y)\) for the \(g_k\)-coordinate of \(\beta(\sum_ix_ie_i,\sum_jy_jf_j)\), so that \(A=\sum_kz_kw_k(x,y)\). The vector \(\sum_{j'}y'_{j'}f'_{j'}\) has the coordinates \((Qy')_j=\sum_{j'}Q_{jj'}y'_{j'}\) in the basis \((f_j)\), and the \(g'\)-coordinates of a vector are \(P^{-1}\) applied to its \(g\)-coordinates. Hence the tensor of \(\beta\) in the new bases is \[ A'=\sum_k\Bigl(\sum_{k'}(P^{-1})_{k'k}z'_{k'}\Bigr)w_k(x,Qy'). \] It arises from \(A\) by the substitution \(y_j=(Qy')_j\) and \(z_k=\sum_{k'}(P^{-1})_{k'k}z'_{k'}\), so \(A\ge A'\). Exchanging the roles of the two choices of bases gives \(A'\ge A\).

(b) The map \(\beta\otimes\beta'\) sends \((e_i\otimes e'_{i'},f_j\otimes f'_{j'})\) to \(\sum_{k,k'}c_{ijk}c'_{i'j'k'}\,g_k\otimes g'_{k'}\), which is the coefficient pattern of \(A\otimes A'\). \(\square\)

Permuting legs. For a permutation \(\pi\) of the three legs, \(\pi A\) is the tensor obtained from \(A\) by moving the variables of each leg \(\ell\) to the leg \(\pi(\ell)\). Then \(\pi(A\oplus U)=\pi A\oplus\pi U\), \(\pi(A\otimes U)=\pi A\otimes\pi U\), \(\pi1\cong1\), \(A\ge A'\) implies \(\pi A\ge\pi A'\), and \(\pi(\pi'A)=(\pi\pi')A\). So each \(\pi\) acts on \(S\) by an automorphism of ordered semirings.

2. Rank and flattening ranks

The rank \(R(A)\) of a tensor \(A\) is the least integer \(m\ge0\) with \(m\ge A\). By the definition of restriction, \(R(A)\le m\) means that \[ A=\sum_{l=1}^m\varphi_l\,\psi_l\,\chi_l, \] a sum of \(m\) products of a linear form \(\varphi_l\) in the variables \(x\), a linear form \(\psi_l\) in the \(y\) and a linear form \(\chi_l\) in the \(z\). Expanding \(A\) term by term shows that \(R(A)\) is at most the number of nonzero coefficients of \(A\).

Lemma 1.4. If \(A\ge A'\), then \(R(A)\ge R(A')\); hence \(R\) is constant on equivalence classes. Moreover \(R(A\oplus U)\le R(A)+R(U)\), \(R(A\otimes U)\le R(A)R(U)\) and \(R(\pi A)=R(A)\).

Proof. If \(m\ge A\ge A'\), then \(m\ge A'\). If \(m\ge A\) and \(n\ge U\), then \(m+n\ge A\oplus U\) and \(mn\cong m\otimes n\ge A\otimes U\) by Lemma 1.2. Finally \(\pi m\cong m\). \(\square\)

The \(X\)-flattening of \(A\) is the matrix with rows indexed by \(I\), columns indexed by \(J\times K\), and entries \(c_{i,(j,k)}=c_{ijk}\). Its rank is \(\rho_X(A)\). The numbers \(\rho_Y(A)\) and \(\rho_Z(A)\) are defined in the same way, with the \(Y\)-leg or the \(Z\)-leg placed against the other two.

Lemma 1.5. Each of \(\rho_X\), \(\rho_Y\), \(\rho_Z\) is monotone (\(A\ge A'\) implies \(\rho(A)\ge\rho(A')\)), additive on direct sums, multiplicative on tensor products, equal to \(1\) at the unit tensor, and at most \(R\).

Proof. We treat \(\rho_X\) and write \(M_A\) for the \(X\)-flattening. Suppose \(A'\) arises from \(A\) by the substitution \(x_i=\sum_{i'}\varphi_{ii'}x'_{i'}\), \(y_j=\sum_{j'}\psi_{jj'}y'_{j'}\), \(z_k=\sum_{k'}\chi_{kk'}z'_{k'}\). The coefficients of \(A'\) are \[ c'_{i'j'k'}=\sum_{i,j,k}c_{ijk}\,\varphi_{ii'}\psi_{jj'}\chi_{kk'}, \] so \(M_{A'}=\Phi^{\mathsf T}M_AN\), where \(\Phi=(\varphi_{ii'})\) and \(N\) is the matrix with the entry \(\psi_{jj'}\chi_{kk'}\) in row \((j,k)\) and column \((j',k')\). The rank of a product is at most the rank of each factor, so \(\rho_X(A')\le\rho_X(A)\).

In the flattening of \(A\oplus U\), a nonzero entry has its row and its column both from \(A\) or both from \(U\). After reordering, the matrix is block diagonal with the blocks \(M_A\) and \(M_U\), and some zero columns; so the ranks add.

The flattening of \(A\otimes U\) is the Kronecker product \(M_A\otimes M_U\), after reordering the columns. Its columns are the vectors \(a\otimes b\) with \(a\) a column of \(M_A\) and \(b\) a column of \(M_U\). They span the tensor product of the column spaces, whose dimension is \(\rho_X(A)\rho_X(U)\).

The flattening of \(1\) is the \(1\times1\) matrix \((1)\). By additivity \(\rho_X(m)=m\); if \(m\ge A\), monotonicity gives \(\rho_X(A)\le m\). Thus \(\rho_X(A)\le R(A)\). \(\square\)

3. Matrix multiplication and the exponent

The matrix multiplication tensor is \[ T_n=\sum_{i,j,k=1}^nx_{ij}\,y_{jk}\,z_{ki}. \] It is the tensor of the multiplication \(F^{n\times n}\times F^{n\times n}\to F^{n\times n}\) in the bases of matrix units, with \(z_{ki}\) paired with the \((i,k)\) entry of the product: the product of the matrix units \(E_{ij}\) and \(E_{j'k}\) is \(E_{ik}\) if \(j=j'\) and \(0\) otherwise.

Lemma 1.6. (a) \(T_n\otimes T_m\cong T_{nm}\).

(b) \(\rho_X(T_n)=\rho_Y(T_n)=\rho_Z(T_n)=n^2\), and \(n^2\le R(T_n)\le n^3\).

(c) \(T_n\ge n\).

Proof. (a) The product of the terms \(x_{ij}y_{jk}z_{ki}\) and \(x_{i'j'}y_{j'k'}z_{k'i'}\) is \(x_{(ij,i'j')}y_{(jk,j'k')}z_{(ki,k'i')}\). Writing \(x_{(ij,i'j')}\) as \(x_{(i,i')(j,j')}\), and similarly on the other legs, identifies \(T_n\otimes T_m\) with \(T_{nm}\), whose indices run through \(\{1,\dots,n\}\times\{1,\dots,m\}\).

(b) In the \(X\)-flattening, the row of \(x_{ij}\) has the entry \(1\) exactly in the columns \((y_{jk},z_{ki})\), \(k=1,\dots,n\). Different rows have disjoint supports, so the \(n^2\) rows are linearly independent. A cyclic permutation of the legs maps \(T_n\) to an isomorphic tensor, which gives the other two flattenings. Lemma 1.5 gives \(R(T_n)\ge n^2\), and \(T_n\) has \(n^3\) terms.

(c) Substitute \(0\) for every variable whose two indices differ. A term \(x_{ij}y_{jk}z_{ki}\) survives exactly when \(i=j=k\), and the surviving terms \(x_{ii}y_{ii}z_{ii}\) form a tensor isomorphic to \(n\). \(\square\)

Definition. The exponent of rank is \[ \nu=\inf_{n\ge2}\log_nR(T_n). \] By Lemma 1.6(b), \(2\le\nu\le3\), and \(R(T_n)\ge n^\nu\) for every \(n\ge1\).

Example 1.7. Strassen found seven products of linear forms whose sum is \(T_2\) (Exercise 1.1). Hence \(R(T_2)\le7\) and \(\nu\le\log_27<2.81\).

4. Polynomial multiplication and dot products

For positive integers \(a,b\) put \[ C(a,b)=\sum_{i=0}^{a-1}\sum_{j=0}^{b-1}x_i\,y_j\,z_{i+j}. \] It is the tensor of the multiplication of polynomials of degree less than \(a\) by polynomials of degree less than \(b\), in the monomial bases.

Lemma 1.8. (a) \(R(C(a,b))=\rho_Z(C(a,b))=a+b-1\), \(\rho_X(C(a,b))=a\) and \(\rho_Y(C(a,b))=b\).

(b) Exchanging the \(X\)-leg and the \(Y\)-leg of \(C(a,b)\) gives a tensor isomorphic to \(C(b,a)\).

Proof. (a) In the \(Z\)-flattening, the row of \(z_k\) has its nonzero entries in the columns \((x_i,y_{k-i})\). Each row is nonzero and different rows have disjoint supports, so \(\rho_Z(C(a,b))=a+b-1\). The rows of the \(X\)-flattening and of the \(Y\)-flattening are nonzero with disjoint supports as well, which gives \(a\) and \(b\).

For the upper bound on the rank, choose distinct \(\alpha_0,\dots,\alpha_{a+b-2}\in F\) and put \(f(\alpha)=\sum_ix_i\alpha^i\) and \(g(\alpha)=\sum_jy_j\alpha^j\). The coefficient of \(\alpha^k\) in \(f(\alpha)g(\alpha)\) is \(h_k=\sum_{i+j=k}x_iy_j\), and the values \(f(\alpha_l)g(\alpha_l)=\sum_kh_k\alpha_l^k\) determine the \(h_k\) through the inverse \(L=(L_{kl})\) of the Vandermonde matrix \((\alpha_l^k)\): \(h_k=\sum_lL_{kl}f(\alpha_l)g(\alpha_l)\). Hence \[ \begin{aligned} C(a,b)&=\sum_kz_kh_k\\ &=\sum_lf(\alpha_l)\,g(\alpha_l)\Bigl(\sum_kL_{kl}z_k\Bigr), \end{aligned} \] a sum of \(a+b-1\) products of linear forms.

(b) After the exchange the tensor is \(\sum_{i,j}y_ix_jz_{i+j}\), with \(j<b\) on the \(X\)-leg and \(i<a\) on the \(Y\)-leg; it is \(C(b,a)\) with the summation indices renamed. \(\square\)

The dot products of length \(m\) are \[ \begin{aligned} B_X(m)&=x\sum_{l=1}^my_lz_l,\\ B_Y(m)&=y\sum_{l=1}^mz_lx_l,\\ B_Z(m)&=z\sum_{l=1}^mx_ly_l. \end{aligned} \] Each has a single variable on one leg; \(B_Y(m)\) and \(B_Z(m)\) arise from \(B_X(m)\) by moving that leg. Renaming \(x_0\) as \(x\) shows \(C(1,b)\cong B_X(b)\).

Lemma 1.9. (a) \(B_X(m)\otimes B_X(n)\cong B_X(mn)\), and \(B_X(m)\ge B_X(n)\) for \(m\ge n\); the same holds for \(B_Y\) and \(B_Z\).

(b) \(R(B_X(m))=m\).

(c) \(B_X(m)\,B_Y(m)\,B_Z(m)\cong T_m\).

Proof. (a) The product has the terms \((x\otimes x)(y_l\otimes y_{l'})(z_l\otimes z_{l'})\), indexed by the pairs \((l,l')\). For \(m\ge n\), substitute \(0\) for \(y_l\) and \(z_l\) with \(l>n\).

(b) The tensor has \(m\) terms, and its \(Y\)-flattening has \(m\) nonzero rows with disjoint supports.

(c) Write the three tensors with the summation indices \(a,b,c\): \(B_X(m)=\sum_axy_az_a\), \(B_Y(m)=\sum_bx_byz_b\), \(B_Z(m)=\sum_cx_cy_cz\). Their product is \[ \sum_{a,b,c}x_{bc}\,y_{ac}\,z_{ab}, \] where \(x_{bc}\) stands for \(x\otimes x_b\otimes x_c\), and so on. Renaming \(y_{ac}\) as \(y_{ca}\) gives \(\sum x_{bc}y_{ca}z_{ab}\), which is \(T_m\) with \((i,j,k)=(b,c,a)\). \(\square\)

5. From rank to algorithms

Proposition 1.10. If \(\nu\le\tau\), then for every \(\varepsilon>0\) there is a constant \(C\) such that, for every \(n\ge1\), two \(n\times n\) complex matrices can be multiplied with at most \(Cn^{\tau+\varepsilon}\) arithmetic operations.

Proof. Let \(0<\delta<\varepsilon\). By the definition of \(\nu\) there is \(u\ge2\) with \(r=R(T_u)<u^{\tau+\delta}\), and by Lemma 1.6(b), \(r\ge u^2\). Write \(T_u=\sum_{l=1}^r\varphi_l\psi_l\chi_l\) and let \(\varphi_l[ij]\), \(\psi_l[jk]\), \(\chi_l[ki]\) be the coefficients of \(x_{ij}\), \(y_{jk}\), \(z_{ki}\) in the three linear forms. Comparing the coefficients of \(x_{i'j}y_{j'k'}z_{ki}\) on both sides gives \[ \begin{aligned} &\sum_{l=1}^r\varphi_l[i'j]\,\psi_l[j'k']\,\chi_l[ki]\\ &\qquad=[i'=i]\,[j=j']\,[k'=k], \end{aligned} \] where \([\,\cdot\,]\) is \(1\) if the condition holds and \(0\) otherwise. Let \(\mathcal R\) be an associative ring containing \(\mathbf C\) in its center, and let \(X,Y\) be \(u\times u\) matrices with entries in \(\mathcal R\). Put \(\varphi_l(X)=\sum_{i,j}\varphi_l[ij]X_{ij}\) and \(\psi_l(Y)=\sum_{j,k}\psi_l[jk]Y_{jk}\). The identity gives \[ (XY)_{ik}=\sum_{l=1}^r\chi_l[ki]\,\varphi_l(X)\,\psi_l(Y). \] Each product on the right keeps the factor coming from \(X\) on the left, so the identity holds in noncommutative rings.

Take \(\mathcal R=\mathbf C^{m\times m}\): a \(um\times um\) matrix is a \(u\times u\) matrix of \(m\times m\) blocks. Computing the \(2r\) block combinations \(\varphi_l(X)\), \(\psi_l(Y)\), the \(r\) block products, and the combinations \(\sum_l\chi_l[ki]\varphi_l(X)\psi_l(Y)\) costs at most \(c\,m^2\) operations besides the \(r\) products, for a constant \(c\) depending only on the decomposition. Let \(S(N)\) be the number of operations of the resulting recursive algorithm for \(N\times N\) matrices, \(N=u^L\). Then \(S(1)=1\) and \(S(N)\le rS(N/u)+c(N/u)^2\), so \[ S(u^L)\le r^L+c\sum_{h=0}^{L-1}r^h\,u^{2(L-1-h)}. \] If \(r>u^2\), the sum is at most \(r^{L}/(r-u^2)\), and \(S(N)\le C_1N^{\log_ur}\le C_1N^{\tau+\delta}\). If \(r=u^2\), the sum is \(cL\,u^{2(L-1)}\), and \(S(N)\le C_1N^2(1+\log N)\). For an arbitrary \(n\), choose \(L\) with \(u^{L-1}<n\le u^L\) and pad the matrices with zeros to size \(N=u^L<un\). In both cases the number of operations is at most \(Cn^{\tau+\varepsilon}\). \(\square\)

So Theorem A follows from the bound \(\nu\le9/4\), proved as Theorem 7.4.

6. The plan

Lesson 2 introduces characters: additive, multiplicative and monotone maps from \(S\) to the nonnegative reals. Each character \(\lambda\) has three exponents with \(\lambda(B_X(m))=m^{p_X}\), and so on, and \(\lambda(T_m)=m^{3t}\) with \(t=(p_X+p_Y+p_Z)/3\); characters are also monotone under degenerations. Lesson 3 separates blocks of a tensor that share one leg, which gives an entropy inequality for characters. Lesson 4 applies it to polynomial multiplication: a symmetrized profile \(P(a,b)\) of the values \(\lambda(C(a,b))\) is discretely concave and satisfies a shifted tripling inequality. Lesson 5 shows that these properties force \(P(a,a)\ge a^{4/3}\), while Lemma 1.8 gives \(P(a,a)\le(2a-1)^{1/t}\); hence \(t\le3/4\) and \(\lambda(T_d)\le d^{9/4}\) for every character. Lessons 6 and 7 prove that for every \(k<d^\nu\) some character satisfies \(\lambda(T_d)\ge k\); together with Lesson 5 this gives \(\nu\le9/4\).

7. Exercises

1.1 (medium). Check Strassen's identity: \(T_2\) is the sum of the seven products \[ \begin{aligned} &(x_{11}+x_{22})(y_{11}+y_{22})(z_{11}+z_{22}),\\ &(x_{21}+x_{22})\,y_{11}\,(z_{12}-z_{22}),\\ &x_{11}\,(y_{12}-y_{22})(z_{21}+z_{22}),\\ &x_{22}\,(y_{21}-y_{11})(z_{11}+z_{12}),\\ &(x_{11}+x_{12})\,y_{22}\,(z_{21}-z_{11}),\\ &(x_{21}-x_{11})(y_{11}+y_{12})\,z_{22},\\ &(x_{12}-x_{22})(y_{21}+y_{22})\,z_{11}. \end{aligned} \]

1.2 (easy). Write \(C(2,2)\) as a sum of three products of linear forms, using the points \(0,1,-1\) in the proof of Lemma 1.8.

1.3 (easy). Show that \(R(m)=m\), and that \(R(A)\ge\max(\rho_X(A),\rho_Y(A),\rho_Z(A))\) for every tensor \(A\).

1.4 (easy). For a permutation \(\pi\) of the legs, show that \(\pi B_X(m)\) is isomorphic to \(B_X(m)\), \(B_Y(m)\) or \(B_Z(m)\), according as \(\pi(X)\) is the \(X\)-, the \(Y\)- or the \(Z\)-leg. How many of the six permutations give each of the three tensors?

1.5 (medium). Show that \(T_n\le T_{n'}\) for \(n\le n'\), and deduce that \(\nu=\lim_{j\to\infty}\frac1j\log_dR(T_{d^j})\) for every integer \(d\ge2\).

8. Solutions

1.1. Since \(T_2=\sum_{i,k}z_{ki}(x_{i1}y_{1k}+x_{i2}y_{2k})\), the identity says that the coefficient of each \(z_{ki}\) in the sum of the seven products is the \((i,k)\) entry of the product of the matrices \((x_{ij})\) and \((y_{jk})\). Call the seven products, without their \(z\)-factors, \(M_1,\dots,M_7\). The coefficient of \(z_{11}\) is \(M_1+M_4-M_5+M_7\). Expanding, \[ \begin{aligned} &(x_{11}+x_{22})(y_{11}+y_{22})\\ &\quad+x_{22}(y_{21}-y_{11})\\ &\quad-(x_{11}+x_{12})y_{22}\\ &\quad+(x_{12}-x_{22})(y_{21}+y_{22}) \end{aligned} \] equals \(x_{11}y_{11}+x_{12}y_{21}\). In the same way the coefficient of \(z_{21}\) is \(M_3+M_5=x_{11}y_{12}+x_{12}y_{22}\), that of \(z_{12}\) is \(M_2+M_4=x_{21}y_{11}+x_{22}y_{21}\), and that of \(z_{22}\) is \(M_1-M_2+M_3+M_6\), which equals \(x_{21}y_{12}+x_{22}y_{22}\).

1.2. With \(f(\alpha)=x_0+\alpha x_1\) and \(g(\alpha)=y_0+\alpha y_1\), write \(e_0=f(0)g(0)=x_0y_0\) and \(e_\pm=f(\pm1)g(\pm1)=(x_0\pm x_1)(y_0\pm y_1)\). The coefficients of \(fg\) are \(h_0=e_0\), \(h_1=\frac12(e_+-e_-)\) and \(h_2=\frac12(e_++e_-)-e_0\). Collecting the terms of \(z_0h_0+z_1h_1+z_2h_2\) by \(e_0\), \(e_+\) and \(e_-\) gives \[ \begin{aligned} C(2,2)={}&e_0\,(z_0-z_2)\\ &+\tfrac12e_+\,(z_1+z_2)\\ &+\tfrac12e_-\,(z_2-z_1), \end{aligned} \] a sum of three products of linear forms.

1.3. \(R(m)\le m\) by definition, and \(R(m)\ge\rho_X(m)=m\) by Lemma 1.5. The second statement is the last part of Lemma 1.5 for each of the three flattenings.

1.4. The single variable of \(B_X(m)\) sits on the \(X\)-leg and moves to the leg \(\pi(X)\); the other two legs carry the paired variables \(y_l\) and \(z_l\), in some order, and renaming gives the dot product with its single variable on \(\pi(X)\). Each leg is the image \(\pi(X)\) for exactly two of the six permutations.

1.5. For \(n\le n'\), substitute \(0\) for every variable of \(T_{n'}\) with an index greater than \(n\). Since \(R(T_{d^j})\ge(d^j)^\nu\), the limit inferior of \(\frac1j\log_dR(T_{d^j})\) is at least \(\nu\). Let \(\delta>0\) and choose \(u\ge2\) with \(R(T_u)\le u^{\nu+\delta}\). For \(\ell=\lceil j\log_ud\rceil\) we have \(d^j\le u^\ell\), so \[ \begin{aligned} R(T_{d^j})&\le R(T_{u^\ell})\le R(T_u)^\ell\\ &\le u^{(\nu+\delta)(j\log_ud+1)}, \end{aligned} \] by Lemma 1.4 and Lemma 1.6(a). Hence \(\frac1j\log_dR(T_{d^j})\le(\nu+\delta)(1+\frac1{j\log_ud})\), and the limit superior is at most \(\nu+\delta\).

References