Blog > Counting the Possible Orderings of Pairwise Multiplication

Counting the Possible Orderings of Pairwise Multiplication

February 12th, 2014

Suppose we are given n distinct positive real numbers a_1 > a_2 > \cdots > a_n > 0. The question we are going to consider in this post is as follows:

Question. How many different possible orderings are there of the n(n+1)/2 numbers \{a_ia_j\}_{1\leq i\leq j\leq n}?

To help illustrate what we mean by this question, consider the n = 2 case, where a_1 > a_2 > 0. Then the 3 possible products of a_1 and a_2 are a_1^2, a_2^2, a_1a_2, and it is straightforward to see that we must have a_1^2 > a_1a_2> a_2^2, so there is only one possible ordering in the n = 2 case.

In the n = 3 case, we have a_1 > a_2 > a_3 > 0 and 6 possible products: a_1^2, a_2^2, a_3^2, a_1a_2, a_1a_3, a_2a_3. Some relationships between these 6 numbers are immediate, such as a_1^2 > a_1a_2 > a_1a_3 > a_2a_3 > a_3^2. However, it could be the case that either a_2^2 > a_1a_3 or a_1a_3 > a_2^2 (we ignore the degenerate cases where two products are equal to each other), so there are two different possible orderings in this case:

a_1^2 > a_1a_2 > a_2^2 > a_1a_3 > a_2a_3 > a_3^2\quad\text{ or }\\ a_1^2 > a_1a_2 > a_1a_3 > a_2^2 > a_2a_3 > a_3^2.

In this post, we will consider the problem of how many such orderings exist for larger values of n. This problem arises naturally from a problem in quantum entanglement: the number of such orderings is exactly the minimum number of linear matrix inequalities needed to characterize the eigenvalues of quantum states that are “PPT from spectrum” [1].

A Rough Upper Bound

We now begin constructing upper bounds on the number of possible orderings of \{a_ia_j\}_{1\leq i\leq j\leq n}. Since we are counting orderings between n(n+1)/2 numbers, a trivial upper bound is given by (n(n+1)/2)!, since that is the number of possible orderings of n(n+1)/2 arbitrary numbers. However, this quantity is a gross overestimate.

We can improve this upper bound by creating an n \times n matrix whose (i,j)-entry is a_ia_j (note that this matrix is symmetric, positive semidefinite, and has rank 1, which is roughly how the connection to quantum entanglement arises). For example, in the n = 4 case, this matrix is as follows:

\begin{bmatrix}a_1^2 & a_1a_2 & a_1a_3 & a_1a_4 \\ * & a_2^2 & a_2a_3 & a_2a_4 \\ * & * & a_3^2 & a_3a_4 \\ * & * & * & a_4^2\end{bmatrix},

where we have used asterisks (*) to indicate entries that are determined by symmetry. The fact that a_1 > a_2 > \cdots > a_n > 0 implies that the rows and columns of the upper-triangular part of this matrix are decreasing. Thus we can get an upper bound to the solution to our problem by counting the number of ways that we can place the numbers 1, 2, \ldots, n(n+1)/2 (exactly once each) in the upper-triangular part of a matrix in such a way that the rows and columns of that upper-triangular part are decreasing. For example, this can be done in 2 different ways in the n = 3 case:

\begin{bmatrix}6 & 5 & 4 \\ * & 3 & 2 \\ * & * & 1\end{bmatrix} \quad \text{and} \quad \begin{bmatrix}6 & 5 & 3\\ * & 4 & 2\\ * & * & 1\end{bmatrix}.

The matrix above on the left corresponds to the case a_1a_3 > a_2^2 discussed earlier, while the matrix above on the right corresponds to the case a_2^2 > a_1a_3.

A formula for the number of such ways to place the integers 1, 2, \ldots, n(n+1)/2 in a matrix was derived in [2] (see also A003121 in the OEIS), which immediately gives us the following upper bound on the number of orderings of the products \{a_ia_j\}_{1\leq i\leq j\leq n}:

\displaystyle(n(n+1)/2)! \frac{1! 2! \cdots (n-1)!}{1! 3! \cdots (2n-1)!}.

For n = 1, 2, 3, …, this formula gives the values 1, 1, 2, 12, 286, 33592, 23178480, …

A Better Upper Bound

Before improving the upper bound that we just presented, let’s first discuss why it is not actually a solution to the original question. In the n = 4 case, our best upper bound so far is 12, since there are 12 different ways to place the integers 1,2,\ldots,10 in the upper-triangular part of a 4 \times 4 matrix such that the rows and columns of that upper-triangular part are decreasing. However, one such placement is as follows:

\begin{bmatrix}10 & 9 & 7 & 6 \\ * & 8 & 5 & 3 \\ * & * & 4 & 2 \\ * & * & * & 1\end{bmatrix}.

The above matrix corresponds to the following inequalities in terms of \{a_ia_j\}_{1\leq i\leq j\leq n}:

a_1^2 > a_1a_2 > a_2^2 > a_1a_3 > a_1a_4 > a_2a_3 > a_3^2 > a_2a_4 > a_3a_4 > a_4^2.

The problem here is that there actually do not exist real numbers a_1 > a_2 > a_3 > a_4 > 0 that satisfy the above string of inequalities. To see this, notice in particular that we have the following three inequalities: a_2^2 > a_1a_3, a_1a_4 > a_2a_3, and a_3^2 > a_2a_4. However, multiplying the first two inequalities together gives a_1a_2^2a_4 > a_1a_2a_3^2, so a_2a_4 > a_3^2, which contradicts the third inequality.

More generally, there can not be indices i,j,k,\ell,m,n such that we simultaneously have the following three inequalities:

a_ia_j > a_ka_\ell, a_\ell a_m > a_j a_n, and a_i a_m < a_k a_n.

I am not aware of a general formula for the number integer matrices that do not lead to these types of “bad” inequalities, but I have computed this quantity for n ≤ 7 (C code is available here), which gives the following better upper bound on the number of possible orderings of the products \{a_ia_j\}_{1\leq i\leq j\leq n} for n = 1, 2, 3, …: 1,1,2,10,114,2612,108664, …, which we see is significantly smaller than the upper bound found in the previous section for n ≥ 5.

This Bound is Not Tight

It is straightforward to write a script that generates random numbers a_1 > a_2 > \cdots > a_n > 0 and determines the resulting ordering of the pairwise products \{a_ia_j\}_{1\leq i\leq j\leq n}. By doing this, we can verify that the upper bounds from the previous section are in fact tight when n ≤ 5. However, when n = 6, we find that 4 of the 2612 potential orderings do not seem to actually be attained by any choice of a_1 > a_2 > \cdots > a_6 > 0. One of these “problematic” orderings is the one that arises from the following matrix:

\begin{bmatrix}21 & 20 & 19 & 18 & 17 & 11\\ * & 16 & 15 & 14 & 10 & 6\\ * & * & 13 & 12 & 8 & 5\\ * & * & * & 9 & 7 & 3\\ * & * & * & * & 4 & 2\\ * & * & * & * & * & 1\end{bmatrix}

The problem here is that the above matrix implies the following 5 inequalities:

a_1a_5 > a_2^2, \quad \ \ a_2a_4 > a_3^2, \quad \ \ a_2a_5 > a_4^2, \quad \ \ a_3a_4 > a_1a_6, \quad \text{and }\ \ \ a_3a_6 > a_5^2.

However, multiplying the first four inequalities gives a_1a_2^2a_3a_4^2a_5^2 > a_1a_2^2a_3^2a_4^2a_6, so a_5^2 > a_3a_6, which contradicts the fifth inequality above. We can similarly prove that the other 3 seemingly problematic orderings are in fact not attainable, so there are exactly 2608 possible orderings in the n = 6 case.

I haven’t been able to compute the number of orderings when n ≥ 7, as my methods for obtaining upper and lower bounds are both much too slow in these cases. The best bounds that I have in the n = 7 case say that the number of orderings is between 50900 and 108664, inclusive.

Update [Feb. 13, 2014]: Giovanni Resta has improved the lower bound in the n = 7 case to 107498, which narrows the n = 7 region down considerably. I’ve also improved the upper bound to 108146 (see this improved version of the C script). In all likelihood, 107498 is the correct number of orderings in this case, and it’s the upper bound 108146 that needs to be further improved.

Update [Feb. 14, 2014]: This sequence is now in the OEIS. See A237749.

Update [Feb. 18, 2014]: Hans Havermann has found a couple of references that talk about this problem (in the language of Golomb rulers) and compute all values for n ≤ 7. See [3] and [4].

References

  1. R. Hildebrand. Positive partial transpose from spectra. Phys. Rev. A, 76:052325, 2007. E-print: arXiv:quant-ph/0502170
  2. R. M. Thrall. A combinatorial problem. Michigan Math. J., 1:81–88, 1952.
  3. M. Beck, T. Bogart, and T. Pham. Enumeration of Golomb rulers and acyclic orientations of mixed graphs. Electron. J. Combin., 19:42, 2012. E-print: arXiv:1110.6154 [math.CO]
  4. T. Pham. Enumeration of Golomb rulers. Master’s Thesis, San Francisco State University, 2011.
  1. February 18th, 2014 at 12:59 | #1

    In his 2011 thesis, Tu Pham computed a table of what appears to be the number of combinatorially different Golomb rulers with a given number of markings. It is 1, 2, 10, 114, 2608, and 107498.

  2. February 18th, 2014 at 13:23 | #2

    @Hans Havermann – Brilliant, thank you! I’ve updated the post with the references. It’s nice to get an exact answer in the n = 7 case and to see that this problem has been looked at before. :)

  1. No trackbacks yet.