Which Young Tableaux Can Represent an Outer Sum?

Colin Mallows Flemington, NJ USA colinm16@comcast.net

Robert J. Vanderbei^{1}

Department of Operations Research and Financial Engineering Princeton University Princeton, NJ 08544 USA

                  rvdb@princeton.edu

Abstract

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 (i, j)-th 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.

1 Research supported by ONR Grant N0014-13-1-0093.

1 Introduction

Let x and y be real vectors of lengths m and n, respectively, each with increasing elements. Define s = {s_{ij}} where s_{ij} = x_{i} + y_{j} (s is the “outer sum” of x and y; we write s = x ∘ y). Suppose x and y are in general position, so that the m × n numbers {s_{ij}} are all different. Let t_{ij} be the rank of s_{ij} in this set of numbers. Then the array t = {t_{ij}} is an m × n Young tableau, with entries (1, 2, …, mn), satisfying t_{ij} < t_{ik} whenever j < k and t_{ij} < t_{kj} whenever i < k. We say that this tableau represents the outer sum. This raises an interesting question: Can all Young tableaux be generated in this way? In this paper, we prove that all 2 × n tableaux can represent an outer sum, and show that some larger tableaux cannot. We will describe our efforts to characterize these tableaux.

We begin with some brief motivation for our interest in this problem. During consideration of a new deconvolution algorithm for estimating the distribution of a random variable Y based on m observations of a random variable X and n observations of the independent sum X +Y (see [1] for details), one of us encountered the question posed in the title. He did some hand calculations (many of which were later found to be in error), and submitted the results to the OEIS ([2], sequence \underline{A211400}). The second author saw that linear programming (LP) could provide definitive answers in many small cases of the problem, and obtained results for the cases

(m, n) = (2, 3), (2, 4), … (2, 9), (3, 3), …, (3, 7), (4, 4).

In this paper, we prove that for all n ≥ 1, every 2 × n Young tableau can represent an outer sum, and show that for m, n ≥ 3, this is not the case.

Remark 1. This problem is exactly equivalent to one expressed in terms of the outer product of two positive ordered vectors, using products instead of sums, simply by taking logs. We could also think in terms of “outer difference” and “outer division”; these are all equivalent problems.

Remark 2. It is completely trivial that the (unique) 1 × n tableau does represent (and in fact equals) the outer sum x ∘ y where x = (0) and y = (1, 2, …, n).

Remark 3. For any vector x = (x_{1}, …, x_{m}) and real k we define x + k to be the vector (x_{1} + k, …, x_{m} + k). Then for any k and l, x ∘ y and (x + k) ∘ (y + l) have the same tableau representation.

Example 4. The 3 × 3 tableau

[ \begin{matrix}1 & 2 & 6 \\ 3 & 5 & 7 \\ 4 & 8 & 9 \end{matrix} ]

cannot represent an outer sum. Let x be (a, b, c), and, ignoring the obvious vector/scalar notational conflict, let y be (x, y, z). Then from 2 < 3 we have

a + y < b + x,

and from 7 < 8 we have

b + z < c + y.

Adding these inequalities gives

a + y + b + z < b + x + c + y;

i.e., a + z < c + x, which contradicts the entries 6, 4 in the tableau. This gives us our first taboo configuration:

T_{3}: t_{12} < t_{21} and t_{23} < t_{32} and t_{31} < t_{13}.

There are 42 Young tableaux of size 3 × 3; just 3 of these satisfy this taboo condition, and another 3 the same with all inequalities reversed, leaving 36 that can represent an outer sum. This result and several higher-order cases are presented in OEIS [2], sequence \underline{A211400}.

Remark 5. Among the m × n tableaux with m, n ≥ 3 are some whose leading 3 × 3 subtableaux are copies of the 3 × 3 tableau above. These cannot represent an outer sum.

Remark 6. Suppose A is an m × n tableau. In the following, we will consider various subtableaux of A. For most purposes, we need not distinguish between an a×b sub-matrix B of A, which is the usual concept, simply dropping m − a rows and n − b columns of A, and the corresponding sub-tableau C, which is obtained from B by replacing its elements by their ranks (within the set of elements of B). Thus C will be a proper a × b Young tableau. For example, the (2, 3) × (1, 3) sub-matrix of the 3 × 3 tableau above is the 2 × 2 matrix with rows (3, 7) and (4, 9), while the corresponding 2 × 2 sub-tableau has rows (1, 3) and (2, 4). We need not distinguish between these, because all relevant information is carried by the ordering of their elements, without regard to their numerical values. We will never need to perform any arithmetic operations on these elements, apart from considering their ordering.

2 The 2 × n case

Theorem 7. For all n ≥ 1, each of the 2 × n Young tableaux can represent an outer sum.

Proof. The number of distinct 2 × n Young tableaux is the Catalan number

C_{n} = \frac{1}{n + 1} ( \begin{matrix}2n \\ n \end{matrix} ) .

Very many enumerative problems have these numbers as their solution (see \underline{A000108} in the OEIS) and we discuss just one of these, namely the number of paths of 2n steps in the positive quadrant, starting from the origin (0, 0) and ending at (n, n), where each step is either eastwards one unit, or northwards one unit, and where the whole path stays below (or on) the line y = x. We call these “lower paths” (usually referred to as “Dyck paths” in the literature). The top row of the Young tableau tells when the eastwards steps occur, and the bottom row tells when the northwards steps occur. We will show that each such path corresponds to an outer sum. The generating function of the Catalan sequence is C(x) = (1 − \sqrt{1 − 4x})/2x = 1 + x + 2x^{2} + 5x^{3} + 14x^{4} + 42x^{5} + · · ·.

For n = 1, the tableau represents (0, 1) ∘ (0). For n ≥ 2 we can describe a general lower path p (of length 2n) as the concatenation (p_{1}, p_{2}) of two lower paths, of lengths 2a and 2b, respectively, where a ≥ 1 and b ≥ 0, and where the path p_{1} stays strictly below the line y = x except at its endpoints. We call p_{1} a sub-lower path. The number of such paths of length 2a is the coefficient of x^{a} in xC(x), since except for the first and last steps, the path stays below or on the line y = x − 1. The total number of lower paths of length 2n is thus the coefficient of x^{n} in 1 + xC(x) · C(x) which is just C(x). (This argument is one way of deriving C(x).) The corresponding tableaux have the property that the first time both partial rows have equal length (apart from the initial state, where both have length zero) is when both rows have length a. This can occur with a = 1, in which case the first column of the tableau is (1, 2). If a ≥ 2 the top row of the tableau starts (1, 2, …), the bottom row has (2a − 1, 2a) in the (a − 1)-th and a-th positions, and the first a columns of T contain a permutation of the integers (1, 2, …, 2a).

We proceed by induction. Suppose we have shown that for n ≤ n_{0}, all 2 × n Young tableaux, or the associated lower paths, can represent an outer sum. We take x = (0, 1). Consider a 2 × n tableau T with n = n_{0} + 1, and its component paths p_{1} and p_{2} as above. Except when b = 0, each of a and b is positive and less than or equal to n_{0}, so by the inductive hypothesis each component path can represent an outer sum, x ∘ y with y = (y_{1}, …, y_{a}) and x ∘ z with z = (z_{1}, …, z_{b}) say. If a < n, we have t_{1,(a+1)} = 2a + 1, so we may take k = 2 + y_{a}, and T represents the outer sum x∘(y, z+k). The only case needing proof is when a = n, b = 0. In this case the tableau T must be of the form

[ \begin{matrix}1 & 2 & ⋯ & ⋯ & f \\ g & ⋯ & ⋯ & 2n − 1 & 2n \end{matrix} ]

with n ≤ f ≤ 2n − 2 and 3 ≤ g ≤ n + 1. Consider the 2 × (n − 1) matrix

M = [ \begin{matrix}2 & ⋯ & f \\ g & ⋯ & 2n − 1 \end{matrix} ] .

Since T corresponds to a sub-lower path, the elements of this matrix have the same order relations as a Young tableau T^{∗} of dimension 2 × (n − 1). The (i, j) entry t_{ij}^{∗} of T^{∗} is just M_{ij} −1. T^{∗} corresponds to a lower path of length 2(n−1) and so to an outer sum x∘y^{∗} with y^{∗} = (y_{2}, y_{3}, … y_{n}) say. We have only to show that we can choose y_{1} to make the tableau T represent the outer sum x ∘ (y_{1}, y^{∗}). For this, we need y_{1} < y_{2}, rank(1 + y_{1}) = g. Since in the outer sum x ∘ y^{∗}, rank(1 + y_{2}) = g − 1, we must have that y_{g−2} < 1 + y_{2}. So we can fit 1 + y_{1} between y_{g−2} and 1 + y_{2}, so that y_{1} < y_{2}, and we are done.

3 Linear programming

To use linear programming (LP) to study the m×n tableaux, we solve the following problem:

maximize ε
subject to y_{i(k)} + x_{j(k)} + ε ≤ y_{i(k+1)} + x_{j(k+1)},  k = 1, …, mn − 1,
y_{k} + ε ≤ y_{k+1},  k = 1, …, m − 1,
x_{k} + ε ≤ x_{k+1},  k = 1, …, n − 1,
0 ≤ y_{k} ≤ 1,  k = 1, …, m,
0 ≤ x_{k} ≤ 1,  k = 1, …, n.

Here, i(k) and j(k) denote the row and column of the k-th ranking entry in the tableau. If the optimal value of ε is positive, then an outer sum representation exists for that tableau. Otherwise not.

3.1 The 3 × 4 case

One of us has used LP to study the 462 Young tableaux of size 3 × 4, finding 295 that can represent an outer sum, leaving 167 that cannot. Study of these 167 showed that 159 of them satisfied the above 3×3 taboo condition (or its reverse, reversing all inequalities), applied to each of four sub-matrices, each omitting one column of the 3 × 4 tableau, leaving 8 tableaux that do not. Examination of these suggested four new taboo configurations, namely

T_{41}: t_{12} < t_{21} and t_{24} < t_{33} and t_{23} < t_{14} and t_{31} < t_{22}
T_{42}: t_{13} < t_{21} and t_{24} < t_{32} and t_{22} < t_{14} and t_{31} < t_{23}

and the same with all inequalities reversed.

For a 4 × 3 tableau there are similar transposed taboo conditions. See Figure 1 for pictures of these taboo configurations. The values of n in the figure give the number of 3×4 tableaux that satisfy each taboo configuration, or its reversal.

3.2 The 4 × 4 case

Examination of the 4 × 4 tableaux gave the following results.

Total number of tableaux  24024
Representing outer sums  6660
Not representing  17364
Taboo T_{3}  16432
Taboo T_{41} or T_{42}, but not T_{3}  932

We do not need any new taboo configurations.

3.3 The 3 × 5 case

Examination of the 3 × 5 tableaux gave the following results.

Total number of tableaux  6006
Representing outer sums  2583
Not representing  3423
Taboo T_{3}  3233
Not representing, but not T_{3} 190
T_{41}, not T_{3} or T_{42}  93
T_{42}, not T_{3} or T_{41}  93
Both T_{41} and T_{42}, not T_{3}  4

Again, no new taboo configurations are needed for this 3×5 case. At this point we hoped that we had found a complete set of taboo configurations. But when we studied the 3 × 6 cases, we found new taboos.

3.4 The 3 × 6 case

Examination of the 3 × 6 tableaux gave the following results.

Total number of tableaux  87516
Representing an outer sum  23580
Not representing  63936
Taboo T_{3}  60784
Not Taboo T_{3}  3152
Taboo T_{41} and/or T_{42}, not T_{3} 3112
Not T_{3} or T_{41} or T_{42}  40

These last 40 tableaux were found to require 8 new taboo configurations, with their reversals, as shown in Figure 1. The frequencies add to 48, not 40, since four tableaux satisfy both T_{61} and T_{63} (or their reversals), while four more satisfy both T_{62} and T_{64}.

Figure 1: Eleven taboo configurations. In each panel of the Figure, an arrow from node a to node b denotes the inequality t_{a} < t_{b}. Any tableau with a sub-tableau satisfying all such inequalities cannot represent an outer sum. In each panel, n is the number of tableaux (of minimal size) that satisfy the inequalities shown (or the same with all inequalities reversed).

This result dashed our hopes. It seems clear that more taboo configurations will be needed for the 3 × 8 case (perhaps not for the 3 × 7 case), and we can guess at some of these, by analogy with T_{61} and T_{67}. But even if we could identify a complete description of all the taboo conditions, we would still have a difficult enumerative problem: to count the Young tableaux that avoid all of these.

4 Final comment

The problem remains “hard”, as the entry \underline{A211400} in the OEIS says. We hope that someone with more insight than us will make further progress on this problem. Complete lists of the “solved” configurations in the 3 × 5 and 3 × 6 cases are available online [3, 4].

References

[1] C. L. Mallows, Decomposition by simulation. In Complex Datasets and Inverse Problems: Tomography, Networks and Beyond, Vol. 54, IMS Lecture Notes – Monograph Series, 2007, pp. 1–11.

[2] The On-Line Encyclopedia of Integer Sequences, 2015. Published electronically at

   http://oeis.org.

[3] R. J. Vanderbei, Young tableaux, 2015. Available at

   http://www.princeton.edu/~rvdb/YoungTableaux/solved_3x5.txt.

[4] R. J. Vanderbei, Young tableaux, 2015. Available at

   http://www.princeton.edu/~rvdb/YoungTableaux/solved_3x6.txt.

2010 Mathematics Subject Classification: Primary 05E05; Secondary 05E10, 20C30, 17B10. Keywords: outer sum, Young tableau, Dyck path, Catalan number, linear programming

(Concerned with sequences \underline{A000108} and \underline{A211400}.)

Received April 1 2015; revised versions received July 23 2015; July 30 2015. Published in Journal of Integer Sequences, July 30 2015.

Return to Journal of Integer Sequences home page.