Information Technology Reference
In-Depth Information
Again, we can extend this to a linear mapping
V
1
≤···≤
V
n
≥
U
1
≤···≤
U
n
.We
denote this mapping by
h
1
≤···≤
h
n
.
Fact 2
R
(
t
)
∧
R
(
h
1
≤···≤
h
n
(
t
))
for any tensor t . If all h
i
are isomorphisms,
then equality holds.
∗
V
1
≤ ··· ≤
∗
U
1
≤ ··· ≤
Let
t
V
n
and
s
U
n
. We can embed both tensors
into the larger space
(
V
1
U
1
)
≤ ··· ≤
(
V
n
U
n
)
as follows: Since each
V
i
is
a subspace of
V
i
U
i
, each rank-one tensor of
V
1
≤···≤
V
n
is also a rank-one
tensor of
(
V
1
U
1
)
≤···≤
(
V
n
U
n
)
. Every tensor
t
in
V
1
≤···≤
V
n
is a sum
of rank-one tensors, so
t
embeds into
(
V
1
U
1
)
≤···≤
(
V
n
U
n
)
as well. The
same works for
s
.
t
s
denotes the tensor that we get by viewing
t
and
s
as tensors
in
(
V
1
U
1
)
≤···≤
(
V
n
U
n
)
and forming their sum. The following fact follows
immediately.
Fact 3
R
(
t
s
)
ↆ
R
(
t
)
+
R
(
s
)
.
Open Problem 3
Does
R
(
t
s
)
=
R
(
t
)
+
R
(
s
)
hold for all tensors
t
and
s
?This
is known as
Strassen's additivity conjecture
.
Finally, we define the tensor product of
t
and
s
, which is an element of
(
V
1
≤
U
1
)
≤
···≤
(
V
n
≤
U
n
)
. For two rank-one tensors
x
=
v
1
≤···≤
v
n
and
y
=
u
1
≤···≤
u
n
,
their tensor product is defined as
≤
=
(v
1
≤
u
1
)
≤···≤
(v
n
≤
u
n
).
x
y
If we write
t
=
x
1
+···+
x
r
as a sum of rank-one tensors and
s
=
y
1
+···+
y
p
,
then we define their tensor product as
p
r
t
≤
s
=
x
i
≤
y
j
.
(6.4)
i
=
1
j
=
1
It is easy to verify that this is well defined.
If you think in coordinates, then the tensor product of
t
k
d
1
×···×
d
n
=
(
t
i
1
,...,
i
n
)
∗
k
e
1
×···×
e
n
and
s
=
(
s
j
1
,...,
j
n
)
∗
is given by
k
d
1
e
1
×···×
d
n
e
n
t
≤
s
=
(
t
i
1
,...,
i
n
s
j
1
,...,
j
n
)
∗
.
The pair
(
i
1
,
j
1
)
is interpreted as a number from
{
1
,...,
d
1
e
1
}
and is used to index
the first coordinate,
for the second, and so on.
From (
6.4
), the next fact follows easily.
Fact 4
(
i
2
,
j
2
)
R
(
t
≤
s
)
ↆ
R
(
t
)
R
(
s
)
.
Note that in this case, the inequality may be strict. For instance, the rank of 2
×
2-
matrix multiplication is 7, however, the rank of 2
m
2
m
-matrix matrix multiplication
is strictly less than 7
m
for large enough
m
, since there are algorithms for matrix
multiplication that are asymptotically faster than Strassen's algorithm.
×
