Which Young Tableaux Can Represent an Outer Sum?
Robert J. Vanderbei
Department of Operations Research and Financial Engineering
Princeton, NJ 08544
Given two vectors, not necessarily of the same length, each having
increasing elements, we form the matrix whose (i,j)-th
element is the
sum of the i-th element from the first vector and the j-th element
from the second vector. Such a matrix is called an outer sum of the
two vectors (a concept that is analogous to outer products). If we
assume that all the entries of this matrix are distinct, then we can
form another matrix of the same size but for which the
element is not the matrix element itself but rather the rank of this
element in a sorted list of all the numbers in the first matrix. Such
a matrix is called a Young tableau. We say that it "represents" the
outer sum. In this paper, we address the question as to whether all
Young tableaux can be generated this way. When one of the two
dimensions is two, then the answer is yes. In all higher dimensional
cases, the answer is no. We prove the positive result and give
examples illustrating the negative result.
Full version: pdf,
(Concerned with sequences
April 1 2015; revised versions received July 23 2015; July 30 2015.
Published in Journal of Integer Sequences, July 30 2015.
Journal of Integer Sequences home page