Tensors and Some Combinatorial Properties of Tensors

We begin with the definition of a tensor (in algebra) and then focus on the tensors by which we mean multi-dimensional arrays (or hypermatrices) of real numbers. A square matrix is doubly stochastic if its entries are all nonnegative and each row and column sum is 1. A celebrated result known as Birkhoff’s theorem about doubly stochastic matrices states that an n × n matrix is doubly stochastic if and only if it is a convex combination of some n×n permutation matrices (a.k.a Birkhoff polytope). The Birkhoff polytope of n × n stochastic matrices in Rn2 is of dimension (n − 1)2 with n2 facets and n! vertices. We consider the generalization of the Birkhoff’s theorem in higher dimensions. An n×n×n stochastic tensor is a nonnegative array (hypermatrix) in which every sum over one index is 1. A permutation tensor can be identified with a Latin square (vice versa). We study the polytope of all these tensors, the convex set of all tensors with some positive diagonals, and the polytope generated by the permutation tensors. We present lower and upper bounds for the number of vertices of the polytopes, and discuss further questions on the topic. Determinant and permanent are basic and important functions of n × n matrices. We attempt to define these for tensors. More generally, we will consider defining the generalized matrix functions for tensors