Sets of uniqueness and minimal matrices

Adolfo Torres-Cházaro

Departamento de Matemáticas Universidad Autónoma Metropolitana, Unidad Iztapalapa Michoacán y Purísima, 09340 México, D.F., MEXICO

Ernesto Vallejo^{1}

Instituto de Matemáticas Universidad Nacional Autónoma de México Area de la Inv. Cient., 04510 México, D.F., MEXICO e-mail: evallejo@matem.unam.mx

Abstract

In this note we give an algebraic characterization of sets of uniqueness in terms of matrices with non-negative integer coefficients and prescribed row and column sums, and of the dominance order of partitions or majorization. Our proof uses some identities involving characters of the symmetric group. As an application we describe all sets of uniqueness contained in the box B(2, 2, r), for all r.

1 Introduction.

For a positive integer m let [ m] := {1, …, m}. Given a subset S of the 3-dimensional box B = B(p, q, r) := [ p] × [ q] × [ r] we consider the cardinalities of its slices parallel to the coordinate planes

λ_{i} = |{ (x_{1}, x_{2}, x_{3}) ∈ S | x_{1} = i }|,  1 ≤ i ≤ p,
μ_{j} = |{ (x_{1}, x_{2}, x_{3}) ∈ S | x_{2} = j }|, 1 ≤ j ≤ q, (1)
ν_{k} = |{ (x_{1}, x_{2}, x_{3}) ∈ S | x_{3} = k }|,  1 ≤ k ≤ r.

The slice vectors λ_{S} := (λ_{1}, …, λ_{p}), μ_{S} := (μ_{1}, …, μ_{q}), ν_{S} := (ν_{1}, …, ν_{r}) are compositions of the cardinality of S. The set S is called a set of uniqueness if it is the only subset of B(p, q, r) with slice vectors equal to λ_{S}, μ_{S}, ν_{S}. Sets of uniqueness were introduced in [3], where a geometric characterization of them was given by the absence of certain configurations in B(p, q, r). Their work can be viewed as an extension of previous work on similar questions in the context of Boolean function theory, switching circuit theory and game theory (see references in [3]). In this note we give an algebraic characterization of sets of uniqueness which uses matrices with prescribed row and column sums and the dominance order of partitions, see Theorem 1′. Our proof uses some identitites involving characters of the symmetric group. In a future paper we will study some connections between sets of uniqueness and the Kronecker product of irreducible characters of the symmetric group.

1Supported by DGAPA UNAM IN-103195 and IN-103397

Before we state our main theorem we fix some notation. A composition of a positive integer n is a vector λ = (λ_{1}, …, λ_{p}) of non-negative integers whose coordinates sum n. A partition of n is a composition λ of n such that λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{p} > 0. Given two compositions λ = (λ_{1}, …, λ_{p}), μ = (μ_{1}, …, μ_{q}) of the same number n we say that λ dominates μ, in symbols λ ⊵ μ, if ∑_{i=1}^{k} λ_{i} ≥ ∑_{i=1}^{k} μ_{i} for all 1 ≤ k ≤ min{p, q}. If λ ⊵ μ and λ ≠ μ, we write λ ⊳ μ. The dominance order is also called majorization. If λ is a partition, its conjugate λ′ is defined by λ′_{i} := |{j ∈ [ p] | λ_{j} ≥ i}|.

Let λ = (λ_{1}, …, λ_{p}), μ = (μ_{1}, …, μ_{q}), ν = (ν_{1}, …, ν_{r}) be fixed compositions of an integer n. We denote by m^{∗}(λ, μ, ν) the number of subsets S of B(p, q, r) such that λ_{S} = λ, μ_{S} = μ and ν_{S} = ν. Observe that if λ̃, resp. μ̃, resp. ν̃ is obtained from λ, resp. μ, resp. ν by permutation of coordinates, then m^{∗}(λ̃, μ̃, ν̃) = m^{∗}(λ, μ, ν). Also note that if λ̂, resp. μ̂, resp ν̂ is obtained from λ, resp. μ, resp. ν by deleting zeros, then m^{∗}(λ̂, μ̂, ν̂) = m^{∗}(λ, μ, ν). Therefore we may assume without loss of generality that λ, μ, ν are partitions of n. We denote by M(λ, μ) the set of matrices A with non-negative integer coefficients of size p × q such that its i-th row sums λ_{i} and its j-th column sums μ_{j}. If A ∈ M(λ, μ) we denote by π(A) the partition of n obtained from A by ordering its entries decreasingly. We say that A is minimal in M(λ, μ) if π(A) is minimal in the set {π(B) | B ∈ M(λ, μ)} with the dominance order. Finally, recall that A is called a plane partition if its rows and columns are weakly decreasing.

In this note we prove the following characterization for sets of uniqueness in dimension 3, which is similar in spirit to Theorem 2.3 (see comment after the theorem).

Theorem 1. Let λ, μ, ν be partitions of n. Then

(i) m^{∗}(λ, μ, ν) = 1 if and only if there exists exactly one matrix A ∈ M(λ, μ) with π(A) = ν′ and A is minimal in M(λ, μ).

(ii) If m^{∗}(λ, μ, ν) = 1, then the unique matrix A ∈ M(λ, μ) with π(A) = ν′ is a plane partition.

Plane partitions correspond to geometric objects we call pyramids. A set S ⊆ B(p, q, r) is called a pyramid if for all (a, b, c) ∈ S and for all (x, y, z) ∈ B(p, q, r) the conditions x ≤ a, y ≤ b and z ≤ c imply (x, y, z) ∈ S. There is a simple well-known oneto-one correspondence between pyramids S ⊆ B(p, q, r) and plane partitions A = (a_{ij}) of size p × q such that 0 ≤ a_{ij} ≤ r, see [7, Section 423]. For this reason a pyramid is also called the graph or the diagram of its associated plane partition. The correspondence is given by S ⟼ A_{S} = (a_{ij}), where a_{ij} := |{k ∈ [ r] | (i, j, k) ∈ S}|; its inverse is A ⟼ S_{A}, where S_{A} := {(i, j, k) ∈ B(p, q, r) | 1 ≤ k ≤ a_{ij}}. This correspondence has the following useful property: If S is a pyramid, then A_{S} ∈ M(λ_{S}, μ_{S}) and π(A_{S}) = ν_{S}′. Conversely, if A ∈ M(λ, μ) is a plane partition and π(A) = ν′, then S_{A} has slice vectors λ, μ and ν. Using this property we reformulate Theorem 1 as follows:

Theorem 1′. Let S ⊆ B(p, q, r) and suppose that its slice vectors λ_{S}, μ_{S} and ν_{S} are partitions of the cardinality of S. Then

(i) If S is a set of uniqueness, then S is a pyramid, and its associated plane partition A_{S} is the only matrix in M(λ_{S}, μ_{S}) with π(A_{S}) = ν_{S}′. Moreover A_{S} is minimal in M(λ_{S}, μ_{S}).

(ii) Suppose S is a pyramid and let A_{S} denote its associated plane partition. If A_{S} is the only matrix in M(λ_{S}, μ_{S}) satisfying π(A_{S}) = ν_{S}′ and if A_{S} is minimal in M(λ_{S}, μ_{S}), then S is a set of uniqueness. □

Examples. (1) For 1 ≤ a < p, 1 ≤ b < q, 1 ≤ c < r we define the hook set S = H(a, b, c) as the union of the boxes B(a+1, 1, 1), B(1, b+1, 1) and B(1, 1, c+1). S is a pyramid with slice vectors λ_{S} = (b+c+1, 1^{a}), μ_{S} = (a+c+1, 1^{b}) and ν_{S} = (a+b+1, 1^{c}). Its corresponding plane partition is

A_{S} = [\begin{matrix}c + 1 & 1 & ⋯ & 1 \\ 1 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 1 & 0 & ⋯ & 0 \end{matrix}] .

It is easy to prove that A_{S} satisfies the conditions in Theorem 1′ (ii). Therefore S is a set of uniqueness.

(2) Let S be the pyramid corresponding to the plane partition

A = [\begin{matrix}3 & 3 & 1 \\ 2 & 1 & 1 \\ 2 & 0 & 0 \end{matrix}] .

Then λ_{S} = μ_{S} = ν_{S} = (7, 4, 2). Since the transpose A^{T} is in M(λ_{S}, μ_{S}) and π(A) = π(A^{T}), then S is not a set of uniqueness. This is the minimal example of a pyramid which is not a set of uniqueness, see [12, 3.3 and 5.1]. It can be checked either by computer or by tedious hand calculations that A is minimal in M(λ_{S}, μ_{S}).

The paper is organized as follows: Section 2 contains several known results about characters of the symmetric group and matrices. In section 3 we prove Theorem 1. Finally in section 4 we give the complete list of all minimal matrices of size 2 × 2.

2 Matrices and characters

There is an elementary one-to-one correspondence between the subsets S of B(p, q, r) and 3-dimensional (0,1)-matrices of size p × q × r given by S ↦ M_{S} = (a_{ijk}), where

a_{ijk} = \begin{cases}1, & if (i, j, k) ∈ S; \\ 0, & otherwise. \end{cases}

The slice vectors of a 3-dimensional (0,1)-matrix M = (a_{ijk}) of size p × q × r are defined similarly as in (1): λ_{M} := (λ_{1}, …, λ_{p}), μ_{M} := (μ_{1}, …, μ_{q}) and ν_{M} := (ν_{1}, …, ν_{r}) where λ_{i} = ∑_{j,k} a_{ijk}, μ_{j} = ∑_{i,k} a_{ijk} and ν_{k} = ∑_{i,j} a_{ijk}. Clearly for every S ⊆ B(p, q, r) one has λ_{S} = λ_{M_{S}}, μ_{S} = μ_{M_{S}} and ν_{S} = ν_{M_{S}}. Therefore for any three partitions λ, μ, ν of n, m^{∗}(λ, μ, ν) is equal to the number of 3-dimensional (0,1)-matrices M such that λ_{M} = λ, μ_{M} = μ, ν_{M} = ν. The proof of Theorem 1 will be based on a formula due to Snapper which expresses m^{∗}(λ, μ, ν) in terms of an inner product of certain characters of the symmetric group. We review below this and other similar results.

Let λ = (λ_{1}, …, λ_{p}), μ = (μ_{1}, …, μ_{q}) and ν = (ν_{1}, …, ν_{r}) be partitions of a positive integer n, and denote by m^{∗}(λ, μ) the number of (0, 1)-matrices A of size p×q whose i-th row sums λ_{i} and whose j-th column sums μ_{j}. Consider the following characters of the symmetric group S(n): Let ϕ^{λ} be the permutation character associated to the partition λ and let α_{n} be the alternating character of S(n), see [2, 5, 10]. Finally let < ·, · > denote the usual inner product of characters. We will need the following results.

2.1 Theorem. [4, 8, 9] m^{∗}(λ, μ) > 0 ⟺ λ ⊴ μ′.

2.2 Theorem. [1, Thm. 16; 2, Thm. 2; 5, 1.3] m^{∗}(λ, μ) = ⟨ϕ^{λ}ϕ^{μ}, α_{n}⟩.

2.3 Theorem. [9, p.62; 11, Thm. 8.1; 6, p.83] m^{∗}(λ, μ) = 1 ⟺ λ = μ′.

This result has a geometric reformulation [3, Thm. 3]: Let S ⊆ B(p, q) = [ p] × [ q]. A bad rectangle for S, see [3, p.150], consists of two distinct points x^{1}, x^{2} in S, and two distinct points z^{1}, z^{2} in B(p, q) \ S such that (i) they are the vertices of a rectangle with sides parallel to the coordinate axes, and (ii) x^{1} and x^{2} (and hence z^{1} and z^{2}) are diagonally opposite in the rectangle. Then S is a set of uniqueness if and only if S has no bad rectangle. If λ_{S} and μ_{S} are partitions of the cardinality of S, and not merely compositions, then the absence of bad rectangles is equivalent to λ_{S} = μ_{S}′. So Theorem 2.3 gives an algebraic characterization of uniqueness in dimension 2. Our Theorem 1(i) gives a characterization of uniqueness for dimension 3 in the same spirit.

Coleman’s result holds for multidimensional matrices, in particular:

2.4 Theorem. [11, Thm. 7.1] m^{∗}(λ, μ, ν) = ⟨ϕ^{λ}ϕ^{μ}ϕ^{ν}, α_{n}⟩.

2.5. Theorem. [2, Prop. 2; 5, 2.9.16] ϕ^{λ}ϕ^{μ} = ∑_{A∈M(λ,μ)}ϕ^{π(A)}.

3 Proof of Theorem 1

(i) It follows from (2.4), (2.5) and (2.2) that

m^{∗}(λ, μ, ν) = ∑_{A∈M(λ,μ)} m^{∗}(π(A), ν).

Suppose m^{∗}(λ, μ, ν) = 1. Let A ∈ M(λ, μ) be the only matrix such that m^{∗}(π(A), ν) > 0, then by (2.3) π(A) = ν′. If B ∈ M(λ, μ) is different from A, then m^{∗}(π(B), ν) = 0 and by (2.1) π(B) ⋬ ν′ = π(A). Therefore A is minimal in M(λ, μ). The converse is similar. (ii) Let m^{∗}(λ, μ, ν) = 1, and denote by A the only matrix in M(λ, μ) with π(A) = ν′. Suppose A is not a plane partition. Since rows and columns play symmetric roles we may assume that row i is not decreasing. Let k < l be such that a_{ik} < a_{il}. Since μ_{k} ≥ μ_{l}, there exists j ≠ i such that a_{jk} > a_{jl}. Let B be obtained from A by replacing the

submatrix [\begin{matrix}a_{ik} & a_{il} \\ a_{jk} & a_{jl} \end{matrix}] by the submatrix [\begin{matrix}a_{ik} + 1 & a_{il} − 1 \\ a_{jk} − 1 & a_{jl} + 1 \end{matrix}]. Clearly B ∈ M(λ, μ). We

define an auxiliary matrix B̃ by replacing in A the submatrix [a_{ik}, a_{il}] by the submatrix [a_{ik} + 1, a_{il} − 1]. Then clearly π(B) ⊴ π(B̃) ⊴ π(A). Since m^{∗}(λ, μ, ν) = 1, it follows from (i) that π(B) ≠ π(A). This contradicts the minimality of A. Therefore A has to be a plane partition. □

4 Minimal 2×2 matrices

Let λ, μ be partitions of n with two parts. In this section we find all minimal matrices in M(λ, μ). Since λ and μ play symmetric roles we may assume that λ_{1} ≥ μ_{1} ≥ μ_{2} ≥ λ_{2} > 0.

4.1 Theorem. The minimal matrices in M(λ, μ) are:

(i) If λ_{1} = 2a + 1, λ_{2} = 2b + 1, a ≥ b ≥ 0, μ_{1} = μ_{2},

[\begin{matrix}a & a + 1 \\ b + 1 & b \end{matrix}] , [\begin{matrix}a + 1 & a \\ b & b + 1 \end{matrix}] .

(ii) If λ_{1} = 2a, λ_{2} = 2b, a ≥ b > 0, μ_{1} = μ_{2},

[\begin{matrix}a & a \\ b & b \end{matrix}] .

(iii) If μ_{1} > μ_{2}, λ_{2} = 2b + 1, b ≥ 0,

[\begin{matrix}μ_{1} − b − i − 1 & μ_{2} − b + i \\ b + i + 1 & b − i \end{matrix}] , 0 ≤ i ≤ min \{b, \frac{1}{2}(μ_{1} − μ_{2} − 1)\} .

(iv) If μ_{1} > μ_{2}, λ_{2} = 2b, b > 0,

[\begin{matrix}μ_{1} − b − i & μ_{2} − b + i \\ b + i & b − i \end{matrix}] , 0 ≤ i ≤ min \{b, \frac{1}{2}(μ_{1} − μ_{2})\} .

4.2 Corollary. Let S ⊆ B(2, 2, r) be such that λ_{S}, μ_{S}, ν_{S} are partitions. Then S is a set of uniqueness if and only if S is a pyramid.

The rest of the section is devoted to prove the theorem and its corollary.

4.3 Lemma. Let A, B ∈ M(λ, μ) be such that A ≠ B and π(A) = π(B), then μ_{1} = μ_{2} and B is obtained from A by permutation of columns.

Proof. Let f = λ_{1} − μ_{2} = μ_{1} − λ_{2}, then there exist 0 ≤ i, j ≤ λ_{2} such that

A = [\begin{matrix}f + i & μ_{2} − i \\ λ_{2} − i & i \end{matrix}] , B = [\begin{matrix}f + j & μ_{2} − j \\ λ_{2} − j & j \end{matrix}] . If A ≠ B and π(A) = π(B) a simple case

by case analysis shows that B = [\begin{matrix}μ_{2} − i & f + i \\ i & λ_{2} − i \end{matrix}] . □

Lemma 4.4 Let A ∈ M(λ, μ). (i) If μ_{1} > μ_{2} and A is minimal in M(λ, μ), then A is a plane partition. (ii) If A is a plane partition, then A is minimal in M(λ, μ).

Proof. (i) Since μ_{1} > μ_{2}, by Lemma 4.3 there is no B ∈ M(λ, μ) with π(A) = π(B). Let ν = π(A)′. Then it follows from Theorem 1 that m^{∗}(λ, μ, ν) = 1 and that A is a plane

partition. (ii) Let A = [\begin{matrix}a & b \\ c & d \end{matrix}] be a plane partition. Since λ_{1} ≥ μ_{1}, then a ≥ b ≥ c ≥ d,

that is, π(A) = (a, b, c, d). If B ∈ M(λ, μ) and B ≠ A, then either B = [\begin{matrix}a + i & b − i \\ c − i & d + i \end{matrix}],

0 < i ≤ c or B = [\begin{matrix}a − j & b + j \\ c + j & d − j \end{matrix}], 0 < j ≤ d. In the first situation the first part of π(B)

is a + i > a, therefore π(B) ⊳ π(A) or both partitions are not comparable. In the second situation the last part of π(B) is d − j < d, again π(B) ⊳ π(A) or both partitions are not comparable. Then A is minimal. □

Proof of Theorem 4.1. (i) Since |M(λ, μ)| = 2b + 2, the matrices come in pairs:

A_{i} = [\begin{matrix}a − i & a + i + 1 \\ b + i + 1 & b − i \end{matrix}] , B_{i} = [\begin{matrix}a + i + 1 & a − i \\ b − i & b + i + 1 \end{matrix}] , 0 ≤ i ≤ b,

and π(A_{i}) = π(B_{i}). If a = b, clearly π(A_{i}) ⊵ π(A_{0}). If a > b, we extend the notion of dominance to any pair of vectors of non-negative integers of the same length. Then π(A_{i}) ⊵ (a + i + 1, a − i, b + i + 1, b − i) ⊵ (a + 1, a, b + 1, b) = π(A_{0}). (ii) is similar to (i).

(iii) By Lemma 4.4 the minimal elements of M(λ, μ) and plane partitions coincide. The matrices in (iii) satisfying 0 ≤ i ≤ min \{b, \frac{1}{2}(μ_{1} − μ_{2} − 1)\} are precisely the plane partitions. (iv) is similar to (iii).

Proof of Corollary 4.2. One implication is a particular case of Theorem 1′. For the other suppose S is a pyramid, then its associated matrix A_{S} is a plane partition. By Lemma 4.4 A_{S} is minimal. It follows from Lemma 4.3 and Theorem 4.1 that there is no other B ∈ M(λ_{S}, μ_{S}) with π(B) = π(A_{S}). Finally Theorem 1′ implies that S is a set of uniqueness. □

5 Discussion

The class of sets of uniqueness is difficult to grasp. In general it is not easy to prove that a set is a set of uniqueness, because one has to prove the non-existence of a large number of obstructions to uniqueness: the k-bad configurations, see [3, Thm. 1]. One way to overcome this difficulty is by considering additive sets. This notion was introduced in [3] where the authors proved that additive sets are sets of uniqueness [3, Thm. 2]. In many cases it is easy to prove additivity, see for example [12, Thm. 3.4]. Another approach is by considering pyramids. They admitt less k-bad configurations that an arbitrary set, see [12, Prop. 3.2 and Thm. 5.1]. In fact it follows from our Theorem 1′ that a set of uniqueness is, up to permutation of slices, a pyramid. So it is enough to give a characterization of uniqueness for pyramids. The same Theorem 1′ provides such a characterization. However, given a plane partition A ∈ M(λ, μ) we do not have methods for deciding whether A is the only matrix in M(λ, μ) with π(A) = ν or whether A is minimal in M(λ, μ). These are open problems which seem to be difficult and we propose for further study.

References

[1] A.J. Coleman, Induced Representations with applications to S_{n} and GL(n), in Queen’s papers in pure and applied mathematics, No. 4, Queens University, Kingston, Ontario, 1966.

[2] P. Doubilet, J. Fox, G.R. Rota, The elementary theory of the symmetric group, in Combinatorics, representation theory and statistical methods in groups, T.V. Narayama, R.M. Mathsen and J.G. Williams eds., Lecture Notes in Pure and Applied Mathematics, Vol. 57, Marcel Decker, New York, 1980.

[3] P. C. Fishburn, J. C. Lagarias, J. A. Reeds and L. A. Shepp, Sets uniquely determined by projections on axes II. Discrete case, Discrete Math. 91 (1991), 149-159.

[4] D. Gale, A theorem of flows in networks, Pacif. J. Math. 7 (1957) 1073-1082.

[5] G.D. James and A. Kerber, The representation theory of the symmetric group, Encyclopedia of mathematics and its applications, Vol. 16, Addison-Wesley, Reading, Massachusetts, 1981.

[6] T.Y. Lam, Young diagrams, Schur functions, the Gale-Ryser theorem and a conjecture of Snapper, J. Pure Appl. Algebra 10 (1977), 81-94.

[7] P. A. MacMahon, Combinatorial Analysis, Vol. II. Cambridge Univ. Press, London-New York 1916; reprinted by Chelsea, New York, 1960.

[8] H.J. Ryser, Combinatorial properties of matrices of zeros and ones, Canad. J. Math. 9 (1957), 371-377.

[9] H.J. Ryser, Combinatorial mathematics, Carus monograph No. 14, Math. Association of America, John Wiley and Sons, 1963.

[10] B.E. Sagan, The symmetric group, Wadsworth & Brooks/Cole, Pacific Grove, California, 1991.

[11] E. Snapper, Group characters and nonnegative integral matrices, J. Algebra 19 (1971), 520-235.

[12] E. Vallejo, Reductions of additive sets, sets of uniqueness and pyramids, Discrete Math. 173 (1997), 257-267.