Information Technology Reference
In-Depth Information
Chapter 6
Explicit Tensors
Markus Bläser
Abstract
This is an expository article the aim of which is to introduce interested
students and researchers to the topic of tensor rank, in particular to the construction of
explicit tensors of high rank. We try to keep the mathematical concepts and language
used as simple as possible to address a broad audience. This article is thought to be
an appetizer and does not provide by any means a complete coverage of this topic.
·
·
Keywords
Algebraic complexity theory
Tensor rank
Lower bounds
·
Mathematics Subject Classification (2010)
68Q17
15A69
6.1 Tensors and Rank
Let
U
and
V
be vector spaces over some field
k
. It is a well-known fact that every
linear map
˃
:
k
ˇ
×
m
, where
U
≥
V
is represented by a matrix
A
=
(
a
i
,
j
)
∗
ˇ
=
dim
V
. The rank of the matrix
A
is the maximum number of
rows that are linearly independent. There are a lot of equivalent definitions of the
rank of a matrix, for instance,
dim
U
and
m
=
•
the maximum number of columns that are linearly independent,
•
ˇ
−
dim ker
˃
,
•
dim im
˃
,
This work was supported through funds provided by the Deutsche Forschungsgemeinschaft
(BL 511/10-1) and by the Indo-German Max-Planck Center for Computer Science (IMPECS).
