Logarithmic decrement

2013-08-27T15:29:30Z

173.228.4.4: Wrong units; in previous revision, "delta" was not dimensionless, it had the units (1/time). But the formula for "zeta" requires "delta" to be dimensionless

[[File:Dominance order partitions of 6.png|thumb|right|150px| Example of dominance ordering of [[partition (number theory)|partitions]] of n. Here, ''n'' = 6, [[Graph (mathematics)|nodes]] are partitions of 6, [[Graph (mathematics)|edges]] indicate that the upper node dominates the lower node. While this particular partial ordering is [[graded poset|graded]], this is not true for the dominance ordering on partitions of any number ''n'' > 6.]]

In [[discrete mathematics]], '''dominance order''' (synonyms: '''dominance ordering''', '''majorization order''', '''natural ordering''') is a [[partial order]] on the set of [[partition (number theory)|partitions]] of a positive integer ''n'' that plays an important role in [[algebraic combinatorics]] and [[representation theory]], especially in the context of [[symmetric function]]s and [[representation theory of the symmetric group]].

== Definition ==

If ''p''1,''p''2,… and ''q''1,''q''2,… are partitions of ''n'', with the parts arranged in the weakly decreasing order, then ''p'' precedes ''q'' in the dominance order if for any ''k'' ≥ 1, the sum of the ''k'' largest parts of ''p'' is less than or equal to the sum of the ''k'' largest parts of ''q'':

: <math> p\trianglelefteq q \text{ if and only if } p_1+\cdots+p_k \leq q_1+\cdots+q_k \text{ for all } k\geq 1.</math>

In this definition, partitions are extended by appending zero parts at the end as necessary.

== Properties of the dominance ordering ==

* Among the partitions of ''n'', (1,…,1) is the smallest and (n) is the largest.
* The dominance ordering implies [[lexicographical ordering]], i.e. if ''p'' dominates ''q'' and ''p'' ≠ ''q'', then for the smallest ''i'' such that ''p''''i'' ≠ ''q''''i'' one has ''p''''i'' > ''q''''i''.
* The poset of partitions of ''n'' is [[linearly ordered]] (and is equivalent to lexicographical ordering) if and only if ''n'' ≤ 5. It is [[graded poset|graded]] if and only if ''n'' ≤ 6. See image at right for an example.
* A partition ''p'' [[Covering relation|cover]]s a partition ''q'' if and only if ''p''''i'' = ''q''''i'' + 1, ''p''''k'' = ''q''''k'' − 1, ''p''''j'' = ''q''''j'' for all ''j'' ≠ ''i'',''k'' and either (1) ''k'' = ''i'' + 1 or (2) ''q''''i'' = ''q''''k'' (Brylawski, Prop. 2.3). Starting from the [[Young diagram]] of ''q'', the Young diagram of ''p'' is obtained from it by first removing the last box of row ''k'' and then appending it either to the end of the immediately preceding row ''k'' − 1, or to the end of row ''i'' < ''k'' if the rows ''i'' through ''k'' of the Young diagram of ''q'' all have the same length.
* Every partition ''p'' has a [[Partition (number theory)#Ferrers diagram|conjugate]] (or dual) partition ''p''′, whose Young diagram is the transpose of the Young diagram of ''p''. This operation reverses the dominance ordering:
:: <math>p\trianglelefteq q </math> if and only if <math>q^{\prime}\trianglelefteq p^{\prime}.</math>
* The dominance ordering determines the inclusions between the [[Zariski closure]]s of the conjugacy classes of [[nilpotent orbit#Poset structure|nilpotent matrices]].

== Lattice structure ==

Partitions of ''n'' form a [[lattice (order)|lattice]] under the dominance ordering, denoted ''L''''n'', and the operation of conjugation is an [[Antihomomorphism|antiautomorphism]] of this lattice. To explicitly describe the lattice operations, for each partition ''p'' consider the '''associated (''n'' + 1)-tuple''':

: <math> \hat{p}=(0, p_1, p_1+p_2, \ldots, p_1+p_2+\cdots+p_n). </math>

The partition ''p'' can be recovered from its associated (''n''+1)-tuple by applying the step 1 [[finite difference|difference]], <math>p_i=\hat{p}_i-\hat{p}_{i-1}.</math> Moreover, the (''n''+1)-tuples associated to partitions of ''n'' are characterized among all integer sequences of length ''n'' + 1 by the following three properties:

* Nondecreasing, <math>\hat{p}_i\leq \hat{p}_{i+1};</math>
* Concave, <math>2\hat{p}_i\geq \hat{p}_{i-1}+\hat{p}_{i+1};</math>
* The initial term is 0 and the final term is ''n'', <math>\hat{p}_0=0, \hat{p}_n=n.</math>

By the definition of the dominance ordering, partition ''p'' precedes partition ''q'' if and only if the associated (''n'' + 1)-tuple of ''p'' is term-by-term less than or equal to the associated (''n'' + 1)-tuple of ''q''. If ''p'', ''q'', ''r'' are partitions then <math>r\trianglelefteq p, r\trianglelefteq q</math> if and only if <math>\hat{r}\leq\hat{p}, \hat{r}\leq\hat{q}.</math> The componentwise minimum of two nondecreasing concave integer sequences is also nondecreasing and concave. Therefore, for any two partitions of ''n'', ''p'' and ''q'', their [[meet (mathematics)|meet]] is the partition of ''n'' whose associated (''n'' + 1)-tuple has components <math>\operatorname{min}(\hat{p}_i,\hat{q}_i).</math> The natural idea to use a similar formula for the [[join (mathematics)|join]] ''fails'', because the componentwise maximum of two concave sequences need not be concave. For example, for ''n'' = 6, the partitions [3,1,1,1] and [2,2,2] have associated sequences (0,3,4,5,6,6,6) and (0,2,4,6,6,6,6), whose componentwise maximum (0,3,4,6,6,6,6) does not correspond to any partition. To show that any two partitions of ''n'' have a join, one uses the conjugation antiautomorphism: the join of ''p'' and ''q'' is the conjugate partition of the meet of ''p''′ and ''q''′:

: <math> p\lor q=(p^{\prime} \land q^{\prime})^{\prime}. </math>

For the two partitions ''p'' and ''q'' in the preceding example, their conjugate partitions are [4,1,1] and [3,3] with meet [3,2,1], which is self-conjugate; therefore, the join of ''p'' and ''q'' is [3,2,1].

Thomas Brylawski has determined many invariants of the lattice ''L''''n'', such as the minimal height and the maximal covering number, and classified the [[Partially ordered set#Interval|interval]]s of small length. While ''L''''n'' is not [[distributive lattice|distributive]] for ''n'' ≥ 7, it shares some properties with distributive lattices: for example, its [[Möbius function (combinatorics)|Möbius function]] takes on only values 0, 1, −1.

== Generalizations ==

[[File:Tableaux dominance.svg|thumb|right|200px| The dominance order on Young tableaux for the partition 6 = 4 + 2]]
Partitions of ''n'' can be graphically represented by [[Young diagram]]s on ''n'' boxes.
Standard [[Young tableaux]] are certain ways to fill Young diagrams with numbers, and a partial order on them (sometimes called the ''dominance order on Young tableaux'') can be defined in terms of the dominance order on the Young diagrams. For a Young tableau ''T'' to dominate another Young tableau ''S'', the shape of ''T'' must dominate that of ''S'' as a partition, and moreover the same must hold whenever ''T'' and ''S'' are first truncated to their sub-tableaux containing entries up to a given value ''k'', for each choice of ''k''.

Similarly, there is a dominance order on the set of standard Young bitableaux, which plays a role in the theory of ''standard monomials''.

== See also ==

* [[Young's lattice]]
* [[Majorization]]

== References ==

* [[Ian G. Macdonald]], ''Symmetric functions and Hall polynomials'', [[Oxford University Press]], 1979, ISBN 0-19-853530-9 (See section I.1, pp. 5–7)
* [[Richard P. Stanley]], [http://www-math.mit.edu/~rstan/ec/ ''Enumerative Combinatorics'', Volume 2]. Cambridge University Press, 1999 ISBN 0-521-56069-1
* Thomas Brylawski, [http://dx.doi.org/10.1016/0012-365X(73)90094-0 ''The lattice of integer partitions''], Discrete Mathematics, vol. 6, no. 3, 1973, pp. 201–219

[[Category:Enumerative combinatorics]]
[[Category:Algebraic combinatorics]]
[[Category:Lattice theory]]
[[Category:Representation theory]]

formulasearchengine - User contributions [en]

Logarithmic decrement