Information Technology Reference
In-Depth Information
(
M
i
)
ↆ
Why does this hold? The fact that the rank of
R
r
is equivalent to the fact
(
+
)
×
(
+
)
that all
minors vanish. These minors are polynomials and hence
continuous functions. Therefore all
r
1
r
1
minors of
M
vanish, too.
For tensors, this is not the necessarily true. Consider the following tensor
t
given
by the following two slices:
(
r
+
1
)
×
(
r
+
1
)
10
00
01
10
(
t
1
,
i
,
j
)
=
and
(
t
2
,
i
,
j
)
=
(6.2)
Define
1
∂
·
(∂,
1
∂
·
(
t
∂
=
)
≤
(
, ∂)
≤
(
, ∂)
−
,
)
≤
(
,
)
≤
(
,
)
1
1
1
0
1
1
0
1
0
The two slices of
t
∂
are
1
∂
∂∂
01
1
and
.
2
∂
So
t
∂
≥
t
when
∂
≥
(
t
∂
)
ↆ
2 for all
∂ >
(
)
=
3.
We can prove this using the so-called
substitution method
. This method was first
introduced by Pan [
Pan66
] to prove the optimality of theHorner scheme. See [
BCS97
]
for more applications of this method and more references.
Let
0. And
R
0. On the other hand,
R
t
r
t
=
u
i
≤
v
i
≤
w
i
(6.3)
i
=
1
with
u
i
=
(
u
i
,
1
,
u
i
,
2
),
v
i
=
(v
i
,
1
,v
i
,
2
),
w
i
=
(w
i
,
1
,w
i
,
2
),
1
ↆ
i
ↆ
r
,
be an optimal decomposition of
t
into rank-one tensors. Since
t
1
,
1
,
1
=
1, there is
an
i
0
such that
u
i
0
,
1
r
. Think of
t
as consisting of two slices as
in (
6.2
). From the decomposition (
6.3
), we will construct a new tensor in
k
1
×
2
×
2
,
which is a linear combination of the two slices, in such a way that the rank drops by
one. Specifically,
=
0, w.l.o.g.
i
0
=
˃
1
10
r
t
.
1
(˃
u
i
,
1
+
u
i
,
2
)
≤
v
i
≤
w
i
=
:=
i
=
If we set
˃
=−
u
r
,
2
/
u
r
,
1
, this kills the
r
th rank-one tensor. Therefore,
t
)
+
R
(
t
)
∧
R
(
1
.
But
t
is a matrix whose rank is obviously two. Therefore,
R
3. Since
t
has only
three entries that are nonzero, there is a trivial decomposition of
t
of length 3.
(
t
)
∧
