Information Technology Reference
In-Depth Information
=
+
for a tensor of order
d
1. Note that if
d
is odd, then the approach above using
an invertible matrix only gives the lower bound
n
e
.
If we take
K
2
e
X
n
instead of an extension field, then we can show the
same bound as (
6.6
) and get another example of an explicit tensor. As a basis of
K
,
we choose the basis 1
=
k
[
X
]
/(
)
X
n
−
1
. This induces a basis of
K
1
,
m
,
X
,...,
in the natural way.
How does the tensor of the multiplication of
K
1
×
m
look like? First consider the case
m
=
1. The tensor looks like
⊤
⊛
⊝
⊠
123
...
n
23
.
.
.
0
.
.
.
00
(6.7)
3
.
.
.
.
.
.
.
.
.
n
0
...
00
{
,
}
×
×
>
How to interpret this? It is a
0
1
-valued tensor of size
n
n
n
. An entry
k
0
in position
is 1. All other entries
are 0 whether it is explicitly indicated or not. The tensor for arbitrary
m
looks like
follows:
(
i
,
j
)
means that the entry in position
(
i
,
j
,
k
)
⊤
⊛
⊝
⊠
.
T
1
T
2
T
m
T
=
Each
T
j
is a copy of the tensor in (
6.7
). However, these tensors
T
j
live in different
slices.
T
is a tensor in
k
n
×
nm
×
nm
, each
T
j
lives in the slices
jn
in
the third component. Now, as in the beginning, we want to apply substitution method.
We will only work with the copy
T
1
, kill 2
n
(
j
−
1
)
n
+
1
,...,
1 products, and then we can simply
apply induction. In an optimal decomposition of
T
into rank-one tensors
−
r
T
=
u
i
≤
v
i
≤
w
i
,
i
=
1
w
1
,...,w
n
−
1
restricted to the first
n
−
we can assume that
1 coordinates, are linearly
independent. Let
h
be the projection along the linear span of
w
1
,...,w
n
−
1
onto
k
mn
∅
e
n
,
e
n
+
1
,...,
e
mn
⃐
. Here,
e
i
∗
is the
i
th unit vector and
∅
...
⃐
the linear span.
Applying
h
, we kill
n
1 products in the decomposition of
T
. What happens to
T
under this homomorphism? Note that only the first
n
rows of
T
are affected, which
just contain the copy
T
1
.In(
6.7
),
h
maps multiples of the slices 1
−
1 onto the
n
th one. The result is a lower triangular matrix with all 1s on the diagonal. Therefore,
the matrix has full rank. Like before, we can now kill another
n
products and the
tensor that is still computed is
,...,
n
−
