Information Technology Reference
In-Depth Information
the minimum number of matrices of the form
x
T
k
m
,
so-called rank-one-matrices, such that
A
can be written as the sum of these
matrices,
k
ˇ
and
y
•
·
∗
∗
y
with
x
just to mention a few. The rank of linear maps and matrices is well understood. There
are efficient algorithms to compute the rank, the most famous method is Gaussian
elimination.
Let
W
be another vector space over
k
,dim
W
=
n
.Let
ʻ
:
U
×
V
≥
W
be a
bilinear map. By choosing bases
u
1
,...,
u
of
U
,
v
1
,...,v
m
of
V
and
w
1
,...,w
n
ˇ
of
W
, we can associate structural constants
b
h
,
i
,
j
with
ʻ
:
n
ʻ(
u
h
,v
i
)
=
b
h
,
i
,
j
w
j
,
1
ↆ
h
ↆ
ˇ,
1
ↆ
i
ↆ
m
.
(6.1)
j
=
1
k
ˇ
×
m
×
n
as a three-dimensional matrix, a so-called
tensor
. As we have seen, there are many ways to define the rank of a matrix, which
is nothing but a tensor in
k
ˇ
×
m
×
1
. From the many equivalent definitions of rank
of a matrix given above, it turns out that the appropriate one for tensors is the last
one. We call a tensor
S
We can view
B
=
(
b
h
,
i
,
j
)
∗
=
(
s
h
,
i
,
j
)
a rank-one tensor or triad, if there are vectors
T
k
ˇ
,
b
T
k
m
, and
c
T
k
n
a
=
(
a
1
,...,
a
ˇ
)
∗
=
(
b
1
,...,
b
m
)
∗
=
(
c
1
,...,
c
n
)
∗
such that
=
a
h
b
i
c
j
,
ↆ
ↆ
ˇ,
ↆ
ↆ
,
ↆ
ↆ
.
s
h
,
i
,
j
1
h
1
i
m
1
j
n
We will write
S
c
. Then the
rank of a tensor T
is the minimum number
r
such that there are rank-one tensors
S
1
,...,
=
a
≤
b
≤
S
r
with
T
=
S
1
+···+
S
r
.
We denote the rank of
T
by
R
. The question of the rank of tensors of order
three or equivalently, of the rank of the corresponding bilinear mapping is a central
question in algebraic complexity theory. The flagship problem is of course matrix
multiplication, which is a bilinear mapping
k
n
×
n
(
T
)
k
n
×
n
k
n
×
n
. The current best
×
≥
n
2
.
38
upper bounds are bounds are
O
(
)
,see[
CW90
,
Sto10
,
Wil12
], whereas the best
lower bound is the recent 3
n
2
n
2
−
o
(
)
by Landsberg [
Lan12
].
6.1.1 What is So Special About Matrices?
The rank of a matrix is a well-understood quantity. The maximum rank of a matrix
in
k
ˇ
×
m
and it is easy to come up with a matrix that achieves this
maximum. For instance, the identity matrix padded with rows or columns of zeroes
does the job. Or Vandermonde matrices. The fact that we have a lot of equivalent
characterizations of the rank of the matrix seems to be crucial for the fact that it is
is min
{
ˇ,
m
}
