A direct bijection between descending plane partitions with no special parts and permutation matrices

We present a direct bijection between descending plane partitions with no special parts and permutation matrices. This bijection has the desirable property that the number of parts of the descending plane partition corresponds to the inversion number of the permutation. Additionally, the number of maximum parts in the descending plane partition corresponds to the position of the one in the last column of the permutation matrix. We also discuss the possible extension of this approach to finding a bijection between descending plane partitions and alternating sign matrices.     

A bijection between certain non-crossing partitions and sequences

We present a bijection between non-crossing partitions of the set [2n+1] into n+1 blocks such that no block contains two consecutive integers, and the set of sequences such that 1?s_i?i, and if s_i=j, then s_i-r?j-r for 1?r?j-1.     

The spectra of nonnegative integer matrices via formal power series

We characterize the possible nonzero spectra of primitive integer matrices (the integer case of Boyle and Handelman's Spectral Conjecture). Characterizations of nonzero spectra of nonnegative matrices over and follow from this result. For the proof of the main theorem we use polynomial matrices to reduce the problem of realizing a candidate spectrum to factoring the polynomial as a product where the 's are polynomials in satisfying some technical conditions and is a formal power series in . To obtain the factorization, we present a hierarchy of estimates on coefficients of power series of the form to ensure nonpositivity in nonzero degree terms.

     

Alternating sign matrices and descending plane partitions

An alternating sign matrix is a square matrix such that (i) all entries are 1, ?1, or 0, (ii) every row and column has sum 1, and (iii) in every row and column the nonzero entries alternate in sign. Striking numerical evidence of a connection between these matrices and the descending plane partitions introduced by Andrews (Invent. Math.53 (1979), 193–225) have been discovered, but attempts to prove the existence of such a connection have been unsuccessful. This evidence, however, did suggest a method of proving the Andrews conjecture on descending plane partitions, which in turn suggested a method of proving the Macdonald conjecture on cyclically symmetric plane partitions (Invent. Math.66 (1982), 73–87). In this paper is a discussion of alternating sign matrices and descending plane partitions, and several conjectures and theorems about them are presented.     

Strong shift equivalence and shear adjacency of nonnegative square integer matrices

For two square matrices A, B of possibly different sizes with nonnegative integer entries, write A ≈₁ B if A = RS and B = SR for some two nonnegative integer matrices R,S. The transitive closure of this relation is called strong shift equivalence and is important in symbolic dynamics, where it has been shown by R.F. Williams to characterize the isomorphism of two topological Markov chains with transition matrices A and B. One invariant is the characteristic polynomial up to factors of λ. However, no procedure for deciding strong shift equivalence is known, even for 2×2 matrices A, B. In fact, for n × n matrices with n > 2, no nontrivial sufficient condition is known. This paper presents such a sufficient condition: that A and B are in the same component of a directed graph whose vertices are all n × n nonnegative integer matrices sharing a fixed characteristic polynomial and whose edges correspond to certain elementary similarities. For n > 2 this result gives confirmation of strong shift equivalences that previously could not be verified; for n = 2, previous results are strengthened and the structure of the directed graph is determined.     

A bijection for partitions with initial repetitions

A theorem of Andrews equates partitions in which no part is repeated more than 2k−1 times to partitions in which, if j appears at least k times, all parts less than j also do so. This paper proves the theorem bijectively, with some of the generalizations that usually arise from such proofs.     

The lattice of integer partitions

In this paper we study the lattice L_n of partitions of an integer n ordered by dominance. We show L_n to be isomorphic to an infimum subsemilattice under the component ordering of certain concave nondecreasing (n+1)-tuples. For L_n, we give the covering relation, maximal covering number, minimal chains, infimum and supremum irreducibles, a chain condition, distinguished intervals; and show that partition conjugation is a lattice antiautomorphism. L_n is shown to have no sublattice having five elements and rank two, and we characterize intervals generated by two cocovers. The Möbius function of L_n is computed and shown to be 0,1 or -1. We then give methods for studying classes of (0,1)-matrices with prescribed row and column sums and compute a lower bound for their cardinalities.     

Linear operators that preserve maximal column ranks of nonnegative integer matrices

The maximal column rank of an by matrix over a semiring is the maximal number of the columns of which are linearly independent. We characterize the linear operators which preserve the maximal column ranks of nonnegative integer matrices.

     

The difference between doubly nonnegative and completely positive matrices

The convex cone of n×n completely positive (CP) matrices and its dual cone of copositive matrices arise in several areas of applied mathematics, including optimization. Every CP matrix is doubly nonnegative (DNN), i.e., positive semidefinite and component-wise nonnegative, and it is known that, for n4 only, every DNN matrix is CP. In this paper, we investigate the difference between 5×5 DNN and CP matrices. Defining a bad matrix to be one which is DNN but not CP, we: (i) design a finite procedure to decompose any n×n DNN matrix into the sum of a CP matrix and a bad matrix, which itself cannot be further decomposed; (ii) show that every bad 5×5 DNN matrix is the sum of a CP matrix and a single bad extreme matrix; and (iii) demonstrate how to separate bad extreme matrices from the cone of 5×5 CP matrices.     

The nonnegative rank factorizations of nonnegative matrices

Let A ∈ P^{m × n}_r, the set of all m × n nonnegative matrices having the same rank r. For matrices A in P^{m × n}_n, we introduce the concepts of “A has only trivial nonnegative rank factorizations” and “A can have nontrivial nonnegative rank factorizations.” Correspondingly, the set P^{m × n}_n is divided into two disjoint subsets P₍₁₎ and P₍₂₎ such that P₍₁₎∪P₍₂₎ = P^{m × n}_n. It happens that the concept of “A has only trivial nonnegative rank factorizations” is a generalization of “A is prime in P^{n × n}_n.” We characterize the sets P₍₁₎ and P₍₂₎. Some of our results generalize some theorems in the paper of Daniel J. Richman and Hans Schneider [9].     

Stirling numbers and integer partitions

In this paper, we prove that the Stirling numbers of both kinds can be written as sums over integer partitions. As corollaries, we rewrite some identities with Stirling numbers of both kinds without Stirling numbers.     

Successions in integer partitions

A partition of an integer n is a representation n=a ₁+a ₂+⋅⋅⋅+a _k , with integer parts 1≤a ₁≤a ₂≤…≤a _k . For any fixed positive integer p, a p-succession in a partition is defined to be a pair of adjacent parts such that a _i+1−a _i =p. We find generating functions for the number of partitions of n with no p-successions, as well as for the total number of such successions taken over all partitions of n. In the process, various interesting partition identities are derived. In addition, the Hardy-Ramanujan asymptotic formula for the number of partitions is used to obtain an asymptotic estimate for the average number of p-successions in the partitions of n. This material is based upon work supported by the National Research Foundation under grant number 2053740.     

A bijection of the set of 3-regular partitions

A bijection of the set of 3-regular partitions of an integer n is constructed. It is shown that this map has order 2 and that the 3-cores of a partition and its image have diagrams which are mutual transposes. It is conjectured that this is the same bijection as the one induced, using the labeling of Farahat, Müller, and Peel, from the action of the alternating character upon the 3-modular irreducible representations of the symmetric group of degree n.     

On the weighted enumeration of alternating sign matrices and descending plane partitions

We prove a conjecture of Mills, Robbins and Rumsey [Alternating sign matrices and descending plane partitions, J. Combin. Theory Ser. A 34 (3) (1983) 340-359] that, for any n, k, m and p, the number of n×n alternating sign matrices (ASMs) for which the 1 of the first row is in column k+1 and there are exactly m −1?s and m+p inversions is equal to the number of descending plane partitions (DPPs) for which each part is at most n and there are exactly k parts equal to n, m special parts and p nonspecial parts. The proof involves expressing the associated generating functions for ASMs and DPPs with fixed n as determinants of n×n matrices, and using elementary transformations to show that these determinants are equal. The determinants themselves are obtained by standard methods: for ASMs this involves using the Izergin-Korepin formula for the partition function of the six-vertex model with domain-wall boundary conditions, together with a bijection between ASMs and configurations of this model, and for DPPs it involves using the Lindström-Gessel-Viennot theorem, together with a bijection between DPPs and certain sets of nonintersecting lattice paths.     

Dominance method for plane partitions III-flagged skew plane partitions

This paper investigates the enumerative problems of flagged skew plane partitions in which each row (column) has an upper and a lower bounds on the entries. By means of dominance technique, a direct and elementary derivation for their generating functions is presented which may be more accessible to readers.     

Mutually describing multisets and integer partitions

To each finite multiset $A$, with underlying set $S\left(A\right)$, we associate a new multiset $d\left(A\right)$, obtained by adjoining to $S\left(A\right)$ the multiplicities of its elements in $A$. We study the orbits of the map $d$ under iteration, and show that if $A$ consists of nonnegative integers, then its orbit under $d$ converges to a cycle. Moreover, we prove that all cycles of $d$ over $\mathbb{Z}$ are of length at most $3$, and we completely determine them. This amounts to finding all systems of mutually describing multisets. In the process, we are led to introduce and study a related discrete dynamical system on the set of integer partitions of $n$ for each $n\ge 1$.     

Distinct r-tuples in integer partitions

The Ramanujan Journal - Let $$p>3$$ be a prime and let a be a positive integer. We show that if or $$a>1$$ , then with $$(-)$$ the Jacobi symbol, which confirms a conjecture of Z.-W....     

The lattice of integer partitions and its infinite extension

In this paper, we use a simple discrete dynamical model to study integer partitions and their lattice. The set of reachable configurations of the model, with the order induced by the transition rule defined on it, is the lattice of all partitions of a positive integer, equipped with a dominance ordering. We first explain how this lattice can be constructed by an algorithm in linear time with respect to its size by showing that it has a self-similar structure. Then, we define a natural extension of the model to infinity, which we compare with the Young lattice. Using a self-similar tree, we obtain an encoding of the obtained lattice which makes it possible to enumerate easily and efficiently all the partitions of a given integer. This approach also gives a recursive formula for the number of partitions of an integer, and some informations on special sets of partitions, such as length bounded partitions.