Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Matrice unimodulaire
Résumé
In mathematics, a unimodular matrix M is a square integer matrix having determinant +1 or −1. Equivalently, it is an integer matrix that is invertible over the integers: there is an integer matrix N that is its inverse (these are equivalent under Cramer's rule). Thus every equation Mx = b, where M and b both have integer components and M is unimodular, has an integer solution. The n × n unimodular matrices form a group called the n × n general linear group over , which is denoted .
Unimodular matrices form a subgroup of the general linear group under matrix multiplication, i.e. the following matrices are unimodular:
Identity matrix
The inverse of a unimodular matrix
The product of two unimodular matrices
Other examples include:
Pascal matrices
Permutation matrices
the three transformation matrices in the ternary tree of primitive Pythagorean triples
Certain transformation matrices for rotation, shearing (both with determinant 1) and reflection (determinant −1).
The unimodular matrix used (possibly implicitly) in lattice reduction and in the Hermite normal form of matrices.
The Kronecker product of two unimodular matrices is also unimodular. This follows since where p and q are the dimensions of A and B, respectively.
A totally unimodular matrix
(TU matrix) is a matrix for which every square non-singular submatrix is unimodular. Equivalently, every square submatrix has determinant 0, +1 or −1. A totally unimodular matrix need not be square itself. From the definition it follows that any submatrix of a totally unimodular matrix is itself totally unimodular (TU). Furthermore it follows that any TU matrix has only 0, +1 or −1 entries. The converse is not true, i.e., a matrix with only 0, +1 or −1 entries is not necessarily unimodular. A matrix is TU if and only if its transpose is TU.
Totally unimodular matrices are extremely important in polyhedral combinatorics and combinatorial optimization since they give a quick way to verify that a linear program is integral (has an integral optimum, when any optimum exists).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.