Représentation induite d'un groupe fini

En mathématiques une représentation induite est une représentation d'un groupe canoniquement associée à une représentation de l'un de ses sous-groupes. L'induction est adjointe à gauche de la . Cette propriété intervient dans la formule de réciprocité de Frobenius. Cet article traite le cas des groupes finis. Définitions et exemples Dans tout l'article, G désigne un groupe fini, H un sous-groupe de G et θ une représentation de H dans un espace vectoriel de dimension finie W sur un corps K. G/H désigne l'ensemble des classes à gauche modulo H. Définitions

La représentation induite par une représentation θ du sous-groupe H de G est la représentation de G, notée ρ = Ind θ, ou simplement Ind(θ) s'il n'y a pas de risque d'ambiguïté, telle que : ** θ est une sous-représentation de la restriction Res(ρ) de ρ à H ; ** pour toute représentation σ de G, le morphisme naturel suivant est un isomorphisme entre espaces des morphismes de représentations :\hom_G(\math

On canonical representation of convex polyhedra

Stefano Picozzi

Convex polyhedra are important objects in various areas of mathematics and other disciplines. A fundamental result, known as Minkowski-Weyl theorem, states that every polyhedron admits two types of representations, either as the solution set to a finite system of linear inequalities or the Minkowski sum of a finite set of points and half-rays. These are usually referred to as its H-representations and its V-representations, respectively. Neither H-representations nor V-representations are unique. Hence, deciding whether two H-representations, or two V-representations describe the same polyhedron is a nontrivial problem. We identify particular representations which are easy to determine, are compact, and reflect the geometrical properties of the underlying polyhedron. Key ingredients to this discussion are affine transformations of polyhedra, duality and complexity of polyhedral decision problems. In this dissertation, we discuss in detail the problem of refining the definitions of Hand V- representations such as to guarantee a one to one correspondence between polyhedra and their representations. As a convenient formalism, we introduce the notion of the canonical representation rule, which is any function assigning to each polyhedron P a particular H-representation, and a particular V-representation. The orthogonal representation rule is a well-known example of such a function. We define the lexico-smallest representation rule, an improved canonical representation rule that produce representations which are nonredundant, make the underlying geometry transparent and, furthermore, are sparse. These rules also exhibit nice polarity properties that can be exploited for computation. The key computational tool is linear programing. Furthermore, we show that the lexico-smallest H-representation of a perfect bipartite matching polyhedron is easy to determine using the combinatorial properties of the underlying graph. Finally, we discuss the complexity of various polyhedral verification problems related to representation of convex polyhedra. The standard technique to identify the redundancies within an H- or a V-representation is to use linear programming. We discuss the complexity of the converse reduction. More precisely, we show that deciding the feasibility of a system of linear inequalities can be reduced to deciding redundancy in an H- or in a V- representation in linear time. Also, we will study the equivalence of these problems with those of identifying the implicit linearities within an H- or a V- representation, and the boundedness of a polyhedron.

EPFL2005

The lexico-smallest representation of convex polyhedra

Stefano Picozzi

Every convex polyhedron in the Euclidean space

R^d

admits both H- and V-representation. For both formats, a representation is canonical if it is minimal and unique up to some elementary operations. In this paper, we extend the usual definition of canonical representation to a family of such representations that can be computed in polynomial time. In particular, this allows to define the lexico-smallest representation which computation is easy in practice. Furthermore, it guarantees certain sparsity property reflecting the real dimension of the studied object. As a consequence, H-representations of non-full dimensional polyhedra and V-representations of polyhedra without extreme points can be compared more efficiently.

2003

On canonical representation of convex polyhedra

Stefano Picozzi

EPFL2005

The lexico-smallest representation of convex polyhedra

Stefano Picozzi

Every convex polyhedron in the Euclidean space

R^d

2003