Viennot's geometric construction

Last updated April 14, 2019

In mathematics, Viennot's geometric construction (named after Xavier Gérard Viennot) gives a diagrammatic interpretation of the Robinson–Schensted correspondence in terms of shadow lines. It has a generalization to the Robinson–Schensted–Knuth correspondence, which is known as the matrix-ball construction.

In mathematics, the Robinson–Schensted correspondence is a bijective correspondence between permutations and pairs of standard Young tableaux of the same shape. It has various descriptions, all of which are of algorithmic nature, it has many remarkable properties, and it has applications in combinatorics and other areas such as representation theory. The correspondence has been generalized in numerous ways, notably by Knuth to what is known as the Robinson–Schensted–Knuth correspondence, and a further generalization to pictures by Zelevinsky.

In mathematics, the Robinson–Schensted–Knuth correspondence, also referred to as the RSK correspondence or RSK algorithm, is a combinatorial bijection between matrices $A$ with non-negative integer entries and pairs $(P, Q)$ of semistandard Young tableaux of equal shape, whose size equals the sum of the entries of $A$ . More precisely the weight of $P$ is given by the column sums of $A$ , and the weight of $Q$ by its row sums. It is a generalization of the Robinson–Schensted correspondence, in the sense that taking $A$ to be a permutation matrix, the pair $(P, Q)$ will be the pair of standard tableaux associated to the permutation under the Robinson–Schensted correspondence.

The construction

Starting with a permutation $\sigma \in S_{n}$ , written in two-line notation, say:

\sigma ={\begin{pmatrix}1&2&\cdots &n\\\sigma _{1}&\sigma _{2}&\cdots &\sigma _{n}\end{pmatrix}},

one can apply the Robinson–Schensted correspondence to this permutation, yielding two standard Young tableaux of the same shape, P and Q. P is obtained by performing a sequence of insertions, and Q is the recording tableau, indicating in which order the boxes were filled.

In mathematics, a Young tableau is a combinatorial object useful in representation theory and Schubert calculus. It provides a convenient way to describe the group representations of the symmetric and general linear groups and to study their properties. Young tableaux were introduced by Alfred Young, a mathematician at Cambridge University, in 1900. They were then applied to the study of the symmetric group by Georg Frobenius in 1903. Their theory was further developed by many mathematicians, including Percy MacMahon, W. V. D. Hodge, G. de B. Robinson, Gian-Carlo Rota, Alain Lascoux, Marcel-Paul Schützenberger and Richard P. Stanley.

Viennot's construction starts by plotting the points $(i,\sigma _{i})$ in the plane, and imagining there is a light that shines from the origin, casting shadows straight up and to the right. This allows consideration of the points which are not shadowed by any other point; the boundary of their shadows then forms the first shadow line. Removing these points and repeating the procedure, one obtains all the shadow lines for this permutation. Viennot's insight is then that these shadow lines read off the first rows of P and Q (in fact, even more than that; these shadow lines form a "timeline", indicating which elements formed the first rows of P and Q after the successive insertions). One can then repeat the construction, using as new points the previous unlabelled corners, which allows to read off the other rows of P and Q.

Animation

For example consider the permutation

\sigma ={\begin{pmatrix}1&2&3&4&5&6&7&8\\3&8&1&2&4&7&5&6\end{pmatrix}}.

Then Viennot's construction goes as follows:

Applications

One can use Viennot's geometric construction to prove that if $\sigma$ corresponds to the pair of tableaux P,Q under the Robinson–Schensted correspondence, then $\sigma ^{-1}$ corresponds to the switched pair Q,P. Indeed, taking $\sigma$ to $\sigma ^{-1}$ reflects Viennot's construction in the $y=x$ -axis, and this precisely switches the roles of P and Q.

Related Research Articles

In linear algebra, the determinant is a scalar value that can be computed from the elements of a square matrix and encodes certain properties of the linear transformation described by the matrix. The determinant of a matrix $A$ is denoted $det(A)$ , $det A$ , or $| A |$ . Geometrically, it can be viewed as the volume scaling factor of the linear transformation described by the matrix. This is also the signed volume of the n-dimensional parallelepiped spanned by the column or row vectors of the matrix. The determinant is positive or negative according to whether the linear mapping preserves or reverses the orientation of n-space.

In mathematics, a permutation group is a group G whose elements are permutations of a given set M and whose group operation is the composition of permutations in G. The group of all permutations of a set M is the symmetric group of M, often written as Sym(M). The term permutation group thus means a subgroup of the symmetric group. If M = {1,2,...,n} then, Sym(M), the symmetric group on n letters is usually denoted by S_n.

Pauli matrices Matrices important in quantum mechanics and the study of spin

In mathematical physics and mathematics, the Pauli matrices are a set of three $2 \times 2$ complex matrices which are Hermitian and unitary. Usually indicated by the Greek letter sigma, they are occasionally denoted by tau when used in connection with isospin symmetries. They are

In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group S_n defined over a finite set of n symbols consists of the permutation operations that can be performed on the n symbols. Since there are n! possible permutation operations that can be performed on a tuple composed of n symbols, it follows that the number of elements of the symmetric group S_n is n!.

Simplex generalization of the notion of a triangle or tetrahedron to arbitrary dimensions

In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. Specifically, a k-simplex is a k-dimensional polytope which is the convex hull of its k + 1 vertices. More formally, suppose the k + 1 points $are affinely independent, which means are linearly independent. Then, the simplex determined by them is the set of points$

In mathematics, permutation is the act of arranging the members of a set into a sequence or order, or, if the set is already ordered, rearranging (reordering) its elements—a process called permuting. Permutations differ from combinations, which are selections of some members of a set regardless of order. For example, written as tuples, there are six permutations of the set {1,2,3}, namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). These are all the possible orderings of this three-element set. Anagrams of words whose letters are different are also permutations: the letters are already ordered in the original word, and the anagram is a reordering of the letters. The study of permutations of finite sets is an important topic in the fields of combinatorics and group theory.

In mathematics, when X is a finite set of at least two elements, the permutations of X fall into two classes of equal size: the even permutations and the odd permutations. If any total ordering of X is fixed, the parity of a permutation $of X can be defined as the parity of the number of inversions for σ, i.e., of pairs of elements x, y of X such that and .$

In linear algebra, the permanent of a square matrix is a function of the matrix similar to the determinant. The permanent, as well as the determinant, is a polynomial in the entries of the matrix. Both are special cases of a more general function of a matrix called the immanant.

In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say $P$ , represents a permutation of $m$ elements and, when used to multiply another matrix, say $A$ , results in permuting the rows or columns of the matrix $A$ .

In mathematics, and in particular in group theory, a cyclic permutation is a permutation of the elements of some set X which maps the elements of some subset S of X to each other in a cyclic fashion, while fixing all other elements of X. If S has k elements, the cycle is called a k-cycle.

In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depend on the size of the matrix. The value of this polynomial, when applied to the coefficients of a skew-symmetric matrix, is called the Pfaffian of that matrix. The term Pfaffian was introduced by Cayley (1852) who indirectly named them after Johann Friedrich Pfaff. The Pfaffian is nonvanishing only for 2n × 2n skew-symmetric matrices, in which case it is a polynomial of degree n.

In geometry and linear algebra, a Cartesian tensor uses an orthonormal basis to represent a tensor in a Euclidean space in the form of components. Converting a tensor's components from one such basis to another is through an orthogonal transformation.

In linear algebra, the Laplace expansion, named after Pierre-Simon Laplace, also called cofactor expansion, is an expression for the determinant |B| of an n × n matrix B that is a weighted sum of the determinants of n sub-matrices of B, each of size (n−1) × (n−1). The Laplace expansion is of didactic interest for its simplicity and as one of several ways to view and compute the determinant. For large matrices, it quickly becomes inefficient when compared to methods using matrix decomposition.

In mathematics, a Specht module is one of the representations of symmetric groups studied by Wilhelm Specht (1935). They are indexed by partitions, and in characteristic 0 the Specht modules of partitions of n form a complete set of irreducible representations of the symmetric group on n points.

In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They are related to quantum computers in a similar fashion as finite automata are related to Turing machines. Several types of automata may be defined, including measure-once and measure-many automata. Quantum finite automata can also be understood as the quantization of subshifts of finite type, or as a quantization of Markov chains. QFAs are, in turn, special cases of geometric finite automata or topological finite automata.

In mathematics, Plancherel measure is a measure defined on the set of irreducible unitary representations of a locally compact group $, that describes how the regular representation breaks up into irreducible unitary representations. In some cases the term Plancherel measure is applied specifically in the context of the group being the finite symmetric group - see below. It is named after the Swiss mathematician Michel Plancherel for his work in representation theory.$

In mathematics, the Lindström–Gessel–Viennot lemma provides a way to count the number of tuples of non-intersecting lattice paths.

In combinatorial mathematics, the hook-length formula is a formula for the number of standard Young tableaux whose shape is a given Young diagram. It has applications in diverse areas such as representation theory, probability, and algorithm analysis; for example, the problem of longest increasing subsequences.

References

Bruce E. Sagan. The Symmetric Group. Springer, 2001.

Bruce E. Sagan is a Professor of Mathematics at Michigan State University. He specializes in enumerative, algebraic, and topological combinatorics. He is also known as a musician, playing music from Scandinavia and the Balkans.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.