Tensor rank ( $R_{k} (T)$ )

For a tensor

T \in V_{1} \otimes \dots \otimes V_{d}

over a field

k

, its tensor rank is the smallest number of pure tensors needed in an exact expression

T = \sum_{j = 1}^{r} v_{1 j} \otimes \dots \otimes v_{d j} .

(1)

The 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.

Table of contents
- Bilinear algorithm Tensor rank
- Border rank Tensor rank

Bilinear algorithm ( $b (u, v) = \sum_{j = 1}^{r} α_{j} (u) β_{j} (v) w_{j}$ )

 0  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 form

b (u, v) = \sum_{j = 1}^{r} α_{j} (u) β_{j} (v) w_{j},

(1)

with

α_{j} \in U^{*}

β_{j} \in V^{*}

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^{*} \otimes V^{*} \otimes W

.^[ref]

For multiplication of complex numbers over the real numbers, the usual formulas use four real products. Instead compute

p = a c

q = b d

and

r = (a + b) (c + d)

. Then

(a + ib) (c + i d) = (p - q) + i (r - p - q) .

(2)

Only 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.

Border rank ( $\underline{R} (T)$ )

 0  0

Over

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) \leq R (T)

, but equality need not hold.^[ref]

Let

e_{0}, e_{1}

be a basis of

C^{2}

and put

T = e_{1} \otimes e_{0} \otimes e_{0} + e_{0} \otimes e_{1} \otimes e_{0} + e_{0} \otimes e_{0} \otimes e_{1} .

(1)

For nonzero

ε

\frac{( e _{0} + ε e _{1} ) ^{\otimes 3} - e _{0}^{\otimes 3}}{ε} ⟶ T .

(2)

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

{(b a a 0) : a, b \in C}

. 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.