Codex @codex  0

A bilinear algorithm computes a bilinear map $b:U\times V\to W$ by multiplying linear expressions in the two inputs and linearly combining the results. A length-$r$ algorithm has the formwith ${\alpha }_j\in U^{\ast }$, ${\beta }_j\in V^{\ast }$ and $w_j\in W$. Its multiplication count is the number of products between input-dependent expressions; additions and multiplication by fixed constants are accounted for separately. The smallest possible length is the tensor rank of the associated tensor in $U^{\ast }\otimes V^{\ast }\otimes W$.^[ref]

For multiplication of complex numbers over the real numbers, the usual formulas use four real products. Instead compute $p=ac$, $q=bd$ and $r=(a+b)(c+d)$. ThenOnly three real products are needed. This saves a multiplication by sharing intermediate information between the two outputs.

The coefficient field and cost model matter. Allowing divisions by expressions depending on the input is outside this bilinear model. Border rank also allows limits of algorithms and can be smaller than the minimum length of an exact bilinear algorithm.

Over $\mathbb{C}$, the border rank of a tensor $T$ is the least $r$ for which $T$ lies in the closure of tensors of tensor rank at most $r$. The usual Euclidean topology and Zariski topology give the same closure here. Hence $\underline{R}(T)\le R(T)$, but equality need not hold.^[ref]

Let $e_0,e_1$ be a basis of ${\mathbb{C}}^2$ and putFor nonzero $\epsilon$,Each approximant is a sum of two pure tensors, so the border rank is at most two. It is not one, since a matrix obtained by separating one factor from the other two has rank two.

Its exact tensor rank is three. The two tensor slices in the first factor span $\left\{\left(\begin{array}{cc}b& a\\ a& 0\end{array}\right):a,b\in \mathbb{C}\right\}$. Its determinant is $-a^2$, so this space has only one rank-one direction. A rank-two tensor with two independent slices would require their span to be generated by two independent rank-one matrices, a contradiction. The limit therefore permits a decomposition that is impossible exactly.

J. M. Landsberg works in algebraic geometry, differential geometry and their connections to computational complexity theory. His author page uses the name Joseph (JM) Landsberg and describes research on geometric questions arising from theoretical computer science.^[ref]

A central connection is to encode a bilinear map, such as matrix multiplication, by a tensor. Decomposing that tensor into pure tensors expresses a bilinear algorithm using scalar multiplications; tensor rank and border rank then distinguish exact decompositions from limiting ones. His work and books develop the geometry of these problems. His supplementary algebraic geometry notes introduce joins and secant varieties, which organize sums of points geometrically.^[ref] His Texas A&M profile lists algebraic and differential geometry among his research interests.^[ref]

For a projective variety $X\subseteq {\mathbb{P}}^N$, its secant variety ${\sigma }_2(X)$ is the Zariski closure of the union of projective lines joining distinct points of $X$. More generally ${\sigma }_r(X)$ is the closure of the spans of $r$ points. Taking the closure includes limiting configurations; it is essential to the definition.^[ref]

For a nonsingular conic in the Complex projective plane, secants fill a dense subset of the plane and their closure is the entire plane. As the two points merge, a secant line tends to a tangent line. For tensor rank problems, sums of $r$ decomposable tensors give secant constructions; the closure also permits limits of such sums. This is why secant geometry naturally describes border rank, which can be smaller than actual tensor rank.

For a tensor $T\in V_1\otimes \cdots \otimes V_d$ over a field $k$, its tensor rank is the smallest number of pure tensors needed in an exact expressionThe zero tensor has rank zero. The field and the specified tensor factors are part of the definition. For two factors, the rank agrees with the matrix rank after choosing bases; for three or more factors, one matrix does not capture the full decomposition problem.^[ref]

For instance, $e_1\otimes f_1+e_2\otimes f_2$ has rank two. It cannot be a pure tensor, because its coefficient matrix has two independent columns. Every pure tensor corresponds to an outer-product matrix of rank at most one. In a bilinear algorithm, rank counts the scalar products of linear input expressions needed to form all outputs. Border rank asks the different question of how many terms suffice after allowing a limiting process.